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 を条件に追加している。


matchDeath :: [Int] -> Bool
matchDeath (a:b:d:e:h:s:t:r:[]) =
  d/=0 && s/=0 && debt + star == death
  where
    debt  =             d * 1000 + e * 100 + b * 10 + t
    star  =             s * 1000 + t * 100 + a * 10 + r
    death = d * 10000 + e * 1000 + a * 100 + t * 10 + h

filterDeath =
  map (zip "abdehstr") $ filter matchDeath  $ permutation 8 [0,1,2,3,4,5,6,7,8,9]

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


matchDeath' :: [Int] -> Bool
matchDeath' (a:b:e:h:s:t:r:[]) =
  debt + star == death
  where
    debt  =             d * 1000 + e * 100 + b * 10 + t
    star  =             s * 1000 + t * 100 + a * 10 + r
    death = d * 10000 + e * 1000 + a * 100 + t * 10 + h
    d = 1

filterDeath' =
  map (zip "abehstr")  $ filter matchDeath' $ permutation 7 [0,2,3,4,5,6,7,8,9]

2. 一般化

ここからが本番だ。

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


test1 = print $ findConditions $ "debt" + "star" == "death"

test2 = print $ findConditions $ "debt + star = death"

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


main = do
  equ:_ <- getArgs
  print $ findConditions $ fromString equ

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


$ verbal-arithmetic-general-exe "debt + star = death"

3. 式のデータ

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


data VExp = Val [Char]
          | Add VExp VExp
          deriving(Show)

data VEqu = Equals VExp VExp
          deriving(Show)

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


equ1 = Equals (Add (Val "debt") (Val "star")) (Val "death")

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


equ2 = Val "debt" `Add` Val "star" `Equals` Val "death"

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

(+)  = Add
(==) = Equals

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


equ3 = Val "debt" + Val "star" == Val "death"

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


instance IsString VExp where
  fromString xs = Val xs
  

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


equ4 = "debt" + "star" == "death"

4. 一般解

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


findConditions :: VEqu -> [[(Char,Int)]]
findConditions equ =
  let
    cs = chars equ
  in
   filter (match equ) $ map (zip cs) $ permutation (length cs) [0..9]


match :: VEqu -> [(Char,Int)] -> Bool
match equ xs = (and $ map f $ firstChars equ) && evaluate equ xs
  where
    f x =
      let Just y = lookup x xs
      in  y /= 0

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


evaluate :: VEqu -> [(Char,Int)] -> Bool
evaluate (Equals exp1 exp2) xs = expEvaluate exp1 xs P.== expEvaluate exp2 xs 
  where
    expEvaluate :: VExp -> [(Char,Int)] -> Int
    expEvaluate (Add exp1 exp2) xs = expEvaluate exp1 xs P.+ expEvaluate exp2 xs
    expEvaluate (Val cs) xs = listToInt $ map f cs
      where
        f x =
          let Just y = lookup x xs
          in  y

5. パーサー

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

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


pVal :: PS.Parser VExp
pVal = do
  xs <- PS.many1 $ PS.letter <|> PS.alphaNum
  return $ Val xs

pAdd :: PS.Parser (VExp -> VExp -> VExp)
pAdd = PS.char '+' >> return Add

pExp :: PS.Parser VExp
pExp = pValS `PS.chainl1` pOpS
  where
    pValS = do
      val <- pVal
      PS.spaces
      return val
    pOpS = do
      op <- pAdd <|> mzero
      PS.spaces
      return op

pEquals :: PS.Parser VEqu
pEquals = do
  exp1 <- pExp
  PS.char '='
  PS.spaces
  exp2 <- pExp
  return $ Equals exp1 exp2

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


instance IsString VEqu where
  fromString xs =
    case PS.parse pEquals "verbal" xs of
      Right equ -> equ
      Left  err -> error (show err)

6. まとめ・感想

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

自作のHaskellアプリ(AHA & Bingo)を stack 対応した話

