[SOLVED] New Year Puzzle and fun programming challenge

Beryllos · 01-02-2019, 01:03 PM

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
1: 20-19
...
22: 21+9**0 (or 21+9^0)
...

This problem is customarily solved by hand, but this year I would like to solve it by a program. I will program it in python and post my progress as I go. So far, all I have is these notes:

Generate list of permutations of digits:

Code:

import itertools
itertools.permutations([2,0,1,9],4)

Generate list of left-to-right sequences of operations (not specifying the order of execution of the operations):

Code:

# to choose 3 operations with no leading negative sign
itertools.product(['add',
                   'subtract',
                   'multiply',
                   'divide',
                   'power',
                   'concatenate'
                   ],repeat=3)

This could alternatively be done by nested 'for' loops.
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).

astrogeek · 01-02-2019, 02:25 PM

Looks like an interesting diversion, thanks!

Quote:

Originally Posted by Beryllos

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.

The rules seem clear enough, but I am sure there is room for a little interpretive wiggle room.

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!

rtmistler · 01-02-2019, 02:52 PM

The other amplification would be whether or not it is mandatory to use every digit, with every computation.

And:

Quote:

Originally Posted by Beryllos

This problem is customarily solved by hand, but this year I would like to solve it by a program.

You post this next year, we're going to call you on it!

Beryllos · 01-02-2019, 04:03 PM

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)

which works out to exactly 3.0 in python. In C it works if I make any part of pow's second argument float, e.g.,

Code:

0+pow(9,1/(float)2)

Clarification: Each digit of the year (2, 0, 1, 9) must be used exactly once in the full expression.

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.
((1c0)c2)-9   # evaluates to 93 (102-9), valid according to the rules
((9+1)/2)c0   # invalid attempt to set up 5c0 which would evaluate to 50

astrogeek · 01-02-2019, 04:09 PM

That restricts the solutions quite a bit and eliminates a bash-only script from the competition, thanks.

astrogeek · 01-03-2019, 12:25 AM

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
  0: * * * * * * * * * *
 10: * * * * * . * * * *
 20: * * * . . . . * * *
 30: * . . . . . . . * *
 40: . . . . * * * . . .
 50: . . . . . . . . . .
 60: . . . . * . . . . *
 70: * * . . . . . . * .
 80: * * * . . . . * * *
 90: * * * * . * . . . .
100: *

Total integers found: 48

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 16 17 18 19 
20 21 22 27 28 29 30 38 39 44 45 46 64 69 70 71 78 
80 81 82 87 88 89 90 91 92 93 95 100

I print the square format to show quickly the distribution of found integers, the total so I can quickly tell whether a new expression produces any new results, and of course the integers found.

I'll reserve the code until others have submitted their (probably better) approaches.

UPDATE: Added yet another new expression bringing total to 48

Beryllos · 01-03-2019, 01:27 AM

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.

astrogeek · 01-03-2019, 05:22 PM

Quote:

Originally Posted by Beryllos

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.

Not really, but thanks for thought! I just thought about it all day before getting a chance to write the code, so I had a very good idea how I wanted to approach the problem before I started.

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
  0: T R V P N E A O O P
 10: P O N S K . D H B S
 20: S F S . . . . C H V
 30: G . . . . . . . V L
 40: . . . . K T K . . .
 50: . . . . . . . . . .
 60: . . . . R . . . . M
 70: I M . . . . . . M .
 80: O P M . . . . H K H
 90: I S J S . U . . . .
100: R

Total integers found: 48

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 16 17 18 19 
20 21 22 27 28 29 30 38 39 44 45 46 64 69 70 71 78 
80 81 82 87 88 89 90 91 92 93 95 100

So far I have not found an expression to hit that empty row in the middle which does not require concatenation of another operation... I am open to ideas!

Beryllos · 01-03-2019, 10:37 PM

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

import itertools

# initialize year
year=[2,0,1,9]

# initialize results array (format to be determined)
results=[[] for i in range(101)]

# for all permutations of the year's digits (24 of them)
for digits in itertools.permutations(year,4):

# for all possible sets of operations (216 of them)
    for operations in itertools.product(range(6),repeat=3):

# for all possible orders of operations (6 permutations, but 1 of those is redundant)
        for order in itertools.permutations(range(3),3):

# insert all the real functionality here... ;)

At this point, we have 24*216*6 = 31104 trials, which seems doable.

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):
# both left and right operands are lists [int status, float value]
# This function first checks operands for preexisting errors.
# If no errors, it selects and performs the single operation.
# Upon completion, status is set to one of the following:
#     (1-4) number of concatenated digits,
#     (0) other operation has taken place, or
#     (-1) error.

# insert all the important code here
    return [status, value]

This function would be used in rather complicated statements like this:

Code:

# if order of operations is [0, 1, 2]
    status, value = evaluate(evaluate(evaluate(digit[0], op[0], digit[1]),
                                                         op[1], digit[2]),
                                                         op[2], digit[3])

# if order of operations is [0, 2, 1] or [2, 0, 1]
    status, value = evaluate(evaluate(digit[0], op[0], digit[1]),
                             op[1],
                             evaluate(digit[2], op[2], digit[3]))

# and similar expressions for the other 3 cases...

I could get that to work, but it seems rather inelegant. The elegant approach would be a recursive function. This problem is practically begging for a recursive solution.

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.

astrogeek · 01-03-2019, 11:21 PM

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).

Beryllos · 01-03-2019, 11:38 PM

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.

astrogeek · 01-04-2019, 12:15 AM

Quote:

Originally Posted by Beryllos

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.

I think the multiple symmetries visible in my formatted output would probably indicate something about the possible solutions to someone smart enough to extract meaning from it, but I have not been able to say anything definitive about it.

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 non-existence 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, (9-1)^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!

Beryllos · 01-04-2019, 03:42 PM

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: (10-2)*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:
newyear.py.txt

Program output:

Code:

astrogeek · 01-04-2019, 07:58 PM

Quote:

Originally Posted by Beryllos

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: (10-2)*9=72.

Thanks for the code and the result!

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:

Originally Posted by Beryllos

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.

I'll look forward to it!

Quote:

Originally Posted by Beryllos

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.

yea, mine is only good for four digits, although it is easy to change them for another year. Also, my choices of expressions to evaluate are not comprehensive, as your certainly is! For other years (sets of digits) other sets of expressions would apply - but that is the fun aspect of the puzzle!

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!

astrogeek · 01-06-2019, 01:35 AM

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 non-zero 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.