Haskell で 覆面算


Haskell で 覆面算 をやってみた。

DEBT + STAR = DEATH が与えられたとき、等式が成立するには
D = 1, E = 0, B = 8, T = 5, S = 9, A = 6, R = 7, H = 2
とならなければならない、という問題を解くものである。
先日とある脱出ゲームで出題されたが手計算ではまったく解けなかった。

ソースコードはこちら。
https://github.com/mitsuji/verbal-arithmetic

1. 特殊解

まずは、特殊ケースとして "DEBT + STAR = DEATH" だけを解くことを考える。
リストの要素を指定された数だけ使用した全ての順列に評価される関数
permutation を 作ると、下記のように総当りで解くことができる。

単語の先頭の数字はゼロにならないので、D != 0 と S != 0 を条件に追加している。

また、繰り上がりを考えると等式を見ただけで D = 1 が明らかなので、
これを条件に加えると、試行回数が激減して実行時間を短縮できる。

2. 一般化

ここからが本番だ。

脱出ゲームに勝つためには、わざわざ関数を書かなくても、
例えば下記のように記述したら解答を表示してくれるライブラリが必要だ。

また、このような関数をあらかじめコンパイルしておけば、

このように、コマンドにパラメータを渡すだけで解答を得ることができるだろう。

3. 式のデータ

まずは、入力となる数式(文字式?)を表現するためのデータ型を考えてみる。
今回は式(VExp)と等式(VEqu)を別の型として定義してみた。

このデータ型を使用すると、
式 DEBT + STAR = DEATH は下記のようなデータになる。
ポーランド記法とかいうやつだ。

関数を演算子として使えば、下記のように書くこともできる。

ここで、下記の関数を定義してみると、

下記のような記述が可能になる。だいぶ見やすくなってきた。

そして、VExp を IsString 型クラスのインスタンスにして、

ソースコードの先頭に {-# LANGUAGE OverloadedStrings #-} を書くと
下記のような記述が可能になる。
これは、コード上に文字列リテラルがあり、VExp型に推論されるときは
VExp の fromString を使って、VExp型のデータを作りなさいという意味である。
コード上で式を扱うには、まずはこれで充分だろう。

4. 一般解

特殊解の関数を参考にして作成した関数が下記である。
chars 関数で式内のユニークな文字を抽出し、総当りの場合の数を決めている。
また、firstChars 関数で式内の単語の先頭の文字を抽出し、!= 0 条件を追加している。

match 関数に渡された数字を元に実際に計算を行う関数は下記のようになった。
listToInt 関数は、数字のリストを10進数で数値に変換する関数である。

5. パーサー

ここまでで計算自体はできるようになったが、コマンドラインに式を渡せるようにするには、
式全体を文字列として受け取って、式のデータに変換するパーサーを書く必要がある。

こんな感じのパーサーになった。スペースの扱いで1日くらいハマった。

最後に VEqu を IsString のインスタンスにして
式全体を文字列として記述し、直接式のデータとして扱えるようにした。

6. まとめ・感想

  • 実行形式バイナリにコンパイルすればHaskellでもそこそこ速かった。
  • IsString 型クラスを使うと、いろんな型のデータを文字列リテラルから作れる。
  • パーサーを書くときはスペースの処理が重複しないように注意しないとハマる。
  • 式の表現は完璧なので、計算のアルゴリズムを改善してみたい。非総当りとか。
  • 引き続き、掛け算と引き算くらいまでは対応してみたい。