Create a gist now

Instantly share code, notes, and snippets.

class Array
def x
self[0]
end
def y
self[1]
end
end
# -----
X_REPLACE_TABLE = [[0,1,0],[1,0,1],[0,1,0]]
O_REPLACE_TABLE = [[1,0,1],[0,1,0],[1,0,1]]
def solve(board_state, n, actions)
if actions == []
board_state
else
hd, *tl = actions
new_board_state = apply(board_state, n, hd)
solve(new_board_state, n + 1, tl)
end
end
def apply(board_state, n, action)
old_board_size = 3 ** n
new_board_size = 3 ** (n + 1)
new_board_state = []
for i in 0 ... new_board_size
new_board_state[i] = []
end
for i in 0 ... old_board_size do
for j in 0 ... old_board_size do
if board_state[i][j] == 0
for k in 0 .. 2 do
for l in 0 .. 2 do
new_board_state[3 * i + k][3 * j + l] = 0
end
end
else
for k in 0 .. 2 do
for l in 0 .. 2 do
if action == "X"
new_board_state[3 * i + k][3 * j + l] = X_REPLACE_TABLE[k][l]
else
new_board_state[3 * i + k][3 * j + l] = O_REPLACE_TABLE[k][l]
end
end
end
end
end
end
new_board_state
end
def pp_board(board)
board_size = board.size
for i in 0 ... board_size
for j in 0 ... board_size
if board[i][j] == 0
print "_"
elsif board[i][j] == 2
print "+"
else
print "*"
end
end
print "\n"
end
print "\n"
end
def count_areas(board)
areas = 0
board_size = board.size
for i in 0 ... board_size
for j in 0 ... board_size
if board[i][j] == 0
areas += 1
board = paint_board(board, board_size, i, j)
end
end
end
areas
end
def paint_board(board, bs, i, j)
queue = [[i, j]]
while queue.size > 0
point = queue.shift
x = point.x
y = point.y
if board[x][y] == 0
board[x][y] = 2
if x > 0 && board[x-1][y] != 2 then queue << [x-1, y] end
if y > 0 && board[x][y-1] != 2 then queue << [x, y-1] end
if x < bs - 1 && board[x+1][y] != 2 then queue << [x+1, y] end
if y < bs - 1 && board[x][y+1] != 2 then queue << [x, y+1] end
end
end
board
end
def test(actions_str, count_str)
puts "#{actions_str} (expected:#{count_str})"
actions = actions_str.split("")
final_board = solve([[1]], 0, actions)
pp_board final_board
areas = count_areas final_board
puts areas
p areas == count_str.to_i
puts
puts "------------"
puts
end
# -----
# test("X", "5")
# test("XX", "5")
# test("XXX", "17")
# test("XXXX", "65")
# test("XXXXX", "257")
# test("O", "4")
# test("OO", "12")
# test("OOO", "28")
# test("OOOO", "60")
# test("OOOOO", "124")
# test("OXX", "21")
# test("OXO", "18")
# test("OOOX", "130")
# test("OXXO", "29")
# test("XXOX", "81")
# test("XOXXO", "89")
# test("OOOOX", "630")
# test("OXOOO", "66")
# test("OXOXOX", "2001")
# test("OXOXXO", "417")
# test("OXXOXX", "1601")
# test("XXXOXOO", "345")
# test("OOOOOXO", "3258")
# test("OXXOXXX", "6401")
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment