1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
|
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)
|