テトロミノビンゴ

テトロミノビンゴ
CodeIQ に出した「テトロミノ＋ビンゴ！」の解説・解題
にあった問題を解いてみた。
言語は Ruby。
リンク先にある data.txt が入力データとして必要。
手元の環境での実行時間は1.1秒程度。Ideone.com 程度の処理速度なら1秒未満のはず。

カードの状態は1次元の配列(プログラム中では mark という変数)で持つことにして、カードの端での条件判定をしなくてすむように、添え字とマス目の対応は下図のようにした。

 6  7  8  9 10
12 13 14 15 16
18 19 20 21 22
24 25 26 27 28
30 31 32 33 34

テトロミノの種類の判定は、テトロミノを構成するマス目を昇順に としたとき、
をキーに持つハッシュ (@tetromino) を参照することで行っている。

find_tetromino がマークのついたマス目の塊を探しているところ。
mark[cell] = cell とか mark[d] = cell とかいう書き方が一見変だが、要するに cell からつながっているマス目に cell (の値)で印をつけていっている。mark[d] == cell で、マス目 d が検査済みかどうかを判定できるようにこうした。group.member?(d) と判定するより少し速い。
塊の大きさは group.size で見ているが、塊の大きさを持つ変数を別に作るよりかすかに速い。
(配列やハッシュのメソッドより自前のコードのほうが速そうと思って余計なことをすると、裏目に出ることが多い気がする。)
return if group.size > 4 はその下の end の外側に出せるが、この位置のほうがかすかに速い気がする。

class TetrominoBingo
  # テトロミノの種類の判定用のデータ @tetromino を最初に作っておく
  def initialize
    tetromino_data = [
      [:I, [0,0], [0,1], [0,2], [0,3]],
      [:L, [0,0], [0,1], [0,2], [1,2]],
      [:O, [0,0], [0,1], [1,0], [1,1]],
      [:S, [0,0], [0,1], [1,1], [1,2]],
      [:T, [0,0], [1,0], [2,0], [1,1]]
    ]
    @tetromino = {}
    tetromino_data.each do |name, *coord|
      4.times do
        @tetromino[coord_to_cell(coord)] = name
        # 反転
        @tetromino[coord_to_cell(coord.map {|x, y| [-x, y]})] = name
        # 回転
        coord.map! {|x, y| [-y, x]}
      end
    end
  end

  # initialize の下請け
  def coord_to_cell(coord)
    cells = coord.map {|x, y| x + (N + 1) * y} .sort
    top_left = cells.shift
    cells.map {|cell| cell - top_left}
  end

  def group_to_tetromino(group)
    top_left = group.sort!.shift
    @tetromino[group.map {|cell| cell - top_left}]
  end

  # cell からつながるテトロミノが見つかったら、その種類を返す
  # 見つからなければ nil を返す
  def find_tetromino(mark, cell)
    mark[cell] = cell
    group = [cell]
    k = 0
    while c = group[k] do
      [c-1, c+1, c-N-1, c+N+1].each do |d|
        next if not mark[d] or mark[d] == cell
        mark[d] = cell
        group << d
        return if group.size > 4
      end
      k += 1
    end
    return group_to_tetromino(group) if group.size == 4
  end

  def prize(card, nums)
    mark = Array.new((N + 1) * (N + 2))
    nums.each do |n|
      next unless pos = card.index(n)
      prz = find_tetromino(mark, pos + pos/N + N + 1)
      return prz if prz
    end
    :-
  end
end

N = 5
tet = TetrominoBingo.new
file = open('data.txt')
nums = file.gets.split(',').map(&:to_i)
count = {:I => 0, :L => 0, :O => 0, :S => 0, :T => 0, :- => 0}
count[tet.prize($_.split(/[,\/]/).map(&:to_i), nums)] += 1 while file.gets
file.close
p count