0

“寻找数字问题”是这样的：

Find unique decimal digits A, B, C such that

     CCC
  +  BBB
  +  AAA
  = CAAB

为了在 Common Lisp 中使用递归来解决它，我编写了以下代码：

(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))))))

传递的结果 ( lst) 是(9 9 9)

预期结果 ( lst) 是(9 8 1)意义A=9, B=8，C=1因此等式CCC + BBB + AAA = CAAB成立，即

      111     ;  CCC
   +  888     ;  BBB
   +  999     ;  AAA
   = 1998     ; CAAB

我应该更改代码的哪些部分以提供预期的结果？有人可以修复代码吗？请注意，必须使用递归。只有一行递归就足够了，例如;; recursion happens here注释所在的行。

修复此代码的最小编辑是什么？

4

3 回答 3

3

使您的代码工作所需的最小编辑是以下三个小更改（;;;; NB在注释中标记）：

  1. 您不能像您一样通过手术修改引用列表的结构。为此，它必须重新分配。
(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 
          ) )
  1. 您必须更改代码的结构（将一个右括号向上移动一行）以始终撤消pushof jinto 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))))))
  1. 一旦找到结果，您还必须实际返回结果（也可以在上面的代码段中看到）。

如果您更改return-from行以打印结果而不是返回结果，您将打印所有结果。

如果您想将它们全部放在一个列表中而不是打印出来，您可以通过外科手术将每个结果附加到某个外部范围中定义的某个列表（或者cons如果您愿意，可以在所有完成后将其反转到前面）。

或者通常，您可以更改此代码以接受回调并在找到每个结果时调用它，并让此回调对它执行任何操作 - 打印它，将其附加到外部列表，等等。

备注：您的代码遵循一般的方法，通过递归创建三个嵌套循环结构。lst实际结果是在递归的最深层次上计算的——并通过手术操作输入，对应于jfrom 1to的最内层循环9（同时避免重复）。

这里有很多无关紧要的代码。例如，ifin(if (found? ...) lst)根本不需要，只需替换为(found? ...). 我也更喜欢不同的名字——occupied应该是真的被命名used，lst应该是res（对于“结果”），index被规范地命名为just i，widthis just n，等等（命名很重要）......但你确实要求最小的改变。

此代码逐渐计算结果lst，作为进入嵌套循环最内层的副作用，最终完全设置。

因此，此代码遵循例如 Peter Norvig 的 PAIP Prolog 解释器的示例，它遵循相同的范例。在伪代码中：

  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

这是您的代码重新构造、重命名和简化：

(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)))

现在，这与您曾经在问题中使用的 C++ 代码非常相似，其中工作函数（此处为f）也仅收到一个参数，指示嵌套循环的深度级别 - 对应于所尝试数字的索引，- - 其余变量在外部范围内（那里是全局的；这里是包含函数中的辅助变量find2）。

顺便说一句，0由于某种原因，您没有尝试任何 s 。

于 2022-02-04T17:58:18.527 回答
1

