Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
'''
Move string validator for 3x3 mazes
Take a string of NESW as a command line argument or via STDIN.
Verify that the string solves all valid 3x3 mazes, or give a counterexample.
'''
def all_layouts(n):
maximum = 2 ** (2 * n * (n-1))
length = len(bin(maximum - 1)) - 2
for t in range(maximum):
unpadded = bin(t)[2:]
padding = '0' * (length - len(unpadded))
padded = padding + unpadded
yield padded
def all_mazes(n):
for layout in all_layouts(n):
for exit_cell in range(n*n):
for start_cell in range(n*n):
if start_cell != exit_cell:
yield (layout, exit_cell, start_cell, n)
def solvable_mazes(n):
for maze in all_mazes(n):
if is_solvable(maze):
yield maze
def is_solvable(maze):
layout, exit_cell, start_cell, n = maze
if exit_cell in indirect_neighbours(start_cell, layout, n):
return True
def indirect_neighbours(start_cell, layout, n):
connected = set()
new_cells = set((start_cell,))
while new_cells:
connected |= new_cells
boundary = new_cells
new_cells = set(neighbour
for cell in boundary
for neighbour in neighbours(cell, layout, n)
) - connected
return connected
def neighbours(cell, layout, n):
for candidate in potential_neighbours(cell, n):
if is_valid_neighbour(cell, candidate, layout, n):
yield candidate
def is_valid_neighbour(cell_1, cell_2, layout, n):
area = n * n
return (cell_2 >= 0 and
cell_2 < area and
adjacent(cell_1, cell_2, n) and
not wall(cell_1, cell_2, layout, n)
)
def potential_neighbours(cell, n):
yield cell - 1
yield cell + 1
yield cell - n
yield cell + n
def adjacent(cell_1, cell_2, n):
x1 = cell_1 % n
y1 = cell_1 // n
x2 = cell_2 % n
y2 = cell_2 // n
distance = abs(x2 - x1) + abs(y2 - y1)
return distance == 1
def wall(cell_1, cell_2, layout, n):
if cell_1 < cell_2:
cell_A = cell_1
cell_B = cell_2
else:
cell_A = cell_2
cell_B = cell_1
if cell_A == cell_B - 1:
return layout[cell_A - cell_A // n] == '1'
elif cell_A == cell_B - n:
return layout[n*(n-1) + cell_A] == '1'
def solves(maze, string_to_test):
layout, exit_cell, start_cell, n = maze
current_cell = start_cell
for move in string_to_test:
destination_cell = current_cell + offset(move, n)
if is_valid_neighbour(current_cell, destination_cell, layout, n):
current_cell = destination_cell
if current_cell == exit_cell:
return True
def offset(move, n):
return (-n * (move == 'N') +
1 * (move == 'E') +
n * (move == 'S') +
-1 * (move == 'W')
)
def first_unsolved_maze(string_to_test, n):
for maze in solvable_mazes(n):
if not solves(maze, string_to_test):
return maze
def invalid_characters(string_to_test):
double_check = set(string_to_test)
return double_check - set('NESW')
def check_3x3_mazes(string_to_test):
print('Length of string: ' + str(len(string_to_test)))
print('Checking validity...')
surplus = invalid_characters(string_to_test)
if surplus:
print('Invalid characters present:')
print(surplus)
else:
failed_maze = first_unsolved_maze(string_to_test, 3)
if failed_maze:
print('Fails for this maze:')
print(visualised(failed_maze))
else:
print('Valid string.')
def visualised(maze):
layout, exit_cell, start_cell, unused = maze
output = ' __ __ __\n|'
output += 'S ' if start_cell == 0 else 'E ' if exit_cell == 0 else ' '
output += '|' if layout[0] == '1' else ' '
output += 'S ' if start_cell == 1 else 'E ' if exit_cell == 1 else ' '
output += '|' if layout[1] == '1' else ' '
output += 'S ' if start_cell == 2 else 'E ' if exit_cell == 2 else ' '
output += '|\n|'
output += '__' if layout[6] == '1' else ' '
output += '|' if layout[0] == '1' else ' '
output += '__' if layout[7] == '1' else ' '
output += '|' if layout[1] == '1' else ' '
output += '__' if layout[8] == '1' else ' '
output += '|\n|'
output += 'S ' if start_cell == 3 else 'E ' if exit_cell == 3 else ' '
output += '|' if layout[2] == '1' else ' '
output += 'S ' if start_cell == 4 else 'E ' if exit_cell == 4 else ' '
output += '|' if layout[3] == '1' else ' '
output += 'S ' if start_cell == 5 else 'E ' if exit_cell == 5 else ' '
output += '|\n|'
output += '__' if layout[9] == '1' else ' '
output += '|' if layout[2] == '1' else ' '
output += '__' if layout[10] == '1' else ' '
output += '|' if layout[3] == '1' else ' '
output += '__' if layout[11] == '1' else ' '
output += '|\n|'
output += 'S ' if start_cell == 6 else 'E ' if exit_cell == 6 else ' '
output += '|' if layout[4] == '1' else ' '
output += 'S ' if start_cell == 7 else 'E ' if exit_cell == 7 else ' '
output += '|' if layout[5] == '1' else ' '
output += 'S ' if start_cell == 8 else 'E ' if exit_cell == 8 else ' '
output += '|\n|__'
output += '|' if layout[4] == '1' else ' '
output += '__'
output += '|' if layout[5] == '1' else ' '
output += '__|\n'
return output
if __name__ == '__main__':
import sys
arguments = sys.argv
if len(arguments) >= 2:
first_argument = sys.argv[1]
check_3x3_mazes(first_argument)
else:
check_3x3_mazes(input('Enter string:'))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment