SPOILERS for Lab 1 below

In the tutorial on 2024-08-01, we discussed various approaches to solving Lab 1 (MazeAgent), and implemented some of these as we worked our way to a solution. Unfortunately, and in traditional form for live coding, my final implementation had a bug that we were not able to spot live.

Below is the code cleaned up and with the bug fixed (and with a pretty printer so we can see the map as it explores):

# The actions available to us and their effect on the state
ACTIONS = {
    'D': (0, -1),
    'U': (0, 1),
    'L': (-1, 0),
    'R': (1, 0),
}

# How to undo an action
REVERSE = {
    'D': 'U',
    'U': 'D',
    'L': 'R',
    'R': 'L',
}

class MazeAgent():
    def reset(self):
        # The sequence of actions we have (successfully) taken
        self.stack = []
        # Our last known position
        self.pos = None
        # What we know to be at various locations in the world
        # Could just be a set, but values let us print a pretty map
        self.known = {}
        # Where we expect to be if our attempted action succeeded
        self.next_pos = None

    def get_next_move(self, x, y):
        # Update pos
        prev_pos = self.pos
        self.pos = (x, y)

        # If our action failed
        if self.pos == prev_pos:
            # We know there's a wall (or edge of map) there
            self.known[self.next_pos] = '#'
            # Remove the unsuccessful action from our path
            self.stack.pop()  # THIS WAS MISSING IN TUTORIAL

        # We always know that wherever we are standing is clear
        self.known[self.pos] = '.'

        # Pretty print grid
        self.__print_grid()

        # Consider possible actions and take any we don't know the outcome of
        for d, (dx, dy) in ACTIONS.items():
            nx, ny = x + dx, y + dy
            if (nx, ny) not in self.known:
                self.next_pos = (nx, ny)
                self.stack.append(d)
                return d

        # If all action outcomes are known states, backtrack
        return REVERSE[self.stack.pop()]

    def __print_grid(self):
        for r in range(10):
            for c in range(10):
                k = (9 - r, c)
                tile = ' '
                if k == self.pos:
                    tile = 'X'
                elif k in self.known:
                    tile = self.known[k]
                print(tile, end='')
            print()

The issue was that if we attempt to make a move, and fail to do so, we were forgetting to remove that action from the history of actions taken. This meant that when we attempted to backtrack, we would undo a move that didn't need undoing, and end up losing our bread crumbs and unable to find our way back. Adding the self.stack.pop() to discard any failed moves resolved the issue. All other changes are to improve readability and should not affect behaviour.

Hopefully everyone understood the idea behind the solution despite the bug, but if you still have any questions feel free to post them here or raise them in the next tutorial.

Cheers, Gozz

Another minor error: The printer transposes the map along the diagonal. It should be k = (c, 9 - r).