New Year Puzzle and fun programming challenge
The 2019 New Year Puzzle
The objective is to obtain as many integers as possible from 0 to 100 by using each of the digits of 2019 exactly once, by the following operations: decimal concatenation (e.g., join 2 and 0 to make 20), addition, subtraction, multiplication, division, and power (exponentiation), with any order of operations (in other words, parentheses or grouping). Concatenation is only allowed for the original digits, not the results of other operations. Leading zeroes are not allowed (e.g., 02 is not accepted to represent the value of 2). A leading negative sign is allowed (e.g., 19+20), but I am not sure it is ever necessary. Examples: Code:
0: 0*219 Generate list of permutations of digits: Code:
import itertools Code:
# to choose 3 operations with no leading negative sign A leading negative sign, if required, may be prepended to the sequences generated by the above function. Order of operations (parentheses, grouping): If we have 4 digits joined by 3 operations, with no leading negative sign, I think I have worked out on paper that we need only consider 5 grouping configurations. I have not reduced that to code yet. After those preliminaries, the program needs to eliminate illegal sequences (concatenation of leading zeroes, concatenation of results of other operations), evaluate each expression, and tabulate the results. I'll post my code when I get that far, probably tomorrow, but in the mean time I will follow the discussion and answer questions (if any). 
Looks like an interesting diversion, thanks!
Quote:
Since the result is to be integers, does that imply that the operations produce only integer results as well? For example, can we say 9/2, implicitly truncating the remainder? Looks like a job for bash math! 
The other amplification would be whether or not it is mandatory to use every digit, with every computation.
And: Quote:

Good questions/clarifications.
Regarding integer math: The way this challenge is usually done, all arithmetic is exact (think "float") and the result must be an exact whole number (that is, its fractional part must be equal to zero). So, for example, this would be a valid solution: Code:
3: 0+9**(1/2) Code:
0+pow(9,1/(float)2) Since you mention next year, in 2020 the solutions are going to be a bit scarce because two '2's and two '0's is not a lot of material to work with! For example, there is no sequence of operations that makes 5 (or many other numbers in the range 0 to 100). And also I have another correction/clarification: One may concatenate the result of a concatenation, but not the result of any other operation. Examples: Code:
# In this pseudocode, 'c' is the concatenate operator. 
That restricts the solutions quite a bit and eliminates a bashonly script from the competition, thanks. ;)

I have been out all day, and expected to find a few entries when I checked in  but none yet!
While doing other things (like driving, in snow!) I managed to put together a simple C framework in my head which iterates the digits and enforces the rules of the game for me, so that I can focus more on the expressions. I translated most of that into code this evening and the current version produces the following at this time: Code:
0 1 2 3 4 5 6 7 8 9 I'll reserve the code until others have submitted their (probably better) approaches. ;) UPDATE: Added yet another new expression bringing total to 48 
You are fast! Thanks for reserving your code until I get further along. I am still working on the bit that orders the operations equivalent to moving parentheses around. I think I'm not far off.