巷で話題の Haskell のビルドツール stack だが、自作のアプリも stack でのビルドに対応してみた。

https://github.com/mitsuji/aha
https://github.com/mitsuji/bingo

stack の便利さをどう表現しようか。筆者の場合は git に出会ったときと状況が似ていると感じている。

ソースコード管理の重要さを知りながらも、cvs や subversion を「どうしても使わなければ」と思うことはなかったが、git に出会ってからは git というツールとともにソースコード管理そのものも、ちょっとしたものを作るときでもあたりまえのこととして受け入れるようになった。

stack の場合は、自分のソースをパッケージとして組むことをあたりまえのこととしてくれるツールという感じがする。

stack は 依存ライブラリと依存コンパイラ(ghc)のバージョンをまとめて解決してくれるので、とてもありがたい。 scala の sbt に 影響を受けているようだが、sbtはさすがに jdk のバージョンも管理してくれるわけではないので stack の方が上を行っていると思う。

下記のコマンドで最新のghcが入る。

$ stack setup

プロジェクトに cd して下記のコマンドでプロジェクトがビルドできる。

$ stack build

プロジェクトに cd して下記のコマンドでプロジェクト内のソースを参照しつつREPL。

$ stack ghci

プロジェクトに cd して下記のコマンドで ~/.local/bin に 実効形式がインストールされる。

$ stack install

Haskell 入門の敷居がまた下がった。

Haskell is ready for industry !

Haskell Platform や パッケージ管理システムを使わずに GHC と Cabal をインストールする – CentOS 7 編

[モチベーション]

Haskell のコンパイラのデファクトスタンダードである GHC は、わりと頻繁に新しいバージョンがリリースされている。

開発が活発なのは利用者としてはうれしいことだが、Haskell Platform や 各ディストリビューションのパッケージ管理システムを使って環境を構築していると、各バージョンのGHCを切り替えて使うことが難しく、それが作業の妨げになることがある。

GHCのバイナリパッケージを自分でインストールしてPATHの設定も自分で行っておくと各バージョンの切り替えが可能となる。

自前構築は面倒なイメージがあるが、ポイントを押さえれば意外と簡単なのでここで共有する。

今回は “CentOS 7 編”だ。x86_64版が最小構成でインストールされていると仮定する。

Haskell Platform や パッケージ管理システムを使わずに GHC と Cabal をインストールする – Debian 8 (Jessie) 編

[概要]

下記を行うための手順を示す。

1. GHCのバイナリパッケージのインストール

GHCのバイナリパッケージを /usr/local/apps/ にインストールする。
下記のように複数バージョンを保持する前提。

/usr/local/apps/ghc-7.6.3
/usr/local/apps/ghc-7.8.4
/usr/local/apps/ghc-7.10.1
/usr/local/apps/ghc-7.10.2

2. cabalコマンドのビルド

公式サイトから落としてきた cabal コマンドを使用して自前のcabalコマンドをビルドする。

[1. GHCのバイナリパッケージのインストール]

GHCのバイナリパッケージは下記のサイトで公開されている。
https://www.haskell.org/ghc/

Debian版 と CentOS版があるが、依存しているGMPライブラリのバージョンがキモとなるため、CentOS 7 では Debian版を使用する。
https://www.haskell.org/ghc/download_ghc_7_10_2#x86_64linux

gcc と perl が必要なのでインストールしておく。
gmp-devel は ghci の実行時に必要となるので一緒に入れておく。
*.tar.bz2 を解凍するために、bzip2もここでいれておく。

$ sudo yum install gcc perl gmp-devel bzip2

バイナリパッケージをダウンロードする。

$ curl -O http://downloads.haskell.org/~ghc/7.10.2/ghc-7.10.2-x86_64-unknown-linux-deb7.tar.bz2

tar ボールを解凍して、解凍先に cd する。
bzip2がないと、このときエラーになる。

$ tar jxf ghc-7.10.2-x86_64-unknown-linux-deb7.tar.bz2
$ cd ghc-7.10.2

