[SOLVED] New Year Puzzle and fun programming challenge

Beryllos · 01-06-2019, 12:12 PM

Quote:

Originally Posted by astrogeek

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?

Yes, I forgot to check for leading zeroes, and realized it later when I added some print statements to look at a few of the results. Here is an update on that, with the new lines in bold:

Code:

# concatenation (with error check)
    elif operation == 5:
        if right_data[1] <= 0 or left_data[1] <= 0:
            return 0, -1
# left_data[1], right_data[1], and status are number of digits
# only for concatenated digits, and 0 for all other operations
        value = left_data[0]*10**right_data[1]+right_data[0]
        status = left_data[1]+right_data[1]
# check for leading zero
        if value < 10**(status-1):
            return 0, -1
        return value, status

Quote:

Originally Posted by astrogeek

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!

The exhaustive-search approach certainly has its problems. For example, it doesn't scale well. I tried it on 5-digit numbers, and it took roughly 100 times longer.

I don't have any great ideas (or insights) for reducing the number of expressions tried. I see room for small improvements. For example, if an expression works with +0 or *1, one doesn't have to try -0 or /1. Also I see that many power calculations go out of the 0-100 range; one could limit the range of numbers going into the power function.

Right now I am working on printing the arithmetic expressions in a human-friendly format, after reducing the number of results to be displayed. I hope to post that in the next day or two.

Beryllos · 01-06-2019, 10:49 PM

Oh, wait a second... The "correction" in my previous post was a bit hasty. It works, but it would make a lot more sense to check the input to the function rather than the output. Here is the better way:

Code:

# concatenation (with error check)
    elif operation == 5:
# return error code if either operand is a calculation result
# or if the left operand is zero (leading zero not allowed)
        if right_data[1] <= 0 or left_data[1] <= 0 or left_data[0] == 0:
            return 0, -1
# left_data[1], right_data[1], and status are number of digits
# only for concatenated digits, and 0 for all other operations
        value = left_data[0]*10**right_data[1]+right_data[0]
        status = left_data[1]+right_data[1]
        return value, status

Beryllos · 01-07-2019, 03:59 PM

Whew! I have just finished a version that constructs string expressions with arithmetic symbols and parentheses. At the moment, it outputs everything in the order it finds it, which is about 12,000 lines, a bit inconvenient. Next I'll work on printing only selected results.

Here is a sample of the output:

Code:

$ python3 newyear-v2.py | grep '28 =' | uniq
28 = 20-1+9
28 = 20-(1-9)
28 = 20+9-1
28 = 29+0-1
28 = 29-(0+1)
28 = 29-0-1
28 = 2*9+10
28 = 29-1+0
28 = 29-(1+0)
28 = 29-1-0
28 = 29-(1-0)
28 = 29-1^0
28 = 0+29-1
28 = 0-1+29
28 = 0-(1-29)
28 = 10+2*9
28 = 10+9*2
28 = 9+20-1
28 = 9*2+10
28 = 9-1+20
28 = 9-(1-20)
$

Here is the program:
newyear-v2.py.txt
The string manipulations are in the function that performs the basic calculations.

I changed the way the functions return data. In this program, all functions simply return 0 for success and -1 for failure, and all data is returned through one of the function arguments.

astrogeek · 01-07-2019, 05:40 PM

Very nice!

I have been thinking of printing expressions as they are evaluated, along with a few more stats such as how often an expression succeeds or fails, and how many different expressions evaluate to the same result. I thought that streaming out all the processing, well formatted, then piping it through a filter or two might be the best way to go - and yours reinforces that thought!

I haven't had time to work on my code the past couple of days, but it continues to occupy my thoughts when my brain cell is not otherwise occupied. The more I consider the "stratification" of expressions when viewed in terms of zero digits, the more I think that has great potential to minimize the required expressions and impose an order on their evaluation.

Thanks for continuing with your own approach and I hope that you are enjoying it as much as I have - an oddly pleasing diversion!

Beryllos · 01-07-2019, 07:27 PM

Quote:

Originally Posted by astrogeek

Very nice!
...
Thanks for continuing with your own approach and I hope that you are enjoying it as much as I have - an oddly pleasing diversion!

Yes, I am having fun with it. Getting the parentheses right was a good challenge for me. Order of operations and parentheses seem so obvious, but "teaching" a machine to do it wasn't very obvious. It required a bit of thought and some doodling on paper, and I wasn't sure my algorithm was correct until I ran it. Woo-hoo!

I have finished the core functionality that I intended to do, but I think I am good for at least one more round in order to refine the output. It might be nice to condense the list to one "good-looking" expression for each whole number that can be calculated. One possibility for narrowing it down is to take the digits in the same order as the year, like these examples:

Code:

 1 = 20-19
 2 = 20/(1+9)
 3 = 2+0+1^9
 7 = 2*(0-1)+9
 8 = 2*0-1+9
 9 = 2*0+1*9
10 = 20-1-9

That order is possible for some but not all whole numbers in the target range.

dogpatch · 01-07-2019, 08:58 PM

comment eliminated

l0f4r0 · 01-08-2019, 03:30 AM

@Beryllos/astrogeek: did you consider power with negative numbers?
E.g: 1 = 1^(-9)+2*0
I am not sure it will give you any new results but maybe it could be of interest for you if you want to print all possibilities...

Beryllos · 01-08-2019, 07:17 AM

I'm glad you brought that up. In my original post, I mentioned that a leading negative sign is allowed, but I didn't actually try it. With this year's digits, I think the only possible use of it is raising 1 to any power, as in your example. With other digits in other years, there are more possibilities.

I think I will work that into the next version of my program, probably restricting it to powers because that is where it can generate new values.

For example... Do you know the old song, In the Year 2525? It came to mind as I thought up these examples:

Code:

 1 = 25*5^(-2)
10 = 2/5^(-2)/5    (digits in 2525 order!)

Beryllos · 01-08-2019, 09:32 AM

Quote:

Originally Posted by Beryllos

I think I will work that into the next version of my program, probably restricting it to powers because that is where it can generate new values.

Thinking more about this, I am not sure that we really can generate new numbers by using negative powers. For example, multiplication by a negative power (a*b^(-c)) gives the same number as dividing by a positive power (a/b^c). I don't see that it opens a way to numbers that are otherwise inaccessible. So I will continue to omit leading minus signs until it can be shown that it is necessary.

igadoter · 01-08-2019, 04:55 PM

Just one have set containing 2,0,1,9 - now one generate sequences say: 2+0-9*1, such sequences has no meaning at all, some can be incorrect 2++0 - in fact it is exercise from lexical analysis - at first one has to define which sequences are allowed - like say what is identifier in C, then one defines semantic - one builds machine (computer) to evaluate such sequence to 'number', ie. element of 0-2019. Some different sequences have the same value. The only problem is to assure that space of allowed sequences is finite. Description of exercise has to be concise. Now one go through all sequences.

astrogeek · 01-08-2019, 08:11 PM

Quote:

Originally Posted by l0f4r0

@Beryllos/astrogeek: did you consider power with negative numbers?
E.g: 1 = 1^(-9)+2*0
I am not sure it will give you any new results but maybe it could be of interest for you if you want to print all possibilities...

As already noted by Beryllos, taking a negative power is equivalent to dividing by a positive power. Some of the necessary expressions such as a^(b-c) may produce either positive or negative powers, or zero power. But in general intentionally taking a negative power turns out to be not very useful in this exercise because it will always produce a fractional result which is only useful if inverted - but inversion can only be done if you have an extra digit handy to do it, and if you do then you can always rewrite it as a positive power anyway.

Thanks for the thought!

astrogeek · 01-08-2019, 08:54 PM

Quote:

Originally Posted by Beryllos

Yes, I am having fun with it. Getting the parentheses right was a good challenge for me. Order of operations and parentheses seem so obvious, but "teaching" a machine to do it wasn't very obvious. It required a bit of thought and some doodling on paper, and I wasn't sure my algorithm was correct until I ran it. Woo-hoo!

I have finished the core functionality that I intended to do, but I think I am good for at least one more round in order to refine the output. It might be nice to condense the list to one "good-looking" expression for each whole number that can be calculated. One possibility for narrowing it down is to take the digits in the same order as the year, like these examples:

Code:

 1 = 20-19
 2 = 20/(1+9)
 3 = 2+0+1^9
 7 = 2*(0-1)+9
 8 = 2*0-1+9
 9 = 2*0+1*9
10 = 20-1-9

That order is possible for some but not all whole numbers in the target range.

Glad to hear you are having fun!

I had a little time to play today and have added shell argument handling for the year, plus some simple options to select output format. I also changed my expression ID to an integer which allows to provide a more useful reference the generating expressions. Finally I have put in place a mechanism for showing the expressions, althought I am not sure those are all correct at this time.

I have structured my expressions into groups as follows (pasted comment code):

Code:

First group only two expressions, always evaluated

/* Sum all, prod all always
   No powers, may be 0^0
   No division, may be x/0
      a+b+c+d
      a*b*c*d
*/

Second group assumes only one non-zero digit

