Gauche: SEND + MORE = MONEY を解くコードを読み解く

Wiliki のScheme:数遊びのページに覆面算を解くプログラムが紹介されています。

以下は、上のリンク先に掲載されている SEND + MORE = MONEY を解くプログラムです。

(use util.combinations)
(use util.match)

(define (solve)
  (let/cc return
    (combinations-for-each
     (cut permutations-for-each
          (match-lambda ((S E N D M O R Y)
                         (and (not (eqv? S #\0)) (not (eqv? M #\0))
                              (let ((SEND  (x->integer (string S E N D)))
                                    (MORE  (x->integer (string M O R E)))
                                    (MONEY (x->integer (string M O N E Y))))
                                (when (= (+ SEND MORE) MONEY)
                                  (return SEND MORE MONEY))))))
          <>)
     (string->list "0123456789") 8)))

本記事では、上の solve 関数で使われている関数およびマクロについて解説していきながら、いかに解を探索し求めているかをみていきます。

let/cc マクロ

let/cc マクロは以下のように展開されます。

(call/cc (lambda (var) body ...))

つまり、let/cc は call/cc を短く書けるようにするためのマクロです。
上のコードでは、解が見つかった時点で関数から脱出する用途として let/cc が使われています。

;; let/cc のお試しサンプル
(define (f)
  (let/cc return
    (dolist (e (iota 10))
      (if (= e 4) 
          (return 'found) ; 4 を見つけたで関数から脱臭
          (print e)))))

実行結果です。

gosh> (f)
0
1
2
3
found

string->list 関数

string->list 関数は、文字列を文字のリストに変換します。

gosh> (string->list "0123456789")
(#\0 #\1 #\2 #\3 #\4 #\5 #\6 #\7 #\8 #\9)

combinations-for-each 関数

combinations-for-each 関数は、それぞれの組み合わせについて、引数で渡された関数を呼び出します。
(use util.combinations) が必要です。

gosh> (use util.combinations)
gosh> (combinations-for-each print '(1 2 3) 2) ; リストから 2 つを選ぶ組み合わせ
(1 2)
(1 3)
(2 3)
#<undef

0 から 9 までの数値のうち、どれを各文字に束縛するかをここで選んでいます。

cut マクロ

cut は部分適用を実現するためのマクロです。
cut は lambda 式に展開されます。macroexpand を使うとマクロが展開されたコードが確認できます。

gosh> (macroexpand '(cut - <> 4))
(lambda (#:G99) (- #:G99 4))

<> の部分が引数として渡されるのが確認できます。

cut の実行結果です。

gosh> ((cut - <> 4) 10)
6
gosh> ((cut - 4 <>) 10)
-6

上の solve 関数で cut を使っているのは、lambda 式より短く書けるからだと推測しています。また、lambda 式nの場合は、引数に名前を付ける手間がありますが、cut だとその手間がありません。

permutations-for-each 関数

permutations-for-each 関数は、個々の順列に対して、引数で渡された関数を呼び出します。

gosh> (use util.combinations)
gosh> (permutations-for-each print '(1 2 3))
(1 2 3)
(1 3 2)
(2 1 3)
(2 3 1)
(3 1 2)
(3 2 1)
#<undef>

combinations-for-each で、どの数値が使われるかを決めて、
permutations-for-each で、どの文字にどの数値を束縛するかを決めるのですね。

match-lambda マクロ

match-lambda マクロは、関数を返します。ドキュメントによると以下の式と同等となります。

(lambda (expr) (match expr clause ...))

上の solve 関数では、permutations-for-each から渡される順列に対して、
パターンマッチを通じて各文字に数値を束縛しています。

gosh> (match-lambda ((A B) (+ A B)))
#<closure (#f #:G31)>
gosh> ((match-lambda ((A B) (+ A B))) '(10 20)) ; A=10, B=20 に束縛される
30

それから、最上位の文字(SとM)がゼロでないことを確かめて、
文字から数値へ変換を行ってから計算が正しいかをチェックしています。

gosh> (string #\2 #\5)
"25"
gosh> (x->integer (string #\2 #\5))
25

以上が solve 関数が覆面算を解く仕組みの解説となります。

ちなみにプログラムを実行してみると、以下の答えが出力されました。

SEND + MORE = MONEY
9567   1085   10652