Created
December 6, 2016 12:47
-
-
Save mattsan/621225f9dea3ffd91d7db8bb937645e6 to your computer and use it in GitHub Desktop.
オフラインリアルタイムどう書く E10 「塗って繋ぐ」をRubyで塗る ref: http://qiita.com/emattsan/items/350f3c604715b1200e7a
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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 |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment