e10.rb

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