前回まででなんとか制約プログラミングで実験できるところまでこぎ着けたので公式サイトのExamplesをやっていきたいと思います。

send+more=money

有名な論理パズルです。

   send
 + more
 ------
  money

与えられたこの式は、ひとつのアルファベットがひとつの数字に割り当てられます。別のアルファベットが同じ数字になってはいけません。単語の最初の文字は0以外でなければいけません（つまりsとmは0以外）。これらの制約を満たす数字を探す問題です。

制約を分かりやすくリストにすると

1. 0 <= s,e,n,d,m,o,r,y <= 9 の整数
2. s,e,n,d,m,o,r,yは全て違う数字
3. s != 0
4. m != 0
5. (s*1000+e*100+n*10+d) + (m*1000+o*100+r*10+e) = (m*10000+o*1000+n*100+e*10+y)

となります。

プログラム例

サンプルプログラムを見てみましょう。

サイトのコードではequation_rowがGecode.solveのブロック内に定義されていますが、最後の検算にも使いたかったのでトップレベルに出してあります。（Rubyの楽なとこですねduck typing！）

実行

制約を考えないと8変数でそれぞれが10の値を取り得るので単純計算すると10**10で10000000000通りになるんでしょうか。どのくらい実行時間はかかるのでしょう。早速実行してみます。

$ time ruby send-more-money.rb 
s e n d m o r y
9 5 6 7 1 0 8 2
send + more = 10652
money = 10652

real    0m0.392s
user    0m0.096s
sys 0m0.031s

あっさりと約0.4sで解が求まりました。いいですね！

仕事も始まったので今日からは少し短めでこの辺にしておきます。

次回はこのsend+more=moneyプログラムの細部を解説していきたいと思います。

前回の最後でrakeタスクで警告が出ないようにしましたが、specファイルがどうもRSpec 1の時代のものという事がわかり実行してみましたが1/3くらいコケる orz これにかかづらっていては何日も浮上できそうにないです。

SpecをRSpec 2に移行させてGecode 3ベースに対応させていくとか自分にできるかどうかはおいておいて、魅力的ではありますが

gecoder-reduxはRuby 1.9で動く？

よく考えたらgecoder-redux自体を修正したいわけではなく制約プログラミングを試してみたいだけなので、当面Ruby 1.9でそこそこ動いてくれればよいわけですから、まずは第１回目の最も単純なサンプルが実行できるようになっているかを実行してみます。

前に入れたgemに影響されないように新しいgemsetを作って実行してみます。

$ cd /path/to/gecoder/work
$ rvm gemset create gecoder-exec
$ rvm use ruby-1.9.3-p327@gecoder-exec
$ echo 'rvm ruby-1.9.3-p327@gecoder-exec' > .rvmrc
$ ruby -I /path/to/gecoder-redux/lib ex00.rb 
x y z
0 3 3

ヽ(´ー｀)ノ できた。

実行環境作り

毎回、LOAD PATHを指定するのは面倒なので.rvmrcの中でRUNLIBを設定してしまいます。

$ cd /path/to/gecoder/work
$ echo 'export RUBYLIB=/path/to/gecoder-redux/lib:$RUBYLIB' >> .rvmrc
$ pushd ..
$ popd
$ ruby ex00.rb
x y z
0 3 3

この作業ディレクトリでRubyプログラムを実行すればRuby 1.9対応（のはず）のGecode/Rをrequireできるようになりました。

Ruby1.9での実行環境ができたので次回からは公式サイトの例を進めていきながら制約プログラミングしていきたいと思います。

おまけ

gecoder-reduxでは第２回のSymbol#to_i未定義をどうやって回避したのか気になったのでソースの対応箇所を見てみると...

Hash、Gecode::Util::COMPARISON_ALIASESのkey配列のindexを使うように修正されています。alias_[0-9]+_without_short_circuitが他とぶつかりそうで怖いなぁと一瞬思いましたが、生成されたreceiverオブジェクトの特異メソッドとして定義されるので心配ありませんね。

