New Year Puzzle
Posted 01-04-2019 at 07:43 PM by astrogeek
Updated 02-22-2019 at 04:41 PM by astrogeek (Reorganizing categories)
Updated 02-22-2019 at 04:41 PM by astrogeek (Reorganizing categories)
NOTE: See updates at bottom of this post - last 1/5/19
Way back around new year's day during the winter of '19 (remember that kiddies?), LQ member Beryllos posted a New Year Puzzle and programming challenge in the Programming forum.
The goal of the puzzle is to generate as many whole numbers as possible between 0 and 100 using only the digits of the year, 2,0,1 and 9 in simple constant arithmetic expressions such as 9 * (10 - 2).
The rules are simple, with only a little bit of clarification required, which I summarize here:
I think the puzzle must pre-date computers, intended to be a pencil and paper amuzement for those so inclined, but the challenge here is to work out a computer program to find the solutions.
As I got about my daily life sustaining tasks, the challenge continued to bounce around inside my otherwise largely empty skull, and by the end of the day I had worked out a strategy to attack the problem in C.
I decided that with only 24 permutations of digits, one of which was always zero, and the limited range of operations and result values, I could probably work out the basic math expressions as quickly as I could write code to generate them. So I decided to write a simple loop to produce the permutations and an output loop to let me quickly see the results, then I could go directly to the point of the puzzle - the math expressions.
I'll post my code in two parts with introductory comments. First the variable definitions, loop for permutation of the digits and output handling. Second, the expressions to be evaluated within the loop.
I track results with an array of 101 chars, initialized to all zeros. When an expression produces a valid result I will set the corresponding array element to a non-zero value. When done we can iterate the array for non-zero values, the array index being the result value.
I wanted the code to be able to implicitly enforce the rules as much as possible, so that I would not have to spend time writing tests for each expression. So the function setint() is used to store the results and also enforces the range, 0 <= result <=100. Change of sign is always valid, so not knowing what my expressions would actually produce when written, I invert any negative values here which is equivalent to any change of sign in an expression, so is allowed.
The test for whole number result is a comparison of the float value produced by an expression with an integer cast of the same value.
The function also takes a single char argument which is used as the result flag, and is also a tracer of the expression which first produced a given result value.
There are only four digits, so generating all permutations was as simple as nesting four suitable for loops, using the loop counters, p1 thru p4, as indexes to the digits in an array of integers d[].
At this point all I need do is write the math expression in the inner loop using the digits d[p1], d[p2], d[p3] and d[p4] exactly once in each. This makes it easy to check the validity of each expression and to write the math without a lot of obfuscating code.
Finally, we write a set of expressions to put into our permutations loop.
For my concatenation operator I multiply the leading digit by 10 and add the digit to be concatenated. For example to produce '92' from '9' and '2' I would use 9*10 +2 in my expression. Note that the multiplier 10 is not the digits '1' and '0' - it is an operator, not a number.
Because the expressions are compact I can write them all inside the setint(...) call, with leading alpha expression identifier. The expression identifier order shown is not significant, it simply resulted from the order in which I wrote and grouped the expressions.
I use simple conditionals to prevent concatenation of leading zeroes and division by zero.
When we put the expressions inside the loop code and compile, it produces this (I have broken the last line and added some space formatting to this post)...
Beryllos then posted their own solution written in python code which was much more thorough. It recurses all permutations of digits and operations, producing all possible solutions. See the linked thread above for their solution with code.
I had expected the result to turn up at least a few values I had not found, but it turned out that my C code and expressions had produced all but one of the possibilities, 72, as noted in the code above. I expected that I had missed more, so that was very gratifying!
It was a fun exercise, and I thought a useful enough programming example, so I have posted it to my blog for future reference.
Thanks to Beryllos for the diversion! Comments, improvements and adaptations to other purposes welcomed!
UPDATED: In haste I had made an incorrect assumption in thinking that because all expressions appeared in the results, all were necessary. Because I recorded only the first expression to produce a given number, it was possible that one or more later expressions would overlap an entire set and the first would still appear, so that appearance of expression ID in the result set was order dependent.
I have now modified the expression set, effectively removing five of them, still producing the same complete result set.
Also, after stepping away from it for a couple of days, I see a better path to writing the expressions which leads to a minimal set of expressions which will produce all solutions for any set of up to four digits (0-9999).
It is based on realization of how the number of zeroes among the digits determines the set of operations which must be performed to produce all possible solutions. They form a hierarchy of operations which allows you to exclude the need to handle whole families of expressions (i.e. greatly simplifying the overall problem).
I will try to work those thoughts into a new iteration of code and expressions as time permits - but also present it here as a sub-challenge for those who like thinking about such things!
Way back around new year's day during the winter of '19 (remember that kiddies?), LQ member Beryllos posted a New Year Puzzle and programming challenge in the Programming forum.
The goal of the puzzle is to generate as many whole numbers as possible between 0 and 100 using only the digits of the year, 2,0,1 and 9 in simple constant arithmetic expressions such as 9 * (10 - 2).
The rules are simple, with only a little bit of clarification required, which I summarize here:
Code:
* You may use the operations of addition, subtraction, multiplication, division and exponents,
plus parenthesis for grouping as necessary
* You may concatenate the original digits, 90 for example, but not the result of any other
operations. Concatenations may not produce leading zeroes, like '09'.
* You may change sign as you like, -(2 - 9) * 10 for example
* You must use each original digit exactly once in each expression
* The result of each expression must be a whole number without rounding or truncation, so
expressions like 9/2 + 1 = 5 are not valid - which puts bash scripts out of the competition!
As I got about my daily life sustaining tasks, the challenge continued to bounce around inside my otherwise largely empty skull, and by the end of the day I had worked out a strategy to attack the problem in C.
I decided that with only 24 permutations of digits, one of which was always zero, and the limited range of operations and result values, I could probably work out the basic math expressions as quickly as I could write code to generate them. So I decided to write a simple loop to produce the permutations and an output loop to let me quickly see the results, then I could go directly to the point of the puzzle - the math expressions.
I'll post my code in two parts with introductory comments. First the variable definitions, loop for permutation of the digits and output handling. Second, the expressions to be evaluated within the loop.
I track results with an array of 101 chars, initialized to all zeros. When an expression produces a valid result I will set the corresponding array element to a non-zero value. When done we can iterate the array for non-zero values, the array index being the result value.
I wanted the code to be able to implicitly enforce the rules as much as possible, so that I would not have to spend time writing tests for each expression. So the function setint() is used to store the results and also enforces the range, 0 <= result <=100. Change of sign is always valid, so not knowing what my expressions would actually produce when written, I invert any negative values here which is equivalent to any change of sign in an expression, so is allowed.
The test for whole number result is a comparison of the float value produced by an expression with an integer cast of the same value.
The function also takes a single char argument which is used as the result flag, and is also a tracer of the expression which first produced a given result value.
There are only four digits, so generating all permutations was as simple as nesting four suitable for loops, using the loop counters, p1 thru p4, as indexes to the digits in an array of integers d[].
At this point all I need do is write the math expression in the inner loop using the digits d[p1], d[p2], d[p3] and d[p4] exactly once in each. This makes it easy to check the validity of each expression and to write the math without a lot of obfuscating code.
Code:
#include <stdio.h>
#include <math.h>
char ints[101] = {0};
void setint(char id, float num){
if(num < 0)
num = -num;
int inum = (int)num;
if(inum == num && inum <= 100 && ints[inum] == 0)
ints[inum] = id;
}
int main(void){
int idx = 0, col = 0, tot=0;
float d[] = {2, 0, 1, 9};
int p1, p2, p3, p4;
for(p1 = 0; p1 < 4; p1++){
for(p2 = 0; p2 < 4; p2++){
if(p2 == p1)
continue;
for(p3 = 0; p3 < 4; p3++){
if(p3 == p1 || p3 == p2)
continue;
for(p4 = 0; p4 < 4; p4++){
if(p4 == p1 || p4 == p2 || p4 == p3)
continue;
/* Write expressions here using d[p1] thru d[p4] exactly once,
passing result to setint() for validation and capture */
....
/* End expression loop */
}
}
}
}
/* Print squarish matrix of generated values and get total number */
printf(" 0 1 2 3 4 5 6 7 8 9");
for(idx = 0; idx <= 100; idx += 10){
printf("\n%3i: ", idx);
for(col = 0; col < 10; col++){
if(ints[idx + col] > 0)
tot++, printf("%c ", ints[idx + col]);
else
printf(". ");
if(idx == 100)
break;
}
}
printf("\nTotal integers found: %i\n", tot);
for(idx = 0; idx <= 100; idx++){
if(ints[idx] > 0)
printf("%i ", idx);
}
puts("");
return 0;
}
For my concatenation operator I multiply the leading digit by 10 and add the digit to be concatenated. For example to produce '92' from '9' and '2' I would use 9*10 +2 in my expression. Note that the multiplier 10 is not the digits '1' and '0' - it is an operator, not a number.
Because the expressions are compact I can write them all inside the setint(...) call, with leading alpha expression identifier. The expression identifier order shown is not significant, it simply resulted from the order in which I wrote and grouped the expressions.
I use simple conditionals to prevent concatenation of leading zeroes and division by zero.
Code:
setint('A', d[p1] * d[p2] * d[p3] + d[p4]);
setint('B', (d[p1] - d[p2]) * (d[p3] + d[p4]));
/* Concat operator is d[x]*10+d[y] where d[x] is not zero */
if(d[p1]!=0){
setint('C', (d[p2] + d[p3]) / d[p1] + d[p4]); // (9+1)/2 +0
setint('D', (d[p1]*10 + d[p2]) - d[p3] - d[p4]);
setint('E', (d[p1]*10 + d[p2]) * (d[p3] - d[p4]));
setint('F', powf(d[p2],d[p3]) + (d[p1]*10 + d[p4])); // 9^1+20
setint('G', (d[p1]*10 + d[p2] - d[p3]) * d[p4]); //(10-2)*9 - Beryllos
/* Prevent div by zero and leading zero on second concat */
if(d[p2]!=0){
setint('H', ((d[p1]*10 + d[p3]) / d[p2]) + d[p4]);
setint('I', ((d[p1]*10 + d[p3]) / d[p2]) - d[p4]);
setint('J', (d[p1]*10 + d[p3]) + (d[p2]*10 + d[p4]));
setint('K', (d[p1]*10 + d[p3]) - (d[p2]*10 + d[p4]));
setint('L', ((d[p1]*10 + d[p3]) * d[p4]) / d[p2] ); // 9*10/2
setint('M', (d[p1]*100 + d[p3]*10 + d[p4]) / d[p2] ); // 190/2
}
}
setint('N', powf(d[p1], d[p2]) + d[p3] + d[p4]);
setint('O', powf(d[p1], d[p2]) - d[p3] + d[p4]);
setint('P', powf(d[p1], d[p2]) + powf(d[p3], d[p4]));
setint('Q', powf(d[p1] + d[p2] - d[p3], d[p4]));
Code:
gcc -Wall -lm nygen.c -o nygen
./nygen
0 1 2 3 4 5 6 7 8 9
0: G Q P P I C O O O A
10: D N D F H . B D A K
20: B F F . . . . B D F
30: F . . . . . . . E J
40: . . . . I L H . . .
50: . . . . . . . . . .
60: . . . . Q . . . . K
70: E K G . . . . . K .
80: O P P . . . . D G D
90: E F E F . M . . . .
100: Q
Total integers found: 49
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 72 78
80 81 82 87 88 89 90 91 92 93 95 100
I had expected the result to turn up at least a few values I had not found, but it turned out that my C code and expressions had produced all but one of the possibilities, 72, as noted in the code above. I expected that I had missed more, so that was very gratifying!
It was a fun exercise, and I thought a useful enough programming example, so I have posted it to my blog for future reference.
Thanks to Beryllos for the diversion! Comments, improvements and adaptations to other purposes welcomed!
UPDATED: In haste I had made an incorrect assumption in thinking that because all expressions appeared in the results, all were necessary. Because I recorded only the first expression to produce a given number, it was possible that one or more later expressions would overlap an entire set and the first would still appear, so that appearance of expression ID in the result set was order dependent.
I have now modified the expression set, effectively removing five of them, still producing the same complete result set.
Also, after stepping away from it for a couple of days, I see a better path to writing the expressions which leads to a minimal set of expressions which will produce all solutions for any set of up to four digits (0-9999).
It is based on realization of how the number of zeroes among the digits determines the set of operations which must be performed to produce all possible solutions. They form a hierarchy of operations which allows you to exclude the need to handle whole families of expressions (i.e. greatly simplifying the overall problem).
I will try to work those thoughts into a new iteration of code and expressions as time permits - but also present it here as a sub-challenge for those who like thinking about such things!
Total Comments 0
