Dijkstra's Forever ! uncategorized solution for Open Labyrinth by Miaou - python coding challenges

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

Dijkstra's Forever ! solution in Uncategorized category for Open Labyrinth by Miaou

def checkio(labyrinth):
    # I'm definetely a fan of Dijkstra's (!!!)
    # Object oriented Dijkstra: each cell contains 3 fields
    #  (and I will not use a class for that, just a tuple)
    # which are: the distance from the beginning (cost),
    #            whether the cell is "explored" (path to this cell found),
    #            the cell before in the path from the begining.
    
    assert len(labyrinth) == 12 # ;)
    assert labyrinth[1][1] == 0 # ;)
    assert labyrinth[10][10] == 0 # ^^
    
    # 1) Init grid of cells.
    grid = [[(None,False,None)]*12 for i in range(12)]
    
    # 2) I will use a set to store the index of cell I touched but not
    #   explored yet. These are candidates to pursue my exploration.
    #   Dijkstra said : continue with the candidate which has the lowest cost.
    sCandidates = { (1,1) } # Exploration starts from there.
    grid[1][1] = (0,False,None) # Initial cell has cost 0 (beggining)
    # 3) Main loop until destination is reached !
    #   (and while there are candidates. If no more candidates:
    #    bug because destination is not reachable)
    while sCandidates and not grid[10][10][1]:
        # 3.1) Pick best candidate (lowest cost)
        i,j = min(sCandidates, key=lambda cand:grid[cand[0]][cand[1]][0])
        sCandidates.remove((i,j))
        # 3.2) Discover neighbors
        for di,dj in [(-1,0),(1,0),(0,-1),(0,1)]:
            # If neighbor is a hole, see next neigh
            if labyrinth[i+di][j+dj] == 1: continue
            # ... and if neigh is already explored too
            if grid[i+di][j+dj][1]: continue
            # If neighbor has never been seen before, then we record the path,
            #  and add it to the candidates
            if grid[i+di][j+dj][0] == None: # == None is != 0   ;)
                grid[i+di][j+dj] = (grid[i][j][0]+1,False,(i,j))
                sCandidates.add((i+di,j+dj))
            # but if neighbor is not already explored and the current path
            #  is shorter than the recorded path, then replace it
            #if grid[i][j][1] + 1 < grid[i+di][j+dj][0]:
            # (this case will never happen, due to the constant distance 1
            #  between the cells)
        grid[i][j] = (grid[i][j][0],True,grid[i][j][2]) # (i,j) is explored
    assert grid[10][10][1], "No Way Out found !!!"
    
    # 4) Rollback path: each cell contains its precedence on the path from
    #  initial cell to this cell.
    # We only have to see which cell is before destination and then before,
    #  and so on until we reach start.
    i,j = 10,10
    path = [] # Stores deltas
    while (i,j) != (1,1):
        pi,pj = grid[i][j][2]
        path.insert(0,(i-pi,j-pj))
        i,j = pi,pj
    
    # 5) Translation of the path into a string
    #  (ok, here I chose the oneline solution...)
    return ''.join( (di==-1 and 'N') or
                    (di==1 and 'S') or
                    (dj==-1 and 'W') or
                    (dj==1 and'E') for di,dj in path )
    
    


