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.

Pages: 1 2

10 Responses to “Vietnam Snake”

  1. Jussi Piitulainen said

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

  2. Ernie Gore said

    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.

  3. Ernie Gore said

    Should have added that making no assumption about the integrity(?) of the two fractions yields 2672 solutions.

  4. programmingpraxis said

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

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

  6. Jussi Piitulainen said

    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 66 
    
  7. FA said

    Scala 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
    }

  8. FA said

    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

  9. Paul said

    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.

  10. Brett Warren said

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: