找到密码算法的解决方案

Question

此代码旨在找到解决密码算法问题的所有可能的解决方案。对我试图解决的问题的描述如下：

在密码算法问题中，给出了一个将数字替换为表示数字的字符的问题。这样一个问题的解决方案是一组数字，当在问题中被替换时，给出一个真正的数值解释。示例: IT ___ OK是否有一个解决方案{i= 1；K= 1；O= 3；S= 5；T= 6}？我是__ __好吗？

我只能用蛮力解决这个问题，虽然我相信有更有效的方法。我也希望收到关于我的格式，命名，和真正的任何你认为可以改进的反馈。

(defun place-value-to-integer (the-list &OPTIONAL place-value) 
  (let ((place-value (if place-value place-value 1))) 
    (if (= (length the-list) 1) (* place-value (first the-list))
      (+ (* place-value (first (last the-list))) (place-value-to-integer (butlast the-list) (* 10 place-value))))))

(defun fill-from-formula (formula guess)
  (loop for digit in formula collect (gethash digit guess)))

(defun check-answer (augend-formula addend-formula sum-formula guess)
  (let ((augend (fill-from-formula augend-formula guess))
    (addend (fill-from-formula addend-formula guess))
    (sum (fill-from-formula sum-formula guess)))
        (= (place-value-to-integer sum) (+ (place-value-to-integer augend) (place-value-to-integer addend)))))

(defun brute-force-guess(augend-formula addend-formula sum-formula unique-values &OPTIONAL callback guess) 
  (let ((guess (if (null guess) (make-hash-table) guess)))
    (loop for digit in '(0 1 2 3 4 5 6 7 8 9) do 
      (setf (gethash (car unique-values) guess) digit) 
      (if (= (length unique-values) 1) 
        (if (check-answer augend-formula addend-formula sum-formula guess) (print-result augend-formula addend-formula sum-formula guess) nil)
        (brute-force-guess augend-formula addend-formula sum-formula (cdr unique-values) callback guess)))))

(defun print-result (augend-formula addend-formula sum-formula guess) 
  (format t "One answer is ~a + ~a = ~a ~%" 
      (fill-from-formula augend-formula guess)
      (fill-from-formula addend-formula guess)
      (fill-from-formula sum-formula guess)))

(defun find-unique-values (the-list) 
  (let ((unique-items ())) 
    (loop for sublist in the-list do 
      (loop for item in sublist do
          (unless (member item unique-items) (setf unique-items (append (list item) unique-items))))) unique-items))

(let ((problemA (list (list 'I 'S) (list 'I 'T) (list 'O 'K)))
      (problemB (list (list 'I) (list 'A 'M) (list 'O 'K))))
    (brute-force-guess (first problemA) (second problemA) (third problemA) (find-unique-values problemA) #'print-result)
    (brute-force-guess (first problemB) (second problemB) (third problemB) (find-unique-values problemB) #'print-result))

Answer 1

目前的一些初步说明(稍后我将补充)：

每当您需要编写(if n n 2)或(if (not n) 2 n)时，都可以编写(or n 2)。or将接受任意数量的参数，并返回nil或计算为非nil的第一个参数。

使用可选参数时，可以为它们设置默认值。

(defun place-value-to-integer (the-list &OPTIONAL place-value) 
  (let ((place-value (if place-value place-value 1)))
  ...

可以写成

(defun place-value-to-integer (the-list &OPTIONAL (place-value 1)) 
  ...

我现在没有时间进入其他部分，但是您正在使用loop来setf一系列hash值，这告诉我您可能可以使用一种更实用的方法来简化它(这可能是例外之一，但乍一看不像是一个例外)。

编辑：

(if a b nil)等同于(when a b) (使用第二个而不是第一个)是很好的风格。

EDIT2:好的，哇，嘿。那是我生命中的两个小时，我再也回不来了。我写下并编辑了一篇关于我的过程的相当长的文章(如果你关心的话，那就是这里)。这是我如何解决这个问题的蛮力方法。

EDIT3:稍微简化。

(defpackage :cry-fun (:use :cl :cl-ppcre))
(in-package :cry-fun)

(defun digits->number! (&rest digits)
  (apply #'+ (loop for d in (nreverse digits) for i from 0
                   collect (* d (expt 10 i)))))

(defun number->digits (num &optional (pad-to 5))
  (let ((temp num)
        (digits nil))
     (loop do (multiple-value-call 
                   (lambda (rest d) (setf temp rest digits (cons d digits)))
                (floor temp 10))
           until (= pad-to (length digits)))
     digits))

(defun string->terms (problem-string)
  (reverse
   (mapcar (lambda (s) (mapcar (lambda (i) (intern (format nil "~a" i))) 
                   (coerce s 'list)))
           (split " " (string-downcase problem-string)))))

(defmacro solve-for (problem-string)
  (let* ((arg-count (length (remove-duplicates (regex-replace-all " " problem-string ""))))
         (nines (apply #'digits->number! (make-list arg-count :initial-element 9))))
    `(loop for i from 0 to ,nines
           when (apply (solution-fn ,problem-string) (number->digits i ,arg-count))
           collect it)))

(defmacro solution-fn (problem-string)
  (let* ((terms (string->terms problem-string))
         (args (remove-duplicates (apply #'append terms))))
    `(lambda ,args
       (when (= (+ ,@(loop for term in (cdr terms) collect `(digits->number! ,@term)))
                (digits->number! ,@(car terms)))
             (list ,@(mapcan (lambda (i) (list (symbol-name i) i)) args))))))

编辑:添加注释以显示“解决方案-fn”的中间值示例

(defmacro solution-fn (problem-string)
  (let* ((terms (string->terms problem-string)) 
     ;example: (terms ((o k) (i t) (i s)))
         (args (remove-duplicates (apply #'append terms)))) 
         ;example: (args (o k t i s))
    `(lambda ,args
       (when (= (+ ,@(loop for term in (cdr terms) collect `(digits->number! ,@term)))  
                (digits->number! ,@(car terms)))
        ;example: (when (= (+ (i t) (i s)) (o k)
             (list ,@(mapcan (lambda (i) (list (symbol-name i) i)) args))))))
        ;example: (list "o" o "k" k "t" t "i" i "s" s)