/* Operations which make sense with at least one zero and one non-zero digit,
   assume all others are zero
         a + (b*c*d) - Each digit itself if any zero
         a^(b*c*d) - 1 if any zero
         (a+b+c)^d - 1 if any zero, else possible power of sum
         (b+c+d)/a - 0 if any zeros, else possible quotient
         ab+(c*d) - Tens power of a, ab if any other non-zero, ab+product
         ab+c+d - Tens power of a plus any non-zero digits
         abc-d - 100+ if a==1, only diff of d makes sense
*/

Third group assumes two non-zero digits, two zero

/* Operations which make sense with at least one zero and two non-zero digits,
   assume all others are zero
         a-b+c+d - Diff of two non-zero digits plus any others
         a-b+(c*d) - Diff of all non-zero digits
         (a*b)+(c*d) - Product of non-zero pairs
         (a*b)+c+d - Product of non-zero pairs plus any non-zero digits
         (a+c)*(b+d) - Products of all non-zero pairs and sums of pairs
         (a-c)*(b+d) - Products of all non-zero pairs and difference of pairs

         (a^c)+b+d - 1 plus all other terms
         (a^(c*d))+b - 1 plus non-zero term
         (a^b)+(c*d) - Powers of pairs
         (a^b)+c+d - Powers of pairs plus any non-zero digits
         (a^b)-c+d - Powers of pairs minus any non-zero digits

         (ac+d)*b - Product of tens power of a plus others times b
         ac+b^d - Tens power of a plus 1 or power
         ac+(b*d) - Tens power of a plus product or zero
         ac+bd - Tens power of a plus tens power of b
         acd-b - Hundreds power of a minus b
         acd/b - Hundreds power of a divided by b

         (a+c+d)/b - Quotient of sums
         (a+(c*d))/b - Quotient of pairs if any zero
*/

Fourth group assumes three non-zero digits

/* Operations which make sense with one zero and three non-zero digits,
   assume other  is zero
           a-b-c+d - Diff of non-zero
           a+b+(c*d) - Product of pairs
           a*b+(c^d) - Product of non-zero plus 1
           a*b-(c^d) - Product of non-zero minus 1
           a*b*c+0

           (a+(b^d))^c - a plus 1 to the power c (possibly 0^0)
           (a-(b^d))^c - a minus 1 to power c (possibly 0^0)
           a^b+c^d - Sum of powers of pairs
           a^b-c^d - Difference of powers of pairs
           a^b-cd - Power of pairs minus tens power of other
           (a+b+d)^c - Sum to power
           (a-b+d)^c - Diff to power
           a^(b+c)+d - a to power of sum
           a^(b-c)+d - a to power of difference

           ab-c+d - Tens power of a plus b, minus c plus zero or more
           ab+(c^d) - Tens power of a plus b plus 1
           ab-(c^d) - Tens power of a plus b minus 1
           ab+cd - Sum of tens powers
           ab-cd - Difference of tens powers
           (ab*c)+d - Tens power of a plus b times c, plus zero or more
           (ab/c)+d - Tens power of a plus b, divided by c

           ad-(b/c) - Tens power of a minus quotient b/c
           (ad-c)/b - Tens power of a minus c divided by b
           (ad-b)*c - Tens power of a minus b times c
*/

Fifth group assumes all four non-zero digits 

/* Operations which make sense with four non-zero digits

         Expressions not yet listed in comments
*/

Note that the above expressions in my comments may not agree exactly with what is in my code, but that is the model I am working towards.

In total I have 54 distinct expressions at this time and it produces results in agreement with your latest version in my selected test cases (2019, 2020, 2029, 1234, 2468, 5789, and a few others).

I do not know it it is complete, but evaluating by expression groups with same or fewer number of zeros as above imposes a very useful structure on the expressions which does seem to lead to a minimal number of expressions, and avoids evaluating expressions which will not produce solutions.

My current output formats look like this...

Code:

./genx -n 2029 -m
       0   1   2   3   4   5   6   7   8   9
  0:  002 102 101 207 204 210 325 202 329 201
 10:  207 302 206 001 205   . 330 304 204 326
 20:  203 317 104 316   .   .   . 325 317 213
 30:  212 105   .   .   .   . 305   . 104   .
 40:    .   .   . 327 323   . 321 326   . 214
 50:    .   .   .   .   .   .   .   . 211   .
 60:    . 310   .   . 307   .   .   . 319   .
 70:    .   . 319   .   .   .   .   .   . 210
 80:  309 208 308 209   .   . 310   .   . 322
 90:  328 317 104 212 105   .   .   .   .   .
100:  306
Total integers found: 53

The three digit IDs which mark solutions have first digit as expression group minus one (0-4), next two digits are position within group of generating expression.

Or using expression format...

Code:

./genx -n 2029 -e
13 = 2+0+2+9
0 = 2*0*2*9
2 = 2+(0*2*9)
...
47 = 90/2+2
43 = 90/2-2
8 = 9-(2+0)/2
Total integers found: 53

