The "finding the digits problem" is this:
Find unique decimal digits A, B, C such that
CCC
+ BBB
+ AAA
= CAAB
To solve it using recursion in Common Lisp, I've written this code:
(defun find! ()
(found? 0 ;; initially point to the number 1
'(1 2 3) ;; initial list
'() ;; initially no numbers found
3 ;; numbers list width is 3
) )
(defun found? (index lst occupied width)
(if (< index (1- width))
(do ( (j 1 (1+ j) ) )
( (> j 9) lst)
(unless (some (lambda (x) (= x j)) occupied)
(setf (nth index lst) j)
(push j occupied)
(if (found? (1+ index) lst occupied width) ;; recursion happens here
lst
(setf occupied (remove j occupied)))))
(do ( (j 1 (1+ j) ) )
( (> j 9) lst)
(unless (some (lambda (x) (= x j)) occupied)
(setf (nth index lst) j)
(let ((lefthnd (* 111 (reduce #'+ lst)))
(rghthnd (reduce #'+
(mapcar
(lambda (x y) (* x y))
'(1000 100 10 1)
(list (third lst) (first lst)
(first lst) (second lst))))))
(if (= lefthnd rghthnd)
lst
'nil))))))
The delivered result (lst) is (9 9 9)
The expected result (lst) is (9 8 1) meaning A=9, B=8, C=1 so that the equation CCC + BBB + AAA = CAAB holds i.e.
111 ; CCC
+ 888 ; BBB
+ 999 ; AAA
= 1998 ; CAAB
Which parts of the code should I change so that it gives the expected result? Can someone fix the code? Note that using recursion is a must. Only one line of recursion is enough i.e. like the line where the ;; recursion happens here comment is.
What is the minimal edit to fix this code?
The minimal edit needed to make your code work is the following three small changes (marked with ;;;; NB in the comments):
(defun find! ()
(found? 0 ;; initially point to the number 1
(list 1 2 3) ;; initial list ;;;; NB freshly allocated!
'() ;; initially no numbers found
3 ;; numbers list width is 3
) )
push of j into occupied:(defun found? (index lst occupied width)
(if (< index (1- width))
(do ( (j 1 (1+ j) ) )
( (> j 9) lst)
(unless (some (lambda (x) (= x j)) occupied)
(setf (nth index lst) j)
(push j occupied)
(if (found? (1+ index) lst occupied width) ;; recursion happens here
lst) ;;;; NB
(setf occupied (remove j occupied)))) ;;;; NB _always_ undo the push
(do ( (j 1 (1+ j) ) )
( (> j 9) lst)
(unless (some (lambda (x) (= x j)) occupied)
(setf (nth index lst) j)
(let ((lefthnd (* 111 (reduce #'+ lst)))
(rghthnd (reduce #'+
(mapcar
(lambda (x y) (* x y))
'(1000 100 10 1)
(list (third lst) (first lst)
(first lst) (second lst))))))
(if (= lefthnd rghthnd)
(return-from found? lst) ;;;; NB actually return here
'nil))))))
If you change the return-from line to print the result instead of returning it, you will get all of them printed.
If you want to get them all in a list instead of being printed, you can surgically append each of the results to some list defined in some outer scope (or cons onto the front and reverse it when it's all done, if you prefer).
Or in general, you can change this code to accept a callback and call it with each result, when it is found, and let this callback to do whatever it does with it -- print it, append it to an external list, whatever.
Remarks: your code follows a general recursive-backtracking approach, creating three nested loops structure through recursion. The actual result is calculated -- and put into lst by surgical manipulation -- at the deepest level of recursion, corresponding to the innermost loop of j from 1 to 9 (while avoiding the duplicates).
There's lots of inconsequential code here. For instance, the if in (if (found? ...) lst) isn't needed at all and can be just replaced with (found? ...). I would also prefer different names -- occupied should really be named used, lst should be res (for "result"), index is canonically named just i, width is just n, etc. etc. (naming is important)... But you did request the smallest change.
This code calculates the result lst gradually, as a side effect on the way in to the innermost level of the nested loops, where it is finally fully set up.
Thus this code follows e.g. an example of Peter Norvig's PAIP Prolog interpreter, which follows the same paradigm. In pseudocode:
let used = []
for a from 1 to 9:
if a not in used:
used += [a]
for b from 1 to 9:
if b not in used:
used += [b]
for c from 1 to 9:
if c not in used and valid(a,b,c):
return [a,b,c] # or:
# print [a,b,c] # or:
# call(callback,[a,b,c]) # etc.
remove b from used
remove a from used
Here's your code re-structured, renamed, and streamlined:
(defun find2 ( &aux (res (list 0 0 0))
(used '()) (n (length res)))
(labels
((f (i)
(do ((d 1 (1+ d))) ; for d from 1 to 9...
((> d 9) 'FAIL) ; FAIL: no solution!
(unless (member d used) ; "d" for "digit"
(setf (nth i res) d) ; res = [A... B... C...]
(cond
((< i (- n 1)) ; outer levels
(setf used (cons d used))
(f (1+ i)) ; recursion! going in...
(setf used (cdr used))) ; and we're out.
(T ; the innermost level!
(let ((left (* 111 (reduce #'+ res)))
(rght (reduce #'+
(mapcar #'* '(1000 100 10 1)
(list (third res) ; C A A B
(first res)
(first res)
(second res))))))
(if (= left rght)
(return-from find2 res))))))))) ; success!
(f 0)))
This is now closely resembling the C++ code you once had in your question, where the working function (here, f) also received just one argument, indicating the depth level of the nested loop -- corresponding to the index of the digit being tried, -- and the rest of the variables were in an outer scope (there, global; here, the auxiliary variables in the containing function find2).
By the way, you aren't trying any 0s for some reason.