From 05f01b6fa9fb1e49643b7d755b1bda653fe05bdb Mon Sep 17 00:00:00 2001 From: Arthur de Jong Date: Sun, 13 Nov 2016 18:34:48 +0100 Subject: Add basic documentation This also adds copyright headers (MIT license) and renames the module. --- README | 39 ++++++++++ rush_hour.py | 192 ++++++++++++++++++++++++++++++++++++++++++++++ setup.cfg | 2 +- tests/test_sample.doctest | 23 +++++- x.py | 112 --------------------------- 5 files changed, 254 insertions(+), 114 deletions(-) create mode 100644 README create mode 100644 rush_hour.py delete mode 100644 x.py diff --git a/README b/README new file mode 100644 index 0000000..340cddc --- /dev/null +++ b/README @@ -0,0 +1,39 @@ +rush_hour +========= + +A Python module to solve the Rush Hour game efficiently. It has no external +dependencies and should work with both Python 2 and Python 3. + +See the module documentation (pydoc rush_hour) for details on the API. + + +Running tests +------------- + +There is a basic testset included in the module which is based on doctests. +The easiest way to run the tests is with the nosetests (or nosetests3) +command. + + +Copyright +--------- + +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. diff --git a/rush_hour.py b/rush_hour.py new file mode 100644 index 0000000..582213c --- /dev/null +++ b/rush_hour.py @@ -0,0 +1,192 @@ +# 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) diff --git a/setup.cfg b/setup.cfg index d44989c..335f266 100644 --- a/setup.cfg +++ b/setup.cfg @@ -4,7 +4,7 @@ doctest-extension=doctest doctest-options=+IGNORE_EXCEPTION_DETAIL with-coverage=true cover-branches=true -cover-package=x +cover-package=rush_hour cover-erase=true cover-html=true cover-html-dir=coverage diff --git a/tests/test_sample.doctest b/tests/test_sample.doctest index 5ab8910..350aac7 100644 --- a/tests/test_sample.doctest +++ b/tests/test_sample.doctest @@ -1,6 +1,27 @@ test_sample.doctest - simple test for rush hour solution finder ->>> from x import find_solutions +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. + + +>>> from rush_hour import find_solutions >>> def get_moves(board): diff --git a/x.py b/x.py deleted file mode 100644 index e82a04e..0000000 --- a/x.py +++ /dev/null @@ -1,112 +0,0 @@ - - -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): - return tuple(''.join(x) for x in zip(*board)) - - -def transpose_move(move): - 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): - 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) -- cgit v1.2.3