branch if box clear solution for Express Delivery by DiZ - python coding challenges

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

branch if box solution in Clear category for Express Delivery by DiZ

from heapq import heappush, heappop

def checkio(field):
    dirs = {'D':(1,0), 'U':(-1,0), 'R':(0,1), 'L':(0,-1)}
    start = next((i, j) for i, l in enumerate(field) for j, c in enumerate(l) if c == 'S')
    seen, bag = set(), [(0, True, start, '')]
    while bag:
        score, cargo, (x, y), path = heappop(bag)
        if cargo and field[x][y] == 'E': return path
        seen.add((cargo, (x, y)))
        if field[x][y] == 'B':
            heappush(bag, [score + 1, not cargo, (x, y), path + 'B'])
        for direction, (u, v) in dirs.items():
            xn, yn = u + x, v + y
            if (cargo, (xn, yn)) in seen: continue
            if 0 <= xn < len(field) and 0 <= yn < len(field[0]) and field[xn][yn] != 'W':
                heappush(bag, [score + 1 + cargo, cargo, (xn, yn), path + direction])

Feb. 18, 2015

Comments:

ljy95135 on May 24, 2016, 12:20 a.m.
Great, it so succinct using heapq, getting loads of ideas to read it. It seems that headpop get the smallest item, and when it pops a path to the end, it‘s the result, can you explain more about why? Thank you!

DiZ on May 26, 2016, 9:38 p.m.
This is an heap-based Dijkstra's algorithm: it constructs the right path by testing all possibilities. Here we want in order: - The shortest time: `score` counts the minutes Stephen takes to travel from start to end (1min when you don't carry the box, and 2min when you carry it) - The box to be with Stephen at the end: `cargo` is a boolean meaning that Stephen carries the box or not. So we are going to treat the smallest paths first and we are also going to check if Sthephen has the box at the end. But when you push an element in an heap, it is inserted at the right place: all elements in heap are sorted. So popping an element returns the smallest one following our criteria, thus it returns the result.

ljy95135 on May 27, 2016, 2:31 a.m.
Yes, so cool! An improved Dijkstra's algorithm is really brilliant! Thank you.

DiZ on May 30, 2016, 1:14 p.m.
Is is called an <a href="https://en.wikipedia.org/wiki/A*_search_algorithm">A* algorithm</a> ;-)

han97 on July 31, 2016, 4:50 p.m.
It looks like Dijkstra algorithm, but i don't get it, because when in Dijsktra we check if new distance is less then we got, and only then we add it to priorityQueue, like this: <a href="https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm">https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm</a>#Usingapriority_queue

Mine

0 %

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