您似乎可以使用另一种语言解决问题，所以我不会花太长时间谈论使用的问题/算法（您已经知道该怎么做）。但是，由于您似乎正在学习 Common Lisp，我将提供一个典型的 StackOverflow 答案，并提供很多您没有要求的建议！

  • 修正你的括号/缩进，这将使你的代码更清晰。
  • 将您的代码拆分为更多、更小的函数。您正在使用具有多个参数的递归函数解决问题，该函数有 20 多行长。这使得阅读和调试变得非常困难。
  • 使用内置函数: (some (lambda (x) (= x j)) occupied) == (member j occupied :test #'=)，在这种情况下，它仍然可以在不指定测试的情况下工作（这在技术上是错误的，这两个函数不会返回相同的东西，但你只能将结果用作布尔值，所以这实际上是同样的事情在这里）。
  • (mapcar (lambda (x y) (* x y)) ...)只是更长的写作方式(mapcar #'* ...)
  • 'nil == nil，你不需要引用它。()使用它来代替表示空列表（而不是布尔值）也是（可以说）很好的风格nil，但这确实是一个小问题。

就算法而言，如果您使用较小的函数重写它，我将很乐意提供帮助。目前，它真的很难阅读和理解。

编辑：我仍然尝试花时间重写代码并提出更清洁的解决方案。TL;DR：这是最终结果，对您的代码进行了“最小”的修改：

(defun find! ()
  (found? 0 (list 1 2 3) () 3))

(defun compute-lefthand (list)
  (* 111 (reduce #'+ list)))

(defun compute-righthand (list)
  (reduce #'+ (mapcar #'*
                      '(1000 100 10 1)
                      (list (third list)
                            (first list)
                            (first list)
                            (second list)))))

(defun check-solution (list)
  (when (= (compute-lefthand list)
           (compute-righthand list))
    list))

(defun try-solution (j index list occupied width)
  (unless (member j occupied)
    (setf (nth index list) j)
    (found? (1+ index)
            list
            (cons j occupied)
            width)))

(defun found? (index lst occupied width)
  (if (= index width)
      (check-solution lst)
      (dotimes (j 10)
        (when (try-solution j index lst occupied width)
          (return lst)))))

除了我最初的回答中已经提到的样式问题之外，您的初始代码具有不稳定的控制流。很难确定每个递归调用真正返回了什么，因为您没有更小的函数，因此不清楚每个部分的目标是什么，信息如何从递归调用传输到父级，这修改的对象等等。现在，我的代码不是最干净的，我可能不会使用这种策略来解决问题，但我尝试尽可能接近您的初始代码。主要区别：

  • 我把事情分成更小的功能。这使一切变得更清晰，最重要的是，更容易测试。每个函数都会返回一些清晰的东西。例如，check-solution如果它代表一个正确的解决方案，则返回列表，nil否则；when我使用 a而不是if控制结构这一事实清楚地表明了这一点。
  • 我替换do为dotimeswhich 也更清晰；现在可以立即看到正在变化的变量以及它在每一步中的变化方式。
  • 我不使用宏的&optional return参数do/dotimes，而是使用显式的return. 然后可以清楚地确定返回什么以及何时返回。
  • 我不用push/pop来修改我的清单。您正在使用递归策略，因此您的“修改”应采用传递给函数的不同参数的形式。通过准确了解每个函数对每个参数的作用，它再次使对程序的推理变得更容易。一个更好的解决方案也是删除对的调用setf，而是将(cons <smtg> lst)其用作递归调用的参数，但这很好。

初始程序中的错误可能是由于您的函数没有返回您的想法，因为您有几个连续的表达式，每个表达式在不同的情况下调用，它们的返回值本身是错误的，因为它们的顺序不正确并且使用do的可选返回值修改对象并在错误的时间返回它们。

TL;DR：把事情分开；让每个功能做一件事情。

于 2022-01-31T16:14:57.460 回答
1

你的代码

(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))))))

缩进和注释样式：行尾注释使用单个分号，对齐非正文参数，正文缩进两个空格

(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))))))

使用更有说服力的谓词：find 或 member。不要将 * 包装在 lambda 中，不做其他任何事情。（我将把 find 放在一边！以后。）

(defun found? (index lst occupied width)
  (if (< index (1- width))
      (do ((j 1 (1+ j)))
          ((> j 9) lst)
        (unless (find j occupied :test #'=)
          (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 (find j occupied :test #'=)
          (setf (nth index lst) j)
          (let ((lefthnd (* 111 (reduce #'+ lst)))
                (rghthnd (reduce #'+
                                 (mapcar #'*
                                         '(1000 100 10 1)
                                         (list (third lst)
                                               (first lst)
                                               (first lst)
                                               (second lst))))))
            (if (= lefthnd rghthnd)
                lst
                'nil))))))

a 的主体do不返回任何内容。有很多死代码，我们现在删除：

(defun found? (index lst occupied width)
  (if (< index (1- width))
      (do ((j 1 (1+ j)))
          ((> j 9) lst)
        (unless (find j occupied :test #'=)
          (setf (nth index lst) j)
          (push j occupied)
          (unless (found? (1+ index) lst occupied width) ; recursion
            (setf occupied (remove j occupied)))))
      (do ((j 1 (1+ j)))
          ((> j 9) lst)
        (unless (find j occupied :test #'=)
          (setf (nth index lst) j)))))

我们可以有条件地推送，而不是推送然后有条件地移除：

(defun found? (index lst occupied width)
  (if (< index (1- width))
      (do ((j 1 (1+ j)))
          ((> j 9) lst)
        (unless (find j occupied :test #'=)
          (setf (nth index lst) j)
          (when (found? (1+ index) lst occupied width) ; recursion
            (push j occupied))))
      (do ((j 1 (1+ j)))
          ((> j 9) lst)
        (unless (find j occupied :test #'=)
          (setf (nth index lst) j)))))

虽然它在性能上有所不同，但将外部条件放入内部主体使其在此处更具可读性：

(defun found? (index lst occupied width)
  (do ((j 1 (1+ j)))
      ((> j 9) lst)
    (unless (find j occupied :test #'=)
      (setf (nth index lst) j)
      (when (and (< index (1- width))
                 (found? (1+ index) lst occupied width)) ; recursion
        (push j occupied)))))

除了数到 9 几次之外，这没有任何作用，这似乎与您的发现一致。

我猜你想从死代码中返回一些东西。您可能想使用return-from它。

(defun found? (index lst occupied width)
  (if (< index (1- width))
      (do ((j 1 (1+ j)))
          ((> j 9) lst)
        (unless (find j occupied :test #'=)
          (setf (nth index lst) j)
          (push j occupied)
          (if (found? (1+ index) lst occupied width) ; recursion
              (return-from found? lst)
              (setf occupied (remove j occupied)))))
      (do ((j 1 (1+ j)))
          ((> j 9) lst)
        (unless (find j occupied :test #'=)
          (setf (nth index lst) j)
          (let ((lefthnd (* 111 (reduce #'+ lst)))
                (rghthnd (reduce #'+
                                 (mapcar #'*
                                         '(1000 100 10 1)
                                         (list (third lst)
                                               (first lst)
                                               (first lst)
                                               (second lst))))))
            (when (= lefthnd rghthnd)
              (return-from found? lst)))))))

这返回 (1 2 9)，这是错误的。问题似乎是即使您运行超过 9，您也会返回列表，但是您想返回 nil，因为您没有找到任何东西。

(defun found? (index lst occupied width)
  (if (< index (1- width))
      (do ((j 1 (1+ j)))
          ((> j 9) nil)                 ; <- nothing found
        (unless (find j occupied :test #'=)
          (setf (nth index lst) j)
          (push j occupied)
          (if (found? (1+ index) lst occupied width) ; recursion
              (return-from found? lst)
              (setf occupied (remove j occupied)))))
      (do ((j 1 (1+ j)))
          ((> j 9) nil)                 ; <- nothing found
        (unless (find j occupied :test #'=)
          (setf (nth index lst) j)
          (let ((lefthnd (* 111 (reduce #'+ lst)))
                (rghthnd (reduce #'+
                                 (mapcar #'*
                                         '(1000 100 10 1)
                                         (list (third lst)
                                               (first lst)
                                               (first lst)
                                               (second lst))))))
            (when (= lefthnd rghthnd)
              (return-from found? lst)))))))

这将返回 (9 8 1)，这是正确的。现在我似乎明白了你想要做什么，让我们再重构一下。无需从占用的列表中推送和删除，只需在前面暂时创建一个新元素的新列表：

(defun found? (index lst occupied width)
  (if (< index (1- width))
      (do ((j 1 (1+ j)))
          ((> j 9) nil)
        (unless (find j occupied :test #'=)
          (setf (nth index lst) j)
          (when (found? (1+ index)      ; recursion
                        lst
                        (cons j occupied)
                        width)
            (return-from found? lst))))
      (do ((j 1 (1+ j)))
          ((> j 9) nil)
        (unless (find j occupied :test #'=)
          (setf (nth index lst) j)
          (let ((lefthnd (* 111 (reduce #'+ lst)))
                (rghthnd (reduce #'+
                                 (mapcar #'*
                                         '(1000 100 10 1)
                                         (list (third lst)
                                               (first lst)
                                               (first lst)
                                               (second lst))))))
            (when (= lefthnd rghthnd)
              (return-from found? lst)))))))

我认为使用循环而不是 do 使这更具可读性：

(defun found? (index lst occupied width)
  (if (< index (1- width))
      (loop :for j :from 1 :to 9
            :unless (find j occupied :test #'=)
              :do (setf (nth index lst) j)
                  (when (found? (1+ index) ; recursion
                                lst
                                (cons j occupied)
                                width)
                    (return-from found? lst)))
      (loop :for j :from 1 :to 9
            :unless (find j occupied :test #'=)
              :do (setf (nth index lst) j)
                  (let ((lefthnd (* 111 (reduce #'+ lst)))
                        (rghthnd (reduce #'+
                                         (mapcar #'*
                                                 '(1000 100 10 1)
                                                 (list (third lst)
                                                       (first lst)
                                                       (first lst)
                                                       (second lst))))))
                    (when (= lefthnd rghthnd)
                      (return-from found? lst))))))

由于循环相当复杂，我只想写和读一次，所以把外部条件移到里面：

(defun found? (index lst occupied width)
  (loop :for j :from 1 :to 9
        :unless (find j occupied :test #'=)
          :do (setf (nth index lst) j)
              (if (< index (1- width))
                  (when (found? (1+ index)  ; recursion
                                lst
                                (cons j occupied)
                                width)
                    (return-from found? lst))
                  (let ((lefthnd (* 111 (reduce #'+ lst)))
                        (rghthnd (reduce #'+
                                         (mapcar #'*
                                                 '(1000 100 10 1)
                                                 (list (third lst)
                                                       (first lst)
                                                       (first lst)
                                                       (second lst))))))
                    (when (= lefthnd rghthnd)
                      (return-from found? lst))))))

你看到占用只是 lst 的前一个或两个元素，颠倒了吗？我们可以通过递归构建 lst，而不是设置列表元素。我们实际上需要为此返回递归结果，所以这是更好的引用透明性。

(defun find! ()
  (found? 0                             ; initially show the number 1
          '()                           ; initially no numbers found
          3))                           ; numbers list width is 3

(defun found? (index part width)
  (loop :for j :from 1 :to 9
        :unless (find j part :test #'=)
          :do (if (< index (1- width))
                  (let ((solution (found? (1+ index) ; recursion
                                          (cons j part)
                                          width)))
                    (when solution
                      (return-from found? solution)))
                  (let* ((full (cons j part))
                         (lefthnd (* 111 (reduce #'+ full)))
                         (rghthnd (reduce #'+
                                          (mapcar #'*
                                                  '(1000 100 10 1)
                                                  (list (third full)
                                                        (first full)
                                                        (first full)
                                                        (second full))))))
                    (when (= lefthnd rghthnd)
                      (return-from found? full))))))

索引和宽度现在只用于计数，所以我们只需要一个数字，我们可以向零计数。这也表明我们应该将基本情况移出循环：

(defun find! ()
  (found? '()                           ; initially no numbers found
          3))                           ; numbers list width is 3

(defun found? (part count)
  (if (zerop count)
      (let* ((full part)       ; just rename to show that the number is complete
             (lefthnd (* 111 (reduce #'+ full)))
             (rghthnd (reduce #'+
                              (mapcar #'*
                                      '(1000 100 10 1)
                                      (list (third full)
                                            (first full)
                                            (first full)
                                            (second full))))))
        (when (= lefthnd rghthnd)
          (return-from found? full)))
      (loop :for j :from 1 :to 9
            :unless (find j part :test #'=)
              :do (let ((solution (found? (cons j part)
                                          (1- count))))
                    (when solution
                      (return-from found? solution))))))

我认为这或多或少是你可以做的，如果你把它保持在一个单一的功能。现在您可能希望将排列的生成与实际代码分开。例如，在广泛使用的库中有一些函数可以处理此类事情alexandria。

于 2022-02-01T10:21:31.813 回答