Dijkstra's shortest path

labirynth.py

class Tile:
    def __init__(self, passable=False):
        self.passable = passable
        self.steps = float("inf")

    def __bool__(self):
        return self.passable


def create(f):
    start = None
    end = None
    tiles = [ [Tile()]*25 for i in range(25) ]

    for y, row in enumerate(f):
        for x, tile in enumerate(row.strip()):
            if tile in (' ', 'S', 'E'):
                tiles[y][x] = Tile(True)

            if tile == 'S':
                start = (y,x)

            if tile == 'E':
                end = (y,x)

    return tiles, start, end


def show(tiles, start, end, solution):
    for y, row in enumerate(tiles):
        for x, tile in enumerate(row):
            if (y,x) == start:
                print("S", end='')
            elif (y,x) == end:
                print("E", end='')
            elif (y, x) in solution:
                print("+", end='')
            elif tile:
                print(" ", end='')
            else:
                print("#", end='')
        print()

solution.py

#!/usr/bin/env python3
# encoding: utf-8

def solve(tiles, start, end, show_find, show_walk):
    # diagonal movement is forbidden
    DIRECTIONS = [ (-1,0), (0,1), (1,0), (0, -1) ]

    def find_exit(tiles, start, steps=0):
        show_find(tiles, start, end)

        # unpack coordinates
        y, x = start

        # first and foremost, save number of steps in which tile at (y,x) can
        # be reached
        tiles[y][x].steps = steps

        # if we're at the end, just stop
        if start == end:
            return

        def check_direction(dy, dx):
            # consider a direction if:
            #  - tile at (y+dy, x+dx) is passable
            #  - number of steps in which that tile can be reached is *greater*
            #    than current steps + 1
            if tiles[y+dy][x+dx] and tiles[y+dy][x+dx].steps > tiles[y][x].steps + 1:
                find_exit(tiles, (y+dy, x+dx), steps+1)

        # make sure to check all directions
        for dy, dx in DIRECTIONS:
            check_direction(dy, dx)

    # fill in table of steps
    find_exit(tiles, start)

    def walk(tiles, end):
        solution = []

        # walk the table backwards from end to to the start
        while end != start:
            y, x = end

            # save each coordinate we visit
            solution.append(end)
            show_walk(tiles, start, end, solution)

            # for each direction, find number of steps in that direction
            # steps
            candidates = {}
            for dy, dx in DIRECTIONS:
                # make sure not to leave the map ;)
                if 0 <= y+dy <= 24 and 0 <= x+dx <= 24:
                    candidates[(y+dy,x+dx)] = tiles[y+dy][x+dx].steps

            # select direction that gives us the smallest number of steps
            end = min(candidates, key=candidates.get)

        solution.append(end)
        show_walk(tiles, start, end, solution)
        return solution

    return walk(tiles, end)


if __name__ == '__main__':
    import sys
    import labirynth

    tiles, start, end = labirynth.create(open(sys.argv[1]))
    solve(tiles, start, end, labirynth.show_steps, labirynth.show_walk)