在 core.logic Clojure (CLP) Cryptoarithmetic 中使用 apply

Question

(ns verbal-arithmetic
  (:require
    [clojure.core.logic :refer [all run* everyg lvar == membero fresh conde succeed fail conso resto]]
    [clojure.core.logic.fd :as fd]))

(comment
  "Solving cryptarithmetic puzzle"
  " SEND
  + MORE
  ______
   MONEY")


(defn send-more-money-solutions []
  (run* [s e n d m o r y]
        (fd/in s e n d m o r y (fd/interval 0 9))
        (fd/!= s 0)
        (fd/!= m 0)
        (fd/distinct [s e n d m o r y])
        (fd/eq (= (apply + [(* 1000 s) (* 100 e) (* 10 n) d
                            (* 1000 m) (* 100 o) (* 10 r) e])
                  (apply + [(* 10000 m) (* 1000 o) (* 100 n) (* 10 e) y])))))

上面的例子不起作用，因为 apply 在 fd/eq 中不能正常工作。 send-more-money-solutions 的以下版本有效，因为我不使用 apply。我需要使用 apply 来概括解决方案以处理具有不同长度的任意字符串。

(defn send-more-money-solutions []
  (run* [s e n d m o r y]
        (fd/in s e n d m o r y (fd/interval 0 9))
        (fd/!= s 0)
        (fd/!= m 0)
        (fd/distinct [s e n d m o r y])
        (fd/eq (= (+ (* 1000 s) (* 100 e) (* 10 n) d
                     (* 1000 m) (* 100 o) (* 10 r) e)
                  (+ (* 10000 m) (* 1000 o) (* 100 n) (* 10 e) y)))))

我该怎么办？（对于上面，我有一个想法，我可以写一个宏（虽然还不确定如何）但实际上我需要能够使用变量，这是一系列逻辑变量。如下所示）

(fd/eq (= (+ (apply + lvars1) (apply + lvars2))
          (apply + lvars3)))

错误信息看起来像

java.lang.IllegalArgumentException: Can't call nil, form: (nil + [(* 1000 s) (* 100 e) (* 10 n) d (* 1000 m) (* 100 o) (* 10 r) e] G__1124704)

我认为 fd/eq 宏中发生了一些奇怪的事情，所以我应该尝试不使用 eq 宏。

提前谢谢大家！

Answer 1

I need to be able to use a variables that is a sequence of logic variables

确切地说，这个问题的一般解决方案是引入任意动态数量的逻辑变量和relate/constrain它们。

求解器

首先定义一些递归目标来处理逻辑变量序列。（幸运的是 previous problems 我已经有了这些！）

将一系列逻辑变量的总和与另一个逻辑变量相关联：

(defn sumo [vars sum]
  (fresh [vhead vtail run-sum]
    (conde
      [(== vars ()) (== sum 0)]
      [(conso vhead vtail vars)
       (fd/+ vhead run-sum sum)
       (sumo vtail run-sum)])))

将两个逻辑变量序列的乘积和关联到另一个逻辑变量：

(defn productsumo [vars dens sum]
  (fresh [vhead vtail dhead dtail product run-sum]
    (conde
      [(emptyo vars) (== sum 0)]
      [(conso vhead vtail vars)
       (conso dhead dtail dens)
       (fd/* vhead dhead product)
       (fd/+ product run-sum sum)
       (productsumo vtail dtail run-sum)])))

加上一点辅助函数来生成幅度乘数：

(defn magnitudes [n]
  (reverse (take n (iterate #(* 10 %) 1))))

然后将它们连在一起：

(defn cryptarithmetic [& words]
  (let [distinct-chars (distinct (apply concat words))
        char->lvar (zipmap distinct-chars (repeatedly (count distinct-chars) lvar))
        lvars (vals char->lvar)
        first-letter-lvars (distinct (map #(char->lvar (first %)) words))
        sum-lvars (repeatedly (count words) lvar)
        word-lvars (map #(map char->lvar %) words)]
    (run* [q]
      (everyg #(fd/in % (fd/interval 0 9)) lvars) ;; digits 0-9
      (everyg #(fd/!= % 0) first-letter-lvars) ;; no leading zeroes
      (fd/distinct lvars) ;; only distinct digits
      (everyg (fn [[sum l]] ;; calculate sums for each word
                (productsumo l (magnitudes (count l)) sum))
              (map vector sum-lvars word-lvars))
      (fresh [s]
        (sumo (butlast sum-lvars) s) ;; sum all input word sums
        (fd/== s (last sum-lvars)))  ;; input word sums must equal last word sum
      (== q char->lvar))))

您的示例中有些内容应该看起来很熟悉，但主要区别在于可以动态处理单词（及其字符）的数量。使用 lvar 为所有字符集以及每个单词的总和创建新的逻辑变量。然后逻辑变量是 constrained/related 使用 everyg 和上面的递归目标。

示例问题

该函数将return给定单词的所有解决方案，而"send more money"只有一种可能的解决方案：

(cryptarithmetic "send" "more" "money")
=> ({\s 9, \e 5, \n 6, \d 7, \m 1, \o 0, \r 8, \y 2})

另一个有四个词的例子是"cp is fun true"（参见Google Cryptarithmetic Puzzles），它有72种可能的解决方案：

(cryptarithmetic "cp" "is" "fun" "true")
=>
({\c 2, \e 4, \f 9, \i 7, \n 3, \p 5, \r 0, \s 6, \t 1, \u 8}
 {\c 2, \e 5, \f 9, \i 7, \n 3, \p 4, \r 0, \s 8, \t 1, \u 6}
 {\c 2, \e 6, \f 9, \i 7, \n 3, \p 5, \r 0, \s 8, \t 1, \u 4}
 ...

这是我在 Wikipedia 上能找到的最大的一个，该函数在我的笔记本电脑上找到了大约 30 秒内的唯一解决方案：

(cryptarithmetic "SO" "MANY" "MORE" "MEN" "SEEM" "TO"
                 "SAY" "THAT" "THEY" "MAY" "SOON" "TRY"
                 "TO" "STAY" "AT" "HOME" "SO" "AS" "TO"
                 "SEE" "OR" "HEAR" "THE" "SAME" "ONE"
                 "MAN" "TRY" "TO" "MEET" "THE" "TEAM"
                 "ON" "THE" "MOON" "AS" "HE" "HAS"
                 "AT" "THE" "OTHER" "TEN" "TESTS")
=> ({\A 7, \E 0, \H 5, \M 2, \N 6, \O 1, \R 8, \S 3, \T 9, \Y 4})

这里有一个函数可以很好地打印结果：

(defn pprint-answer [char->digit words]
  (let [nums (map #(apply str (map char->digit %))
                  words)
        width (apply max (map count nums))
        width-format (str "%" width "s")
        pad #(format width-format %)]
    (println
     (clojure.string/join \newline
       (concat
        (map #(str "+ " (pad %)) (butlast nums))
        [(apply str (repeat (+ 2 width) \-))
         (str "= " (pad (last nums)))]))
     \newline)))

(cryptarithmetic "wrong" "wrong" "right")
(map #(pprint-answer % ["wrong" "wrong" "right"]) *1)
; + 12734
; + 12734
; -------
; = 25468

在 core.logic Clojure (CLP) Cryptoarithmetic 中使用 apply

Using apply in core.logic Clojure (CLP) Cryptoarithmetic

clojure

logic-programming

clojure-core.logic

clpfd

cryptarithmetic-puzzle

求解器

示例问题