maze_string_checker

'''
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:'))