Vietnam Snake

May 26, 2015

I solved this as a lunchtime exercise one day at work. It’s easy to write a function that takes a permutation of the nine digits and checks if it satisfies the snake:

(define (vietnam? xs)
(= (+ (list-ref xs 0)
(/ (* 13 (list-ref xs 1))
(list-ref xs 2))
(list-ref xs 3)
(* 12 (list-ref xs 4))
(- (list-ref xs 5))
-11
(/ (* (list-ref xs 6)
(list-ref xs 7))
(list-ref xs 8))
-10)
66))

Then it’s just a matter of generating all the permutations and discarding those that fail. To make the output more useful we sort in ascending order:

> (for-each
(lambda (v) (display v) (newline))
(sort lt? (filter vietnam? (perm ‘(1 2 3 4 5 6 7 8 9)))))
(1 2 6 4 7 8 3 5 9)
(1 2 6 4 7 8 5 3 9)
(1 3 2 4 5 8 7 9 6)
(1 3 2 4 5 8 9 7 6)
(1 3 2 9 5 6 4 7 8)
(1 3 2 9 5 6 7 4 8)
(1 3 4 7 6 5 2 9 8)
(1 3 4 7 6 5 9 2 8)
(1 3 6 2 7 9 4 5 8)
(1 3 6 2 7 9 5 4 8)
(1 3 9 4 7 8 2 5 6)
(1 3 9 4 7 8 5 2 6)
(1 4 8 2 7 9 3 5 6)
(1 4 8 2 7 9 5 3 6)
(1 5 2 3 4 8 7 9 6)
(1 5 2 3 4 8 9 7 6)
(1 5 2 8 4 7 3 9 6)
(1 5 2 8 4 7 9 3 6)
(1 5 3 9 4 2 7 8 6)
(1 5 3 9 4 2 8 7 6)
(1 8 3 7 4 5 2 6 9)
(1 8 3 7 4 5 6 2 9)
(1 9 6 4 5 8 3 7 2)
(1 9 6 4 5 8 7 3 2)
(1 9 6 7 5 2 3 4 8)
(1 9 6 7 5 2 4 3 8)
(2 1 4 3 7 9 5 6 8)
(2 1 4 3 7 9 6 5 8)
(2 3 6 1 7 9 4 5 8)
(2 3 6 1 7 9 5 4 8)
(2 4 8 1 7 9 3 5 6)
(2 4 8 1 7 9 5 3 6)
(2 6 9 8 5 1 4 7 3)
(2 6 9 8 5 1 7 4 3)
(2 8 6 9 4 1 5 7 3)
(2 8 6 9 4 1 7 5 3)
(2 9 6 3 5 1 4 7 8)
(2 9 6 3 5 1 7 4 8)
(3 1 4 2 7 9 5 6 8)
(3 1 4 2 7 9 6 5 8)
(3 2 1 5 4 7 8 9 6)
(3 2 1 5 4 7 9 8 6)
(3 2 4 8 5 1 7 9 6)
(3 2 4 8 5 1 9 7 6)
(3 2 8 6 5 1 7 9 4)
(3 2 8 6 5 1 9 7 4)
(3 5 2 1 4 8 7 9 6)
(3 5 2 1 4 8 9 7 6)
(3 6 4 9 5 8 1 7 2)
(3 6 4 9 5 8 7 1 2)
(3 9 2 8 1 5 6 7 4)
(3 9 2 8 1 5 7 6 4)
(3 9 6 2 5 1 4 7 8)
(3 9 6 2 5 1 7 4 8)
(4 2 6 1 7 8 3 5 9)
(4 2 6 1 7 8 5 3 9)
(4 3 2 1 5 8 7 9 6)
(4 3 2 1 5 8 9 7 6)
(4 3 9 1 7 8 2 5 6)
(4 3 9 1 7 8 5 2 6)
(4 9 6 1 5 8 3 7 2)
(4 9 6 1 5 8 7 3 2)
(5 1 2 9 6 7 3 4 8)
(5 1 2 9 6 7 4 3 8)
(5 2 1 3 4 7 8 9 6)
(5 2 1 3 4 7 9 8 6)
(5 3 1 7 2 6 8 9 4)
(5 3 1 7 2 6 9 8 4)
(5 4 1 9 2 7 3 8 6)
(5 4 1 9 2 7 8 3 6)
(5 4 8 9 6 7 1 3 2)
(5 4 8 9 6 7 3 1 2)
(5 7 2 8 3 9 1 6 4)
(5 7 2 8 3 9 6 1 4)
(5 9 3 6 2 1 7 8 4)
(5 9 3 6 2 1 8 7 4)
(6 2 8 3 5 1 7 9 4)
(6 2 8 3 5 1 9 7 4)
(6 3 1 9 2 5 7 8 4)
(6 3 1 9 2 5 8 7 4)
(6 9 3 5 2 1 7 8 4)
(6 9 3 5 2 1 8 7 4)
(7 1 4 9 6 5 2 3 8)
(7 1 4 9 6 5 3 2 8)
(7 2 8 9 6 5 1 3 4)
(7 2 8 9 6 5 3 1 4)
(7 3 1 5 2 6 8 9 4)
(7 3 1 5 2 6 9 8 4)
(7 3 2 8 5 9 1 6 4)
(7 3 2 8 5 9 6 1 4)
(7 3 4 1 6 5 2 9 8)
(7 3 4 1 6 5 9 2 8)
(7 5 2 8 4 9 1 3 6)
(7 5 2 8 4 9 3 1 6)
(7 6 4 8 5 9 1 3 2)
(7 6 4 8 5 9 3 1 2)
(7 8 3 1 4 5 2 6 9)
(7 8 3 1 4 5 6 2 9)
(7 9 6 1 5 2 3 4 8)
(7 9 6 1 5 2 4 3 8)
(8 2 4 3 5 1 7 9 6)
(8 2 4 3 5 1 9 7 6)
(8 3 2 7 5 9 1 6 4)
(8 3 2 7 5 9 6 1 4)
(8 5 2 1 4 7 3 9 6)
(8 5 2 1 4 7 9 3 6)
(8 5 2 7 4 9 1 3 6)
(8 5 2 7 4 9 3 1 6)
(8 6 4 7 5 9 1 3 2)
(8 6 4 7 5 9 3 1 2)
(8 6 9 2 5 1 4 7 3)
(8 6 9 2 5 1 7 4 3)
(8 7 2 5 3 9 1 6 4)
(8 7 2 5 3 9 6 1 4)
(8 9 2 3 1 5 6 7 4)
(8 9 2 3 1 5 7 6 4)
(9 1 2 5 6 7 3 4 8)
(9 1 2 5 6 7 4 3 8)
(9 1 4 7 6 5 2 3 8)
(9 1 4 7 6 5 3 2 8)
(9 2 8 7 6 5 1 3 4)
(9 2 8 7 6 5 3 1 4)
(9 3 1 6 2 5 7 8 4)
(9 3 1 6 2 5 8 7 4)
(9 3 2 1 5 6 4 7 8)
(9 3 2 1 5 6 7 4 8)
(9 4 1 5 2 7 3 8 6)
(9 4 1 5 2 7 8 3 6)
(9 4 8 5 6 7 1 3 2)
(9 4 8 5 6 7 3 1 2)
(9 5 3 1 4 2 7 8 6)
(9 5 3 1 4 2 8 7 6)
(9 6 4 3 5 8 1 7 2)
(9 6 4 3 5 8 7 1 2)
(9 8 6 2 4 1 5 7 3)
(9 8 6 2 4 1 7 5 3)

You can run the program at http://ideone.com/usJPll, where you will see the code that generates permutations, it fails with a “time limit exceeded” error, though I don’t know why, as it runs quickly (less than a second) on my machine at home. You might also examine The Guardian‘s official solution. If you insist on solving the problem by hand, observe that the two divisions work best if they leave integers, so either C or I should probably be 1 and the other should be 2, 3, or 4. Neither (B / C) nor E must be too large because they are multiplied by 13 and 12, respectively. Once you’ve chosen those values, do the math and rearrange the remaining terms with a constant on the right-hand side; if you’re lucky, the solution won’t be too hard to spot, or if it is, try again with a different set of starting values. I’m pretty sure there are 136 solutions, though some published accounts differ.

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 )

Google photo

You are commenting using your Google 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 )

Connecting to %s

%d bloggers like this: