Terminal Animation with Python

I got stuck while working on the Advent of Code Day 12, 2022 puzzle and turned to using a terminal visualization to see what was going on. This post walks through how I used the rich library in Python to figure it out.

Background

The puzzle is a grid, you are given a start point and an end point and you need to find the shortest path to the end. Each point on the grid is at a specific height and you can only travel higher 1 level.

🔔 Spoiler alert: My error was right here. It didn't say anything about traveling down by only 1 level, which I wrongly assumed. Always read the setup.

I rewrote my search algorithm 3 or 4 times thinking that was where I was making a mistake. Nope. It was the defintion of the problem.

Algorithm

The algortihm is pretty straight-forward, you start at the starting point and look at each neighbor, confirm if you can travel there and if so add them to a queue. Keep track of each spot you visit, so you don't get into an infinite loop.

Iterate over the queue popping each point off, did we find the end? Nope, check the neighbors, adding them to the queue and repeat. This will find the shortest path because each iteration over all the neighbors is one step in every possible direction. So when found it will be the shortest number of steps, since every other path will have to take more steps.

I learned this algorithm is called a breadth first search.

Visualization to see what is happening

By having the wrong test criteria I couldn't find the end point and I couldn't figure out why. I threw in a bunch of debug print statements and confirmed it was running. It worked against the sample data. 🤔

I turned to visualization to try and see what it was doing.

In Python, it is easy to update a single line of input using a \r carriage return instead of newline \n. Try this example in the REPL to illustrate:

for i in range(10):
    print(f" On step # {i}", end="\r")
    time.sleep(0.2)
print()

I wasn't quite sure how to do a multi-line animation, without using curses or a more elaborate setup.

I'd heard about the rich library that allows for building richer displays on the terminal. So looking to see if it can handle animation or live updating and sure enough it can.

To use, wrap your loop doing the calcuation in a with Live() block and do an update to redraw the grid after each new calculation.

from rich.live import Live
 
# code to draw the grid
def display_grid(visited, w, h):
    s = ""
    for y in h:
        for x in w:
            if (x,y) == end:
                s += "E"
            elif (x,y) in visited:
                s += "#"
            else:
                s += "."
        s += "\n"
    return s
 
 
with Live("", refresh_per_second=24) as live:
    while queue:
 
        # do search and update points visited
 
        live.update(display_grid(visited, w, h))
 

Using that code, I generated the first animation and could see it was searching and then stopping before finding the end.

It is working but could tell something is wrong with the criteria because it was getting stuck. I inspected the map input and looking where it was getting stuck saw that there was no path.

So like every other time I think I found a bug in Advent of Code. I went back and re-read the instructions carefully and finally realized my mistake.

The visualization really helped, showed me it was working as designed and ultimately led me to find a solution.