Quote:
One thing I realized early which saved a lot of time is that there are only 24 permutations of the original digits, and many expressions will produce results which overlap the results of others. So instead of trying to write fully generic expressions, I wrote a few obvious ones such as simple sums and products and included an output format which showed the distribution of the results. Then I could begin with a number or range which was not found by those and try to work backwards to an expression which would fill the gap  which also usually filled others. I have now changed the "found" flag handling to record a single character identifier set by the (last) expression which produced each result, so now I can more quickly tell when an expression works as expected, and also identify any which have NULL effect because later expressions overlap the same complete result set  great simplifier! My current result set, with expression identifiers is: Code:
0 1 2 3 4 5 6 7 8 9 
Still here. I've just been busy with other things. My approach is more of an exhaustive brute force search, beginning with this:
Code:
# This will be in python3 I started to write some code to evaluate the expressions along these lines (very incomplete, mostly comments): Code:
def evaluate(left_operand, operation, right_operand): Code:
# if order of operations is [0, 1, 2] The recursive function I envision receives as its arguments the lists of digits, operations, and order of operations. It performs the next operation in the order specified. Then it shortens the lists of digits, operations, and order, and then feeds that into the next recursive call. It recurses until the last operation is performed, and the final answer is returned up the entire chain. That's what I'm working on now. I'll have more tomorrow, and maybe even a working program. 
I like recursion! Your approach should fill in all the fillable holes in my squareish matrix!
I'll look forward to it (although my python skills are more at the garden snake level). ;) 
I do not know how many of those holes can be filled, but I hope we find out.
Some years are pretty lean. This puzzle in 2000 only had 4 answers: 0, 1, 2, and 20. 
Quote:
The best I can say is that the rough mirroring between the lowest solutions and the highest results from the superposition of the limited long range operations, 9^2 and 10^2, and the largest offset that can be produced by the remaining sums or products in each case (10 and 9 respectively). The empty row is not accessible from either end as far as I can tell, without being able to concat onto another operation... but I am still looking for something to fit there. If your brute force fails to find one then I will be inclined to accept that as "proof" of the nonexistence of any solution. But I am hopeful that someone will happen along with a suggestion that will open another attack on the problem. The . K T K . solutions in the 40 row result from the only possible concatenations of 9 divisible by 2, +/ 1. The R on the high side of the void results from the only other useful power expression, (91)^2 +0. All the surrounding territory in the diamond shaped void appears unreachable to me so far. The remainder of the 21st century has two constraints that will not change  one term is always zero and another is always 2! So the richness of all solutions for the next 82 years will derive from the remaining two digits! But you can get quite a lot out of that! I have enjoyed exploring it, thanks! 
1 Attachment(s)
I have the recursive program up and running. It runs pretty fast, completing the exhaustive search in just under one second. In this first working version of mine, the output is very simple, just a list of numbers and how many times each was found.
It came up with the same numbers that you tabulated, with only one new find, 72, which by now you may have found. I later figured out how that is obtained: (102)*9=72. I am going to work on formatted output, maybe to display some of the expressions. I'll probably post at least one more version in the next few days. By the way, one of the advantages of the recursive approach is that it can be used for any number of digits. That is not an immediate concern for this New Year Puzzle (Y10K is an awful long way off), but it's something to keep in mind for other problems that lend themselves to recursion. Many thanks, astrogeek, for your programming ideas and encouragement. I look forward to seeing your C program. My program, today's version: Attachment 29391 Program output: Code:
0 3611 
Quote:
I expected you to find more that I had missed, so missing only that one (even though it should have been obvious!) is gratifying! Quote:
Quote:
Rather than fill another page here, and to have it more accessible for future reference, I have posted my code and comments to my LQ blog, New Year Puzzle. I will not have a chance to proof read it today but will correct any errors it may contain tomorrow. Thanks for the exercise, very enjoyable! 
I have finally had a chance to give your code more than a superficial reading, sorry it has taken so long.
As I mentioned, my proficiency with python is not good, but I think I have managed to digest it all at this time  very nice! But it appears to me that your concat operation does not avoid use of leading zeroes. Is that correct, or is left_data[0] guaranteed to be nonzero by previous operations in a way I have not seen? I have updated the expression code in my blog entry this evening, removing five expressions, and correcting an incorrect, hasty conclusion. I have tended to think of the problem in terms of minimizing the generating expressions (and using the current year digits), whereas your approach has been to exhaust every possible expression for any set of digits. The two are somewhat complementary in that I can now use your code which produces all possible solutions, to validate my minimal expression sets  thanks for that! Earleir today I was thinking about how to minimize the number and "types" of expressions required for any given number/set of digits and realized that thinking in terms of the potential number of zeroes among the digits produces a hierarchy of expressions which (I think) should lead to a minimal set of expressions for a given number of digits, eliminating the need to process many combinations of operations. It is a satisfying thought, but I have not worked it all the way through yet  I'll post back here when/if I do that. 
All times are GMT 5. The time now is 02:32 AM. 