/////////////////////////////////////////////////////////////////////////////// // Just forgotten /////////////////////////////////////////////////////////////////////////////// // Enigma 1517 Bob Walker, New Scientist magazine, October 25, 2008. /////////////////////////////////////////////////////////////////////////////// // // Joe was furious when he forgot one of his bank account numbers. // He remembered that it had all the digits 0 to 9 in some order, so he tried // the following four sets without success: // // 9 4 6 2 1 5 7 8 3 0 // 8 6 0 4 3 9 1 2 5 7 // 1 6 4 0 2 9 7 8 5 3 // 6 8 2 4 3 1 9 0 7 5 // // When Joe finally remembered his account number, he realised that in each set // just four of the digits were in their correct position and that, if one knew // that, it was possible to work out his account number. // What was it? // /////////////////////////////////////////////////////////////////////////////// // // Solve the problem by running the query: // // all Just_forgotten(number) // /////////////////////////////////////////////////////////////////////////////// // // Results: // // number = [9,6,2,4,3,1,7,8,5,0] // ___ Solution: 1 ___ [00:00:03] __ [Backtracks: 2353202] ____ // // Number of solutions: 1 Number of backtracks: 28975238 // Elapsed time: 00:00:38 // /////////////////////////////////////////////////////////////////////////////// local Seq1 :<[0..9]->>I = [9,4,6,2,1,5,7,8,3,0] local Seq2 :<[0..9]->>I = [8,6,0,4,3,9,1,2,5,7] local Seq3 :<[0..9]->>I = [1,6,4,0,2,9,7,8,5,3] local Seq4 :<[0..9]->>I = [6,8,2,4,3,1,9,0,7,5] pred Just_forgotten(res::[0..9]->>I[0..9]) iff // Array of four correct placement counters, one for each sequence. counters :.[0..3]->I[0..4] & counters := [0,0,0,0] & // For each digit in the forgotten number: If the digit "n" is in the // position "xn", check all four sequences if the digit is in the same // position. If any sequence contains the digit in the same position, // increment the corresponding position counter. res(x0) = 0 & CorrectPlace(0,x0,counters) & res(x1) = 1 & CorrectPlace(1,x1,counters) & res(x2) = 2 & CorrectPlace(2,x2,counters) & res(x3) = 3 & CorrectPlace(3,x3,counters) & res(x4) = 4 & CorrectPlace(4,x4,counters) & res(x5) = 5 & CorrectPlace(5,x5,counters) & res(x6) = 6 & CorrectPlace(6,x6,counters) & res(x7) = 7 & CorrectPlace(7,x7,counters) & res(x8) = 8 & CorrectPlace(8,x8,counters) & res(x9) = 9 & CorrectPlace(9,x9,counters) & // Accept only solutions that have exactly four digits in correct positions. counters(0) = 4 & counters(1) = 4 & counters(2) = 4 & counters(3) = 4 /////////////////////////////////////////////////////////////////////////////// // Check all sequences: If the number "i" is in the position "x" then increment // the correct position counter for the correponding sequence... local pred CorrectPlace(i:<I,x::I,counters:.[0..3]->I[0..4]) iff CorrectOnePlace(Seq1,i,x,counters(0)) & CorrectOnePlace(Seq2,i,x,counters(1)) & CorrectOnePlace(Seq3,i,x,counters(2)) & CorrectOnePlace(Seq4,i,x,counters(3)) /////////////////////////////////////////////////////////////////////////////// // If in the sequence "seq" the number "i" is in the position "x" increment // the correct position counter "counter". Otherwise do nothing... local pred CorrectOnePlace(seq:<[0..9]->>I,i:<I,x::I,counter:.I[0..4]) iff (seq(x) = i & counter := counter+1) | true
This page was created by F1toHTML