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

はじめに

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

codeiq.jp

問題

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

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

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

解説

1枚のカードにつき、ビンゴが発生するラインは12あるので、ゴリっと12⁴全ての組み合わせを試すコードを組みました。 ビンゴが発生箇所を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

終わりに

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