#!/usr/bin/env python

# Copyright (c) 2014 Aymeric Augustin
# Released under the WTFPLv2 - http://www.wtfpl.net/txt/copying/

"""
Quick'n'dirty solver for http://gameaboutsquares.com/.

Install requests or save http://gameaboutsquares.com/game.c.js next to this
file. Then run: python gameaboutsquares.py. Tested with Python 2.7 and 3.4.
"""

from collections import deque, namedtuple, OrderedDict
import re


# The following list is hardcoded because it's difficult to extract a human-
# friendly, plain-text representation of colors from their hexadecimal codes.

COLORS = [
    "red",              # c0392b
    "blue",             # 2980b9
    "dark blue",        # 2c3e50
    "orange",           # e67e22
    "turquoise",        # 16a085
    "green",            # 27ae60
    "purple",           # 9b59b6
    "grey",             # 7f8c8d
    "yellow",           # f1c40f
    "light red",        # c24646
    "dark green",       # 0b7140
    "olive",            # 555744
    "light orange",     # f19c2e
]


# Data structures for items on the board. row and col are integers storing the
# row (top to bottom) and column (left to right) where the item is located.
# way is a string during the loading phase and an integer during the solving
# phase; in both cases in stores the direction of the item. val is an integer
# encoding the color of the item; it can be used as an index in COLORS.

Arrow = namedtuple('Arrow', ['row', 'col', 'way'])

Square = namedtuple('Square', ['row', 'col', 'val', 'way'])

Target = namedtuple('Target', ['row', 'col', 'val'])


# LOADING PHASE

# load_javascript(), load_levels() and preprocess_level(level) build a
# convenient representation of the items in a level with the above data
# structures. Their implementation is both horrific and uninteresting.

def load_javascript():
    try:
        with open('game.c.js', 'r') as f:
            return f.read()
    except IOError:
        import requests
        data = requests.get('http://gameaboutsquares.com/game.c.js').text
        with open('game.c.js', 'w') as f:
            f.write(data)
        return data


def load_levels():
    js = load_javascript()
    js = js.replace('\n', '')

    order = re.search(r'levelOrder="([\w ]+)"\.split\(" "\);', js).group(1)
    order = order.split()

    levels = re.search(r'var h=({.*});', js).group(1)
    levels = re.sub(r'\b(\w+):function\(\){(.*?)},?',
                    r'"\1": [\n\2\n],\n', levels)
    # targets: new a(<col>, <row>, new d, <val>)
    levels = re.sub(r'new a\((-?\d+),(-?\d+),new d,(-?\d+)\);?',
                    r'    Target(\2, \1, \3),\n', levels)
    # arrows: new a(<col>, <row>, new b(<direction>))
    levels = re.sub(r'new a\((-?\d+),(-?\d+),new b\("(\w+)"\)\);?',
                    r'    Arrow(\2, \1, "\3"),\n', levels)
    # squares: new c(<col>, <row>, <val>, new b(<direction>))
    levels = re.sub(r'new c\((-?\d+),(-?\d+),(-?\d+),new b\("(\w+)"\)\);?',
                    r'    Square(\2, \1, \3, "\4"),\n', levels)
    # squares on arrows: new c(<col>, <row>, <val>)
    levels = re.sub(r'new c\((-?\d+),(-?\d+),(-?\d+)\);?',
                    r'    Square(\2, \1, \3, "inherit"),\n', levels)
    levels = eval(levels)

    return OrderedDict((name, levels[name]) for name in order)


def preprocess_level(level):
    raw_arrows = [item for item in level if isinstance(item, Arrow)]
    # Transform orientation information into a numerical value.
    arrows = []
    for arrow in raw_arrows:
        way = ['up', 'down', 'left', 'right'].index(arrow.way)
        arrows.append(Arrow(arrow.row, arrow.col, way))

    raw_squares = [item for item in level if isinstance(item, Square)]
    # As above, also obtain missing orientation information from arrows.
    squares = []
    for square in raw_squares:
        if square.way == 'inherit':
            for arrow in arrows:
                if arrow.row == square.row and arrow.col == square.col:
                    way = arrow.way
                    break
        else:
            way = ['up', 'down', 'left', 'right'].index(square.way)
        squares.append(Square(square.row, square.col, square.val, way))

    raw_targets = [item for item in level if isinstance(item, Target)]
    # Store targets in the same order as squares for convenience.
    targets = [{t.val: t for t in raw_targets}.get(s.val) for s in raw_squares]

    return arrows, squares, targets


# SOLVING PHASE

