リストモナドを使ってみる
このエントリはScala Advent Calendar jp 2010 : ATNDの25日のものです。
メリークリスマス! クリスマスは楽しくみんなでパズルを解いて遊びましょう。
パズルみたいな探索問題をScalaで解く場合は、リストモナドを使うとキレイに書けます。
例: SEND+MORE=MONEY
例として覆面算を解いてみましょう。
各アルファベットに異なる数字が割り当てれる。その数字は何か?
ただし最上位桁が0ではない。
普通にforループを使って解くと、ネストの深さが酷いことになります:)。
// int(1,2,3)を123にする関数 def int(xs : Int*) : Int = xs.foldLeft(0)( _ * 10 + _) // SEND+MORE=MONEYの答えを探索する def solve : (Int,Int,Int) = { for( s <- 0 to 9) for( e <- 0 to 9) for( n <- 0 to 9) ................ for( y <- 0 to 9) if(s != 0 && m != 0 && int(s,e,n,d) + int(m,o,r,e) == int(m,o,n,e,y)) return (int(s, e, n, d) , int(m, o, r, e) , int(m, o, n, e, y)) }
これをリストモナドを使って書くと次のようになります。あいかわらずforを使ってるように見えるかもしれませんが、それは幻想です:)。
def solve : Seq[(Int, Int,Int)] = { val digits = 0 to 9 for { // sは0〜9のどれか s <- digits // eは0〜9からsをのぞいたもののどれか e <- digits diff List(s) // nは0〜9からsとeをのぞいたもののどれか n <- digits diff List(s, e) // dは(ry d <- digits diff List(s, e, n) m <- digits diff List(s, e, n, d) o <- digits diff List(s, e, n, d, m) r <- digits diff List(s, e, n, d, m, o) y <- digits diff List(s, e, n, d, m, o, r) // sは0ではない if s != 0 // mも0ではない if m != 0 // SEND+MORE == MONEYを満すかどうかをチェック if int(s, e, n, d) + int(m, o, r, e) == int(m, o, n, e, y) } yield (int(s, e, n, d) , int(m, o, r, e) , int(m, o, n, e, y)) }
ネストが浅くなって超クール!
