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

问题描述 投票:3回答:1
(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])))))

上面的例子不起作用,因为applyfd/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宏。

谢谢大家!

clojure clpfd logic-programming clojure-core.logic cryptarithmetic-puzzle
1个回答
4
投票

我需要能够使用一系列逻辑变量的变量

确切地说,这个问题的一般解决方案是引入任意的,动态数量的逻辑变量并关联/约束它们。

Solver

首先定义一些递归目标以处理逻辑变量序列。 (幸运的是我已经为previous problems提供了这些!)

  1. 将逻辑变量序列的总和与另一个逻辑变量相关联: (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)])))
  2. 将两个逻辑变量序列的乘积之和与另一个逻辑变量相关联: (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为所有字符集创建新的逻辑变量,以及每个单词的总和。然后使用everyg和上面的递归目标来约束/关联逻辑变量。

Sample Problems

该函数将返回给定单词的所有解决方案,“发送更多钱”只有一个可能的解决方案:

(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,该功能在我的笔记本电脑上找到了〜30s的唯一解决方案:

(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 
© www.soinside.com 2019 - 2024. All rights reserved.