diff options
| -rw-r--r-- | README | 39 | ||||
| -rw-r--r-- | rush_hour.py (renamed from x.py) | 82 | ||||
| -rw-r--r-- | setup.cfg | 2 | ||||
| -rw-r--r-- | tests/test_sample.doctest | 23 |
4 files changed, 143 insertions, 3 deletions
@@ -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. @@ -1,3 +1,72 @@ +# 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): @@ -58,10 +127,18 @@ def possible_row_moves(row): 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: @@ -85,7 +162,8 @@ def possible_moves(board): for move, newrow in possible_row_moves(board[row]): yield ( transpose_move(move), - transpose_board(board[:row] + tuple([newrow]) + board[row + 1:])) + transpose_board( + board[:row] + tuple([newrow]) + board[row + 1:])) def is_solution(board): @@ -95,6 +173,8 @@ def is_solution(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 = [] @@ -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): |