def solve(arrows, squares, targets):

    # Determine the smallest rectangle enclosing all items.
    items = [item for item in arrows + squares + targets if item is not None]
    row_min = min(item.row for item in items)
    row_max = max(item.row for item in items) + 1
    col_min = min(item.col for item in items)
    col_max = max(item.col for item in items) + 1

    def find_path(padding=0):
        # find_path() performs a simple Breadth First Search in a graph where
        # each board position (i.e. what you see on screen) defines a vertex
        # and each movement (i.e. when you click a square) defines an edge.
        # The graph is computed on demand. It isn't stored.

        # find_path() explores positions within a rectangle defined by
        # extending the smallest rectangle enclosing all items with some
        # padding. To simplify the implementation, rows and columns are
        # shifted so the upper left corner of that rectangle is at (0, 0)
        # and its lower left corner is at (n_rows - 1, n_cols - 1).

        row_off = padding - row_min
        col_off = padding - col_min
        n_rows = row_off + row_max + padding
        n_cols = col_off + col_max + padding

        # position_id(squares) turns a position into a unique
        # integer that is used as a graph vertex identifier. This should be
        # cheaper that using the entire position, both in memory and CPU, all
        # the more since it's a perfect hash. It could be reversed, perhaps to
        # improve the display of solutions, but this property isn't used yet.

        n_positions = n_rows * n_cols * 4

        def position_id(squares):
            res = 0
            for row, col, _, way in squares:
                res *= n_positions
                res += ((row + row_off) * n_cols + (col + col_off)) * 4 + way
            return res

        # The following function takes a position, moves one square and
        # returns the resulting position, or None if a square is pushed
        # outside of the rectangle. There are two kind of moves:
        # - If the square is initiating a move, the way parameter isn't
        #   provided and the direction is the square's orientation.
        # - If the square is pushed by another square, the direction is
        #   provided by the way parameter.

        def move_square(squares, square_index, way=None):
            square = squares[square_index]
            if way is None:
                way = square.way

            # Handle movement.
            if way == 0:     # up
                if square.row + row_off == 0:
                    return
                new_row, new_col = square.row - 1, square.col
            elif way == 1:   # down
                if square.row + row_off == n_rows - 1:
                    return
                new_row, new_col = square.row + 1, square.col
            elif way == 2:   # left
                if square.col + col_off == 0:
                    return
                new_row, new_col = square.row, square.col - 1
            elif way == 3:   # right
                if square.col + col_off == n_cols - 1:
                    return
                new_row, new_col = square.row, square.col + 1

            # Handle direction.
            for arrow in arrows:
                if arrow.row == new_row and arrow.col == new_col:
                    new_way = arrow.way
                    break
            else:
                new_way = square.way

            # Create a new position with these changes.
            new_square = Square(new_row, new_col, square.val, new_way)
            new_squares = list(squares)
            new_squares[square_index] = new_square

            # If the movement pushed another square, move it. Recursion is
            # guaranteed to terminate because all moves are in the same
            # direction, so each square may move most once.

            for other_square_index, other_square in enumerate(new_squares):
                if other_square_index == square_index:
                    continue
                if other_square.row == new_row and other_square.col == new_col:
                    return move_square(new_squares, other_square_index, way)
            else:
                return new_squares

        # The following function computes whether a given position is winning.

        def target_reached(squares):
            for square, target in zip(squares, targets):
                if target is None:
                    continue
                if square.row == target.row and square.col == target.col:
                    continue
                return False
            else:
                return True

        # To implement a Breadth First Search, we don't have to compute the
        # entire graph. We just need to keep track of which positions we've
        # already visited, and for each of them, which path led there. In
        # addition to the previous position, we also store the color of the
        # square that moved. We also need a queue of positions to visit.

        source = position_id(squares)
        done = {source: (None, None)}
        todo = deque([(squares, source)])

        while True:

            # Fetch the next position to visit from the queue. If the queue is
            # empty, no solution exists in the current rectangle.

            try:
                cur_squares, cur_position_id = todo.popleft()
            except IndexError:
                return

            # Try each possible move in this position.
            for square_index in range(len(squares)):
                new_squares = move_square(cur_squares, square_index)

                # If it pushes a square outside of the rectangle, ignore it.
                if new_squares is None:
                    continue

                new_position_id = position_id(new_squares)

                # If it results in a position we've already seen, ignore it.
                if new_position_id in done:
                    continue

                done[new_position_id] = (cur_position_id, square_index)

                # If we've found a solution, return it.
                if target_reached(new_squares):
                    path = []
                    while new_position_id != source:
                        new_position_id, square_index = done[new_position_id]
                        path.append(squares[square_index].val)
                    return list(reversed(path))

                # If this is a new valid position, add it to the queue.
                todo.append((new_squares, new_position_id))

    # Since the size of the graph is in O(board size ^ number of squares),
    # which is also O(padding ^ (2 * number of squares)), we start with no
    # padding and increase it up to number of squares - 1 only if needed.

    for padding in range(len(squares)):
        path = find_path(padding)
        if path is not None:
            return path


if __name__ == '__main__':
    levels = load_levels()
    for index, (name, level) in enumerate(levels.items()):
        print("")
        print("Level {} ({})".format(index, name))
        print("")
        solution = solve(*preprocess_level(level))
        if solution is None:
            print("No solution found :(")
        else:
            print("Solution in {} moves:".format(len(solution)))
            print("")
            grouped = []
            for val in solution:
                if grouped and grouped[-1][0] == val:
                    grouped[-1][1] += 1
                else:
                    grouped.append([val, 1])
            for val, count in grouped:
                print(' - {} x {}'.format(count, COLORS[val]))