私自身が表題の問題を解いた時のプログラムについて解説します。
問題の詳細は「最短で当たるビンゴゲーム」（CodeIQ）を参照してください。
こどもから大人まで楽しめるビンゴゲーム。
参加者は5×5のマスに数字が書かれたビンゴカードを持っており、ランダムに選ばれた数字が手元のビンゴカードにあれば、その場所に印をつけます。
よく使われるカードでは中央の1マスはFREEになっていますが、今回はこのマスにも数字が書かれており、一枚のビンゴカードには異なる25個の数字が書かれています。
どの列にどんな値があるかわかりませんが、書かれている数字は1～75までのいずれかです。
縦、横、斜めのいずれか一列(5個の数字)が揃うと「ビンゴ」となります。
今回は4人がビンゴゲームをしており、それぞれ異なる配置のカードを持っています。
ランダムに選ばれる数字も1～75の75種類あり、一度出た数字は二度と出ることはありません。
4人が持っているカードに記載されている番号が一人ずつ標準入力からコンマ区切りで与えられます。
全員がビンゴになるまで数字を出し続けるとき、出る数字の個数が最小になるような場合を求め、出た数字の個数を標準出力に出力してください。
【入出力サンプル】
標準入力
A、B、C、Dの順に1行ずつカードの番号が与えられます。
このようなカードの並びだと1行目のように入力されます。
66 64 40 24 50 14 61 9 34 3 46 21 59 42 72 51 57 67 56 4 27 62 1 8 35
66,64,40,24,50,14,61,9,34,3,46,21,59,42,72,51,57,67,56,4,27,62,1,8,35
51,69,73,57,56,8,33,64,70,68,14,54,2,7,25,66,44,65,40,27,12,53,59,72,31
46,40,38,70,51,26,37,64,2,60,43,45,54,47,69,34,9,33,31,25,48,13,12,36,71
32,25,3,11,24,57,40,12,31,64,75,17,47,51,39,38,33,34,30,6,62,8,59,60,65
標準出力
13
Rubyで解答しています。
#!/usr/bin/ruby
# A〜Cのカードの縦横斜めパターンを保持する
$Cards = []
# 入力値から縦横斜めごとに配列を作る
def getLineSet(line)
splited = line.split(",")
ret = Array.new(12){Array.new(5)} # 縦横斜めごとに配列を作る
for i in 0...25
v = splited[i].to_i
# 横
if (0<=i) && (i<=4) then ret[0][i] = v
elsif (5<=i) && (i<=9) then ret[1][i-5] = v
elsif (10<=i) && (i<=14) then ret[2][i-10] = v
elsif (15<=i) && (i<=19) then ret[3][i-15] = v
elsif (20<=i) && (i<=24) then ret[4][i-20] = v
end
# 縦
if i%5 == 0 then ret[5][i/5] = v
elsif i%5 == 1 then ret[6][i/5] = v
elsif i%5 == 2 then ret[7][i/5] = v
elsif i%5 == 3 then ret[8][i/5] = v
elsif i%5 == 4 then ret[9][i/5] = v
end
# 斜め（0->25)
if (i==0) then ret[10][0] = v
elsif (i==6) then ret[10][1] = v
elsif (i==12) then ret[10][2] = v
elsif (i==18) then ret[10][3] = v
elsif (i==24) then ret[10][4] = v
end
# 斜め (4->20)
if (i==4) then ret[11][0] = v
elsif (i==8) then ret[11][1] = v
elsif (i==12) then ret[11][2] = v
elsif (i==16) then ret[11][3] = v
elsif (i==20) then ret[11][4] = v
end
end
return ret
end
def makePattern()
min = 76 # 最小要素数の番号（全部の数字を使った時が最悪なので+1）
for i in 0..11
for j in 0..11
for k in 0..11
for l in 0..11
sum = $Cards[0][i] + $Cards[1][j] + $Cards[2][k] + $Cards[3][l]
sum.uniq!
if sum.length < min then min = sum.length end
end
end
end
end
return min
end
# main
while line = gets
$Cards.push(getLineSet(line.strip))
end
p makePattern()
★★★の問題ですが比較的簡単です。
出る数字の個数が最小ということは、A〜Dのカードの縦横斜めそれぞれ任意の1列を選択した場合に、そこに含まれる数字の種類が最も少ない組み合わせを選択するということです。
気になるのは計算量ですが縦横斜めで1人あたり12通りなので124=20736通りしかありません。総当たりで十分解けます。
計算処理を楽にするためデータの持ち方を工夫しています。
A〜Dそれぞれ、
data[0] = 横1行目
…
data[4] = 横5行目
data[5] = 縦1列目
…
data[9] = 縦5列目
data[10] = 斜め1〜25
data[11] = 斜め4〜20
の様にデータを作り、$Cardsの0がAのカード、3がDのカードになる様にしています。
これをやっているのがgetLineSet()です。ループを使ってもう少し短くできそうですが、何も考えずに一つずつやってしまいました。
A〜Cのカードの縦横斜めに含まれる数字の組み合わせを総当たりで求めています。Rubyだと配列を連結してuniq!すれば重複を除けるので簡単です。含まれる数字の数は配列の要素数に等しくなります。
あとは最小値を選べば良いだけで、最小値の初期値を76（全て異なる数字でも75なのでそれよりも1大きい）にしておけば現在の最小値より少なくなったら最小値を更新するだけで済みます。
この問題は問題を読んですぐにプログラムを思いつきました。が、くだらないミスをして1時間以上はなりました。ありがちなミスですがループカウンタを間違えたのです。ループが終了する値は時々間違えるので割とすぐ気づくのですが、どういうわけか今回は開始位置を間違えていてなかなか気づけませんでした。
55〜57行目が1..xになっていたのですが（そして、54行目は最初から正しかった）、なんで間違えたかがよくわかりません。何も考えなくても手のくせで0としそうなものなのですが……。