{{ message }}

Instantly share code, notes, and snippets.

# trichoplax/maze_string_checker

Last active Aug 29, 2015
 ''' 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:'))