Solving the Puzzle

Solving the Can You Solve The Impossible Puzzle? with Common Lisp and Org Mode.

Our search space contains 45 possible candidates of pairs of numbers. The tables below will have one candidate of a pair on each row. In the first column, we have the multiple, in the second column the sum and the last two columns the candidate pair. The prune function will help us to reduce the search space on each interaction, filtering the elements without repetition.

(ql:quickload :group-by)

(defun prune (data func)
  (let* ((pre (group-by:group-by-repeated data :keys (list func)))
         (input (remove-if (lambda (p) (<= (length (cdr p)) 1)) pre)))
    (reduce (lambda (acc a) (append acc (cdr a))) input
            :initial-value '((m s x y)))))

(cons '(m s x y)
      (loop for x from 1 to 9
            append (loop for y from 9 downto x
                         collect (list (* x y) (+ x y) x y))))

#+RESULTS[ca79f9a22ba8cd356c32197a5ac0ad93f8159c81]: start

m	s	x	y
9	10	1	9
8	9	1	8
7	8	1	7
6	7	1	6
5	6	1	5
4	5	1	4
3	4	1	3
2	3	1	2
1	2	1	1
18	11	2	9
16	10	2	8
14	9	2	7
12	8	2	6
10	7	2	5
8	6	2	4
6	5	2	3
4	4	2	2
27	12	3	9
24	11	3	8
21	10	3	7
18	9	3	6
15	8	3	5
12	7	3	4
9	6	3	3
36	13	4	9
32	12	4	8
28	11	4	7
24	10	4	6
20	9	4	5
16	8	4	4
45	14	5	9
40	13	5	8
35	12	5	7
30	11	5	6
25	10	5	5
54	15	6	9
48	14	6	8
42	13	6	7
36	12	6	6
63	16	7	9
56	15	7	8
49	14	7	7
72	17	8	9
64	16	8	8
81	18	9	9

In the first time that Barack asked Pete, if Pete knew the answer his multiple would be unique defined in the candidate list, that was not the case, so we must remove the multiples without repetitions.

(prune (cdr data) #'first)

#+RESULTS[6db81e23c88ea3483e1865437f8de0f9cca170cd]: step-1

m	s	x	y
36	12	6	6
36	13	4	9
24	10	4	6
24	11	3	8
12	7	3	4
12	8	2	6
16	8	4	4
16	10	2	8
18	9	3	6
18	11	2	9
4	4	2	2
4	5	1	4
6	5	2	3
6	7	1	6
8	6	2	4
8	9	1	8
9	6	3	3
9	10	1	9

When Barack asked Susan for the first time, she already knew that Pete didn’t know the answer either. So the candidate list in her mind is the list above. But she didn’t know the answer of Barack’s question either, so her sum are not unique in this list too.

(prune (cdr data) #'second)

#+RESULTS[2ac1f2a3d955fbf7a89f6db99a91c8f902775483]: step-2

m	s	x	y
9	6	3	3
8	6	2	4
6	5	2	3
4	5	1	4
8	9	1	8
18	9	3	6
16	8	4	4
12	8	2	6
6	7	1	6
12	7	3	4
18	11	2	9
24	11	3	8
9	10	1	9
16	10	2	8
24	10	4	6

In the second time that Barack asked Pete, he still didn’t know. So we have to exclude all unique multiples again.

(prune (cdr data) #'first)

#+RESULTS[d5b928145f97d2bea7471b63383a9e34d6178b5a]: step-3

m	s	x	y
24	10	4	6
24	11	3	8
12	7	3	4
12	8	2	6
16	10	2	8
16	8	4	4
18	11	2	9
18	9	3	6
6	7	1	6
6	5	2	3
8	9	1	8
8	6	2	4
9	10	1	9
9	6	3	3

The same again for the second time Barack asked Susan:

(prune (cdr data) #'second)

#+RESULTS[17b25e5fc689d147eda2bd35c388cde44f310568]: step-4

m	s	x	y
9	6	3	3
8	6	2	4
8	9	1	8
18	9	3	6
16	8	4	4
12	8	2	6
6	7	1	6
12	7	3	4
18	11	2	9
24	11	3	8
9	10	1	9
16	10	2	8
24	10	4	6

Pete in the third time still didn’t know.

(prune (cdr data) #'first)

#+RESULTS[44d455fea1e59e9db1788bb012f6cdd4abcc32f1]: step-5

m	s	x	y
24	10	4	6
24	11	3	8
12	7	3	4
12	8	2	6
16	10	2	8
16	8	4	4
18	11	2	9
18	9	3	6
8	9	1	8
8	6	2	4
9	10	1	9
9	6	3	3

Susan in the third still didn’t know.

(prune (cdr data) #'second)

#+RESULTS[7a0a13546e37c1bd0d1fff1059eb069b381cbd30]: step-6

m	s	x	y
9	6	3	3
8	6	2	4
8	9	1	8
18	9	3	6
16	8	4	4
12	8	2	6
18	11	2	9
24	11	3	8
9	10	1	9
16	10	2	8
24	10	4	6

Pete once more didn’t know:

(prune (cdr data) #'first)

#+RESULTS[079394364b443353af7d9353a8c0a38835b09ee2]: step-7

m	s	x	y
24	10	4	6
24	11	3	8
16	10	2	8
16	8	4	4
18	11	2	9
18	9	3	6
8	9	1	8
8	6	2	4
9	10	1	9
9	6	3	3

Susan in the fourth time didn’t know either:

(prune (cdr data) #'second)

#+RESULTS[e8f43474732654a4d80a659c50fe51b7ddba6a28]: step-8

m	s	x	y
9	6	3	3
8	6	2	4
8	9	1	8
18	9	3	6
18	11	2	9
24	11	3	8
9	10	1	9
16	10	2	8
24	10	4	6

At this moment, in the fifth time, Pete knew the answer. That is, his number should be 16, since this is the only multiple that unique defines the candidates: 2 and 8.

If Pete didn’t knew at this time, Barack would have asked once more to Susan and we would have to exclude the pair (2,8) from the list of candidates:

(prune (cdr data) #'first)

#+RESULTS[b04f949aa4cfaea9ae9f63533fc50b207336f698]: step-9

m	s	x	y
24	10	4	6
24	11	3	8
18	11	2	9
18	9	3	6
8	9	1	8
8	6	2	4
9	10	1	9
9	6	3	3

In this candidate list, Susan would not be able to identify the numbers since no sum is unique.

Links

• A Multi-Language Computing Environment for Literate Programming and Reproducible Research
• http://orgmode.org
• http://quicklisp.org
• Common Lisp

---