前回まででRuby 1.9.3-p327で単純なサンプルコードを実行するところまでできました。

Symbolにオープンクラスでパッチを当てて対応したわけですが、できればGecode/Rのソースコードを修正して1.9.3対応していきたいのでソースコードリポジトリを見つけようと思います。

公式サイトのProject Detailsを見ると、サイト内にSubversionリポジトリが存在することが分かりました。

でも今更Subversionって気もしますしGithubに展開されていないのかな〜と思って検索してみるとgautamc/gecoder-reduxというのを発見。READMEによると、

I wanted to run gecoder with ruby 1.9 and with the latest version of gecode.

とのことで私が求めてるのこれじゃん！しかし最終更新が1年前とこちらも動いているとは言い難い様子（・ω・）

Commit履歴を眺めたところ元のコードをbundler対応にしてspecを追加したものっぽい。

さっそくForkしてcloneしてみる。

$ cd /path/to/work
$ git clone git://github.com/iwazer/gecoder-redux.git
$ cd gecoder-redux
$ git co -b dev-for-osx
$ rvm use ruby-1.9.3-p327
$ rvm gemset create gecoder-redux
$ rvm use ruby-1.9.3-p327@gecoder-redux
$ echo 'rvm ruby-1.9.3-p327@gecoder-redux' > .rvmrc
$ git add -A
$ git commit -m 'change to rvm develop environment setting'
$ gem install bundler
$ bundle install

rvmで専用のgemsetを作って試そうとしています。

bundlerの指定バージョンが古くて失敗するのでGemfileのbundlerのバージョン指定を"~> 1.2.3"にしてみます。またrcovもRuby 1.9ではsimplecovを使うらしいので修正しました。

$ gem install bundler
$ bundle install
$ bundle exec rake -T
WARNING: 'require 'rake/rdoctask'' is deprecated. Please use 'require 'rdoc/task' (in RDoc 2.4.2+)' instead.
    at /Users/iwazawa/.rvm/gems/ruby-1.9.3-p327@global/gems/rake-0.9.2.2/lib/rake/rdoctask.rb
rake build # Build gem into pkg/
rake clobber_rcov # Remove rcov products for rcov
rake clobber_rdoc # Remove rdoc products
rake console[script] # Start IRB with all runtime dependencies loaded
rake gemcutter:release # Release gem to Gemcutter
rake gemspec # Generate and validate gemspec
rake gemspec:debug # Display the gemspec for debugging purposes, as jeweler knows it (not from the filesystem)
rake gemspec:generate # Regenerate the gemspec on the filesystem
rake gemspec:release # Regenerate and validate gemspec, and then commits and pushes to git
rake gemspec:validate # Validates the gemspec on the filesystem
rake git:release # Tag and push release to git.
rake install # Build and install gem using `gem install`
rake rcov # Analyze code coverage with tests
rake rdoc # Build the rdoc HTML Files
rake release # Release gem
rake rerdoc # Force a rebuild of the RDOC files
rake test # Run tests
rake version # Displays the current version
rake version:bump:major # Bump the major version by 1
rake version:bump:minor # Bump the a minor version by 1
rake version:bump:patch # Bump the patch version by 1
rake version:write # Writes out an explicit version.

rakeタスクの警告が出たが、rakeは動いた。試しにtestタスクを動かしてみませう。

$ bundle exec rake test
WARNING: 'require 'rake/rdoctask'' is deprecated.  Please use 'require 'rdoc/task' (in RDoc 2.4.2+)' instead.
    at /Users/iwazawa/.rvm/gems/ruby-1.9.3-p327@global/gems/rake-0.9.2.2/lib/rake/rdoctask.rb
