0
Help us understand the problem. What are the problem?

More than 5 years have passed since last update.

オフラインリアルタイムどう書く 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
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Sign upLogin
0
Help us understand the problem. What are the problem?