In order to solve the finding the digits problem using recursion in Common Lisp (CL):

**If CCC BBB AAA = CAAB, then find the numbers A, B, C. The numbers are unique integers**

I've written this code:

(defun find! ()
  (found? 0        ;; initially show 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
          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)

Which parts of the CL code should I change so that it gives the expected result?

EXTRA(non essential info about the question) I've written a C code for the same problem using recursion and it delivers the expected result which means that the recursion style solution works. The C code is below. Actually, the CL code above is the direct conversion of the C solution (plus some CL functions like the mapcar and reduce)

#include <iostream>
using namespace std;

const int width = 3; // numbers list width is 3 
int lst[width]; // list to hold the digits 
bool occupied[10]; /* numbers betw. 1-9 */

bool found(int index) {
  if(index < width - 1) {
    for(int j = 1; j <= 9; j  ) {
      if(!occupied[j]) {
    lst[index] = j;
    occupied[j] = true;
    if(found(index   1))
      return true;
    occupied[j] = false; } } }
  
  else {
    for(int j = 1; j <= 9; j  ) {
      if(!occupied[j]) {
    lst[index] = j;
    int lefthnd = 111 * (lst[0]   lst[1]   lst[2]);
    int rghthnd = 1000 * lst[2]   100 * lst[0]   10 * lst[0]   1 * lst[1];
    if(lefthnd == rghthnd) 
      return true;
    else
      return false;
      } } }
  return false; }

int main() {
  for(int i = 1; i < 10; i  )
    occupied[i] = false;
  if(found(0)) {
    cout << "C: " << lst[2] << ",B: " << lst[1] << ",A: " << lst[0] << endl;
    cout << lst[2] << lst[2] << lst[2] << "   "
     << lst[1] << lst[1] << lst[1] << "   "
     << lst[0] << lst[0] << lst[0] << " = "
     << lst[2] << lst[0] << lst[0] << lst[1] << endl; }
  else {
    cout << "No solution is found" << endl; }
  return 0; }

and it delivers the expected result:

C: 1,B: 8,A: 9
111   888   999 = 1998

CodePudding user response：

You seem to be able to solve the problem using another language, so I won't spend too long talking about the problem/algorithm used (you already know how to do it). However, as it seems that you are learning Common Lisp, I am going to provide a typical StackOverflow answer, and give a lot of advice that you haven't asked for !

• Fix your parentheses/indentation, this will make the code clearer for you.
• Split your code in more, smaller functions. You are solving a problem using a recursive function, with several parameters, and the function is more than twenty lines long. This makes it really hard to read and to debug.
• Use built-in functions: (some (lambda (x) (= x j)) occupied) == (member j occupied :test #'=), and in that case, it still works without specifying the test (this is technically wrong, the two functions do not return the same thing, but you only ever use the result as a boolean so this is effectively the same thing here).
• (mapcar (lambda (x y) (* x y)) ...) is just a longer way to write (mapcar #'* ...)
• 'nil == nil, you don't need to quote it. It is also (arguably) good style to use () instead of nil to represent the empty list (as opposed to a boolean value), but this really is a minor point.

As far as the algorithm is concerned, I will gladly help if you rewrite it using smaller functions. At the moment, it really is unnecessarily hard to read and understand.

CodePudding user response：

I think that the code should look more like the following code. The code is divided into small function which means that I can test pieces in the REPL, and the code can be reformulated if required (to make it more recursive, or whatever is required).

; Converts a list of numbers to a numbers
; So, (list-to-num '(1 2 3)) is 123

(defun list-to-num-iter (lst n)
  (if (null lst)
      n
      (list-to-num-iter (cdr lst)
                   (  (* n 10) (* (car lst))))))

(defun list-to-num (lst)
  (list-to-num-iter lst 0))

; A predicate to test if we have got a solution

(defun adds-up-p (a b c)
  (let ((a-lst (list a a a))
        (b-lst (list b b b))
        (c-lst (list c c c))
        (end-lst (list c a a b)))
    (= (list-to-num end-lst)
       (  (list-to-num a-lst)
          (list-to-num b-lst)
          (list-to-num c-lst)))))

; The entry point is digits-problem
; Run it as (digits-problem)
; It prints the result as 'a b c'

(defun digits-problem ()
  (dotimes (a 10)
    (dotimes (b 10)
      (dotimes (c 10)
        (if (adds-up-p a b c)
            (format t "~d ~d ~d ~%" a b c))))))