インストール先を指定して configure する。
gcc や perl がないと、このときエラーになる。

$ ./configure --prefix=/usr/local/apps/ghc-7.10.2

管理者権限で make install

$ sudo make install

下記のように、PATHを追加する。

$ cat ~/.bash_profile
# .bash_profile

# Get the aliases and functions
if [ -f ~/.bashrc ]; then
. ~/.bashrc
fi

# User specific environment and startup programs

PATH=$PATH:$HOME/.local/bin:$HOME/bin
PATH=$PATH:/usr/local/apps/ghc-7.10.2/bin

export PATH

PATHの追加を反映。(ログインしなおしてもよい)

$ source ~/.bash_profile

ghci を起動して下記のように動作すれば成功。

$ ghci
GHCi, version 7.10.2: http://www.haskell.org/ghc/ :? for help
Prelude> 1 + 2 + 3
6
Prelude> :q
Leaving GHCi.

[2. cabalコマンドのビルド]

パッケージ名としてはCabalのライブラリがcabal、cabalコマンドがcabal-installとなっている。

cabal-installのバイナリビルドは下記のサイトで公開されているが、Linux版は32bit版のみの為、64bit環境で動作させるには、少し工夫が必要になる。
https://www.haskell.org/cabal/download.html

glibc.i686、zlib.i686、gmp.i686 は 32bit版のcabalの動作に必要なパッケージ。
zlib-devel は自前の64bit版のcabalをビルドするときに必要なのでここで入れておく。

$ sudo yum install glibc.i686 zlib.i686 gmp.i686 zlib-devel

バイナリビルドをダウンロードする。

$ curl -O https://www.haskell.org/cabal/release/cabal-install-1.22.0.0/cabal-1.22.0.0-i386-unknown-linux.tar.gz

tar ボールを解凍すると cabal という名前のファイルが生成される。これが32bit版 cabalコマンド。

$ tar zxf cabal-1.22.0.0-i386-unknown-linux.tar.gz

cabal のパッケージ情報を更新(ダウンロード)する。

$ ./cabal update

自分の cabal コマンドをビルドする。~/.cabal/bin にインストールされる。

$ ./cabal install cabal-install

下記のように、PATHを追加する。

$ cat ~/.bash_profile
# .bash_profile

# Get the aliases and functions
if [ -f ~/.bashrc ]; then
. ~/.bashrc
fi

# User specific environment and startup programs

PATH=$PATH:$HOME/.local/bin:$HOME/bin
PATH=$PATH:/usr/local/apps/ghc-7.10.2/bin
PATH=$PATH:~/.cabal/bin

export PATH

PATHの追加を反映。(ログインしなおしてもよい)

$ source ~/.bash_profile

自分の cabal が参照されれば成功。

$ which cabal
/home/administrator/.cabal/bin/cabal

Haskell Platform や パッケージ管理システムを使わずに GHC と Cabal をインストールする – Debian 8 (Jessie) 編

[モチベーション]

Haskell のコンパイラのデファクトスタンダードである GHC は、わりと頻繁に新しいバージョンがリリースされている。

開発が活発なのは利用者としてはうれしいことだが、Haskell Platform や 各ディストリビューションのパッケージ管理システムを使って環境を構築していると、各バージョンのGHCを切り替えて使うことが難しく、それが作業の妨げになることがある。

GHCのバイナリパッケージを自分でインストールしてPATHの設定も自分で行っておくと各バージョンの切り替えが可能となる。

自前構築は面倒なイメージがあるが、ポイントを押さえれば意外と簡単なのでここで共有する。

今回は “Debian 8 (Jessie) 編”だ。amd64版が最小構成でインストールされていると仮定する。

Haskell Platform や パッケージ管理システムを使わずに GHC と Cabal をインストールする – CentOS 7 編

[概要]

下記を行うための手順を示す。

1. GHCのバイナリパッケージのインストール

