source: project/release/4/amb/trunk/amb-money.scm @ 13801

Last change on this file since 13801 was 13801, checked in by Kon Lovett, 12 years ago

Save.

File size: 2.3 KB
Line 
1;;;; amb-money.scm
2
3(require-extension amb srfi-1)
4
5;; Assign different numerals to different symbols
6;;    '(s e n d m o r y)
7;; so the following is true:
8;;
9;; s e n d + m o r e = m o n e y
10;;
11;; Symbols s and m are not zero.
12;;
13;; The code below significantly prunes the solution space,
14;; so the result is found in few thousands trials, rather than
15;; in tens of millions of trials when no pruning is applied:
16;; (* 2 2 2 10 10 10 10 10 10 9 1) = 72,000,000
17;;
18;; The pruning is based on the following ideas:
19;; 1. The order of assignments is important, so the variables are
20;;    ordered in some specific way within the 'let* clause,
21;;    rather than the 'let one.
22;; 2. Later variables use the info from the previous ones to reduce their
23;;    domains. This is a constraint propagation mechanism for this puzzle.
24;; 3. Some assignments are deterministic, which significantly reduces the
25;;    original domain space of a variable from 10 (or 9) to 1 (or to 2 if we
26;;    take into account the effect of 'modulo application)
27;;
28;; Example:
29;; (money) ==>
30;; ((4385 trials)
31;;  (s e n d + m o r e = m o n e y)
32;;  (9 5 6 7 + 1 0 8 5 = 1 0 6 5 2))
33
34(define (money)
35
36  (define (set-difference xs ys)
37    (filter (lambda(x) (not (member x ys))) xs))
38
39  (define (distinct? xs)
40    (cond ((null? xs) #t)
41          ((member (car xs) (cdr xs)) #f)
42          (else (distinct? (cdr xs)))))
43
44  (define trial 0)
45
46  (let* ((p1 (amb 0 1))
47         (p2 (amb 0 1))
48         (p3 (amb 0 1))
49
50         (d (amb/random '(0 1 2 3 4 5 6 7 8 9)))
51         (e (amb/random (set-difference '(0 1 2 3 4 5 6 7 8 9) (list d))))
52         (y (modulo (+ d e (* -10 p1)) 10))
53         (n (amb/random (set-difference '(0 1 2 3 4 5 6 7 8 9) (list d e y))))
54         (r (modulo (+ (* 10 p2) e (- p1) (- n)) 10))
55         (o (modulo (+ (* 10 p3) n (- p2) (- e)) 10))
56
57         (m 1)
58         (s (modulo (+ (* 9 m) o (- p3)) 10) ) )
59
60    (set! trial (+ trial 1))
61
62    (assert (distinct? (list s e n d m o r y)))
63    (assert (= (+ d e)    (+ (* 10 p1) y)))
64    (assert (= (+ p1 n r) (+ (* 10 p2) e)))
65    (assert (= (+ p2 e o) (+ (* 10 p3) n)))
66    (assert (= (+ p3 s m) (+ (* 10 m)  o)))
67
68    ;; Result, including a number of recorded trials
69    `((,trial trials)
70      (s e n d + m o r e = m o n e y)
71      (,s ,e ,n ,d '+ ,m ,o ,r ,e '= ,m ,o ,n ,e ,y)) ) )
Note: See TracBrowser for help on using the repository browser.