Breadth-first search uncategorized solution for Open Labyrinth by Bilou06 - python coding challenges

Enable Javascript in your browser and then refresh this page, for a much enhanced experience.

Breadth-first search solution in Uncategorized category for Open Labyrinth by Bilou06

def checkio(labyrinth):
    sX,sY = 1,1
    eX,eY = 10,10
    paths = [(sX,sY,'')]
    visited = [(sX,sY)]
    while len(paths):
        x,y,p = paths.pop(0)
        if x==eX and y==eY:
            return p
        for i,j,s in [(x+1,y,'S'),(x-1,y,'N'),(x,y+1,'E'),(x,y-1,'W')]:
            if labyrinth[i][j] != 1 and (i,j) not in visited: # the borders are always 1
                visited.append((i,j))
                paths.append((i,j,p+s))
            


if __name__ == '__main__':
    #Return any route to exit
    checkio([
        [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
        [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
        [1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1],
        [1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1],
        [1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1],
        [1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1],
        [1, 0, 0, 0, 1, 1, 0, 1, 1, 1, 0, 1],
        [1, 0, 1, 0, 0, 0, 0, 1, 0, 1, 1, 1],
        [1, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 1],
        [1, 0, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1],
        [1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1],
        [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]])
    #be carefull with infinity loop
    checkio([
        [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
        [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
        [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
        [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
        [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
        [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
        [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
        [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
        [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
        [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
        [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
        [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
    ])

April 10, 2013

Comments:

bryukh on April 10, 2013, 9:40 p.m.
Nice, it's short and simple.

JackyCore on April 27, 2013, 8:56 p.m.
Great!

wcp1231 on May 24, 2013, 7:20 a.m.
I like this！

ichaleynbin on June 3, 2013, 4:13 a.m.
Nice Solution. My only comment is that BFS can have up to b^m fringed nodes (your 'paths' list; given python's handling of lists, keeping list lengths under control can be crucial), where DFS will have maximum of b * m. It trades the extra space needed for the guarantee of shortest path, which is not necessary for this problem. Is it a crucial problem? Maybe not here, but its worth taking into account. All things considered, I generally like to ask myself 'what were the designers of the problem specifying when they wrote what they did?' Shortest path is nice and all, but if it doesn't get you extra points, why waste the overhead? They did not ask for 'shortest path', they asked for 'a path.' I know somebody is gonna say 'but its nothing compared to what we've got available!' It never is. But you still see bloated code that bogs down lesser machines. Why? This attitude, when compared with frugality toward resources, will always end up with more bloated code. It might be just a kilobyte here, or a few extra processes there, but thats all you're ever doing with code anyhow, is one thing at a time, and monstrosities come from not making every step as efficient as possible, and wasting valuable computer resources. IMHO, its better to always code as efficiently and frugally as you can, just so you're in the habit of not wasting resources, which (as large as they are) are still limited. Python takes a matter of minutes to fill up gigabytes of ram on certain tasks, so its hard to afford even one extra instruction/datapoint out of a thousand. Lisp codes can fill 4 gigs in under a minute. Otherwise, its very clear, succint code. Well written. Not my usual approach to graph search but perhaps a bit more clear than how I do mine. My only complaint is the specification written was DFS (though I freely admit that the specification was also written to allow BFS, or even A*)

Bilou06 on June 3, 2013, 6:17 a.m.
Thank you for your long comment. I hesitated between DFS and BFS but I decided to chose BFS because these examples with a maximum width of 10 are perfect for BFS. I am solving this task, not another one. I'd be curious to compare performances with other approaches. Maybe Ckeckio will offer this feature one day.

ichaleynbin on June 3, 2013, 7:32 a.m.
Well, from a mathematical analysis of the 'infinity loop' map check, featured second up top here, we can see pretty easily that BFS is not ideal. You did well to filter out the duplicates early, however, BFS has to visit all of the 'alternative' paths as well as the ideal. With your checks, you'll still fringe ~81 nodes to find success, and explore all of them because the winner is at max depth. I believe this is the lower limit for BFS on this particular map, as given the 1,1 to 10,10 path, you must visit all open squares with BFS. If you set up DFS smart, so that it pulls south first, then east (or vice versa: given the path from 1,1 to 10,10 it makes no sense to pull north or west before the others), then you'll only fringe 36~54 nodes and explore only 18 to find the winner. BFS = 81 vs DFS = 18... case closed. I'd like to see the performance data as well, because for small instances such as this the coding itself can matter more than the big O for time. Given the numbers above, I'd only have to code slightly more than 4 times as much stuff per node, which is not wholly unreasonable. But its basic search principles that say "DFS = less memory = faster but not guaranteed optimal solution" and "BFS = more memory = slower but guaranteed optimal solution" Also, please don't take this as a critique, because its really a great solution completely within specification. I just wanted to point out that since they didn't ask for the shortest, the frugal solution when it comes to computer resources is DFS.

LostxinthexMusic on Aug. 16, 2013, 3:05 p.m.
How does this avoid getting stuck down a dead end? I did something similar (basically just forced a for loop without actually using one; I had a brain fart and couldn't figure out how to make it one), but I would get stuck in an infinite loop if there was a dead end more than one space long, so I had to change spots that were double-visited to pseudo-barriers by changing the space to 1.

Bilou06 on Aug. 19, 2013, 8:51 a.m.
There is no dead-end beacause I store any possible path in 'pathes' and drop any path that goes to a dead-end. There is no infinite loop beacause any possiblity can be added to 'pathes' only once. This is what the list 'visited' is for.

lrekucki on Aug. 23, 2013, 8:47 a.m.
This is a really bad implementation of BFS in Python. Sure, maybe efficiency is not a key aspect in 10x10 cases, but not using a set() for a visited nodes or using pop(0) on a list is just sloppy programming.

nptwz on Sept. 20, 2013, 4:08 p.m.
simple but low effiency (why not use set instead of list to store visited node)

nickie on Oct. 9, 2013, 10:50 p.m.
Simple but inefficient.

marshall.zheng on Dec. 12, 2013, 6:58 a.m.
good use case of bfs

username724 on Dec. 19, 2013, 11:41 p.m.
Do you have a python3 version of this? Or is the code portable to python3?

hang.sun.378 on Aug. 24, 2014, 10:05 a.m.
it returns one possible routine but not the best one, you can check the routine at last

russell.l.brand on Jan. 12, 2015, 9:22 p.m.
I am confused. With only append and pop, how do we get DFS rather than BFS? I see they are coming in queue order, but I don't understand why.

kaktycuha on Nov. 8, 2021, 5:38 p.m.
Not a bad solution, you only use WHILE once

vanrzuf on Jan. 21, 2022, 8:55 p.m.
quite compact

GitHub

0 %

You ClassRoom Demo is Ready With the new tool CheckiO ClassRoom, you will be able to analyze your students' progress, have your own leaderboard, change missions order on the map, and so on.