/Users/iwazawa/.rvm/rubies/ruby-1.9.3-p327/bin/ruby -I"lib:lib:test" -I"/Users/iwazawa/.rvm/gems/ruby-1.9.3-p327@global/gems/rake-0.9.2.2/lib" "/Users/iwazawa/.rvm/gems/ruby-1.9.3-p327@global/gems/rake-0.9.2.2/lib/rake/rake_test_loader.rb" "test/**/test_*.rb" 
/Users/iwazawa/Dropbox/develop/github/gecoder-redux/lib/gecoder/bindings.rb:60:in `require': cannot load such file -- gecode (LoadError)
    from /Users/iwazawa/Dropbox/develop/github/gecoder-redux/lib/gecoder/bindings.rb:60:in `load_bindings_lib'
  :

gecodr-with-gecode gemのようにgecodeライブラリが内包されているわけではないためライブラリが見つからないと言われる。

そりゃそうだとREADMEを見ると

I need to manually install gecode-2.2.0 and then make sure ldconfig knows abt its libs. Hoping to update this gem to work with gecode-3.7.1.

最新版のgecodeはHopingということでgecode-2.2.0を公式サイトからダウンロードしてビルドします。

$ cd /path/to/build
$ wget http://www.gecode.org/download/gecode-2.2.0.tar.gz
$ tar zxvf gecode-2.2.0.tar.gz
$ cd gecode-2.2.0
$ ./configure prefix=/path/to/gecoder-redux/lib
$ make
$ make install

configureのprefixにgecoder-redux/libへのパスを指定している理由は、モジュールがライブラリを見つけられるようにビルドするためmkmfするextconf.rbがgecoder-redux/extにあって、その中で

 :
ROOT = Pathname.new(File.dirname(__FILE__) + '/..').realpath
 :
GECODE_LIB_DIR = "#{ROOT}/lib/lib"
GECODE_INCLUDE_DIR = "#{ROOT}/lib/include"
 :

と書かれているので。

Gecodeのビルドは結構時間がかかりますが問題なく終了。続いてモジュールのビルドへ移ります。

$ cd /path/to/gecoder-redux/ext
$ ruby extconf.rb
$ make  
compiling gecode.cc
cc1plus: warning: command line option "-Wdeclaration-after-statement" is valid for C/ObjC but not for C++
cc1plus: warning: command line option "-Wimplicit-function-declaration" is valid for C/ObjC but not for C++
In file included from /Users/iwazawa/Dropbox/develop/github/gecoder-redux/lib/include/gecode/int/linear.hh:1596,
                 from /Users/iwazawa/Dropbox/develop/github/gecoder-redux/lib/include/gecode/minimodel.hh:47,
                 from gecode.hh:12,
                 from gecode.cc:4:
/Users/iwazawa/Dropbox/develop/github/gecoder-redux/lib/include/gecode/int/linear/bool-scale.icc: In member function 'void Gecode::Int::Linear::ScaleBoolArray::update(Gecode::Space*, bool, Gecode::Int::Linear::ScaleBoolArray&)':
/Users/iwazawa/Dropbox/develop/github/gecoder-redux/lib/include/gecode/int/linear/bool-scale.icc:67: warning: implicit conversion shortens 64-bit value into a 32-bit value
  :

う〜む、implicit conversion shortens 64-bit value into a 32-bit valueという、あまりよろしくなさそうな警告が大量に出ますね（汗）制約プログラミングの性格上、集合をビット演算で表現してたりしそうなので、ちゃんと動くかしら...

しかしmakeは最後まで流れるので、ひとまず警告には目をつぶってgecode.bundleというファイルが作成されている事を確認します。

OSXの場合これを、gecoder-redux/libの下にコピーすると実行できるはず。

$ cp -p gecode.bundle ../lib
$ cd ..
$ bundle exec rake test
WARNING: 'require 'rake/rdoctask'' is deprecated.  Please use 'require 'rdoc/task' (in RDoc 2.4.2+)' instead.
    at /Users/iwazawa/.rvm/gems/ruby-1.9.3-p327@global/gems/rake-0.9.2.2/lib/rake/rdoctask.rb
