読者です 読者をやめる 読者になる 読者になる

CodeIQ 挑戦の記録 : 今週のアルゴリズム : 第91回「最短で当たるビンゴゲーム」

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

f:id:ibeckuu:20160420045549j:plain

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

  • ビンゴカードの数字が4枚分標準入力より与えられる。
  • この数字は1から75までの整数で、1枚の中では同じ数字が2回現れる事はない。
  • 一般的なビンゴカードと違い真ん中のマスも「FREE」ではなく数字が書かれている。
  • 4枚全てがビンゴになる時、出る数字の種類が最も少ない場合の数字の個数を解答する。

方針

{5 \times 5}マスのカードのビンゴになる並びは縦・横・斜めの{12}通りである。
全てのカードについて全ての並びの組み合わせを試しても{{12}^{4} = 20,736}通りなので1秒の時間制限にも十分間に合う。
なので、全ての組み合わせを試し、その中で最も数字の種類の少ないものを選んで解答する事とする。
なお、数字の種類を数える方法は、組み合わせの数字全てをハッシュに代入し、ハッシュのサイズで比較する事にする。

全ての組み合わせを試す方法としては、4重ループにせず、再帰を用いた。
再帰を用いた方法であれば、時間はかかるが、カードが何枚でもコードを修正せずに答えを出せる。

実装 (Ruby)



Sponsored Link