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

More than 5 years have passed since last update.

posted at

Organization

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

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

そのうち解説を、描きたい。

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)
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