/Users/iwazawa/.rvm/rubies/ruby-1.9.3-p327/bin/ruby -I"lib:lib:test" -I"/Users/iwazawa/.rvm/gems/ruby-1.9.3-p327@global/gems/rake-0.9.2.2/lib" "/Users/iwazawa/.rvm/gems/ruby-1.9.3-p327@global/gems/rake-0.9.2.2/lib/rake/rake_test_loader.rb" "test/**/test_*.rb" 
/Users/iwazawa/Dropbox/develop/github/gecoder-redux/lib/gecoder/bindings.rb:60:in `require': dlopen(/Users/iwazawa/Dropbox/develop/github/gecoder-redux/lib/gecode.bundle, 9): Symbol not found: __ZTIN6Gecode6MSpaceE (LoadError)
  Referenced from: /Users/iwazawa/Dropbox/develop/github/gecoder-redux/lib/gecode.bundle
  Expected in: flat namespace
 in /Users/iwazawa/Dropbox/develop/github/gecoder-redux/lib/gecode.bundle - /Users/iwazawa/Dropbox/develop/github/gecoder-redux/lib/gecode.bundle

あれ？まだリンクがうまくいってなさげ(´・ω・｀)

nativeモジュールの作成経験が無く、さすがに自力で解決するのがキツいので、gecoder-with-gecodeのextと比べてみるとextconf.rbは同じなのにMakefileのRUBYLIBDIRとRUBYARCHDIRの値が直接パッチが当てられたかのような値に変更されている（・ω・）

< RUBYLIBDIR = /Users/iwazawa/.rvm/gems/ruby-1.9.3-p327/gems/gecoder-with-gecode-1.1.0/lib$(target_prefix)
< RUBYARCHDIR = /Users/iwazawa/.rvm/gems/ruby-1.9.3-p327/gems/gecoder-with-gecode-1.1.0/lib$(target_prefix)
---
> RUBYLIBDIR    = $(sitelibdir)$(target_prefix)
> RUBYARCHDIR   = $(sitearchdir)$(target_prefix)

この$(sitelibdir)と$(sitearchdir)の箇所を試しに/path/to/gecoder-redux/libと直接パスを与えてビルドし直してみると

$ bundle exec rake test
WARNING: 'require 'rake/rdoctask'' is deprecated.  Please use 'require 'rdoc/task' (in RDoc 2.4.2+)' instead.
    at /Users/iwazawa/.rvm/gems/ruby-1.9.3-p327@global/gems/rake-0.9.2.2/lib/rake/rdoctask.rb
/Users/iwazawa/.rvm/rubies/ruby-1.9.3-p327/bin/ruby -I"lib:lib:test" -I"/Users/iwazawa/.rvm/gems/ruby-1.9.3-p327@global/gems/rake-0.9.2.2/lib" "/Users/iwazawa/.rvm/gems/ruby-1.9.3-p327@global/gems/rake-0.9.2.2/lib/rake/rake_test_loader.rb" "test/**/test_*.rb" 
Run options: 

# Running tests:

F

Finished tests in 0.001256s, 796.1783 tests/s, 796.1783 assertions/s.

  1) Failure:
test: GecoderRedux should probably rename this file and start testing for real. (TestGecoderRedux) [/Users/iwazawa/Dropbox/develop/github/gecoder-redux/test/test_gecoder-redux.rb:5]:
hey buddy, you should probably rename this file and start testing for real

1 tests, 1 assertions, 1 failures, 0 errors, 0 skips

流れた。テストが失敗するのはデフォルトのテストファイルが失敗のものしかないからですね。

というかspecsディレクトリの方にspecファイル群があるけどどうやって実行するんだ？

Rakeタスクにdeprecatedの警告が出てますので、ひとまずそれを取ります。警告からRakefileの45行目をrequire 'rdoc/task'に変えれば良い。

ここまでの作業をgitにコミットしておきます。

extの下はMakefileには個人環境のパスが含まれるしgecode.{cc|hh}は自動生成されるのでgitの管理から外します。

$ cd ext
$ make distclean
$ cd ..
$ git rm ext/Makefile ext/gecode.* ext/mkmf.log ext/*.o
$ rm Gemfile.lock
$ vi .gitignore
## 追加
# for gecode lib
ext/Makefile
ext/gecode.*
ext/*.o
ext/mkmf.log
lib/bin
lib/gecode.bundle
lib/include
lib/lib
Gmefile.lock

$ git ad .gitignore
$ git commit -m 'ignore generated files'
$ git add Rakefile
$ git commit -m 'fix deprecated'
$ git add Gemfile
$ git commit -m 'use new version gem'

まだビルド環境を整えているだけですがGitHubに経過をあげておきます。 https://github.com/iwazer/gecoder-redux

今回はここまで。

前回は制約プログラミングについての簡単な説明と、サンプルプログラムをその通り実行してみたら落ちる...というところまででした。

よく考えたら先走りましたので、少し戻ってインストール方法の説明をしておきます。

Gecode/Rのインストール

私の環境はMac OS X Lion（not 山猫）ですが、おそらくSnow Leopard以降なら同じだと思われます。

ソースコードから自分でビルドするにはGecodeのライブラリを入れて、Gecoder（Gecode/R）を入れるようですが、OSXならGecode/Rのインストールガイドの最初にあるとおりgemで一発です。

gem install gecoder-with-gecode

私はRubyの実行環境のセットアップにrvmを使っているので

$ rvm current
ruby-1.9.3-p327
$ gem which gecode
/Users/iwazawa/.rvm/gems/ruby-1.9.3-p327/gems/gecoder-with-gecode-1.1.0/lib/gecode.bundle
$ gem which gecoder
/Users/iwazawa/.rvm/gems/ruby-1.9.3-p327/gems/gecoder-with-gecode-1.1.0/lib/gecoder.rb

こんな感じにインストールされた在処がわかります。

実はGecode,Gecode/Rをソースからビルドっていうのもちょっと試してみたのですが、Gecode 2.2.0のコンパイルがそのままでは失敗するので上記のgemを使った方が良いようです。 最新版に対応できないかなど、またの機会にトライしたいと思います。

ちょっと試してみます。（REPLはpryを使ってます）

$ pry
pry(main)> require 'gecoder'
=> true
pry(main)> Gecode.methods(false)
=> [:load_bindings_lib, :FreeVar, :solve, :maximize, :minimize, :create_model]

インストールされているようです。

なぜ動かなかったか？

前回、サンプルプログラムが動かなかったわけですが、上記のように最新のRubyに入れて試してみたところそうなりました。

せっかちなのでよく見なかったのですが、Featuresの対応バージョンによるとRuby 1.8.6と書かれている orz

残念ながらいささか古いプロダクトで、おそらく更新もされていないという状況と予想されます(´・ω・｀)

簡易インストール版、よく入りましたね（汗）

目標は1.9.3で動かす事として、とりあえず1.8.6なら動くのかを確かめて見たテスト。rvmって便利ヽ(´ー｀)ノ

サンプルをex00.rbというファイルに保存して実行しています。

$ rvm install 1.8.6
$ rvm use 1.8.6
$ gem install gecoder-with-gecode
$ ruby ex00.rb
x y z
0 3 3

やはり動きました。ここからが本番。

Ruby 1.9.3でのエラー

Ruby 1.9.3で動かしたときの直接的なエラーはコレでした。

NoMethodError: undefined method `to_i' for :==:Symbol
    from /Users/iwazawa/.rvm/gems/ruby-1.9.3-p327/gems/gecoder-with-gecode-1.1.0/lib/gecoder/interface/constraints/int_var_constraints.rb:137:in `block in singletonclass'

Symbol:==にto_iメソッドがないと言っています。

問題のコードを見てみると

receiverの特異クラスにメソッドをを定義しようとしてますが、compという変数はGecode::Util::COMPARISON_ALIASESというHashのキーだと分かります。これをto_iしようとしてエラーになってます。このHashは~/.rvm/gems/ruby-1.9.3-p327/gems/gecoder-with-gecode-1.1.0/lib/gecoder/interface/constants.rbに定義されていました。

キーはただのSymbolです。私はRuby歴が比較的短いので推測ですが1.8.6の頃はSymbolのto_iメソッドがID的な整数を返していて、alias_#{comp.to_i}_without_short_circuitはalias_1234_without_short_circuitみたいに定義できていたようです。

$ rvm use 1.8.6
$ ruby -e 'puts :sym.to_i'
10177
$ rvm use 1.9.3-p327
$ ruby -e 'puts :sym.to_i'
-e:1:in `
': undefined method `to_i' for :sym:Symbol (NoMethodError)