if __name__ == '__main__':
    #Return any route to exit
    print(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
    print(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]
    ]))
    print(checkio([
        [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
        [1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1],
        [1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1],
        [1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1],
        [1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1],
        [1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1],
        [1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1],
        [1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1],
        [1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1],
        [1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1],
        [1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1],
        [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
    ]))

April 22, 2013

Comments:

Miaou on April 23, 2013, 6:54 a.m.
Think about it again, storing the for each cell is also useless in this particular path-search problem !

guido on Aug. 22, 2013, 10:10 p.m.
<pre class='brush: python'>def checkio(labyrinth): # I'm definetely a fan of Dijkstra's (!!!) </pre> Funny, Dijkstra is a person, but you seem to be using his name exclusively to refer the algorithm he published. :-) <pre class='brush: python'> # Object oriented Dijkstra: each cell contains 3 fields # (and I will not use a class for that, just a tuple) </pre> Sigh. It's probably the fewest overall number of lines but doesn't make your code very readable. Also you are really treating the individual fields of the grid cell tuples as mutable variables, so you have ugly code when you want to just set the "explored" bit for a given cell (as on line 44). <pre class='brush: python'> # which are: the distance from the beginning (cost), # whether the cell is "explored" (path to this cell found), # the cell before in the path from the begining. assert len(labyrinth) == 12 # ;) assert labyrinth[1][1] == 0 # ;) assert labyrinth[10][10] == 0 # ^^ </pre> Shouldn't you also check that there are exactly 12 rows, that all their items are 0 or 1, and that there are 1s all around the labyrinth? :-) <pre class='brush: python'> # 1) Init grid of cells. grid = [[(None,False,None)]*12 for i in range(12)] </pre> Have a look at what PEP 8 says about spaces after commas. :-) BTW, checkio seems to have a lot of problems involving matrixes represented as lists of lists. The notation grid[i][j] looks kind of messy; if you were to use a single dict with tuples (i, j) as keys you could make the code look a little cleaner since you could write grid[i, j] instead. (Although the key tuples would end up being more expensive.) <pre class='brush: python'> # 2) I will use a set to store the index of cell I touched but not # explored yet. These are candidates to pursue my exploration. # Dijkstra said : continue with the candidate which has the lowest cost. sCandidates = { (1,1) } # Exploration starts from there. grid[1][1] = (0,False,None) # Initial cell has cost 0 (beggining) # 3) Main loop until destination is reached ! # (and while there are candidates. If no more candidates: # bug because destination is not reachable) </pre> I wouldn't call that a bug -- just invalid input. Given the complexity of even determining whether there is a way out or not I would almost think that the algorithm ought to have a special output in that case, rather than failing an assert. It's like a factorization algorithm -- it can also be used to determine whether the input is prime. <pre class='brush: python'> while sCandidates and not grid[10][10][1]: # 3.1) Pick best candidate (lowest cost) i,j = min(sCandidates, key=lambda cand:grid[cand[0]][cand[1]][0]) </pre> This may look compact but it actually runs kind of slow because the lambda is called for every candidate. I bet an explicit for loop over the candidates could beat it (except for the fixed size of the grid, which makes performance concerns somewhat laughable. :-) Or maybe I'm just complaining because understanding code with this many nested brackets gives me a headache. :-) <pre class='brush: python'> sCandidates.remove((i,j)) # 3.2) Discover neighbors for di,dj in [(-1,0),(1,0),(0,-1),(0,1)]: # If neighbor is a hole, see next neigh if labyrinth[i+di][j+dj] == 1: continue </pre> I wish you'd put the continue on a line by itself, that makes it easier to see while squinting that there's a conditional thing going on. BTW you could get an IndexError here if the input didn't have 1s all around the border. <pre class='brush: python'> # ... and if neigh is already explored too if grid[i+di][j+dj][1]: continue # If neighbor has never been seen before, then we record the path, # and add it to the candidates if grid[i+di][j+dj][0] == None: # == None is != 0 ;) </pre> Always use 'is' to compare to None, i.e. "is None", not "== None". <pre class='brush: python'> grid[i+di][j+dj] = (grid[i][j][0]+1,False,(i,j)) sCandidates.add((i+di,j+dj)) # but if neighbor is not already explored and the current path # is shorter than the recorded path, then replace it #if grid[i][j][1] + 1 < grid[i+di][j+dj][0]: </pre> I'm shocked. You put spaces around a binary operator. Twice in one row! :-) <pre class='brush: python'> # (this case will never happen, due to the constant distance 1 # between the cells) </pre> Heh. Did you copy this code from somewhere else? <pre class='brush: python'> grid[i][j] = (grid[i][j][0],True,grid[i][j][2]) # (i,j) is explored assert grid[10][10][1], "No Way Out found !!!" </pre> So my preference might be to return '' in this case. <pre class='brush: python'> # 4) Rollback path: each cell contains its precedence on the path from </pre> I wouldn't call that "rollback"; that word usually refers to changing some state that has been mutated to an earlier value. The phrase you're looking for is "traverse the path back" or perhaps "trace our steps back through the path". Also, "precedence" means "priority"; you meant "predecessor". (Sorry for devolving this into an English lesson. Being able to write understandable English is important if you are a programmer. :-) <pre class='brush: python'> # initial cell to this cell. # We only have to see which cell is before destination and then before, # and so on until we reach start. i,j = 10,10 path = [] # Stores deltas while (i,j) != (1,1): pi,pj = grid[i][j][2] path.insert(0,(i-pi,j-pj)) i,j = pi,pj </pre> Heh. I actually have an algorithmic suggestion here. You can use path.append(...) instead of path.insert(0, ...), and then when the loop is over write "path.reverse()" (that's a list method that reverses the list in place). That's more efficient because Python lists are optimized for append() at the end but not for insert() at the beginning. <pre class='brush: python'> # 5) Translation of the path into a string # (ok, here I chose the oneline solution...) return ''.join( (di==-1 and 'N') or (di==1 and 'S') or (dj==-1 and 'W') or (dj==1 and'E') for di,dj in path ) </pre> You can do this just as nicely with inline 'if': ''.join('N' if di == -1 else 'S' if dj == -1 else 'W' if dj == -1 else 'E' if dj == 1 else None for di, dj in path). <pre class='brush: python'> if __name__ == '__main__': #Return any route to exit print(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 print(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] ])) print(checkio([ [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], [1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1], [1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1], [1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1], [1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1], [1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1], [1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1], [1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1], [1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1], [1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1], [1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], ])) </pre> Next time, let's play "Hunt the Wumpus!"

lesenv on Oct. 3, 2013, 8:25 p.m.
i thought this algorithm was quite nice. after having read guidos post i'm feeling kind of stupid aside him. thumbs up nevertheless

chros on Nov. 7, 2013, 6:18 p.m.
wasn't the question to just find one way through the labyrinth, not necessarily the shortest one? using dijkstra for this seems a bit like "shooting with cannons on sparrows" ;-)

RyanDagg on Jan. 10, 2014, 4:51 p.m.
Nice. I have never implemented Dijstra's algorithm before, tried on this problem for a bit but got frustrated. Ended up using a left-hand approach since the mazes fit the criteria for it. Well done.

GitHub

0 %

PyCharm The Python IDE for Professional Developers. Enjoy productive Python, web and scientific development with PyCharm. Download it now!