Rubyプログラミングの手順〜アタマノタイソウ問題を例に

アタマノタイソウ問題を解く - わさっきのプログラムを作るのにとった手順を，書いてみます．
1. コーディングできるか考える．

バスを待つ間に，頭の中で練ってみる．車通勤の人はしちゃいけないよ．
移動回数最小の解が求められるといいので，幅優先探索を採用．
となると，先入れ先出しのキューを使おう．Rubyなら，pushで入れてshiftで取り出せばいい．
キューには最大でいくつたまるんだろうか．3×3の8パズルなら，空白も一つの値とみなして，状態数は9の階乗となる．暗算できないけど，100万はいかないはず．
しかし，一つの状態から，8つのコマが動き得るんだよな…じゃない．最大4つだ．真ん中が空白のときだけ，その上下左右のコマが動ける．空白が端（≠角）なら3つ，角なら2つ．しかも，そのうちの1つは，直前の状態に戻るので除外される．意外と，探索回数は少なくできるかな…．

2. マシンに向かい，アプリケーションを開く．

Cygwin端末: コマンド実行のため．早いうちから開けるのは，irbなどでちょっとした動作確認をしたいことがあるから．
Meadow: 主力となるテキストエディタ．
Rubyリファレンスマニュアル: 辞書みたいなもん．http://doc.okkez.net/を起点に．

3. 新規にファイルを開く．

テンプレートは，http://d.hatena.ne.jp/takehikom/20090124/1232748407とhttp://d.hatena.ne.jp/takehikom/20090206/1233865553で書いたものを使用．「puzzle-solver.rb」というファイル名で新規に開けば，以下の内容になる．

#!/usr/bin/env ruby
# -*- coding: utf-8 -*-

class PuzzleSolver
  def initialize
  end

  def start
  end
end

if __FILE__ == $0
  PuzzleSolver.new.start
end

文字コードを変更しておく．C-c C-m fのあと，utf-8-unix，そしてEnter．デフォルトでは改行コードがDOS式のCR LFで，都合が悪いこともあるので．

4. コンストラクタを作る．

initializeメソッドに引数を指定する．一つのHashインスタンスとし，ハッシュのキーは，シンボル（「:ナニナニ」）で統一する．
3×3に限定しなくていいので，幅と高さを知ることができるようにしたい．幅は不可欠なので@widthを用意する．高さは，ちょっと考えてみると不要なので，特に用意はしない．
他のメソッドで使用される変数を，インスタンス変数として定義し，初期化する．
メイン処理（「if __FILE__ == $0」と「end」で挟まれた区間）から呼ぶコードに，引数を与える．

5. ちょっと出力させる．

メソッドprint_fieldを定義し，startから呼び出す．
この時点で動作確認をする．エラーを取り除き，期待する結果になるまで何度も，実行と修正を繰り返す．

6. 処理の本体を書く．

もちろんsearchのこと．
変数の区分は以下のとおり．
- メソッド内でのみ使用する変数は，ローカル変数（「@」をつけず，英字はすべて小文字）
- 複数のメソッドで共通して使用するなら，インスタンス変数（「@」をつけ，英字はすべて小文字）
- 同じクラスの複数のインスタンスで共通して使用するなら，クラス変数（「@@」をつけ，英字はすべて小文字）
- 同じクラスの複数のインスタンスで共通して使用する定数は，英字を大文字として，コンストラクタより前で定義する．
今回は，こんな感じに．
- 状態間の遷移関係を格納するハッシュは，出力用メソッドで参照される必要があるので，最初からインスタンス変数とする．
- キュー（処理待ちの状態のリスト）と，何個処理したかのカウンタは，search内で収まるはずなので，当初ローカル変数としていたけど，新しい状態をキューに追加する処理は別途メソッドにしたほうがいいと気づき，ともにインスタンス変数に変更．きれいなコードにするには，@pred_h, @queue, @count_searchを含むクラスを別途定義すべきなのだが，主に時間の都合によりそうしなかった．
- クラス変数と定数は使用せず．
キューからの取り出しと，キューへの格納について，デバッグ用の出力を入れておく．「puts "get(#{@count_search}): #{state}"」と「puts "new: #{state2}"」のこと．ただし「if $DEBUG」は書かない．

7. 基本となるデータ構造を検討する．

状態を表す文字列を，@initや@goalに格納させているけれど，このフォーマットを基本としていいのか?
候補は，この文字列と，これをsplit(//)で1文字単位にばらした配列と，@widthごとに分けた，配列の配列．
状態間の遷移関係のハッシュで迷わなくていいので，文字列を基本とする．
文字列を一つの状態として，盤面でスライドさせる処理はどうなるか…1文字単位にばらした配列に対して，交換する2箇所のインデックスを決定し，「ary[pos1], ary[pos2] = ary[pos2], ary[pos1]」で交換してから，ary.joinで文字列を作ればいい，はず．

8. 最終的な出力処理を書く．

traceのこと．といっても，『ゴールすなわちインスタンス変数@goalから始めて，@initにたどり着ける』よう遷移関係を格納させているので，@initから反復させて各状態を出力させればいい．
traceの呼び出しは，startの中で書く．ついでに，searchの戻り値を，解発見ならtrue，失敗ならfalseとしておく．

9. 動作確認をする．

はじめは，短時間で終わるはずの例として，「PuzzleSolver.new(:width => 2, :blank => "*", :init => "123*", :goal => "231*").start」を．
コンパイルエラーを取り除く．
コンパイルエラーがなくなっても，はじめのうちは想定していない挙動ばかり．一つ一つ，原因を推測してコードを手直しする．
入力をいろいろ変えていく．日本語文字を使っても，問題ないことを確認する．
「アタマノタイソウ」問題を解く．get(26605)までいったところで，期待する解が得られた．
欲張って，「アタマノセイソウ」問題を解かせてみる．get(181441)までいって，「No answer」．9の階乗は「echo '1*2*3*4*5*6*7*8*9'|bc」というコマンドで求めることができ，362880．1の誤差はあるけど，半分だ．8パズルで（任意に取り外して交換することで）取り得る状態の半分が，スライド操作でたどり着けることが確認できたってわけか!

10. 清書をする．

プログラムへの入力の与え方を検討してみる．いつも使うのはコマンドライン引数．だけど，コマンドラインから日本語の（初期・最終）状態を打ち込むのは面倒だ．結局，メイン処理の中に複数の実行方法を書き，「アタマノタイソウ」問題以外はコメントにする．
全体を見て，無駄なコード，おかしな変数名がないかチェックする．変数名の変更は，MeadowのM-% (query-replace)*1を使って慎重に行う．修正のたびにプログラムを走らせる．
debug writeは後ろに「if $DEBUG」をつける．プログラムを実行し直すと，出なくなり，ruby -dとして実行すれば出ることを確認する．
Ruby 1.8でも問題なく動くことを確かめる．あれ，出力が変だ…ruby -Kuとすればいいことに気づく．

（同日夜にいくつか修正しました．）

*1:http://d.hatena.ne.jp/takehikom/20091112/1257975454

わさっきhb

大学（教育研究）とか，親馬鹿とか，和歌山とか，とか，とか．

Rubyプログラミングの手順〜アタマノタイソウ問題を例に