「オフラインリアルタイムどう書く第8回(ビットボンバーマン)」の問題を解いてみた

横浜へなちょこプログラミング勉強会にて過去に出題されたビットボンバーマンを解いてみた。
回答にかかった時間は100分程度と大幅オーバー。

「ビットボンバーマン」と言うからにはきっとビット演算を用いるのだろう...と思ったのだが、いまいち解法が思いつかず力技で解決してしまった。
爆弾の位置を基点として縦軸、横軸それぞれの最も近い壁のインデックスを探し、爆風が届く範囲を求めるようにしている。

class Field
  def initialize x, y, input
    @x, @y = x, y
    @wall, @bomb = input.split("/").map{|str|
      ("%032b" % str.to_i(16)).chars.map &:to_i
    }
    @field = Array.new(32){0}
  end

  def fire
    @field.size.times{|i| bomb i}
  end

  def to_s
    "%08x" % @field.map(&:to_s).join.to_i(2)
  end

  private

  def bomb index
    if @bomb[index] === 1
      bomb_line index, @y.times.map{|i| @x * i + (index % @x)}
      bomb_line index, @x.times.map{|i| i + ((index / @x) * @x)}
    end
  end

  def bomb_line index, line
    wall = line.each_with_object([]){|i, r| r << i if @wall[i] == 1}
    min = (line.index(wall.reverse.find{|i| i < index}) || -1) + 1
    max = (line.index(wall.find{|i| i > index}) || line.size) - 1
    (min..max).each{|i| @field[line[i]] = 1}
  end
end

test = <<_TEST
/*0*/ test( "802b1200/01400c20", "53c40cfc" );
/*1*/ test( "28301068/84080504", "d64fef94" );
/*2*/ test( "100a4010/80010004", "e241850c" );
/*3*/ test( "81020400/000000fc", "0e3cfbfc" );
/*4*/ test( "80225020/7e082080", "7fdd24d0" );
/*5*/ test( "01201200/40102008", "fe1861fc" );
/*6*/ test( "00201000/01000200", "43c48f08" );
/*7*/ test( "00891220/81020408", "ff060c1c" );
/*8*/ test( "410033c0/0c300000", "3cf0c000" );
/*9*/ test( "00000000/01400a00", "7bf7bf78" );
/*10*/ test( "00000000/20000a00", "fca2bf28" );
/*11*/ test( "00000000/00000000", "00000000" );
/*12*/ test( "00cafe00/00000000", "00000000" );
/*13*/ test( "aaabaaaa/50000000", "51441040" );
/*14*/ test( "a95a95a8/56a56a54", "56a56a54" );
/*15*/ test( "104fc820/80201010", "ea30345c" );
/*16*/ test( "4a940214/05000008", "05000008" );
/*17*/ test( "00908000/05000200", "ff043f48" );
/*18*/ test( "00c48c00/fe1861fc", "ff3873fc" );
/*19*/ test( "00000004/81020400", "fffffff0" );
/*20*/ test( "111028b0/40021100", "e08fd744" );
/*21*/ test( "6808490c/01959000", "17f7b650" );
/*22*/ test( "30821004/81014040", "c75de5f8" );
/*23*/ test( "0004c810/10003100", "fe4937c4" );
/*24*/ test( "12022020/88200000", "edf08208" );
/*25*/ test( "2aa92098/01160000", "45165964" );
/*26*/ test( "00242940/10010004", "fc43c43c" );
/*27*/ test( "483c2120/11004c00", "33c3de10" );
/*28*/ test( "10140140/44004a04", "eda3fe3c" );
/*29*/ test( "0c901d38/72602200", "f36da280" );
_TEST

require 'minitest/autorun'

describe 'BitBomberman' do
  test.split("\n").each do |line|
    t, n, input, expect = line.match(/^\/\*(\d+)\*\/\s*test\(\s*"([^"]+)",\s*"([^"]+)"\s*\);$/).to_a
    field = Field.new 6, 5, input
    field.fire
    it input do
      assert_equal expect, field.to_s
    end
  end
end