# rush_hour.py - Module for solving Rush Hour game
# coding: utf-8
#
# Copyright (C) 2016 Arthur de Jong
#
# Permission is hereby granted, free of charge, to any person obtaining a
# copy of this software and associated documentation files (the "Software"),
# to deal in the Software without restriction, including without limitation
# the rights to use, copy, modify, merge, publish, distribute, sublicense,
# and/or sell copies of the Software, and to permit persons to whom the
# Software is furnished to do so, subject to the following conditions:
#
# The above copyright notice and this permission notice shall be included in
# all copies or substantial portions of the Software.
#
# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
# IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,

# FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
# AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
# LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
# FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
# DEALINGS IN THE SOFTWARE.

"""Solve Rush Hour puzzle.

This module provides solutions to the Rush Hour game. The module expects the
board to be input as a list of rows with each cell either being empty
(denoted by a period (.)) or contain a car (denoted by letters). The letter r
represents the red car.

The goal of the game is to move cars (only back and forth) so that the red
car can be moved to the right of the board.

The find_solutions will generate a number of solutions, the shortest
solutions first.

>>> solution = next(find_solutions([
...     '....AA',
...     '..BBCC',
...     'rr..EF',
...     'GGHHEF',
...     '...IEF',
...     '...IJJ']))

A solution consists of a list of moves from the initial board. Each move
consists of a description of the move (e.g. AL2 indicates that car A will be
moved 2 spaces to the left) and a new board configuration.

>>> solution[0][0]
'AL2'
>>> print('\\n'.join(solution[0][1]))
..AA..
..BBCC
rr..EF
GGHHEF
...IEF
...IJJ
>>> ','.join(move for move, board in solution)
'AL2,BL2,CL2,EU2,FU2,HR2,IU1,JL3,ID1,HL2,ED3,FD3,rR4'
>>> print('\\n'.join(solution[-1][1]))
..AA..
BBCC..
....rr
GGHHEF
...IEF
.JJIEF

"""


def clean_board(board):
    """Check that the board is valid."""
    # check that each row has the same length
    if not all(len(board[0]) == len(row) for row in board[1:]):
        raise ValueError('each row should be the same length')
    # TODO: check that each cell is either a capital letter, r or a period
    # TODO: check that each "car" is 2 or 3 characters long
    # TODO: check that each "car" is purely horizontal or vertical
    # TODO: check that there is a "r" "car"
    return tuple(board)


def split_row(row):
    """Split the row in parts of equal characters."""
    value = ''
    for c in row:
        if value and c != value[0]:
            yield value
            value = ''
        value += c
    if value:
        yield value


def possible_row_moves(row):
    """Find the possible moves within a row."""
    # split in parts
    parts = list(split_row(row))
    for i in range(len(parts)):
        # see if we have some empty space
        if parts[i][0] == '.':
            # see if there is a horizontal car before this space
            if i > 0 and len(parts[i - 1]) > 1:
                # we have space to move any "cars" before to the right
                space = parts[i]
                car = parts[i - 1]
                for l in range(1, len(space) + 1):
                    newrow = ''.join(
                        parts[:i - 1] +
                        ['.' * l] + [car] + ['.' * (len(space) - l)] +
                        parts[i + 1:])
                    yield (
                        '%sR%d' % (car[0], l), newrow)
            # see if there is a horizontal car after this space
            if i < len(parts) - 1 and len(parts[i + 1]) > 1:
                # we have space to move any "cars" after this to the left
                space = parts[i]
                car = parts[i + 1]
                for l in range(1, len(space) + 1):
                    newrow = ''.join(
                        parts[:i] +
                        ['.' * (len(space) - l)] + [car] + ['.' * l] +
                        parts[i + 2:])
                    yield (
                        '%sL%d' % (car[0], l), newrow)


def transpose_board(board):
    """Turn horizontal rows will be turned into vertical columns."""
    return tuple(''.join(x) for x in zip(*board))


def transpose_move(move):
    """Tanslate horizontal move strings into vertical moves.

    >>> transpose_move('AR2')
    'AD2'
    >>> transpose_move('OL3')
    'OU3'
    """
    if move[1] == 'L':
        return move[:1] + 'U' + move[2:]
    else:
        return move[:1] + 'D' + move[2:]


def possible_moves(board):
    """Yield possible moves on the board.

    Each move consists of a tuple:
      move (e.g. AR1, BU2)
      new board
    """
    # go over horizontal cars
    for row in range(len(board)):
        for move, newrow in possible_row_moves(board[row]):
            yield (move, board[:row] + tuple([newrow]) + board[row + 1:])
    # go over vertical cars
    board = transpose_board(board)
    for row in range(len(board)):
        for move, newrow in possible_row_moves(board[row]):
            yield (
                transpose_move(move),
                transpose_board(
                    board[:row] + tuple([newrow]) + board[row + 1:]))


def is_solution(board):
    """Check whether the board is a solution (i.e. the red car is on the
    most right column)."""
    return any(row[-1] == 'r' for row in board)


def find_solutions(board):
    """Find solutions to the board. This function will return the shortest
    found solutions first."""
    board = clean_board(board)
    visited = set([board])
    queue = []
    queue.insert(0, [('', board)])
    while queue:
        moves = queue.pop()
        board = moves[-1][1]
        # find possible moves and see if we get somewhere new
        possible = []
        for move, newboard in possible_moves(board):
            if is_solution(newboard):
                yield moves[1:] + [(move, newboard)]
            elif newboard not in visited:
                queue.insert(0, moves + [(move, newboard)])
                visited.add(newboard)