CodeIQ 挑戦の記録 : 今週のアルゴリズム : 第86回「アタック25に挑戦!」

CodeIQというサイトで問題に挑戦した記録です。

https://codeiq.jp/sites/default/files/styles/thumb_175x114/public/engineer/algorithm.jpg?itok=Z_awtPsU

問題文を要約すると次の通り、

  • テレビ番組「アタック25」で次に選択できるパネル番号を求めるプログラムを書く問題。
  • 標準入力からプレイヤーの色、赤( R )、青(B)、白(W)、緑(G)ごとの現在獲得しているパネル番号が与えられる。
  • 各色ごとに、問題に正解した場合に選択できるパネルを列挙し解答する。

「アタック25」のルールはこちら
http://asahi.co.jp/attack25/rule/

パネルを選択できるルールについて確認

  1. 自分の色のパネルで他のプレイヤーのパネルを挟む事ができる位置がある場合 (優先順位1位)
    挟む事ができる位置の中から選ばなければならない。
  2. 自分の色のパネルで他のプレイヤーのパネルを挟む事ができる位置が無い場合で、次の問題に連続して正解したと仮定した時に挟む事ができる 状態になる位置。こちらもあればここから選ばなければならない。 (優先順位2位)
  3. 上記の条件で1箇所も選べる位置がない場合
    空白でないパネルに接している全ての空白パネル (優先順位3位)

選択できるかどうかの判定方法

上記のパネル選択ルールに基づき、コードに落とし込む為にパネルを選択できるかどうかの判定方法を説明する。
(下記の説明は1番のパネルを右方向に探索して選択できるかを判定する場合)

  • 隣のパネルが空白(誰も取っていないパネルを空白と表現する事にする)かパネルの枠外の場合
    パネルを選択できないのでスキップする
f:id:ibeckuu:20160331002313j:plain


  • 隣のパネルが自分と同じ色の場合
    他の色を挟む事も、次の正解時に挟める状態にする事もできない。優先順位3位とする。
f:id:ibeckuu:20160331002403j:plain


  • 隣のパネルから他の色が連続し、自分と同じ色が出現せず枠の終わりに達した場合
    優先順位3位とする
f:id:ibeckuu:20160331002435j:plain


  • 隣のパネルから他の色が連続し、空白に達した場合
    優先順位2位とする
f:id:ibeckuu:20160331002503j:plain


  • 隣のパネルから他の色が連続し、自分と同じ色に達した場合
    優先順位1位とする
f:id:ibeckuu:20160331002528j:plain


なお、例外があり、第1問・誰もパネルを取っていない初期状態では、正解した参加者は13番を指定するルールになっているので、誰もパネルを取っていない状態では全員が13番を選択できると解答しなければならない。
(この条件を考慮せずWAであった)

アルゴリズム

解答のアルゴリズムを大まかに説明する

{R,B,W,G についてループ
 {パネル1から25までループ
  {8方向をループしてパネルを選択できるか判定、   
   8方向の内、優先順位の最も高いものを選ぶ
   }
  対応する優先順位グループの配列にパネル番号を追加
  }
 要素がある優先順位グループの中最も優先順位の高いものを出力
}

実装

提出したコードは下記 (Ruby)

今回の問題はいつものパターンの総数を求める問題や、最大・最小を求める問題とは違っていた。
処理そのものは難しくなく、時間制限を気にする必要もなかったが、選択できるかどうかの判定が複雑で苦労した。
コードも100行近くなり見通しの悪いプログラムになってしまった。
長いコードを読んで頂いた皆さん、ありがとうございました。

では、

Sponsored Link