==のような記号をメソッド名として使えないのでそうしているのでしょう。ということはimmutableなオブジェクトに対して不変な値が必要なのだと思われるので、Object#object_idを返すようにSymbolに定義すれば良い気がします。

その通りスクリプトの最初に追記してex01.rbとして保存し実行すると

$ rvm current
ruby-1.9.3-p327
$ ruby ex01.rb
x y z
0 3 3

実行できた！ヽ(´ー｀)ノ

さて、こんな感じでいろいろと直していきたいのでGecode/Rのソースコードリポジトリを探そうと思いますが、今回はここまでとします。

このシリーズ、ここまでで分かるとおり行き当たりばったりにやってますので、寄り道が多くてまどろっこしいでしょうがお時間があれば、今後もお付き合いください（汗）

こんなページを見つけてしまいました。ヒャッハー！

• Constraint Programming in Ruby

昔この手のプロダクトに一時期関わってたことがあって、離れてからも使いたいな〜というシチュエーションがたまにあったのだけど、手に入る処理系に手軽なのがなくて諦めてたんですよ。

最近覚えているのでは「8チームによるホーム＆アウェイのリーグ戦で、これこれこういう条件を満たす組み合わせが欲しい」というものでした。仕事が忙しかったし、解こうとするまえに友人何人かが人力（Excel表）で解いてしまったので忘れてましたが、そういうのです。

制約プログラミング(Constraint Programming)とは

どういうものかというと、このページの下に載っている例が簡単で分かりやすいかも。

次の等式を満たすx,y,zを求めよ

• x + y = z
• x = y - 3

ただし、x,y,zは0~9の整数。

変数が３つあって、等式が２つなので方程式を解くことによっては解は一意に決まらない。しかし、それぞれの変数は0-9の範囲内と決まっているので順番に試していけば探索で求めることができます。

x=0, y=0, z=0の場合

0 + 0 = 0 # OK
0 = 0 - 3 # NG!

x=0, y=0, z=1の場合

0 + 0 = 1 # NG!

:

x=0, y=3, z=3の場合

0 + 3 = 3 # OK
3 = 3 - 3 # OK

順番に探していけば運が良ければそこそこ早く、運が悪くても可能性を全部試せば解が存在するか否かは分かります。

制約プログラミングはこの探索を効率的に行うことができます。あらかじめ制約を式としてシステムに与えておいて、ひとつの変数を決めるたびに制約式から他の変数の可能性を能動的に削っていき、探索空間を狭めたり速く失敗させたりすることによって探索を速く行います。

例えば、こんな制約プログラミング環境があったとしたらステキな気がします。

Gecode/R

Gecode/Rは制約プログラミング環境GecodeのRubyのためのインターフェースです。Gecodeは汎用的な環境ではありますが、デフォルトの言語インターフェースはC++ですので、いささか取っつきにくいです。

Gecode/Rで先ほどの問題を解くプログラムは下記のように書けます。 ＃WEBページそのものですが

少々冗長にはなりますが、架空のステキなプログラミング環境に近い感じでイイ！ヽ(´ー｀)ノ

さてここで問題。上記のように動くはずなのですが、このプログラムをコピペして実行すると

NoMethodError: undefined method `to_i' for :==:Symbol
    from /Users/iwazawa/.rvm/gems/ruby-1.9.3-p327/gems/gecoder-with-gecode-1.1.0/lib/gecoder/interface/constraints/int_var_constraints.rb:137:in `block in singletonclass'

と言って落ちる orz

諦めるのは非常に残念なので、がんばって追いかけることにします！が今日はここまで。

というわけで連載の予定