Commit | Line | Data |
---|---|---|
7f918cf1 CE |
1 | (* |
2 | * Written by sweeks@sweeks.com on 1999-08-31. | |
3 | * | |
4 | * A solution to mpuz. (Try M-x mpuz in emacs.) | |
5 | * This solution is very loosely based on an OCAML solution posted to | |
6 | * comp.lang.ml by Laurent Vaucher <blo.b@infonie.fr>. | |
7 | *) | |
8 | ||
9 | (* override print so the benchmark is silent *) | |
10 | fun print _ = () | |
11 | ||
12 | structure List = | |
13 | struct | |
14 | open List | |
15 | ||
16 | fun exists(l, p) = List.exists p l | |
17 | ||
18 | fun map(l, f) = List.map f l | |
19 | ||
20 | fun fold(l, b, f) = | |
21 | let | |
22 | fun loop(l, b) = | |
23 | case l of | |
24 | [] => b | |
25 | | x :: l => loop(l, f(x, b)) | |
26 | in loop(l, b) | |
27 | end | |
28 | ||
29 | fun foreach(l, f) = fold(l, (), fn (x, ()) => f x) | |
30 | end | |
31 | ||
32 | structure String = | |
33 | struct | |
34 | open String | |
35 | ||
36 | fun fold(s, b, f) = | |
37 | let | |
38 | val n = size s | |
39 | fun loop(i, b) = | |
40 | if i = n | |
41 | then b | |
42 | else loop(i + 1, f(String.sub(s, i), b)) | |
43 | in loop(0, b) | |
44 | end | |
45 | end | |
46 | ||
47 | structure Mpuz = | |
48 | struct | |
49 | fun solve(a, b, c, d, e) = | |
50 | let | |
51 | fun printNewline() = print "\n" | |
52 | val sub = Array.sub | |
53 | val update = Array.update | |
54 | ||
55 | val letters = | |
56 | List.fold | |
57 | ([a, b, c, d, e], [], fn (s, letters) => | |
58 | String.fold | |
59 | (s, letters, fn (c, letters) => | |
60 | if List.exists(letters, fn c' => c = c') | |
61 | then letters | |
62 | else c :: letters)) | |
63 | ||
64 | val letterValues = | |
65 | Array.array(Char.ord Char.maxChar + 1, 0) | |
66 | ||
67 | fun letterValue(c) = | |
68 | Array.sub(letterValues, ord c) | |
69 | ||
70 | fun setLetterValue(c, v) = | |
71 | Array.update(letterValues, ord c, v) | |
72 | ||
73 | fun stringValue(s) = | |
74 | String.fold(s, 0, fn (c, v) => v * 10 + letterValue c) | |
75 | ||
76 | fun printResult() = | |
77 | (List.foreach | |
78 | (letters, fn c => | |
79 | print(concat[String.str(c), " = ", | |
80 | Int.toString(letterValue(c)), " "])) | |
81 | ; print "\n") | |
82 | ||
83 | fun testOk() = | |
84 | let | |
85 | val b0 = letterValue(String.sub(b, 1)) | |
86 | val b1 = letterValue(String.sub(b, 0)) | |
87 | val a = stringValue a | |
88 | val b = stringValue b | |
89 | val c = stringValue c | |
90 | val d = stringValue d | |
91 | val e = stringValue e | |
92 | in if a * b0 = c | |
93 | andalso a * b1 = d | |
94 | andalso a * b = e | |
95 | andalso c + d * 10 = e | |
96 | then printResult() | |
97 | else () | |
98 | end | |
99 | ||
100 | val values = List.map([0, 1, 2, 3, 4, 5, 6, 7, 8, 9], fn v => | |
101 | (v, ref false)) | |
102 | ||
103 | (* Try all assignments of values to letters. *) | |
104 | fun loop(letters) = | |
105 | case letters of | |
106 | [] => testOk() | |
107 | | c :: letters => | |
108 | List.foreach | |
109 | (values, fn (v, r) => | |
110 | if !r | |
111 | then () | |
112 | else (r := true | |
113 | ; setLetterValue(c, v) | |
114 | ; loop(letters) | |
115 | ; r := false)) | |
116 | ||
117 | in loop(letters) | |
118 | end | |
119 | end | |
120 | ||
121 | structure Main = | |
122 | struct | |
123 | fun doit() = | |
124 | Mpuz.solve("AGH", "FB", "CBEE", "GHFD", "FGIJE") | |
125 | (* | |
126 | * Solution: | |
127 | * J = 0 I = 1 D = 8 E = 2 C = 5 B = 6 F = 4 H = 7 G = 3 A = 9 | |
128 | *) | |
129 | ||
130 | val doit = | |
131 | fn size => | |
132 | let | |
133 | fun loop n = | |
134 | if n = 0 | |
135 | then () | |
136 | else (doit(); | |
137 | loop(n-1)) | |
138 | in | |
139 | loop size | |
140 | end | |
141 | end |