Ruby
どう書く

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

More than 1 year has passed since last update.

当日は時間内に書きあがりませんでした。

その後同じアイディアで動くものを書いたのですが、時間がかかりすぎですべての問題を解く前に 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