Vietnamese snake puzzle - Closed

[Gerson W. Barbosa]

An RPL solution, basically what I did by hand, except that I was a bit smarter and didn't go through some impossible alternatives. But the hp 50g is much faster than I am, so no problem: less than four minutes to find four solutions which can be expanded to more by applying commutative properties of multiplication and addition (9 seconds on the emulator). Writing the program took a bit longer, however, no to mention I lost more the more complicated inner structers last night, by accidentally replacing it with something else. No backups, no notes as it had been done right on the calculator only.

Conclusion: better do this by hand :-)

Code:


%%HP: T(3)A(D)F(.);
\<< { 2. 3. 4. 5. 6. 7. 8. 9. } { } 2. 9.
  FOR i 2. 9.
    FOR b b i \=/
      IF
      THEN b 13. * 87. - 2. 9.
        FOR e e b \=/ e i \=/ AND
          IF
          THEN e 12. * OVER + 4. PICK 1.
            \<<
              IF DUP DUPDUP i == SWAP b == OR SWAP e == OR
              THEN DROP
              END
            \>> DOLIST 1. 4.
            FOR j j 1. + 5.
              FOR k DUP j GET OVER k GET DUP2 * i MOD
                IF NOT
                THEN 0. 0. 0. \-> g h a d f
                  \<< g h * i / PICK3 + OVER 1.
                    \<<
                      IF DUPDUP g == SWAP h == OR
                      THEN DROP
                      END
                    \>> DOLIST 1. 3.
                    START DUPDUP HEAD SWAP TAIL SWAP + SWAP PICK3 SWAP OBJ\-> DROP + NEG + ==
                      IF
                      THEN DUP2 NIP OBJ\-> DROP 'f' STO 'd' STO 'a' STO a b 1. d e f g h i { 9. } \->ARRY 7. ROLL + 6. ROLLD
                      END
                    NEXT DROP2
                  \>>
                ELSE DROP2
                END
              NEXT
            NEXT DROP2
          END
        NEXT DROP
      END
    NEXT
  NEXT NIP
\>>

{ [ 9. 4. 1. 5. 2. 7. 3. 8. 6. ] [ 3. 2. 1. 5. 4. 7. 8. 9. 6. ] [ 7. 3. 1. 5. 2. 6. 8. 9. 4. ] [ 6. 3. 1. 9. 2. 5. 7. 8. 4. ] }

This should work on the HP-48G also, only remember to make this changes and others I may have forgotten:

NIP: SWAP DROP
DUPDUP: DUP DUP
PICK3: 3 PICK

Gerson.

Edited to fix the range of the loops. I had found an incredible 50-second runtime but the outer loops were ranging from 2 to 6, 2 to 4 and 2 to 8, respectively, and yet the program returned the same four solutions. Something to be explored and analyzed to improve the program. There is still room for improvement such as better list handling, for instance.

P.S.: Considering our equation is

a + 13*b + d + 12*e - f - 11 + g*h/i = 76

We can write the following table:

b e f| result
-----+-------
9 x 8| > 109
8 x 9| > 95
7 2 9| > 106
6 2 9| > 90 => b < 6

x 9 8| > 100
x 8 9| > 87 => e < 8

5 7 9| > 140
5 6 9| > 120
4 5 9| > 106
3 5 9| > 90 => e < 5

Now we can safely define the ranges of the outer loops and be sure we won't miss any solution:

Code:


\<< { 2. 3. 4. 5. 6. 7. 8. 9. } { } 2. 9.
  FOR i 2. 5.
    FOR b b i \=/
      IF
      THEN b 13. * 87. - 2. 4.
        FOR e e b \=/ e i \=/ AND
  ...

{ [ 9. 4. 1. 5. 2. 7. 3. 8. 6. ] [ 3. 2. 1. 5. 4. 7. 8. 9. 6. ] [ 7. 3. 1. 5. 2. 6. 8. 9. 4. ] [ 6. 3. 1. 9. 2. 5. 7. 8. 4. ] }

33.6 seconds on the physical HP 50g!

This matches Tugdual's results when c=1, considering all valid permutations:

941527386
941527836
541927836
541927386

321547896
321547986
521347986
521347896

731526894
731526984
531726984
531726894

631925874
631925784
931625874
931625784