Mapping the ocean floor

Here's hoping that my games programming past comes back to help me here.

First of all, we're going to want to examine the floor. The critical bit of information we need is that for any given pair of coordinates, (x,y) we should be able to ask it for the heights of its neighbours, which will return a list like [1,1,2,3] or [1,1]. If we ask an edge or a corner for its neighbours, we'll just return the 2 or 3 neighbours.

Once we have that, we can then iterate over all the neighbours for each cell and ask if they are all greater than the current cell, if they are, we've found a "local minima".

Right, now we've got a basic grid class, we can find the lowest point.

Sadly, due to the way the Jupyter notebook works, we cannot reopen an existing class, so we have to redefine it if we want to add a method, which we do in this case. Note that we're interested in the heights of the lowest points.

We could do this two ways, the longer and more readable way is to make find_lowest_points return a list of coordinates, and then write something that maps those into heights and then adds one to each one to get the risk. Or we can put that into the Grid class as a find_risk_score. I'm going to do the latter for speed, but I think we might need to come back and create a find_lowest_points later.

Great! Let's try that on prod data

Part 2 Filling the basin

I knew I'd need the find_lowest_points.

This is described in a way that makes it look hard, but in fact it's a fairly simple search algorithm.

In this case, what they didn't say out loud, but is true when you look at the examples is that basins are enclosed on all sides by either the edge of the map, or by 9's.

So what we need to do is calculate a basin score for each lowest point, and then we can order them, take the top 3 and multiply them.

How do we calculate a basin score? Well, we can use a simple open and closed list for coordinates, and then explore. When we explore, we start with the first item from the open list, we put it on teh closed list, and then we look at it's neighbours. If they are less than 9, we put them on the open list. If they are 9, they get ignored. If they are on the closed list they are ignored, if they are already on the open list they are ignored.

Then we keep doing that until we run out of coordinates on the open list.

Let's describe that with a really simple basin

929
919
999

We start at 1,1, which is our lowest point, so open = [(1,1)] and closed is []. We put (1,1) on the closed list and remove it from the open list, resulting in open=[], closed=[(1,1)] We evaluate the neighbours of (1,1), (1,0) is 2, so we add it to the open list, (2,1) is a 9, so we skip it, (1,2) is a 9 so we skip it, and (0,1) is a 9 so we skip it. We now have just (1,0) on the open list.

We pop (1,0) on the closed list and remove it from the open list. We examine it's neighbours, (2,0) is a 9, ignore it. (1,1) is on the closed list, ignore it. (0,1) is a 9, ignore it.

Our open list is now empty, so we return, and the closed list contains all of our basin nodes.

That works, let's do this

For fun, I'd added a printing method, so let's print out the production basic. What would be nice would be if I could work out how to get Python notebook to render this as markdown, but I've got work to do today... maybe at lunch