GHCのバイナリパッケージを /usr/local/apps/ にインストールする。
下記のように複数バージョンを保持する前提。

/usr/local/apps/ghc-7.6.3
/usr/local/apps/ghc-7.8.4
/usr/local/apps/ghc-7.10.1
/usr/local/apps/ghc-7.10.2

2. cabalコマンドのビルド

公式サイトから落としてきた cabal コマンドを使用して自前のcabalコマンドをビルドする。

[1. GHCのバイナリパッケージのインストール]

GHCのバイナリパッケージは下記のサイトで公開されている。
https://www.haskell.org/ghc/

Debian 7 (wheezy) でビルドされたものが jessie でも使える。
https://www.haskell.org/ghc/download_ghc_7_10_2#x86_64linux

gcc と make が必要なのでインストールしておく。
libgmp-dev は ghci の実行時に必要となるので一緒に入れておく。

$ sudo apt-get install gcc make libgmp-dev

バイナリパッケージをダウンロードする。

$ wget http://downloads.haskell.org/~ghc/7.10.2/ghc-7.10.2-x86_64-unknown-linux-deb7.tar.bz2

tar ボールを解凍して、解凍先に cd する。

$ tar jxf ghc-7.10.2-x86_64-unknown-linux-deb7.tar.bz2
$ cd ghc-7.10.2/

インストール先を指定して configure する。
gcc や make がないと、このときエラーになる。

$ ./configure --prefix=/usr/local/apps/ghc-7.10.2

管理者権限で make install

$ sudo make install

下記のように、PATHを追加する。

$ cat ~/.bash_profile
PATH=$PATH:/usr/local/apps/ghc-7.10.2/bin

export PATH

PATHの追加を反映。(ログインしなおしてもよい)

$ source ~/.bash_profile

ghci を起動して下記のように動作すれば成功。

$ ghci
GHCi, version 7.10.2: http://www.haskell.org/ghc/ :? for help
Prelude> 1 + 2 + 3
6
Prelude> :q
Leaving GHCi.

[2. cabalコマンドのビルド]

パッケージ名としてはCabalのライブラリがcabal、cabalコマンドがcabal-installとなっている。

cabal-installのバイナリビルドは下記のサイトで公開されているが、Linux版は32bit版のみの為、64bit環境で動作させるには、少し工夫が必要になる。
https://www.haskell.org/cabal/download.html

32bitアーキテクチャを dpkg の対象に追加してからaptを更新する。
libc6:i386、zlib1g:i386、libgmp10:i386 は32bit版のcabalの動作に必要なパッケージ。
zlib1g-dev は自前の64bit版のcabalをビルドするときに必要なのでここで入れておく。

$ sudo dpkg --add-architecture i386
$ sudo apt-get update
$ sudo apt-get install libc6:i386 zlib1g:i386 libgmp10:i386 zlib1g-dev

32bitバイナリの動作についての詳細はこちらを参照。
http://askubuntu.com/questions/454253/how-to-run-32-bit-app-in-ubuntu-64-bit

バイナリビルドをダウンロードする。

$ wget https://www.haskell.org/cabal/release/cabal-install-1.22.0.0/cabal-1.22.0.0-i386-unknown-linux.tar.gz

tar ボールを解凍すると cabal という名前のファイルが生成される。これが32bit版 cabalコマンド。

$ tar zxf cabal-1.22.0.0-i386-unknown-linux.tar.gz

cabal のパッケージ情報を更新(ダウンロード)する。

$ ./cabal update

自分の cabal コマンドをビルドする。~/.cabal/bin にインストールされる。

$ ./cabal install cabal-install

下記のように、PATHを追加する。

$ cat ~/.bash_profile

PATH=$PATH:/usr/local/apps/ghc-7.10.2/bin
PATH=$PATH:~/.cabal/bin

export PATH

PATHの追加を反映。(ログインしなおしてもよい)

$ source ~/.bash_profile

自分の cabal が参照されれば成功。

$ which cabal
/home/administrator/.cabal/bin/cabal