第13回オフラインリアルタイムどう書く。ruby による実装。

オフラインリアルタイムどう書く

• 第13回(9月6日) http://atnd.org/events/41603

の問題「積み木の水槽」
http://nabetani.sakura.ne.jp/hena/ord13blocktup/
の実装例。

他の言語などの解答例は
http://qiita.com/Nabetani/items/936e7885f4c607472060
から辿れます。

ちなみに次回は

• 第14回(9月28日) http://atnd.org/events/43076

です。

で。

def create_field( src )
  # 左右と下に空間があるフィールドを用意する
  [[nil]*10]+src.chars.map{ |s|
    i=s.to_i
    [nil] + [:B]*i + [:W]*(9-i) # :B はブロック、:W は水
  }+[[nil]*10]
end

def solve(src)
  field = create_field( src )
  loop do
    done=false
    ( field.size * 10 ).times do |xy|
      x,y = xy.divmod(10)
      next unless field[x][y]==:W # 注目点が水でなければ何もしない

      #右と左と下を調べて、空間があったらその水は流れ去る
      unless [ field[x+1][y], field[x-1][y], field[x][y-1] ].all?
        done=true
        field[x][y]=nil
      end
    end
    return field.flatten.count(:W).to_s unless done
  end
end

raise "FAIL" unless DATA.each.map do |line|
  num, src, expected = line.split( /\s+/ )
  actual = solve( src )
  ok = expected == actual
  puts( "%s %s->%s ( %s )" % [ ok ? "ok" : "***NG***", src, actual, expected ] )
  $stdout.flush
  ok
end.all?

__END__
0 83141310145169154671122 24  
31  268131111165754619136819109839402 102 

いつもどおり、テストデータの大半は省略。

会場で思いついた実装。

コメントのとおりなんだけど

1. 入力データの外側に何もない空間をひとマス分用意。
2. 入力データのある辺りのブロックのない部分は水で満たす。
3. 水の左右又は下に何もない空間があったらそこを何もない空間にする。
4. やれることがなくなったら終了。水の数を数える。

done があるのがかっこ悪い気がするんだけど、マシにする方法が思いつかない。