CODEWITHSUNDEEP
python
James
James

Reputation: 85

Why is my program running an infinite loop? Python

I am trying to create a maze solver in python using the Breadth-first search. The algorith is supposed to replace the shortest path from S to E (start to end) with 1's. However, my program is running an infinite loop and the only while loop I have is at the end, so I think the problem is there. I can't figure out what is causing it.

import queue


def maze_3():
    maze3 = [
        '00000S000000000000000000000000000000000000000000000000000000000',
        '00000  000000000                                               ',
        '00000  000000000  000000000000000000  000000000000000  00000000',
        '000000            00000000    000000                      00000',
        '   00000000  000000000000         000000000000000000     000000',
        '00000000         000000000000000000000000000000   0000   000000',
        '000000        000      000000000      000     000000       0000',
        '000000  000     000000000        00000000    000000          00',
        '00  000    0  0000000000  000  000   0000  00  00 00000     000',
        '000000    000000         000000000     000  0000          00000',
        '0000000000000000            0000000  0000000   000  00000000000',
        '000000        000  0000000    0000   00000000000000    00000000',
        '0000000000000000E                                       0000000',
    ]
    return maze3


def finished_maze(maze, solution=''):
    global starting_point
    for i, position in enumerate(maze[0]):
        if position == 'S':
            starting_point = i

    j = starting_point
    k = 0
    position = set()

    for move in solution:
        if move == 'Up':
            k -= 1
        elif move == 'Down':
            k += 1
        elif move == 'Left':
            j -= 1
        elif move == 'Right':
            j += 1

    for k, row in enumerate(maze):
        for j, column in enumerate(row):
            if (k, j) in position:
                print('1', end='')
            else:
                print(column, end='')
        print()


def is_valid(maze, moves):
    a = True
    for l, position in enumerate(maze[0]):
        if position == 'S':
            starting_point = l

    j = starting_point
    k = 0

    for move in moves:
        if move == 'Up':
            k -= 1
        elif move == 'Down':
            k += 1
        elif move == 'Left':
            j -= 1
        elif move == 'Right':
            j += 1

        if not ((j >= 0 and j < len(maze[0])) and (k >= 0 and k < len(maze[0]))):
            return not a
        elif maze[k][j] == '0':
            return not a
    return a


def find_solution(maze, moves):
    a = True
    for i, position in enumerate(maze[0]):
        if position == 'S':
            starting_point = i

    j = starting_point
    k = 0
    for move in moves:
        if move == 'Up':
            k -= 1
        elif move == 'Down':
            k += 1
        elif move == 'Left':
            j -= 1
        elif move == 'Right':
            j += 1

        if maze[k][j] == 'E':
            print(finished_maze(maze, moves))
            return a

    return not a


space = queue.Queue()
space.put('')
put = ''
maze = maze_3()

while not find_solution(maze, put):
    put = space.get()
    for i in ['Up', 'Down', 'Left', 'Right']:
        location = put + i
        if is_valid(maze, location):
            space.put(location)

Upvotes: 2

Views: 111

Answers (1)

Marko
Marko

Reputation: 779

This line of code doesn't do what you are expecting it to do:

for move in moves:

It splits it so it gives you every single letter separately.

D
o
w
n
D
o
w
n

It should be like this: (add import re to the start of your file)

for move in re.findall('[A-Z][^A-Z]*', moves):

It gives the following:

Right
Down
Down
Up
Up
Down
Down
Up
Down
Down
Down
Up
Left
Down
Down
Up
Right

Other than that, your program works, but really slowly because you are not checking if you already visited a node.

Extra part on visited list

If you define maze like so:

def maze_3():
    maze3 = [
        '00000S000000000000000000000000000000000000000000000000000000000',
        '00000  000000000                                               ',
        '00000  000000000  000000000000000000  000000000000000  00000000',
        '000000E           00000000    000000                      00000', # here we add an E
        '   00000000  000000000000         000000000000000000     000000',
        '00000000         000000000000000000000000000000   0000   000000',
        '000000        000      000000000      000     000000       0000',
        '000000  000     000000000        00000000    000000          00',
        '00  000    0  0000000000  000  000   0000  00  00 00000     000',
        '000000    000000         000000000     000  0000          00000',
        '0000000000000000            0000000  0000000   000  00000000000',
        '000000        000  0000000    0000   00000000000000    00000000',
        '0000000000000000E                                       0000000',
    ]
    return maze3

It gives the following solution, which is correct:

Down
Down
Right
Down

But if we print all the paths it checked, we can see this:

Up
Down
Left
Right
DownUp
...

The last line says it returns to the location it already visited. If you take a better look at BFS, you will see that it keeps a list of visited nodes. If you add it, it will speed up your code as you will not be checking nodes that you have already visited.

Upvotes: 1

Related Questions