Qiita、下書きが溜まっていたので年末大掃除ってことで書いていきます。
昔、codeiqというサイトで出されていた問題で、
アタック25のアルゴリズムを実装しろという問題がありました。
オセロやリバーシでは、自分の色がなくなった場合は即負けですし、
挟めない場合は自動的にパスになるのですが、アタック25ではこの場合のルールが追加されています。
http://asahi.co.jp/attack25/rule/
まず、ルールを整理します。
- 挟む事ができるパネルを取ることが出来る
- 次に挟むことが出来るパネルを取ることが出来る
- 今まであるパネルにくっつけて取ることが出来る。
- 13を取ることが出来る
上からルールを見ていき、そのルールでは取れるパネルがないときのみ下のルールを参照します。
最初のルールはオセロでもおなじみのルールです。
2番めのルールは、次の問題で連続で正解した場合、パネルで挟むことができる場所を取らないといけない、というルールになります。
3番めは2番めのルールで候補がなかった時で、取られているパネルに隣接(斜め含む)している場所です。
4番目は初期状態の時のことですね。
ということで、それぞれのルールごとに候補を出していって、
なければ次のルール、というふうに考えていきます。
まず、挟むというのはどういうことかをもうちょっと厳密に定義しましょう。
他人の色が連続し、最後に自分の色が来る場所が挟める場所です。
正規表現風に書くと[空きマス][他人の色]+[自分の色]のとき、空きマスが挟める場所です。
では、これをアルゴリズムに落としていきます。
引数としてパネルの位置を取り、以下の処理をする関数を作ります。
引数で得た位置から、8方向に対して歩いていきます。
1歩目 他人の色→継続
それ以外→失敗/中断
2歩目 他人の色→継続
空きマス→成功、このマスを記録/中断
それ以外→失敗/中断
1番目のルールで、自分の色のマスに対してこの関数を実行します。
すべての自分の色のマスでこの関数を実行したあと、候補が0なら次のルールに移り、
候補があればそれらを出力して中断します。
2番めのルールでは、自分の色のマスのかわりに空きマスに対してこの関数を実行します。
次に挟むことが出来る場所とは、空きマスの場所を自分が取れていると仮定したら
挟むことが出来るマス、という意味になります。
これも候補があれば中断し、なければ次のルールに行きます。
3番めは簡単ですね。
すべての取られているマスの八方向のマスが取ることが出来るマスです。
4番目は13と固定ですので簡単です。