オフラインリアルタイムどう書く E10 「塗って繋ぐ」をRubyで塗る

当日は時間内に書きあがりませんでした。
その後同じアイディアで動くものを書いたのですが、時間がかかりすぎですべての問題を解く前に Ctrl+C 。
で。あくまで塗るというアイディアはそのままにできるだけ早いコードを探しました。三日ほどさまよいました。

結果、私の Mac でおよそ 10 秒で全問解き終わるぐらいのコードになりました。
そのうち解説を、描きたい。

問題はこちら http://mtsmfm.github.io/2016/12/03/doukaku-e10.html
みなさんの解答はこちら http://qiita.com/mtsmfm/items/8a78b895910a89e3012d

orde10.rb

require 'benchmark'
require 'set'

PATTERNS = {
  'X' => [[1, 0], [0, 1], [2, 1], [1, 2]],
  'O' => [[0, 0], [2, 0], [1, 1], [0, 2], [2, 2]]
}

def filled_area_count(size, blocks)
  block_set = blocks.map {|x, y| y * size + x }.to_set
  sentinel_index = size ** 2
  board = Array.new(sentinel_index) { sentinel_index }

  transform_table = {}

  next_index = 1
  sentinel_index.times do |i|
    next if block_set.include?(i)
    left_index  = (i % size == 0) ? sentinel_index : board[i - 1]
    upper_index = (i / size == 0) ? sentinel_index : board[i - size]

    if (left_index == sentinel_index) && (upper_index == sentinel_index)
      board[i] = next_index
      next_index += 1
    elsif left_index == upper_index
      board[i] = left_index
    else
      actual_index, alias_index = (left_index < upper_index) ? [left_index, upper_index] : [upper_index, left_index]
      transform_table[alias_index] = actual_index
      board[i] = actual_index
    end
  end

  filled_indices = board.flatten.to_set.delete(sentinel_index)

  transform_table.sort.reverse.each do |alias_index, actual_index|
    filled_indices.delete(alias_index)
    filled_indices.add(actual_index)
  end

  filled_indices.size
end

def solve(input)
  size = 
  blacks = input.chars.reduce([[0, 0]]) {|blacks, c|
    blacks.map {|cell|
      PATTERNS[c].map {|x, y| [cell[0] * 3 + x, cell[1] * 3 + y] }
    }.flatten(1)
  }

  filled_area_count(3 ** input.length, blacks).to_s
end

def test(input, expected)
  actual = solve(input)
  if actual == expected
    print "\x1b[1m\x1b[32m.\x1b[0m"
  else
    puts(<<~EOS)
      \x1b[1m\x1b[31m
      input:    #{input}
      expected: #{expected}
      actual:   #{actual}\x1b[0m
    EOS
  end
end

def test_all(data)
  data.each do |line|
    input, expected = line.split
    test(input, expected)
  end

  puts
end

time = Benchmark.realtime { test_all(DATA) }

puts format('%8.3f sec', time)

__END__
X 5
O 4
XX 5
OX 10
XO 9
XOO 17
OXX 21
OXO 18
OOOX 130
OXXO 29
XXOX 81
XOXXO 89
OOOOX 630
OXOOO 66
OXOXOX 2001
OXOXXO 417
OXXOXX 1601
XXXOXOO 345
OOOOOXO 3258
OXXOXXX 6401