Vietnam Snake
May 26, 2015
Today’s task is to solve a current exercise in recreational mathematics.
The Guardian recently published a math puzzle that is apparently given to third-grade students (eight-year old children) in Vietnam. The puzzle is a graphic in the form of a snake, and the digits 1 through 9 are to be inserted in the nine empty boxes in such a way as to make the formula correct. Although it may not be clear, the colon symbol is used for division, and the normal order of operations is to be preserved, so the formula becomes A + ((13 * B) / C) + D + (12 * E) − F − 11 + ((G * H) / I) − 10 = 66.
Your task is to write a program that generates all possible solutions to the problem. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
Programming Praxis 
Filtering the permutations by the equation in Python leaves 128 solutions. Replacing the equation with the condition that the left-hand side of the equation be between 59.999 and 66.001 leaves 136 solutions :)
(Python division produces floats now. It used to be a form of integer division. Using Python’s integer division the equation leaves 2672 solutions.)
There is a pitfall here: does each of 13B/C and GH/I have to be an integer or only the sum? Assuming the former, there are 20 solutions. Assuming the latter, there are 136 solutions.
Should have added that making no assumption about the integrity(?) of the two fractions yields 2672 solutions.
@ErnieGore: Only the sum. But if you’re working the problem by hand, it is much easier to start with solutions that make the two divisions integral.
I ran into the same discrepancy unless I ran the program using floating-point or rational operators. I get 2672 solutions if I use truncating integer operators. However I suspect many of them are false positives, because (7 3 5 8 6 9 4 1 2) = 66 4/5.
Looking at the permutations where Python (rather, floating point arithmetic) fails the sneak equation: the error is not only small (I expected even smaller but I’m not a numerical analyst) but also exactly the same in all eight cases. Exact rationals, as are common in Scheme, would not have these errors. That’s why Scheme identifies all 136 solutions without any tricks.
@cbrachyrhynchos There are half a dozen different integer division operations (rounding down, up, towards zero, to nearest, maybe worrying about signs or minimizing the absolute value of the remainder), each coupled with a different remainder operation. Technically, Python’s integer division is the flooring variant rather than truncating. That pedantry aside, I’d say that the floating point errors produce eight false negatives to the actual problem while the 2672 solutions found with the flooring division are all true solutions to a slightly different problem.
Code uses Python3 features.
from itertools import permutations def floating(A,B,C,D,E,F,G,H,I): return A + ((13 * B) / C) + D + (12 * E) - F - 11 + ((G * H) / I) - 10 def flooring(A,B,C,D,E,F,G,H,I): return A + ((13 * B) // C) + D + (12 * E) - F - 11 + ((G * H) // I) - 10 print('floating', sum(1 for p in permutations(range(1,10)) if floating(*p) == 66)) print('approxed', sum(1 for p in permutations(range(1,10)) if 65.999 < floating(*p) < 66.001)) print('flooring', sum(1 for p in permutations(range(1,10)) if flooring(*p) == 66)) # floating 128 # approxed 136 # flooring 2672 print('errors', { floating(*p) - 66 for p in permutations(range(1,10)) if 65.999 < floating (*p) < 66.001 if floating(*p) != 66 }) # errors {-1.4210854715202004e-14} # -- eight of them, all equal print(floating(7, 3, 5, 8, 6, 9, 4, 1, 2), flooring(7, 3, 5, 8, 6, 9, 4, 1, 2)) # 66.8 66Scala Worksheet:
object VietnamSnake {
(1 to 9).permutations.filter(l=>13*l(1)*l(8)+l(2)*l(6)*l(7)==(66+10+11-l(0)-l(3)-12*l(4)+l(5))*l(2)*l(8)).size
//> res0: Int = 136
(1.0 to 9.0 by 1.0).permutations.filter(l=>l(0)+13*l(1)/l(2)+l(3)+12*l(4)-l(5)-11+l(6)*l(7)/l(8)-10==66).size
//> res1: Int = 128
}
More beauty scala:
(1 to 9).permutations filter{case Vector(a,b,c,d,e,f,g,h,i) => 13*b*i+c*g*h == (66+10+11-a-d-12*e+f)*c*i } size
In Python (and I guess other languages too) it is a lot easier to multiply the equation with C * I. Then the issue about integer/ real division disappears. This gives 136 solutions.
Simple brute-force solution using a simplified version of the equation for shits and giggles. Assuming that 13B/C can be a non-integer etc. there are 128 solutions:
from itertools import permutations if __name__ == "__main__": set_of_numbers = list(range(1, 10)) valid_variables_list = list() for variable_values in permutations(set_of_numbers): (A, B, C, D, E, F, G, H, I) = variable_values valid_variables = A + (13*B / C) + D + 12*E + (G*H / I) - F == 87 if valid_variables: labeled_variable_values = dict(zip(["A", "B", "C", "D", "E", "F", "G", "H", "I"], variable_values)) valid_variables_list.append(labeled_variable_values) print(valid_variables_list, len(valid_variables_list))