Or verbose expression format prefixes expression number to result

Code:

./genx -n 2029 -ev
Digits=2029, Zeroes=1
1, 13 = 2+0+2+9
2, 0 = 2*0*2*9
101, 2 = 2+(0*2*9)
102, 1 = 2^(0*2*9)
104, 38 = 20+(2*9)
...
323, 44 = (90-2)/2
325, 6 = (9^0+2)*2
326, 47 = 90/2+2
327, 43 = 90/2-2
329, 8 = 9-(2+0)/2
Total integers found: 53

With only the year argument and no option it simply streams out the digits, but that is not shown here.

That was not difficult functionality to add and really speeds evaluating results with test cases, without recompiling!

But I am afraid this is all my play time today! I will try to clean it up and add it here or to my blog soon.

Thanks!

astrogeek · 01-09-2019, 03:43 AM

I found an error (actually a few) in my expressions which I have now resolved.

Fixing one of them caused me to get a different result than your code produces on my 5789 test case. When I tried to resolve that in my own expressions I was left scratching my head.

Code:

./genx -n 5789 -m
       0   1   2   3   4   5   6   7   8   9
  0:    . 301 402 329 402 422 405 323 405 327
 10:  411 218 314 201 314 201 411 406 402 319
 20:  402 319 422 408 403 402 205 411 319 001
 30:  403   . 319 314 205 407 402 408 202 319
 40:  403 319 332   . 332 407 202   . 205 423
 50:  403   . 203   . 422 406 315 423 315 331
 60:  205   .   . 422 332   . 330   .   . 332
 70:  202   . 330 332 105 423 302 332 330   .
 80:  407   . 330 315 302   . 332 315 401 314
 90:  330 315 401   . 315 423 315   .   .   .
100:  401
Total expr evaluations : 2088
Total unique solutions : 82
Total valid solutions  : 466

When I looked at the output of yours for that case I found that you produce zero as a solution while mine does not. Zero appears to be incorrect and results from each of these expressions:

Code:

0 = 5/(7*8)^9
0 = 5/7^(8+9)
0 = (5/7)^(8*9)
0 = 5/7^(8*9)
0 = ((5/7)^8)^9
0 = (5/7^8)^9
0 = 5/(7^8)^9
0 = (5/7)^(8^9)
0 = (5/7)^89
0 = 5/7^89
0 = (5/78)^9
0 = 5/78^9
0 = 5^(7-8*9)
0 = 5^(7-8^9)
0 = 5^(7-89)

I assume that results from python's precision and rounding. I saw in your code that you test for whole number solutions by a limit expression, but am not sure how python handles that, so maybe you just need to set a lower limit...?

Beryllos · 01-09-2019, 09:29 AM

Oh no! I am sorry to have made you chase down my error. You are right, it is related to rounding, but it's not python's fault.

In the main program, I have the following instruction to separate whole numbers from fractions. (The round function is the nearest integer.)

Code:

if abs(value-round(value)) < 1e-10:

The 1e-10 margin allowed all those false results for 0 as you noticed.

Of course the simple way to check for whole numbers it is to test for equality with the nearest integer:

Code:

if value == round(value):

but I decided to allow a margin of error because I expected some roundoff (truncation) error in floating-point division.

Truncation error is implementation-dependent. I can demonstrate it in C. However, in python, at least as it is implemented on my computer, truncation error is negligible, and the calculations involved in this New Year Puzzle seem to come out exact. I hadn't expected it to be so exact.

Therefore, I think the best solution is to use the strict equality test rather than the margin test.

I am also considering modifying the power calculation to skip high powers (say, greater than 100). This precaution is not needed for the four-digit New Year Puzzle, but with 5 or more digits, a small fraction taken to a high power, like (1/9)^340, can underflow to zero, and show up as a false result for 0.

astrogeek · 01-09-2019, 12:52 PM

Quote:

Originally Posted by Beryllos

Oh no! I am sorry to have made you chase down my error. You are right, it is related to rounding, but it's not python's fault.

In the main program, I have the following instruction to separate whole numbers from fractions. (The round function is the nearest integer.)

Code:

if abs(value-round(value)) < 1e-10:

The 1e-10 margin allowed all those false results for 0 as you noticed.

I remembered seeing that in your code but did not look for it again at the time (It was 3AM and I should have long been in bed!). If I had, and thought about it for a full second I would have understood the problem, I think.

I am not testing for those errors myself, but simply depending on the default behavior of C. My whole-number test is to compare the float to its integer cast, ignoring potential floating point limitations. But because my expressions are hard wired instead of permuted I may not see some of those expressions (but I will review them for such potential problems at some point.)

But if we are down to finding only precision limit problems, I'd say we are doing well!

Thanks!