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

「 今週のお題:最短で当たるビンゴゲーム」問題解答 ( CodeIQ )

はじめに

CodeIQという所で週次で出題される「今週のお題」シリーズに解答しましたので、ネタバレです。

codeiq.jp

問題

今回は次のような問題でした。

4人でビンゴゲームを行うとき、全員がビンゴになるまでに必要な数字の個数の最小値を出力する 各人のビンゴカードの情報は、カンマ区切りで1行 ( 各行を並べたもの ) ずつ入力される *なお、ビンゴゲームでよくある「真ん中は最初から開いている」はないものとする

詳細については、CodeIQ magazineの当該記事をご覧ください。

解説

1枚のカードにつき、ビンゴが発生するラインは12あるので、ゴリっと124全ての組み合わせを試すコードを組みました。 ビンゴが発生箇所を0~11の数値で識別し、

  • 0~4: 横一列
  • 5~9: 縦一列
  • 10,11: ななめ

としてカードから数字を抽出し、uniqによって数字の種類を数えています

c=$<.map{|s|s.scan /\d+/}
p (0..11).
  to_a.
  repeated_permutation(4).
  map{|r|
    r.zip(c).
    reduce([]){|s,(i,b)|
      s+
      (0..4).map{|j|
        b[i<5 ? i*5+j : i<10 ? j*5-25+i : 12+2*(i-8)*(j-2)]
      }
    }.
    uniq.
    size
  }.
  min

終わりに

組み合わせの数が少ないので何とかなりますが、まあ、結構実行時間のかかる解にしてしまいました。