Day 15 - Wend and weave our winding way

I love me a path finding algorithm and this feels like a path finding algorithm problem.

This is how I got my teeth cut as a child programming computer games. I loved the earliest Hack, Nethack, Angband and Rogue games, which were available on AMInet for my Amiga for free, and since I couldn't draw, the idea of making games that just had little symbols being printed in different locations was very attractive to me. But the moment you start writing that kind of game, you'll get to a point where you need to find the path from point A to point B, or know whether it's even possible, or find a random path or similar. By the time I was 17, and I opted for the Decision and Discreete mathmatics in my A-Level, we moved onto path anaylsis and I realised that I'd been solving these problems for years, but had no formal training to understand the difference between a breadth first search and a depth first search, or who Djikstra was. I went back and devoured everything I could find on this stuff, and since then I've written these algorithms, especially A*, multiple times.

But that aside, let's properly read the days description.

So there's a few things we need to pick up here. The first is that we cannot move diagonally, so from any given location, we can only move in 4 directions, and one of those is backwards the way we came. The second is that we count nodes as we enter them.

There's a bit of mental thinking here, when we make graphs like this, we can either think of the cost being associated with the node, so the node at (1,1) has cost or risk level 3. Or we can think of the cost as being on the path that connects the node, so traversing from (1,0) or (0,1) to (1,1) will cost 3. Sometimes it doesn't make any difference, and sometimes we might start looking at things like doors, hills or other issues that occur between nodes. It can then sometimes be useful to think of the cost as being between the nodes rather than on the nodes themselves. In this case, we're going to say that the cost of moving from X node to Y node will always be the danger level of Y node. (At this point, I'm also thinking, what's the part 2 here, and I wonder if the part 2 is going to add some additional cost when we move. It would be nice to have a cost function that calculates the cost to get to a node, but it's probably an early optimisation, so I'm not going to do it).

Anyway, the final thing here is that we are looking for the path with the lowest total risk. This can also be described as the path with the lowest cost, or the shortest path. Djikstra is going to be our friend here.

There are a couple of ways we can do this, the easiest is a "breadth first search", we just brute force our way through every node, seeing if we can get there. We're going to need to think about some interesting cases, the main one being that given the following layout:

ab
cd

We can get from A to D either through b or c. Our alogorithm is going to work out teh cost to get from a->b and then from a->b->d. It'll store that cost at d becuase we've got there. Later it might try a->c->d. It will see that we've already got to d via another route, if the total cost via our route is lower than the previous routes cost, then it can update the cost on the node.

This means that as our algorithm winds it way through the map, it will keep updated on each node, the cheapest or fastest way to get from the start to that node. This will mean that when we check for the next node, we can always work out which of its cheapest neighbours it can be connected from.

But, we're only going to have partial knowledge at any given time, so as we explore the potential route, we'll be continually updating our information as we go.

Now we've got a second decision to make in this whole process, how do we select which neighbour to try visiting next? Well this is the difference that an A* algorithm normally makes. It uses an estimation of cost function, and it selects the node with the lowest estimated cost. In our case, we will estimate the cost as being 1 per node travelled, and since from any node at (x1,y1) to get to (x2,y2), if every node was a 1, the estimated cost would be by moving x2-x1 nodes across and y2-y1 nodes down. We call this the Manhatten distance, becuase the Manhatten road system is based on grids, so the cost to get from any intersection is always something like 4 up and 3 across for 7 total.

We're going to use the same approach as we used in Day 9 more or less. We can have an open list, these are all the possible locations we haven't visited yet, which are on our path. We're going to pick the location from the open list that has the lowest estimated cost. We're going to examine the location, and we're going to calculate the cost of getting here as being the cost of our predecessor, plus the cost of the location. We then need to check to see if the new cost is lower than an existing stored cost. If not, we leave it alone. If it's lower, then we change the cost and the predecessor as to where we came from. Then we add all the neighbours of the node to the open list, with an estimated cost of that node being the cost so far plus the estimated cost to the end. We keep doing this until we hit the end node, at that point, we can check the predecessor, and follow the path back trhough the cheapest routes until we hit the start and add up the cost as we go.

Final point, I note that we have no example mazes here. I'm going to use a couple of examples because it should stress test our algorithm, first the simple maze, we've added an obvious bump to it

111
331
331

The total here is 4, going right, right, down, down

Now we add one with a deliberate giant bump, so we expect the path to go round

111
339
331

The total here is likely using path right, down, down, right for 8 total.

Finally lets have a path which should involve backtracking

11111
99191
11191
19999
11111

The ideal path here is right, right, down, down, left, left, down, down, right, right, right, right, right, for 13 cost, beating right, right, right, right, down, down, down, down at 15 cost.

## Import ipytest and get it setup for use in Python Notebook
import pytest
import ipytest
ipytest.autoconfig()

First thing first, let's reuse our Grid cost from Day 9

class Grid:
    def __init__(self,width,height,cells):
        self.width = width
        self.height = height
        self.cells = cells
        
    def get_cell(self, coord):
        return self.cells[coord]
        
    def find_neighbours(self, x,y):
        neighbours = []
        if y > 0:
            neighbours.append((x,y-1))
        if x < self.width-1:
            neighbours.append((x+1,y))
        if y < self.height-1:
            neighbours.append((x,y+1))
        if x > 0:
            neighbours.append((x-1,y))
        return neighbours
        
    def display(self, highlights=[]):
        import IPython.display
        IPython.display.display("*"*self.width)
        for y in range(self.height):
            line = ""
            for x in range(self.width):
                if (x,y) in highlights:
                    line += f" **{self.get_cell((x,y))}**"
                else:
                    line += f" {self.get_cell((x,y))}"
            IPython.display.display(IPython.display.Markdown(line))   
        IPython.display.display("*"*self.width)

    def __eq__(self, other):
        return isinstance(other, Grid) and self.width == other.width and self.height==other.height and self.cells==other.cells
        
def grid_from_lines(lines):
    height = len(lines)
    width = len(lines[0])
    cells = {}
    for y,line in enumerate(lines):
        for x,cell in enumerate(line):
            cells[(x,y)] = int(cell)
    return Grid(width,height,cells)

grid1 = grid_from_lines("""111
331
331""".split("\n"))
grid1.display()

grid2 = grid_from_lines("""111
339
331""".split("\n"))
grid2.display()

grid3 = grid_from_lines("""11111
99191
11191
19999
11111""".split("\n"))
grid3.display()

'***'

1 1 1

3 3 1

3 3 1

'***'

'***'

1 1 1

3 3 9

3 3 1

'***'

'*****'

1 1 1 1 1

9 9 1 9 1

1 1 1 9 1

1 9 9 9 9

1 1 1 1 1

'*****'

Ok, we've got a grid from Day 9, so let's write out basic pathfinding function on it.

We're going to use python's heapq module, which maintains a cheap and easy sorted list, called a heap. Every node we put into it is stored as (cost, node), and heap[0] will be the smallest item. We can use heappush to add an item, and heappopto remove the smallest item. It just makes it easy to always get the smallest item.

from heapq import *

def estimate_cost(start, end):
    return abs(end[0]-start[0])+abs(end[1]-start[1])

def find_path(grid, start=None, end=None):
    if not start: start=(0,0)
    if not end: end=(grid.width-1, grid.height-1)
    nodes = {start:{"from":None, "cost":0}}
    opennodes = []
    heappush(opennodes, (estimate_cost(start,end),start))
    while opennodes:
        _, current = heappop(opennodes)
        if current == end:
            print(f"Finishing, with nodes: {nodes}")
            path = []
            while current:
                path.append(current)
                current = nodes[current]["from"]
            print(f"Finishing, with path: {path}")
            return path

        cost = nodes[current]["cost"]
        print(f"Checking {current} with cost {cost}")
        for neighbour in grid.find_neighbours(current[0],current[1]):
            thiscost = cost+grid.get_cell(neighbour) # How much it costs to get to this neighbour from the current node
            estcost = thiscost + estimate_cost(neighbour,end) # This cost, plus how much we think it'll get to the end
            neighbourtuple = (estcost, neighbour)
            if neighbour not in nodes or thiscost < nodes[neighbour]["cost"]:
                # We've never seen neighbour, so any cost is lower or
                # It's cheaper to get there than any previous cost we looked at
                nodes[neighbour] = {"from":current, "cost":thiscost}
                print(f"  Setting nodes[{neighbour}] to {nodes[neighbour]}")
                if neighbourtuple not in opennodes:
                    print(f"  Adding {neighbourtuple} to opennodes")
                    heappush(opennodes, neighbourtuple)
            else:
                print(f"  Ignoring {neighbour} at cost {cost} as {nodes[neighbour]} is smaller cost")
    print(f"Ran out of nodes looking for {end}, nodes is {nodes}")

find_path(grid1)

Checking (0, 0) with cost 0
  Setting nodes[(1, 0)] to {'from': (0, 0), 'cost': 1}
  Adding (4, (1, 0)) to opennodes
  Setting nodes[(0, 1)] to {'from': (0, 0), 'cost': 3}
  Adding (6, (0, 1)) to opennodes
Checking (1, 0) with cost 1
  Setting nodes[(2, 0)] to {'from': (1, 0), 'cost': 2}
  Adding (4, (2, 0)) to opennodes
  Setting nodes[(1, 1)] to {'from': (1, 0), 'cost': 4}
  Adding (6, (1, 1)) to opennodes
  Ignoring (0, 0) at cost 1 as {'from': None, 'cost': 0} is smaller cost
Checking (2, 0) with cost 2
  Setting nodes[(2, 1)] to {'from': (2, 0), 'cost': 3}
  Adding (4, (2, 1)) to opennodes
  Ignoring (1, 0) at cost 2 as {'from': (0, 0), 'cost': 1} is smaller cost
Checking (2, 1) with cost 3
  Ignoring (2, 0) at cost 3 as {'from': (1, 0), 'cost': 2} is smaller cost
  Setting nodes[(2, 2)] to {'from': (2, 1), 'cost': 4}
  Adding (4, (2, 2)) to opennodes
  Ignoring (1, 1) at cost 3 as {'from': (1, 0), 'cost': 4} is smaller cost
Finishing, with nodes: {(0, 0): {'from': None, 'cost': 0}, (1, 0): {'from': (0, 0), 'cost': 1}, (0, 1): {'from': (0, 0), 'cost': 3}, (2, 0): {'from': (1, 0), 'cost': 2}, (1, 1): {'from': (1, 0), 'cost': 4}, (2, 1): {'from': (2, 0), 'cost': 3}, (2, 2): {'from': (2, 1), 'cost': 4}}
Finishing, with path: [(2, 2), (2, 1), (2, 0), (1, 0), (0, 0)]

[(2, 2), (2, 1), (2, 0), (1, 0), (0, 0)]

It's been a long time since I last implemented that, so I've left the debugging lines in so you can see how I played with it. Couple of gotchas for me in that process.

1. the last node is at height-1, width-1 not height-width, that made it search the whole system and decide there was no path (hence the ran out of nodes, that "looking for {end}" was me trying to work out why I kept running out)
2. The heap holds a tuple of (estimatedcost, coordinate) but everything else looks stuff up by coordinate. that estimated cost I now ignore when popping from the heap because it's one and only purpose is to help us try to find the most effective route, so we don't use it for anything else.2
3. I had to refactor thiscost, estcost out becuase I kept using the wrong one.

Guess we can try that on our other two test paths, and then I'll rewrite it without the debugging

grid2.display(find_path(grid2))
print("")
grid3.display(find_path(grid3))

Checking (0, 0) with cost 0
  Setting nodes[(1, 0)] to {'from': (0, 0), 'cost': 1}
  Adding (4, (1, 0)) to opennodes
  Setting nodes[(0, 1)] to {'from': (0, 0), 'cost': 3}
  Adding (6, (0, 1)) to opennodes
Checking (1, 0) with cost 1
  Setting nodes[(2, 0)] to {'from': (1, 0), 'cost': 2}
  Adding (4, (2, 0)) to opennodes
  Setting nodes[(1, 1)] to {'from': (1, 0), 'cost': 4}
  Adding (6, (1, 1)) to opennodes
  Ignoring (0, 0) at cost 1 as {'from': None, 'cost': 0} is smaller cost
Checking (2, 0) with cost 2
  Setting nodes[(2, 1)] to {'from': (2, 0), 'cost': 11}
  Adding (12, (2, 1)) to opennodes
  Ignoring (1, 0) at cost 2 as {'from': (0, 0), 'cost': 1} is smaller cost
Checking (0, 1) with cost 3
  Ignoring (0, 0) at cost 3 as {'from': None, 'cost': 0} is smaller cost
  Ignoring (1, 1) at cost 3 as {'from': (1, 0), 'cost': 4} is smaller cost
  Setting nodes[(0, 2)] to {'from': (0, 1), 'cost': 6}
  Adding (8, (0, 2)) to opennodes
Checking (1, 1) with cost 4
  Ignoring (1, 0) at cost 4 as {'from': (0, 0), 'cost': 1} is smaller cost
  Ignoring (2, 1) at cost 4 as {'from': (2, 0), 'cost': 11} is smaller cost
  Setting nodes[(1, 2)] to {'from': (1, 1), 'cost': 7}
  Adding (8, (1, 2)) to opennodes
  Ignoring (0, 1) at cost 4 as {'from': (0, 0), 'cost': 3} is smaller cost
Checking (0, 2) with cost 6
  Ignoring (0, 1) at cost 6 as {'from': (0, 0), 'cost': 3} is smaller cost
  Ignoring (1, 2) at cost 6 as {'from': (1, 1), 'cost': 7} is smaller cost
Checking (1, 2) with cost 7
  Ignoring (1, 1) at cost 7 as {'from': (1, 0), 'cost': 4} is smaller cost
  Setting nodes[(2, 2)] to {'from': (1, 2), 'cost': 8}
  Adding (8, (2, 2)) to opennodes
  Ignoring (0, 2) at cost 7 as {'from': (0, 1), 'cost': 6} is smaller cost
Finishing, with nodes: {(0, 0): {'from': None, 'cost': 0}, (1, 0): {'from': (0, 0), 'cost': 1}, (0, 1): {'from': (0, 0), 'cost': 3}, (2, 0): {'from': (1, 0), 'cost': 2}, (1, 1): {'from': (1, 0), 'cost': 4}, (2, 1): {'from': (2, 0), 'cost': 11}, (0, 2): {'from': (0, 1), 'cost': 6}, (1, 2): {'from': (1, 1), 'cost': 7}, (2, 2): {'from': (1, 2), 'cost': 8}}
Finishing, with path: [(2, 2), (1, 2), (1, 1), (1, 0), (0, 0)]

'***'

1 1 1

3 3 9

3 3 1

'***'

Checking (0, 0) with cost 0
  Setting nodes[(1, 0)] to {'from': (0, 0), 'cost': 1}
  Adding (8, (1, 0)) to opennodes
  Setting nodes[(0, 1)] to {'from': (0, 0), 'cost': 9}
  Adding (16, (0, 1)) to opennodes
Checking (1, 0) with cost 1
  Setting nodes[(2, 0)] to {'from': (1, 0), 'cost': 2}
  Adding (8, (2, 0)) to opennodes
  Setting nodes[(1, 1)] to {'from': (1, 0), 'cost': 10}
  Adding (16, (1, 1)) to opennodes
  Ignoring (0, 0) at cost 1 as {'from': None, 'cost': 0} is smaller cost
Checking (2, 0) with cost 2
  Setting nodes[(3, 0)] to {'from': (2, 0), 'cost': 3}
  Adding (8, (3, 0)) to opennodes
  Setting nodes[(2, 1)] to {'from': (2, 0), 'cost': 3}
  Adding (8, (2, 1)) to opennodes
  Ignoring (1, 0) at cost 2 as {'from': (0, 0), 'cost': 1} is smaller cost
Checking (2, 1) with cost 3
  Ignoring (2, 0) at cost 3 as {'from': (1, 0), 'cost': 2} is smaller cost
  Setting nodes[(3, 1)] to {'from': (2, 1), 'cost': 12}
  Adding (16, (3, 1)) to opennodes
  Setting nodes[(2, 2)] to {'from': (2, 1), 'cost': 4}
  Adding (8, (2, 2)) to opennodes
  Ignoring (1, 1) at cost 3 as {'from': (1, 0), 'cost': 10} is smaller cost
Checking (2, 2) with cost 4
  Ignoring (2, 1) at cost 4 as {'from': (2, 0), 'cost': 3} is smaller cost
  Setting nodes[(3, 2)] to {'from': (2, 2), 'cost': 13}
  Adding (16, (3, 2)) to opennodes
  Setting nodes[(2, 3)] to {'from': (2, 2), 'cost': 13}
  Adding (16, (2, 3)) to opennodes
  Setting nodes[(1, 2)] to {'from': (2, 2), 'cost': 5}
  Adding (10, (1, 2)) to opennodes
Checking (3, 0) with cost 3
  Setting nodes[(4, 0)] to {'from': (3, 0), 'cost': 4}
  Adding (8, (4, 0)) to opennodes
  Ignoring (3, 1) at cost 3 as {'from': (2, 1), 'cost': 12} is smaller cost
  Ignoring (2, 0) at cost 3 as {'from': (1, 0), 'cost': 2} is smaller cost
Checking (4, 0) with cost 4
  Setting nodes[(4, 1)] to {'from': (4, 0), 'cost': 5}
  Adding (8, (4, 1)) to opennodes
  Ignoring (3, 0) at cost 4 as {'from': (2, 0), 'cost': 3} is smaller cost
Checking (4, 1) with cost 5
  Ignoring (4, 0) at cost 5 as {'from': (3, 0), 'cost': 4} is smaller cost
  Setting nodes[(4, 2)] to {'from': (4, 1), 'cost': 6}
  Adding (8, (4, 2)) to opennodes
  Ignoring (3, 1) at cost 5 as {'from': (2, 1), 'cost': 12} is smaller cost
Checking (4, 2) with cost 6
  Ignoring (4, 1) at cost 6 as {'from': (4, 0), 'cost': 5} is smaller cost
  Setting nodes[(4, 3)] to {'from': (4, 2), 'cost': 15}
  Adding (16, (4, 3)) to opennodes
  Ignoring (3, 2) at cost 6 as {'from': (2, 2), 'cost': 13} is smaller cost
Checking (1, 2) with cost 5
  Ignoring (1, 1) at cost 5 as {'from': (1, 0), 'cost': 10} is smaller cost
  Ignoring (2, 2) at cost 5 as {'from': (2, 1), 'cost': 4} is smaller cost
  Setting nodes[(1, 3)] to {'from': (1, 2), 'cost': 14}
  Adding (18, (1, 3)) to opennodes
  Setting nodes[(0, 2)] to {'from': (1, 2), 'cost': 6}
  Adding (12, (0, 2)) to opennodes
Checking (0, 2) with cost 6
  Ignoring (0, 1) at cost 6 as {'from': (0, 0), 'cost': 9} is smaller cost
  Ignoring (1, 2) at cost 6 as {'from': (2, 2), 'cost': 5} is smaller cost
  Setting nodes[(0, 3)] to {'from': (0, 2), 'cost': 7}
  Adding (12, (0, 3)) to opennodes
Checking (0, 3) with cost 7
  Ignoring (0, 2) at cost 7 as {'from': (1, 2), 'cost': 6} is smaller cost
  Ignoring (1, 3) at cost 7 as {'from': (1, 2), 'cost': 14} is smaller cost
  Setting nodes[(0, 4)] to {'from': (0, 3), 'cost': 8}
  Adding (12, (0, 4)) to opennodes
Checking (0, 4) with cost 8
  Ignoring (0, 3) at cost 8 as {'from': (0, 2), 'cost': 7} is smaller cost
  Setting nodes[(1, 4)] to {'from': (0, 4), 'cost': 9}
  Adding (12, (1, 4)) to opennodes
Checking (1, 4) with cost 9
  Ignoring (1, 3) at cost 9 as {'from': (1, 2), 'cost': 14} is smaller cost
  Setting nodes[(2, 4)] to {'from': (1, 4), 'cost': 10}
  Adding (12, (2, 4)) to opennodes
  Ignoring (0, 4) at cost 9 as {'from': (0, 3), 'cost': 8} is smaller cost
Checking (2, 4) with cost 10
  Ignoring (2, 3) at cost 10 as {'from': (2, 2), 'cost': 13} is smaller cost
  Setting nodes[(3, 4)] to {'from': (2, 4), 'cost': 11}
  Adding (12, (3, 4)) to opennodes
  Ignoring (1, 4) at cost 10 as {'from': (0, 4), 'cost': 9} is smaller cost
Checking (3, 4) with cost 11
  Setting nodes[(3, 3)] to {'from': (3, 4), 'cost': 20}
  Adding (22, (3, 3)) to opennodes
  Setting nodes[(4, 4)] to {'from': (3, 4), 'cost': 12}
  Adding (12, (4, 4)) to opennodes
  Ignoring (2, 4) at cost 11 as {'from': (1, 4), 'cost': 10} is smaller cost
Finishing, with nodes: {(0, 0): {'from': None, 'cost': 0}, (1, 0): {'from': (0, 0), 'cost': 1}, (0, 1): {'from': (0, 0), 'cost': 9}, (2, 0): {'from': (1, 0), 'cost': 2}, (1, 1): {'from': (1, 0), 'cost': 10}, (3, 0): {'from': (2, 0), 'cost': 3}, (2, 1): {'from': (2, 0), 'cost': 3}, (3, 1): {'from': (2, 1), 'cost': 12}, (2, 2): {'from': (2, 1), 'cost': 4}, (3, 2): {'from': (2, 2), 'cost': 13}, (2, 3): {'from': (2, 2), 'cost': 13}, (1, 2): {'from': (2, 2), 'cost': 5}, (4, 0): {'from': (3, 0), 'cost': 4}, (4, 1): {'from': (4, 0), 'cost': 5}, (4, 2): {'from': (4, 1), 'cost': 6}, (4, 3): {'from': (4, 2), 'cost': 15}, (1, 3): {'from': (1, 2), 'cost': 14}, (0, 2): {'from': (1, 2), 'cost': 6}, (0, 3): {'from': (0, 2), 'cost': 7}, (0, 4): {'from': (0, 3), 'cost': 8}, (1, 4): {'from': (0, 4), 'cost': 9}, (2, 4): {'from': (1, 4), 'cost': 10}, (3, 4): {'from': (2, 4), 'cost': 11}, (3, 3): {'from': (3, 4), 'cost': 20}, (4, 4): {'from': (3, 4), 'cost': 12}}
Finishing, with path: [(4, 4), (3, 4), (2, 4), (1, 4), (0, 4), (0, 3), (0, 2), (1, 2), (2, 2), (2, 1), (2, 0), (1, 0), (0, 0)]

'*****'

1 1 1 1 1

9 9 1 9 1

1 1 1 9 1

1 9 9 9 9

1 1 1 1 1

'*****'

Fabulous, that seems to work, lets try it on the test data and then the production data

def find_path(grid, start=None, end=None):
    if not start: start=(0,0)
    if not end: end=(grid.width-1, grid.height-1)
    nodes = {start:{"from":None, "cost":0}}
    opennodes = []
    heappush(opennodes, (estimate_cost(start,end),start))
    while opennodes:
        _, current = heappop(opennodes)
        if current == end:
            path = []
            while current:
                path.append(current)
                current = nodes[current]["from"]
            return path

        cost = nodes[current]["cost"]
        for neighbour in grid.find_neighbours(current[0],current[1]):
            thiscost = cost+grid.get_cell(neighbour) # How much it costs to get to this neighbour from the current node
            estcost = thiscost + estimate_cost(neighbour,end) # This cost, plus how much we think it'll get to the end
            neighbourtuple = (estcost, neighbour)
            if neighbour not in nodes or thiscost < nodes[neighbour]["cost"]:
                nodes[neighbour] = {"from":current, "cost":thiscost}
                if neighbourtuple not in opennodes:
                    heappush(opennodes, neighbourtuple)
    return []

testgrid = grid_from_lines("""1163751742
1381373672
2136511328
3694931569
7463417111
1319128137
1359912421
3125421639
1293138521
2311944581""".split("\n"))

path = find_path(testgrid)
testgrid.display(path)
print(path)
# Exclude the start from the path, which is the last item as our path is backwards
print(sum([testgrid.get_cell(coord) for coord in path[:-1]]))

'**********'

1 1 6 3 7 5 1 7 4 2

1 3 8 1 3 7 3 6 7 2

2 1 3 6 5 1 1 3 2 8

3 6 9 4 9 3 1 5 6 9

7 4 6 3 4 1 7 1 1 1

1 3 1 9 1 2 8 1 3 7

1 3 5 9 9 1 2 4 2 1

3 1 2 5 4 2 1 6 3 9

1 2 9 3 1 3 8 5 2 1

2 3 1 1 9 4 4 5 8 1

'**********'

[(9, 9), (9, 8), (8, 8), (8, 7), (8, 6), (8, 5), (7, 5), (7, 4), (7, 3), (6, 3), (6, 2), (5, 2), (4, 2), (3, 2), (2, 2), (1, 2), (0, 2), (0, 1), (0, 0)]
40

Now for production data

grid = grid_from_lines([line.strip() for line in open("day15.txt")])

path = find_path(grid)
grid.display(path)
print(path)
# Exclude the start from the path, which is the last item as our path is backwards
print(sum([grid.get_cell(coord) for coord in path[:-1]]))

'****************************************************************************************************'

9 9 3 7 9 1 3 6 1 3 4 8 9 5 7 9 6 8 9 8 8 7 8 9 9 8 3 9 7 1 8 6 5 9 9 4 9 1 4 4 4 8 3 8 9 3 8 7 4 7 4 9 8 5 8 3 6 6 6 8 1 2 3 2 6 9 9 9 1 1 1 9 6 8 5 1 9 1 9 8 2 4 1 9 7 3 9 1 5 9 8 6 9 6 7 1 2 3 6 8

5 2 5 3 9 1 8 3 9 6 5 9 8 2 4 1 9 6 2 9 8 5 9 8 6 9 9 2 4 2 8 8 1 4 8 7 5 9 9 3 8 8 9 4 2 8 7 1 7 5 5 7 9 3 9 5 2 9 5 8 8 8 2 7 6 8 5 1 6 9 5 8 8 3 8 1 1 9 4 9 9 2 9 8 9 4 8 2 7 3 7 8 9 5 7 2 9 9 4 1

4 7 2 9 8 9 1 9 9 3 6 5 9 8 6 9 3 5 1 6 9 9 1 9 5 9 7 8 1 8 9 9 4 8 8 9 7 7 9 9 3 4 6 5 7 7 4 9 8 6 5 9 7 3 6 9 9 9 2 6 9 1 7 1 6 8 9 9 9 9 8 8 8 1 5 9 8 3 6 9 3 7 7 4 8 6 8 1 1 6 9 6 6 7 2 4 2 5 9 2

9 1 2 9 2 7 5 9 8 7 8 7 9 2 9 2 2 3 5 9 8 5 7 8 2 7 7 1 9 1 9 1 9 8 4 8 9 1 6 4 6 9 4 9 3 2 8 9 7 3 1 7 9 9 8 7 9 9 3 6 6 8 1 8 4 9 8 6 4 9 1 8 9 1 9 6 1 7 8 8 5 4 8 9 1 1 2 5 1 9 9 7 4 9 8 6 9 1 9 4

9 6 4 2 4 2 8 9 6 8 6 4 9 5 1 6 4 9 9 9 7 7 2 5 3 9 2 1 6 5 2 5 8 6 9 7 8 6 9 8 8 4 9 9 9 9 1 7 7 2 8 2 4 1 4 6 3 9 9 9 9 3 1 9 7 7 5 8 8 1 9 3 9 9 9 9 4 7 4 7 9 3 7 9 4 4 2 9 6 2 7 9 9 9 4 4 9 7 5 9

3 4 5 7 8 4 7 6 8 5 1 5 2 9 1 9 5 7 8 7 3 7 7 1 6 7 2 5 3 9 8 1 4 5 7 8 8 5 9 2 5 6 7 8 1 9 9 9 7 1 1 9 8 6 9 9 4 1 5 9 8 8 4 8 9 7 9 8 4 8 8 8 4 9 7 9 7 3 9 7 5 9 9 2 9 9 8 7 5 4 9 1 3 8 6 7 4 4 4 6

1 9 2 4 9 5 9 2 6 8 4 9 7 8 8 3 9 8 8 4 7 8 7 9 9 9 9 8 4 8 6 8 9 8 9 6 7 6 3 8 8 6 3 9 6 9 7 9 9 9 6 9 9 9 8 8 7 9 9 9 7 4 2 6 2 8 3 8 6 9 9 3 5 8 9 1 2 1 7 9 9 7 9 6 3 5 8 1 5 7 6 9 9 9 4 7 7 5 7 7

9 7 6 9 6 9 9 2 9 1 5 5 1 9 8 3 7 9 7 2 8 5 9 9 9 7 4 1 9 7 1 5 8 3 3 3 5 1 2 9 4 9 1 6 8 8 6 8 9 6 5 9 1 7 5 3 9 3 8 5 2 9 6 9 8 3 9 3 1 1 7 8 4 9 9 6 9 8 9 1 8 7 9 7 6 9 7 6 1 1 7 1 1 1 7 4 4 9 8 9

8 7 7 4 3 8 9 5 9 3 4 9 3 8 9 6 7 2 2 9 9 4 7 1 6 8 9 5 9 8 9 7 9 7 9 5 4 3 6 9 9 8 8 8 4 9 8 8 1 7 9 9 3 2 9 6 9 9 1 7 2 5 9 5 5 8 7 9 7 4 2 4 1 8 9 5 3 7 5 9 7 8 5 1 6 7 9 7 4 1 3 1 7 8 8 9 8 1 7 7

7 7 5 7 5 9 6 1 3 9 7 2 6 2 6 8 8 4 1 7 8 7 8 2 7 2 6 6 6 9 3 9 4 5 4 8 9 7 1 1 8 7 7 4 7 9 6 9 9 6 6 9 1 6 2 3 3 7 8 8 7 2 9 8 6 5 9 9 7 1 7 6 5 2 9 1 9 9 1 1 7 6 5 9 8 6 1 9 9 8 8 8 7 9 4 5 8 9 9 2

9 7 8 1 7 8 9 9 9 8 1 5 8 7 6 5 5 9 4 3 1 8 5 9 9 4 6 5 8 9 1 6 9 7 9 5 7 2 7 6 4 3 1 1 9 9 6 5 1 9 2 7 9 6 2 9 1 8 4 9 9 7 9 8 2 4 2 7 1 9 5 9 9 8 5 8 4 5 8 9 9 6 9 9 9 6 4 2 2 5 8 1 7 5 7 5 8 6 8 7

8 9 8 4 9 3 8 6 3 1 9 8 4 9 9 9 9 9 1 8 7 3 8 3 2 9 9 2 9 8 8 2 1 7 9 7 7 5 7 7 9 7 8 9 8 8 1 5 9 7 9 8 9 8 6 9 9 9 1 7 8 8 5 1 9 9 8 3 5 9 9 8 9 6 9 8 4 8 7 4 4 8 9 9 9 5 7 9 6 7 3 3 9 9 7 7 4 8 9 7

1 6 6 1 3 9 7 7 9 8 9 8 2 4 9 6 1 9 4 2 7 5 2 9 8 4 9 5 8 7 9 9 9 9 7 9 4 6 8 9 9 1 4 9 1 1 1 7 8 6 2 9 7 3 2 7 2 3 2 8 8 3 9 1 8 4 7 4 7 9 8 9 6 5 9 8 5 8 3 1 2 6 7 8 8 7 7 4 8 7 9 7 9 6 2 6 5 7 9 9

9 2 8 1 1 4 8 9 6 9 8 8 9 4 6 5 8 8 4 1 8 7 7 5 6 9 2 7 9 9 1 1 8 6 4 7 5 9 2 9 9 9 9 4 4 4 1 7 7 9 8 9 8 9 8 3 1 7 7 6 9 9 9 9 1 6 4 8 8 9 3 9 9 9 5 7 9 6 9 7 9 9 5 8 6 6 9 9 8 4 9 1 5 9 5 2 5 6 7 8

9 5 8 3 3 6 8 9 1 9 9 9 6 9 3 8 1 9 6 8 9 9 4 7 2 9 9 8 3 8 2 9 9 6 6 9 7 5 3 6 9 7 9 9 9 1 9 8 2 9 9 9 3 6 5 9 5 4 5 1 6 2 8 6 9 7 5 8 9 6 7 7 9 9 3 8 8 9 1 5 5 1 8 1 9 9 9 9 8 6 8 4 9 9 4 3 9 1 9 2

4 9 9 6 6 9 9 7 7 9 1 7 9 6 4 2 9 7 2 9 2 9 1 8 7 9 3 6 8 7 1 7 9 9 2 1 8 9 3 3 9 6 2 3 7 9 9 9 9 2 7 1 1 9 4 1 5 4 8 3 1 9 7 8 1 9 8 9 9 9 6 8 7 8 8 7 8 3 3 3 8 7 1 9 7 8 9 3 7 8 7 7 8 9 9 8 9 9 7 2

2 9 6 2 9 5 4 9 2 4 1 8 5 9 2 8 5 2 9 5 4 4 7 4 2 1 4 5 7 9 4 9 3 7 8 5 1 9 9 1 8 8 9 1 4 4 8 8 9 7 9 5 1 9 9 5 9 4 9 7 7 7 7 6 3 2 8 9 9 9 9 7 7 9 6 6 2 9 9 5 1 6 9 4 8 2 8 1 7 5 9 8 3 6 4 2 2 9 8 7

4 9 9 8 9 7 9 8 7 9 4 8 9 6 5 1 7 9 8 4 9 5 8 2 1 6 9 8 9 1 9 1 1 5 9 6 8 9 2 9 9 9 5 3 9 4 9 9 9 1 8 2 1 8 4 9 3 8 5 2 9 1 6 3 5 4 1 8 4 7 1 1 6 8 1 9 9 9 3 9 7 8 9 8 5 6 9 9 6 8 8 8 4 1 6 7 9 1 4 5

1 5 9 4 3 3 7 5 1 3 9 7 1 1 8 9 1 9 6 8 9 1 6 1 2 4 9 3 9 8 9 3 9 4 8 3 3 8 7 7 6 8 8 8 8 9 4 9 9 9 7 9 9 5 4 8 7 8 9 5 8 7 9 9 6 9 4 7 4 6 8 9 5 9 1 7 8 9 9 9 6 3 9 5 9 1 8 8 4 8 4 6 8 8 8 5 9 8 9 9

9 1 1 9 5 3 5 2 5 7 7 7 9 7 4 4 9 9 9 9 7 7 1 9 7 6 9 5 1 5 2 5 6 4 8 9 8 8 7 6 9 4 1 9 1 5 2 6 2 8 9 1 9 7 7 6 6 9 9 9 7 8 7 4 4 6 9 9 6 6 9 9 6 9 1 2 6 8 9 9 3 1 8 1 5 8 3 9 9 9 9 5 8 2 9 1 9 1 1 9

9 9 5 9 8 9 1 8 9 9 9 8 9 9 2 5 3 9 4 9 8 1 2 8 3 6 5 3 2 8 9 8 6 9 9 9 5 8 8 1 9 1 9 7 7 8 5 7 8 5 1 9 9 9 2 7 8 8 4 9 2 8 3 7 9 8 4 5 9 2 6 7 7 9 7 2 9 9 8 5 1 5 4 8 9 7 9 8 1 9 8 6 9 1 1 5 4 9 9 8

9 4 2 9 9 8 9 9 9 1 6 5 8 9 8 9 8 9 9 9 8 5 9 6 9 6 9 9 9 9 6 8 9 5 9 9 8 9 6 3 7 8 9 7 1 1 9 9 7 5 9 8 1 8 4 7 3 8 1 3 8 4 2 3 8 6 4 5 9 9 2 9 5 5 8 9 7 6 7 8 9 2 2 3 5 7 2 6 2 5 6 6 9 9 9 2 8 2 3 8

9 1 9 9 9 6 2 1 9 1 9 3 9 3 9 8 5 9 8 7 5 1 9 5 9 6 8 5 2 9 2 1 7 1 9 8 8 8 6 5 1 9 4 9 5 4 9 9 9 5 8 6 9 6 8 9 4 6 2 9 9 9 9 8 2 1 2 9 8 9 1 4 7 8 8 8 6 8 6 6 5 4 8 4 7 6 9 9 3 8 9 6 2 9 4 6 9 6 5 7

7 1 7 9 3 3 6 7 5 1 9 8 5 7 6 4 5 9 9 9 3 2 7 9 1 1 9 2 2 5 6 9 9 8 9 2 9 8 3 9 6 7 1 9 6 7 2 9 4 9 2 2 6 9 9 7 2 8 1 4 9 8 9 9 6 3 3 6 1 8 6 9 5 5 9 1 6 9 8 8 5 9 1 9 1 4 1 9 4 5 1 9 3 6 7 8 8 9 2 1

8 9 3 2 7 8 5 9 9 9 3 6 7 8 4 4 3 8 6 3 9 5 9 8 4 9 9 3 6 5 9 8 1 9 2 9 9 9 4 9 8 9 7 7 2 9 9 7 9 1 1 8 9 7 2 7 9 7 8 1 9 3 9 9 8 7 5 8 9 6 4 7 9 9 4 8 9 5 2 2 6 7 4 6 7 4 3 7 9 4 8 2 5 1 2 8 3 3 9 9

9 5 7 4 6 5 9 7 4 9 3 9 4 8 6 6 9 2 1 5 9 8 1 9 8 7 6 3 7 7 8 5 8 9 9 9 7 3 9 9 4 8 7 9 8 8 2 8 9 2 4 8 7 6 3 1 1 1 7 9 3 8 9 7 8 2 2 4 5 4 9 5 5 7 4 1 5 4 1 6 8 9 1 8 9 5 9 7 8 8 9 4 9 8 8 5 7 3 8 9

8 3 9 3 8 9 6 8 9 5 5 7 3 8 6 2 9 6 9 3 1 8 8 1 4 8 9 8 9 6 7 9 9 9 8 7 8 9 8 6 9 4 6 6 8 9 8 9 9 6 9 8 1 9 9 8 5 4 6 2 9 1 1 8 9 9 1 7 7 6 6 9 7 9 8 2 9 8 9 9 9 9 8 4 9 9 8 9 8 9 1 7 7 8 8 7 6 9 9 9

4 9 5 4 8 9 8 1 4 5 7 3 4 9 9 3 3 4 9 1 8 9 3 8 4 1 7 8 4 2 2 9 2 8 7 8 1 7 8 8 9 7 7 7 6 8 2 8 3 4 3 9 2 1 3 3 8 6 9 3 8 7 6 6 9 7 1 3 6 3 8 2 2 1 8 5 7 8 8 9 6 9 9 8 9 4 1 4 6 9 4 1 1 7 8 8 1 9 5 4

7 1 8 9 9 7 9 6 7 5 8 9 3 1 6 2 9 9 8 8 1 9 5 9 6 8 1 9 8 9 6 8 9 7 3 7 9 7 9 9 9 2 8 9 1 8 9 2 8 8 9 7 1 6 9 9 8 3 9 8 9 5 6 7 6 5 6 3 7 9 8 9 6 6 6 4 9 6 9 1 8 6 9 8 9 8 5 8 4 7 2 5 1 4 9 8 9 3 2 9

5 7 5 1 9 9 7 2 9 9 5 4 4 8 4 9 9 1 7 4 9 6 9 3 9 6 8 9 7 1 8 6 9 1 6 8 5 4 6 8 6 2 9 8 3 3 3 5 2 5 2 8 6 7 8 1 9 6 2 9 9 6 6 9 4 5 8 7 4 9 9 9 7 9 5 3 8 4 6 3 2 5 9 4 3 9 2 9 9 4 2 3 7 9 6 7 9 7 8 9

3 9 5 1 4 1 9 8 5 7 7 4 5 9 4 8 5 4 6 8 6 4 4 9 8 1 9 1 4 6 6 6 9 5 9 6 9 4 8 9 9 2 6 9 9 9 9 7 7 4 9 1 4 7 7 1 7 7 8 7 3 8 8 1 8 7 8 3 9 9 6 8 3 9 8 5 8 9 8 5 1 6 7 9 1 8 1 9 2 1 3 7 5 3 2 9 9 9 8 7

9 3 9 3 9 5 4 1 5 4 1 1 1 7 6 9 1 1 6 3 1 1 6 4 2 8 8 4 8 1 5 7 6 6 4 8 7 5 6 4 7 8 8 9 9 2 4 4 3 9 4 7 9 9 9 1 6 5 8 8 7 1 4 9 8 1 5 7 4 8 8 9 4 1 1 9 9 8 6 8 9 9 9 3 9 9 8 9 5 5 7 6 6 8 9 2 7 8 1 5

7 7 8 1 9 4 9 9 8 7 8 8 5 1 2 1 9 9 1 9 9 9 8 8 2 4 8 3 8 1 8 9 2 8 3 4 2 8 7 3 9 4 7 8 1 7 3 8 2 6 6 9 8 1 5 3 9 1 6 5 5 1 6 1 8 1 9 8 9 2 1 7 9 3 4 9 6 8 3 9 2 5 9 5 3 7 1 8 6 4 9 5 1 7 3 9 6 9 9 8

9 9 9 6 9 4 8 9 4 8 4 2 1 8 9 9 5 9 6 7 1 1 7 2 7 7 3 1 4 4 9 3 2 9 9 6 8 9 8 1 9 4 7 8 7 9 8 9 2 9 4 9 9 9 8 9 7 9 5 2 7 6 9 5 6 9 9 9 6 8 5 9 4 4 6 8 6 7 3 1 9 9 9 1 9 4 8 5 6 6 2 8 3 4 3 8 7 3 7 4

2 9 5 5 8 5 7 8 1 8 4 3 8 2 4 4 2 3 9 3 4 5 9 1 7 6 3 1 9 6 3 9 4 4 6 6 4 8 6 9 3 8 5 9 7 5 9 7 3 5 5 1 3 9 5 9 5 4 8 6 7 9 9 9 9 5 8 7 4 2 1 8 2 7 8 2 9 2 9 6 9 3 9 9 9 2 7 9 1 1 9 8 8 6 9 8 9 1 9 9

1 9 3 5 7 7 9 4 8 1 3 6 8 8 1 9 3 9 9 8 9 9 2 9 5 9 3 2 7 4 9 1 2 9 9 1 9 9 2 9 1 2 2 5 6 4 7 8 9 7 9 8 9 7 7 4 9 6 9 5 8 1 1 8 2 7 4 3 4 1 9 6 8 9 2 9 9 3 5 6 1 2 8 9 9 3 7 9 8 9 6 9 9 9 4 3 4 7 3 9

9 9 9 9 3 7 9 9 8 9 7 9 6 9 8 8 9 9 3 9 4 9 8 9 4 8 9 9 6 7 2 9 5 3 9 4 7 1 2 3 9 9 9 6 6 4 9 6 9 9 8 5 9 9 2 9 4 8 7 5 9 8 5 9 9 9 1 8 8 4 7 1 7 6 7 9 9 4 3 1 9 5 9 9 9 6 1 4 4 8 1 9 9 7 4 6 9 3 9 6

8 9 5 5 8 5 9 3 8 9 7 9 1 7 9 1 6 9 7 6 2 1 7 9 5 9 9 9 7 9 9 8 9 4 6 9 7 8 6 6 9 7 3 6 6 4 8 1 6 3 9 9 1 3 1 6 8 8 4 9 9 2 6 6 9 4 9 6 9 4 9 9 3 6 3 8 9 1 8 6 9 6 7 1 9 4 8 2 9 6 9 7 8 1 8 3 1 8 5 6

7 2 3 7 5 9 9 6 8 7 2 3 4 7 9 1 1 9 7 9 8 9 2 8 3 4 9 8 1 1 3 9 9 8 7 7 3 5 4 1 4 7 1 8 7 8 7 5 1 1 2 2 8 9 1 9 2 6 9 3 8 8 5 9 8 8 8 9 7 7 9 2 5 7 7 1 6 2 8 5 9 6 3 5 9 3 1 9 7 2 2 8 9 5 8 8 5 7 8 1

1 5 8 3 2 9 8 3 9 6 1 9 6 1 8 5 9 1 4 9 6 9 7 8 5 7 6 7 6 9 2 9 8 5 9 7 9 7 3 8 1 1 6 8 1 6 9 3 9 8 8 9 9 4 6 1 8 5 1 8 8 1 8 9 9 9 6 3 7 8 4 2 5 9 8 6 5 4 8 9 1 9 9 9 9 8 8 9 9 9 7 8 7 2 8 1 2 6 6 8

7 4 6 8 7 2 9 7 7 8 7 7 2 9 9 8 8 3 8 9 7 5 7 2 1 9 9 6 4 6 4 5 5 9 8 9 7 7 1 9 9 6 7 1 8 7 3 7 9 6 7 2 6 9 9 9 6 8 4 4 3 9 1 7 7 2 9 5 4 4 9 4 4 6 8 9 7 9 7 5 6 8 9 2 5 7 8 8 2 6 7 6 8 5 2 9 8 4 1 9

8 9 2 5 7 6 1 8 2 2 5 1 3 3 8 9 9 1 9 1 3 6 3 9 9 8 7 8 8 9 8 1 9 8 9 9 8 2 9 1 1 7 5 8 2 6 1 1 1 6 6 3 9 6 8 5 6 9 7 7 9 1 8 9 2 9 6 9 9 5 8 6 9 8 7 6 6 9 4 8 6 2 7 9 3 9 1 5 8 1 6 7 7 9 9 7 9 5 8 2

8 3 2 7 7 2 8 1 9 7 8 9 8 7 1 3 9 8 6 9 3 9 8 9 2 7 2 5 4 9 5 2 9 6 3 9 2 8 9 9 9 3 5 9 2 9 8 8 7 8 8 4 7 4 8 2 9 9 8 8 6 9 6 6 9 1 8 9 2 1 7 7 9 7 2 8 9 1 9 3 8 9 8 9 4 7 9 9 8 9 7 8 9 4 8 8 9 8 3 2

6 8 9 8 9 4 2 1 1 1 4 3 7 7 9 8 6 1 6 7 7 8 9 6 2 3 9 2 2 3 1 5 2 9 9 6 4 9 9 2 8 9 9 6 1 1 9 8 3 2 3 1 1 4 9 6 3 7 2 9 9 7 7 8 9 4 8 2 2 9 9 7 7 8 9 7 7 6 9 8 1 5 9 2 8 8 7 7 6 7 9 5 3 9 3 9 4 5 9 9

8 2 6 5 2 9 5 8 6 8 1 9 7 9 6 7 1 8 6 7 8 7 6 8 1 4 9 8 8 4 3 1 9 8 7 7 1 2 1 6 9 7 7 1 9 7 9 5 5 9 8 4 8 4 1 9 9 9 9 4 3 6 8 2 9 8 4 6 9 7 9 7 3 2 1 1 8 9 2 2 9 5 8 7 5 1 6 8 7 8 8 8 6 1 9 1 7 7 9 9

8 1 9 3 6 5 5 8 8 8 8 4 7 9 9 4 1 6 4 9 9 1 8 2 9 4 4 8 1 9 1 4 6 9 6 5 1 9 8 3 8 9 6 9 3 8 7 9 9 1 2 4 9 8 1 1 3 8 9 8 9 9 6 8 9 1 6 9 1 4 2 9 4 2 7 9 4 6 8 8 9 6 7 1 3 2 8 9 9 8 1 5 8 9 2 5 9 2 8 9

3 8 8 8 5 7 7 5 7 6 6 1 5 9 1 7 6 6 1 3 5 6 4 9 9 7 6 1 8 1 4 3 1 3 7 4 5 2 9 4 7 9 8 8 7 3 9 9 2 4 7 1 4 7 4 8 1 5 3 5 9 4 9 3 9 8 8 9 2 6 6 6 7 4 8 9 3 6 9 4 9 9 9 8 4 3 7 1 1 2 6 8 4 8 8 1 7 9 5 6

4 1 8 9 6 8 8 9 7 3 3 9 8 5 5 9 6 9 8 9 9 5 5 8 5 7 8 9 9 7 9 8 4 9 8 6 9 9 9 9 9 8 8 1 7 9 6 7 4 9 1 3 1 9 9 9 9 9 9 4 8 8 3 1 1 3 8 9 7 4 7 2 7 1 1 7 9 9 9 8 9 5 7 9 4 4 9 7 1 8 5 1 3 9 5 9 9 7 9 2

8 9 8 3 9 9 5 5 7 9 5 2 3 9 5 9 8 8 9 8 8 9 2 3 8 7 7 1 8 4 9 4 2 8 9 5 5 3 8 2 1 9 1 5 6 5 2 1 9 9 8 1 8 9 9 6 1 1 7 4 4 1 9 9 2 4 9 3 9 5 9 3 6 9 7 6 8 5 8 6 9 8 3 4 8 9 2 9 7 3 9 3 6 8 4 9 6 6 9 5

8 6 7 4 8 1 8 1 6 1 9 8 9 1 8 2 7 6 7 5 9 6 9 6 9 7 5 3 9 7 9 2 6 9 6 9 7 9 3 9 9 9 5 9 8 7 9 2 1 6 7 4 3 4 6 8 5 1 3 8 3 9 8 9 1 9 7 7 8 7 9 3 5 8 5 8 8 9 9 9 3 1 6 7 5 8 4 4 3 9 7 8 2 1 6 3 8 8 4 5

6 7 2 1 5 2 6 1 3 2 5 8 2 8 5 5 2 7 8 1 4 6 9 6 1 9 6 3 9 9 4 9 9 9 5 1 6 7 8 8 2 4 1 1 6 6 5 8 8 1 4 7 2 9 7 1 8 4 4 9 5 8 2 5 9 8 2 9 6 3 8 9 9 5 9 2 1 4 9 7 3 7 9 9 7 5 9 7 7 8 2 9 6 9 1 9 6 4 4 7

8 4 3 9 7 1 9 8 9 1 5 6 4 2 6 4 8 9 6 2 5 2 2 6 9 5 9 9 9 6 9 1 9 5 6 9 5 4 7 1 9 7 4 7 5 6 8 5 9 8 9 9 8 1 8 9 6 7 8 9 7 8 8 3 5 9 1 9 9 9 9 8 4 7 9 2 7 3 5 8 8 8 8 1 7 8 8 4 1 2 8 7 9 4 5 3 9 8 4 1

8 6 9 3 9 8 8 9 9 7 9 9 5 8 9 9 1 7 7 4 5 1 5 6 8 7 9 9 4 8 9 7 9 3 9 9 6 9 3 2 9 4 1 9 8 9 9 9 1 8 9 8 8 8 7 9 3 6 6 8 1 9 4 8 7 6 4 9 7 9 6 2 8 9 9 8 4 8 7 7 2 8 5 9 4 9 9 3 3 9 1 4 5 4 6 7 8 1 9 6

7 2 8 9 1 8 8 6 9 2 7 5 9 9 8 9 9 1 9 8 9 1 9 8 1 3 9 9 9 6 5 4 4 7 9 8 1 6 7 9 1 9 4 3 6 9 5 3 5 7 9 2 5 5 7 2 2 7 8 4 8 7 9 5 9 8 7 8 6 9 8 4 7 8 9 2 3 3 3 1 1 2 6 9 1 9 2 5 8 8 3 4 3 1 9 9 1 4 2 1

9 4 5 8 1 5 9 1 1 3 7 9 9 3 1 9 2 1 2 9 7 9 9 8 8 5 9 5 4 4 9 5 6 1 1 9 7 8 5 1 8 9 8 9 8 8 9 7 6 3 5 2 7 8 1 1 7 7 9 1 9 3 1 7 5 8 5 8 7 9 1 8 3 5 7 6 9 1 9 9 3 9 4 4 8 8 9 9 9 6 9 1 7 2 9 7 9 6 8 1

1 6 9 5 9 8 9 9 2 9 9 5 6 7 6 1 8 3 9 8 8 9 6 1 6 8 3 5 3 4 6 9 7 8 2 8 2 3 7 9 1 9 7 9 1 9 8 8 1 9 3 7 9 9 2 7 7 9 8 9 6 1 1 7 3 8 9 6 1 7 9 2 9 5 8 9 9 6 8 1 6 7 9 5 3 9 4 5 8 9 3 5 1 9 9 1 6 3 1 8

3 9 2 5 1 5 8 2 9 8 8 6 1 7 1 9 3 9 6 9 4 8 5 3 4 8 2 8 5 1 9 7 3 9 1 6 5 7 2 7 4 9 5 6 1 9 9 6 1 6 9 9 8 9 3 4 7 8 8 9 1 6 9 6 8 8 9 9 8 4 5 6 8 5 9 2 8 7 2 1 7 8 7 8 8 9 9 9 4 9 9 4 5 9 8 9 5 3 5 5

2 8 6 9 9 1 7 7 9 9 7 9 8 9 9 1 2 4 9 4 4 9 8 1 3 9 9 6 5 8 9 9 9 8 5 8 8 6 6 9 4 1 4 9 9 6 3 9 4 3 5 8 5 7 6 4 9 3 2 7 1 6 6 9 8 5 9 7 7 9 1 1 1 1 5 4 9 1 9 3 3 5 6 8 7 8 4 3 9 2 9 9 1 6 2 9 9 8 5 4

9 4 1 9 8 8 1 6 8 9 8 9 5 1 9 9 1 1 9 7 6 6 4 5 6 9 3 1 8 5 7 9 6 3 3 9 9 3 8 1 5 1 6 4 6 9 3 7 4 7 1 7 6 5 9 6 7 9 9 6 7 9 2 3 8 7 1 8 9 5 9 9 9 9 9 7 7 5 8 2 2 3 3 9 9 9 2 9 4 9 5 8 1 9 8 1 9 9 1 8

7 9 8 6 9 3 9 1 5 3 6 4 9 9 1 9 3 7 6 6 9 9 9 9 6 1 7 9 7 8 3 9 9 2 7 9 4 9 9 2 7 8 4 9 9 4 8 9 7 2 9 1 9 1 4 8 9 7 3 4 8 7 4 9 5 8 8 9 9 7 3 2 2 9 4 7 9 1 5 8 3 7 4 9 4 2 3 9 1 3 9 6 9 5 4 4 1 3 5 4

8 7 8 3 4 9 9 6 7 9 3 1 8 2 4 1 6 1 5 9 8 8 1 2 7 8 7 9 8 5 9 8 5 6 9 6 2 5 1 2 1 2 9 9 9 8 4 8 7 1 5 5 9 9 7 3 4 1 8 6 6 1 6 3 7 5 4 6 9 6 7 1 6 1 9 2 5 7 4 9 4 1 9 9 9 8 8 8 9 7 9 6 5 9 5 6 1 4 7 7

8 9 9 7 6 9 6 8 7 4 9 3 7 7 5 8 1 4 9 9 5 8 8 8 9 9 1 9 7 1 6 3 9 2 5 8 7 7 9 8 2 9 8 7 7 2 4 9 5 5 9 9 8 9 8 2 1 7 5 7 4 5 3 5 4 4 3 8 3 8 8 9 9 3 8 9 9 3 4 9 9 9 2 6 8 9 5 1 6 1 8 8 2 9 1 6 7 6 1 9

9 7 6 9 9 2 1 7 1 9 9 9 9 9 7 7 9 5 2 8 7 6 4 2 9 9 6 9 1 1 9 9 7 7 8 6 9 2 4 5 6 3 7 5 9 4 8 3 2 9 7 5 5 9 1 1 4 3 8 5 9 9 1 7 3 1 6 8 1 9 9 4 9 7 8 7 8 2 3 8 8 6 5 6 2 8 1 9 9 8 8 9 9 8 8 1 9 9 8 5

5 9 2 8 9 8 6 9 9 5 4 1 4 7 2 9 7 6 2 1 3 6 3 5 7 6 8 7 5 7 4 5 9 9 4 4 9 6 3 9 9 9 3 9 5 9 6 1 9 5 8 8 9 8 5 9 8 6 8 4 8 7 8 7 9 9 2 9 9 7 8 3 8 4 9 2 8 1 9 6 9 5 4 2 5 9 9 8 9 9 7 9 1 9 4 7 5 8 9 1

6 9 5 8 7 3 9 2 1 9 9 2 9 9 9 8 8 3 3 5 7 9 5 7 6 1 9 8 9 8 8 5 9 9 7 8 9 8 7 9 5 5 8 7 5 8 6 5 3 4 9 9 9 9 2 9 4 4 7 9 6 3 3 7 2 6 8 7 2 9 4 8 3 1 7 3 6 6 9 9 9 9 6 1 5 7 9 3 1 9 3 9 4 7 9 6 2 3 1 5

7 8 6 3 7 8 9 9 6 9 3 8 4 7 8 2 6 3 1 9 8 8 8 5 3 6 1 9 6 1 8 9 9 3 9 1 1 5 8 7 9 9 3 9 6 7 4 1 9 3 6 5 6 9 2 6 9 9 7 2 9 4 4 8 8 8 1 6 5 7 9 2 9 8 5 7 8 4 8 9 7 9 7 3 6 9 7 2 7 8 9 9 3 9 9 3 7 9 8 4

6 8 2 2 9 6 4 8 9 9 9 1 1 6 7 9 5 3 4 9 4 7 7 8 1 9 8 9 4 5 6 9 9 6 4 9 9 5 4 4 7 4 9 9 5 8 9 8 5 9 5 7 1 2 8 1 8 2 1 1 7 6 9 6 6 1 1 1 6 4 7 6 7 5 9 8 9 9 8 8 1 8 2 1 2 1 6 9 5 6 6 6 3 1 8 1 8 1 6 3

5 3 2 6 6 6 6 8 9 9 2 8 4 9 3 3 9 1 4 4 8 9 8 1 9 4 7 6 9 4 9 9 9 9 6 8 9 9 7 9 9 1 9 4 9 9 7 8 9 3 7 9 8 6 7 9 9 5 6 8 5 6 9 3 6 5 8 8 9 9 2 8 5 9 4 7 7 9 9 7 6 1 1 6 4 9 8 6 7 4 2 9 9 9 2 7 9 2 8 4

8 9 9 1 2 6 8 8 1 3 1 7 1 9 7 7 9 2 2 8 9 8 1 8 5 5 2 4 7 6 4 2 1 9 8 8 7 7 5 9 9 7 9 6 9 8 1 3 4 9 9 9 4 9 7 5 6 5 7 7 1 8 8 6 6 8 9 6 1 1 9 9 2 9 9 8 1 6 9 6 2 9 2 7 7 5 3 6 1 7 3 7 1 7 4 6 1 9 3 5

5 1 9 8 4 3 2 4 7 6 6 8 7 8 7 9 6 9 8 7 9 9 5 2 1 1 9 9 9 3 7 5 9 6 7 8 2 9 7 3 3 7 1 8 9 4 6 1 6 8 6 9 2 1 9 9 9 8 1 4 9 9 9 4 6 6 2 4 6 7 2 2 9 5 6 9 8 9 9 7 6 9 7 9 1 7 2 4 5 8 5 2 8 7 5 8 9 1 1 5

1 2 3 9 1 5 8 9 3 2 8 5 1 7 3 9 8 7 1 5 8 9 1 2 8 6 3 4 9 7 9 8 7 9 8 9 9 7 7 3 7 2 5 9 8 9 7 9 2 9 9 5 9 1 7 1 8 7 7 7 7 3 3 1 1 9 3 5 9 9 7 9 9 8 7 7 2 5 9 9 9 3 4 6 5 9 3 9 8 1 9 9 4 9 9 3 6 7 6 1

3 5 9 1 9 7 9 9 9 2 9 9 8 8 1 7 9 3 8 9 9 2 1 6 4 9 4 1 9 9 9 8 2 8 8 9 8 7 5 3 9 7 9 1 9 3 1 5 9 3 8 7 9 9 9 1 8 9 8 9 9 7 7 5 7 5 9 3 4 8 3 8 7 5 3 3 7 4 3 6 9 7 1 9 8 9 9 8 8 9 3 2 8 9 6 8 8 3 8 9

6 6 9 9 4 1 2 9 6 9 9 9 8 9 7 6 5 4 9 8 9 4 8 7 4 9 9 8 8 8 7 8 7 9 8 7 8 9 8 9 5 8 9 9 2 9 1 2 1 5 6 9 9 3 9 1 7 5 8 9 3 9 4 9 6 5 6 9 3 5 9 9 1 5 6 9 9 6 3 1 2 5 1 8 5 7 4 1 6 3 7 4 6 2 6 6 7 9 9 9

8 9 1 9 7 8 8 5 6 5 4 1 6 9 9 7 1 3 9 9 9 9 7 4 7 3 7 9 7 7 2 7 9 9 9 9 5 2 1 7 1 2 1 8 6 2 7 9 6 7 9 9 2 8 6 8 8 8 9 3 8 9 1 9 1 8 3 6 4 9 3 2 7 8 5 4 6 4 3 1 7 8 3 5 9 1 6 7 9 8 2 5 7 8 7 1 1 9 2 8

6 8 8 6 4 4 4 7 9 9 3 8 1 9 7 9 1 8 2 9 7 5 3 9 8 2 8 8 1 9 1 1 9 9 2 6 8 1 3 6 5 6 9 7 9 5 9 4 7 1 6 6 3 7 9 6 8 2 8 3 8 8 5 9 2 1 6 8 1 9 6 6 4 9 8 6 2 4 9 9 2 1 8 9 8 9 9 8 7 5 3 4 7 9 7 9 1 7 7 7

1 8 9 8 1 9 7 1 9 7 7 1 9 9 9 3 6 8 9 9 8 5 8 9 6 9 1 8 6 5 8 7 2 1 9 7 5 4 9 1 6 8 9 8 9 9 8 5 9 1 5 9 9 1 7 9 5 8 9 5 8 8 7 8 1 7 7 7 9 4 8 2 5 1 5 6 6 6 7 4 7 9 9 2 9 9 9 5 7 5 2 7 7 1 4 2 9 1 9 7

6 9 1 7 9 7 3 2 9 3 6 8 9 9 7 2 6 8 9 7 8 9 6 1 1 3 7 7 2 7 6 8 9 2 9 9 3 7 8 6 6 3 8 7 1 9 7 6 7 9 7 9 2 9 9 2 9 8 6 4 5 9 9 4 7 5 9 9 3 7 9 5 9 8 7 9 6 5 3 5 6 2 9 2 6 7 2 5 7 9 6 2 8 8 8 3 3 7 7 8

4 9 6 5 4 5 9 8 9 5 3 7 7 9 8 8 9 4 2 9 5 1 9 1 6 6 2 4 9 8 9 9 2 8 8 2 9 7 9 4 4 2 7 8 7 4 9 6 7 2 8 8 9 6 7 9 8 2 1 4 8 8 9 1 7 1 4 9 9 7 5 8 5 5 8 9 3 8 8 8 9 9 4 8 3 6 7 3 4 9 2 8 3 9 8 9 6 6 1 7

8 7 1 6 5 5 5 1 1 4 9 8 3 1 8 3 1 7 1 2 7 2 7 9 7 8 8 9 8 9 5 6 6 1 9 9 3 1 9 9 1 3 3 9 4 1 1 9 1 4 9 9 6 7 3 8 8 6 4 9 9 9 9 9 1 3 8 9 6 7 9 9 5 3 9 5 5 9 5 9 7 9 9 9 1 1 9 8 9 8 9 8 4 5 6 1 1 5 4 8

5 9 4 8 8 4 3 7 9 8 9 7 9 3 4 9 2 9 9 7 8 8 2 1 7 1 6 9 9 1 6 8 8 3 6 2 9 9 1 1 8 3 9 7 1 9 9 4 8 5 5 9 6 8 8 7 1 9 3 3 2 6 1 9 1 8 2 9 3 8 9 1 9 6 1 9 8 3 5 7 3 5 9 4 2 9 5 4 8 7 6 3 9 8 1 9 4 3 9 1

3 9 2 9 8 7 9 9 1 3 3 7 9 2 9 5 2 8 3 8 5 4 8 9 7 8 4 4 7 8 3 5 2 9 8 1 6 9 7 9 8 8 7 9 6 8 4 9 2 3 9 9 9 1 7 9 8 8 9 8 7 4 8 6 9 7 1 3 5 9 2 5 7 7 3 7 3 8 1 1 8 7 5 6 9 6 1 9 9 8 9 9 9 6 9 5 7 3 3 2

8 1 1 2 4 9 6 9 9 2 1 3 9 9 9 8 4 8 9 9 1 8 7 5 5 9 2 2 1 9 9 6 8 8 1 9 9 8 7 7 9 1 3 7 9 5 5 5 9 9 7 9 7 5 9 1 5 9 1 4 2 7 9 8 5 9 5 4 6 3 8 7 9 9 9 9 4 9 5 5 3 6 8 5 8 9 9 9 9 7 2 7 2 7 8 6 9 7 8 1

4 3 5 3 6 4 6 1 7 1 1 9 7 9 4 1 6 5 3 4 6 1 7 4 9 7 9 9 9 7 6 6 7 5 8 7 8 3 1 9 7 9 8 9 9 5 5 7 9 7 1 9 1 9 9 7 3 2 5 8 3 9 8 1 6 2 1 8 6 9 7 9 8 9 9 3 7 6 1 9 6 4 9 7 8 9 2 9 1 8 6 9 6 7 8 9 2 9 9 3

9 1 3 9 2 6 3 7 2 9 2 3 5 8 8 3 9 6 9 8 7 3 9 8 9 9 8 6 1 4 2 8 9 4 1 8 4 8 7 5 9 5 8 5 9 9 9 9 2 5 8 6 6 5 8 7 9 2 9 7 7 5 7 8 1 4 2 8 6 8 7 2 9 6 5 2 8 2 5 1 6 2 2 9 8 5 9 2 9 8 8 9 7 9 1 2 2 2 7 2

9 1 5 9 9 7 1 9 5 9 4 1 9 6 9 9 9 1 9 6 4 7 6 4 9 9 9 2 8 2 9 4 5 6 6 1 9 9 9 9 7 9 8 3 7 9 5 1 9 6 1 4 4 3 5 8 3 2 7 3 9 6 1 8 1 7 8 9 5 9 4 7 9 4 3 9 9 7 5 8 7 9 7 9 7 8 8 9 6 7 3 1 2 1 6 8 5 8 7 9

1 9 5 8 9 8 9 5 8 5 9 9 2 8 5 5 7 7 9 5 7 9 5 7 2 7 9 8 4 7 6 5 6 2 9 8 2 2 8 6 6 7 2 9 9 6 7 8 9 5 9 7 8 9 6 8 4 7 3 4 2 9 9 6 2 3 9 6 8 9 5 7 1 9 3 8 9 1 8 5 7 5 9 6 5 5 1 1 9 7 9 9 9 7 8 6 4 8 9 1

9 3 6 9 8 8 7 2 9 4 5 9 9 9 4 5 7 8 7 4 8 9 1 8 8 1 8 3 7 9 6 9 9 1 6 8 6 9 9 4 7 5 7 9 1 9 9 9 7 6 2 9 9 8 4 8 9 7 9 9 6 7 2 8 9 6 2 3 5 1 1 8 9 9 3 3 8 8 7 8 4 8 6 9 6 9 9 7 8 9 9 7 1 1 9 5 9 9 5 6

1 1 5 2 7 2 1 8 1 2 9 9 4 5 3 8 8 7 8 9 2 6 9 9 1 7 9 7 9 6 9 7 9 3 9 9 8 4 1 4 8 7 7 7 4 9 1 5 6 6 9 8 6 4 4 1 8 4 7 4 4 9 8 8 6 1 9 5 8 2 1 5 7 3 5 8 1 5 4 1 1 8 7 9 1 1 9 8 8 7 7 9 8 9 9 6 8 9 8 4

5 4 9 7 5 8 4 4 6 4 9 3 9 9 6 4 8 5 9 1 9 9 1 9 9 2 8 9 9 9 9 4 9 8 9 5 9 9 1 5 7 6 8 9 9 9 8 1 7 2 9 7 9 9 3 8 9 8 5 9 7 2 6 9 2 9 6 5 3 9 8 8 6 1 8 9 6 1 8 5 3 8 7 8 8 8 4 8 4 6 5 8 6 8 9 9 9 9 4 1

6 8 4 8 6 6 3 7 8 4 5 2 9 7 5 9 9 9 9 3 7 9 9 6 8 7 6 7 5 9 5 2 5 6 6 8 2 9 6 6 3 6 1 2 8 3 9 8 1 1 3 9 9 3 7 9 7 8 9 8 6 4 1 6 7 9 5 8 6 9 5 7 3 6 2 9 9 9 7 7 4 8 2 9 9 8 1 6 5 9 5 1 9 9 8 9 8 1 9 9

9 9 9 7 1 9 8 2 9 5 2 7 9 8 4 3 1 2 7 1 9 3 9 8 2 2 6 8 5 1 6 2 9 7 2 6 7 1 8 5 2 4 5 9 9 7 2 3 8 6 5 8 7 8 3 9 1 9 7 1 7 7 7 8 8 1 9 7 8 1 8 9 5 5 1 9 9 2 2 1 7 7 7 8 3 9 6 1 9 7 9 3 2 6 8 6 6 5 9 7

3 9 6 9 8 9 5 9 6 7 1 9 3 2 4 1 9 9 3 9 6 8 7 4 4 9 4 8 6 7 1 6 9 1 9 4 5 1 3 9 6 8 8 1 9 9 7 3 7 9 1 9 7 8 7 9 4 1 9 9 7 4 7 6 7 9 3 3 1 4 7 9 2 8 3 3 8 9 5 9 7 1 9 8 3 3 7 5 2 9 8 8 9 2 9 7 9 9 8 3

9 6 9 7 6 2 9 1 8 9 5 2 5 8 5 8 7 6 9 1 7 4 8 1 9 9 2 4 2 6 9 2 1 6 9 8 1 6 8 9 5 9 1 7 6 7 8 5 8 6 9 3 8 5 5 7 8 4 6 4 9 2 9 9 9 7 5 3 9 9 4 9 9 8 4 2 7 6 1 9 8 9 4 3 9 1 9 8 9 8 9 4 1 3 4 1 2 4 1 9

8 4 6 3 2 7 9 6 6 5 9 9 3 9 8 9 7 4 9 8 9 5 9 9 4 2 3 1 5 8 1 8 2 9 1 9 2 1 1 7 8 9 3 3 8 6 2 2 9 8 4 9 8 9 8 5 1 5 9 1 7 1 9 1 9 8 9 7 9 1 1 1 1 4 6 8 9 5 9 3 9 7 9 6 3 9 9 9 9 9 6 2 2 8 5 8 3 8 7 5

9 1 4 5 5 8 9 7 9 3 8 6 8 5 5 9 1 9 3 6 7 6 7 9 9 9 9 2 6 7 4 2 9 2 7 9 4 3 2 9 6 9 9 9 2 2 1 3 7 6 8 3 5 3 7 8 5 3 8 1 6 1 5 8 4 5 1 6 7 2 5 7 7 7 3 9 7 4 4 8 9 6 9 9 2 8 1 6 5 6 8 8 1 1 3 9 7 7 6 7

9 5 5 9 7 3 3 7 6 1 8 1 5 2 9 2 9 6 9 7 9 9 8 7 8 2 1 4 1 4 1 4 7 9 7 9 4 7 8 5 9 6 3 9 1 9 3 1 3 2 5 3 9 7 6 9 7 5 5 1 1 4 4 1 7 2 9 8 9 7 1 6 5 4 9 9 6 4 3 1 9 8 7 7 9 8 5 5 9 8 4 8 9 8 2 2 8 8 9 6

8 1 9 4 9 8 6 9 7 4 7 3 7 9 5 7 9 9 7 1 9 5 7 8 5 5 7 9 9 3 9 9 9 9 9 8 7 2 9 9 9 6 9 3 9 3 6 9 6 9 6 8 8 6 8 5 7 2 1 8 9 8 4 5 8 7 8 2 6 3 9 9 1 5 9 8 5 8 1 9 8 6 9 4 7 6 8 7 8 9 9 9 1 7 9 2 9 2 9 7

6 9 9 6 2 6 3 1 8 8 1 5 8 6 4 9 9 2 9 8 9 8 2 9 8 9 6 4 2 8 7 3 9 6 8 9 7 9 5 8 4 9 1 8 8 7 3 2 9 3 8 9 1 7 8 3 8 4 8 6 8 5 2 1 2 1 8 9 6 9 9 5 9 9 9 8 2 9 7 3 9 6 9 9 4 3 8 9 7 9 7 8 5 4 4 1 1 3 9 2

7 5 9 6 5 3 9 7 3 1 5 7 5 8 4 7 9 8 8 2 9 8 6 9 9 9 5 5 4 3 5 4 8 9 8 3 9 6 7 3 7 8 9 9 9 3 9 3 9 7 3 7 9 1 6 9 9 9 8 9 8 2 8 7 1 8 1 7 9 1 2 4 8 1 9 9 9 6 1 3 1 7 9 7 9 1 9 9 8 7 1 8 9 2 9 8 9 6 9 9

6 1 9 9 7 9 7 6 3 9 6 8 4 1 6 5 5 3 8 9 3 9 5 8 9 7 1 5 3 1 9 3 7 6 9 4 2 8 1 9 9 7 2 9 5 1 8 3 1 9 8 9 1 7 1 9 2 9 8 9 9 6 8 5 1 7 5 1 7 2 2 9 9 9 9 9 1 3 3 5 1 2 8 5 4 5 9 9 2 9 3 8 9 1 7 3 9 9 1 9

'****************************************************************************************************'

[(99, 99), (98, 99), (97, 99), (97, 98), (97, 97), (96, 97), (95, 97), (95, 96), (95, 95), (94, 95), (94, 94), (93, 94), (92, 94), (92, 93), (92, 92), (92, 91), (92, 90), (91, 90), (91, 89), (90, 89), (89, 89), (88, 89), (87, 89), (86, 89), (86, 88), (85, 88), (85, 87), (84, 87), (83, 87), (82, 87), (81, 87), (80, 87), (79, 87), (78, 87), (77, 87), (76, 87), (75, 87), (74, 87), (73, 87), (72, 87), (71, 87), (70, 87), (70, 86), (69, 86), (68, 86), (67, 86), (66, 86), (65, 86), (65, 85), (64, 85), (64, 84), (64, 83), (64, 82), (64, 81), (64, 80), (64, 79), (64, 78), (64, 77), (64, 76), (64, 75), (64, 74), (64, 73), (64, 72), (64, 71), (64, 70), (63, 70), (63, 69), (63, 68), (63, 67), (63, 66), (63, 65), (62, 65), (62, 64), (62, 63), (62, 62), (62, 61), (62, 60), (62, 59), (62, 58), (62, 57), (62, 56), (62, 55), (61, 55), (61, 54), (61, 53), (60, 53), (60, 52), (60, 51), (60, 50), (60, 49), (59, 49), (58, 49), (57, 49), (57, 48), (56, 48), (56, 47), (56, 46), (56, 45), (55, 45), (54, 45), (54, 44), (53, 44), (53, 43), (52, 43), (51, 43), (50, 43), (49, 43), (48, 43), (48, 42), (48, 41), (47, 41), (46, 41), (45, 41), (44, 41), (43, 41), (43, 40), (42, 40), (41, 40), (41, 39), (40, 39), (40, 38), (39, 38), (39, 37), (39, 36), (38, 36), (37, 36), (36, 36), (35, 36), (34, 36), (33, 36), (32, 36), (32, 35), (31, 35), (30, 35), (29, 35), (28, 35), (27, 35), (27, 34), (27, 33), (26, 33), (25, 33), (25, 32), (24, 32), (24, 31), (23, 31), (22, 31), (21, 31), (20, 31), (19, 31), (18, 31), (17, 31), (16, 31), (16, 32), (15, 32), (14, 32), (13, 32), (12, 32), (12, 31), (11, 31), (10, 31), (9, 31), (8, 31), (7, 31), (6, 31), (5, 31), (5, 30), (4, 30), (3, 30), (3, 29), (3, 28), (3, 27), (3, 26), (3, 25), (3, 24), (2, 24), (2, 23), (1, 23), (1, 22), (1, 21), (2, 21), (2, 20), (2, 19), (3, 19), (3, 18), (3, 17), (3, 16), (3, 15), (3, 14), (3, 13), (3, 12), (3, 11), (3, 10), (3, 9), (3, 8), (2, 8), (2, 7), (2, 6), (2, 5), (2, 4), (2, 3), (2, 2), (2, 1), (1, 1), (0, 1), (0, 0)]
739

A much bigger map

Ok, this should be simple for me, my A* algorithm tries optimially to explore downwards and right constantly, all I need to do is generate a much bigger grid and feed it in.

This map generation feels much harder than the actual path finding! Guess lets give it a go (and be thankful that I didn't prematurely optimise assuming that per node costs would change)

Note: for this I want to compare Grid objects, but I didn't add an __eq__ function, so I'm going to go back and add it

def expandgrid(grid):
    newgrid = Grid(grid.width*5, grid.height*5, {})
    for gy in range(5):
        for gx in range(5):
            for y in range(grid.width):
                for x in range(grid.height):
                    newvalue = grid.get_cell((x,y))+gx+gy
                    if newvalue > 9:
                        newvalue -= 9 # We can't use mod, because we reset to 1 not 0
                    newgrid.cells[(gx*grid.width+x,gy*grid.height+y)] = newvalue
    return newgrid

assert grid_from_lines("1") == grid_from_lines("1")
assert grid_from_lines("""12345
23456
34567
45678
56789""".split("\n")) == expandgrid(grid_from_lines(["1"]))
assert grid_from_lines("""1223344556
3445566778
2334455667
4556677889
3445566778
5667788991
4556677889
6778899112
5667788991
7889911223""".split("\n")) == expandgrid(grid_from_lines(["12","34"]))

Ok, we can create a bigger grid, lets pathfind our way through the test data and see if our expanded path looks sensible

testgrid = expandgrid(grid_from_lines("""1163751742
1381373672
2136511328
3694931569
7463417111
1319128137
1359912421
3125421639
1293138521
2311944581""".split("\n")))

path = find_path(testgrid)
testgrid.display(path)
print(path)
# Exclude the start from the path, which is the last item as our path is backwards
cost = sum([testgrid.get_cell(coord) for coord in path[:-1]])
print(cost)
assert 315 == cost

'**************************************************'

1 1 6 3 7 5 1 7 4 2 2 2 7 4 8 6 2 8 5 3 3 3 8 5 9 7 3 9 6 4 4 4 9 6 1 8 4 1 7 5 5 5 1 7 2 9 5 2 8 6

1 3 8 1 3 7 3 6 7 2 2 4 9 2 4 8 4 7 8 3 3 5 1 3 5 9 5 8 9 4 4 6 2 4 6 1 6 9 1 5 5 7 3 5 7 2 7 1 2 6

2 1 3 6 5 1 1 3 2 8 3 2 4 7 6 2 2 4 3 9 4 3 5 8 7 3 3 5 4 1 5 4 6 9 8 4 4 6 5 2 6 5 7 1 9 5 5 7 6 3

3 6 9 4 9 3 1 5 6 9 4 7 1 5 1 4 2 6 7 1 5 8 2 6 2 5 3 7 8 2 6 9 3 7 3 6 4 8 9 3 7 1 4 8 4 7 5 9 1 4

7 4 6 3 4 1 7 1 1 1 8 5 7 4 5 2 8 2 2 2 9 6 8 5 6 3 9 3 3 3 1 7 9 6 7 4 1 4 4 4 2 8 1 7 8 5 2 5 5 5

1 3 1 9 1 2 8 1 3 7 2 4 2 1 2 3 9 2 4 8 3 5 3 2 3 4 1 3 5 9 4 6 4 3 4 5 2 4 6 1 5 7 5 4 5 6 3 5 7 2

1 3 5 9 9 1 2 4 2 1 2 4 6 1 1 2 3 5 3 2 3 5 7 2 2 3 4 6 4 3 4 6 8 3 3 4 5 7 5 4 5 7 9 4 4 5 6 8 6 5

3 1 2 5 4 2 1 6 3 9 4 2 3 6 5 3 2 7 4 1 5 3 4 7 6 4 3 8 5 2 6 4 5 8 7 5 4 9 6 3 7 5 6 9 8 6 5 1 7 4

1 2 9 3 1 3 8 5 2 1 2 3 1 4 2 4 9 6 3 2 3 4 2 5 3 5 1 7 4 3 4 5 3 6 4 6 2 8 5 4 5 6 4 7 5 7 3 9 6 5

2 3 1 1 9 4 4 5 8 1 3 4 2 2 1 5 5 6 9 2 4 5 3 3 2 6 6 7 1 3 5 6 4 4 3 7 7 8 2 4 6 7 5 5 4 8 8 9 3 5

2 2 7 4 8 6 2 8 5 3 3 3 8 5 9 7 3 9 6 4 4 4 9 6 1 8 4 1 7 5 5 5 1 7 2 9 5 2 8 6 6 6 2 8 3 1 6 3 9 7

2 4 9 2 4 8 4 7 8 3 3 5 1 3 5 9 5 8 9 4 4 6 2 4 6 1 6 9 1 5 5 7 3 5 7 2 7 1 2 6 6 8 4 6 8 3 8 2 3 7

3 2 4 7 6 2 2 4 3 9 4 3 5 8 7 3 3 5 4 1 5 4 6 9 8 4 4 6 5 2 6 5 7 1 9 5 5 7 6 3 7 6 8 2 1 6 6 8 7 4

4 7 1 5 1 4 2 6 7 1 5 8 2 6 2 5 3 7 8 2 6 9 3 7 3 6 4 8 9 3 7 1 4 8 4 7 5 9 1 4 8 2 5 9 5 8 6 1 2 5

8 5 7 4 5 2 8 2 2 2 9 6 8 5 6 3 9 3 3 3 1 7 9 6 7 4 1 4 4 4 2 8 1 7 8 5 2 5 5 5 3 9 2 8 9 6 3 6 6 6

2 4 2 1 2 3 9 2 4 8 3 5 3 2 3 4 1 3 5 9 4 6 4 3 4 5 2 4 6 1 5 7 5 4 5 6 3 5 7 2 6 8 6 5 6 7 4 6 8 3

2 4 6 1 1 2 3 5 3 2 3 5 7 2 2 3 4 6 4 3 4 6 8 3 3 4 5 7 5 4 5 7 9 4 4 5 6 8 6 5 6 8 1 5 5 6 7 9 7 6

4 2 3 6 5 3 2 7 4 1 5 3 4 7 6 4 3 8 5 2 6 4 5 8 7 5 4 9 6 3 7 5 6 9 8 6 5 1 7 4 8 6 7 1 9 7 6 2 8 5

2 3 1 4 2 4 9 6 3 2 3 4 2 5 3 5 1 7 4 3 4 5 3 6 4 6 2 8 5 4 5 6 4 7 5 7 3 9 6 5 6 7 5 8 6 8 4 1 7 6

3 4 2 2 1 5 5 6 9 2 4 5 3 3 2 6 6 7 1 3 5 6 4 4 3 7 7 8 2 4 6 7 5 5 4 8 8 9 3 5 7 8 6 6 5 9 9 1 4 6

3 3 8 5 9 7 3 9 6 4 4 4 9 6 1 8 4 1 7 5 5 5 1 7 2 9 5 2 8 6 6 6 2 8 3 1 6 3 9 7 7 7 3 9 4 2 7 4 1 8

3 5 1 3 5 9 5 8 9 4 4 6 2 4 6 1 6 9 1 5 5 7 3 5 7 2 7 1 2 6 6 8 4 6 8 3 8 2 3 7 7 9 5 7 9 4 9 3 4 8

4 3 5 8 7 3 3 5 4 1 5 4 6 9 8 4 4 6 5 2 6 5 7 1 9 5 5 7 6 3 7 6 8 2 1 6 6 8 7 4 8 7 9 3 2 7 7 9 8 5

5 8 2 6 2 5 3 7 8 2 6 9 3 7 3 6 4 8 9 3 7 1 4 8 4 7 5 9 1 4 8 2 5 9 5 8 6 1 2 5 9 3 6 1 6 9 7 2 3 6

9 6 8 5 6 3 9 3 3 3 1 7 9 6 7 4 1 4 4 4 2 8 1 7 8 5 2 5 5 5 3 9 2 8 9 6 3 6 6 6 4 1 3 9 1 7 4 7 7 7

3 5 3 2 3 4 1 3 5 9 4 6 4 3 4 5 2 4 6 1 5 7 5 4 5 6 3 5 7 2 6 8 6 5 6 7 4 6 8 3 7 9 7 6 7 8 5 7 9 4

3 5 7 2 2 3 4 6 4 3 4 6 8 3 3 4 5 7 5 4 5 7 9 4 4 5 6 8 6 5 6 8 1 5 5 6 7 9 7 6 7 9 2 6 6 7 8 1 8 7

5 3 4 7 6 4 3 8 5 2 6 4 5 8 7 5 4 9 6 3 7 5 6 9 8 6 5 1 7 4 8 6 7 1 9 7 6 2 8 5 9 7 8 2 1 8 7 3 9 6

3 4 2 5 3 5 1 7 4 3 4 5 3 6 4 6 2 8 5 4 5 6 4 7 5 7 3 9 6 5 6 7 5 8 6 8 4 1 7 6 7 8 6 9 7 9 5 2 8 7

4 5 3 3 2 6 6 7 1 3 5 6 4 4 3 7 7 8 2 4 6 7 5 5 4 8 8 9 3 5 7 8 6 6 5 9 9 1 4 6 8 9 7 7 6 1 1 2 5 7

4 4 9 6 1 8 4 1 7 5 5 5 1 7 2 9 5 2 8 6 6 6 2 8 3 1 6 3 9 7 7 7 3 9 4 2 7 4 1 8 8 8 4 1 5 3 8 5 2 9

4 6 2 4 6 1 6 9 1 5 5 7 3 5 7 2 7 1 2 6 6 8 4 6 8 3 8 2 3 7 7 9 5 7 9 4 9 3 4 8 8 1 6 8 1 5 1 4 5 9

5 4 6 9 8 4 4 6 5 2 6 5 7 1 9 5 5 7 6 3 7 6 8 2 1 6 6 8 7 4 8 7 9 3 2 7 7 9 8 5 9 8 1 4 3 8 8 1 9 6

6 9 3 7 3 6 4 8 9 3 7 1 4 8 4 7 5 9 1 4 8 2 5 9 5 8 6 1 2 5 9 3 6 1 6 9 7 2 3 6 1 4 7 2 7 1 8 3 4 7

1 7 9 6 7 4 1 4 4 4 2 8 1 7 8 5 2 5 5 5 3 9 2 8 9 6 3 6 6 6 4 1 3 9 1 7 4 7 7 7 5 2 4 1 2 8 5 8 8 8

4 6 4 3 4 5 2 4 6 1 5 7 5 4 5 6 3 5 7 2 6 8 6 5 6 7 4 6 8 3 7 9 7 6 7 8 5 7 9 4 8 1 8 7 8 9 6 8 1 5

4 6 8 3 3 4 5 7 5 4 5 7 9 4 4 5 6 8 6 5 6 8 1 5 5 6 7 9 7 6 7 9 2 6 6 7 8 1 8 7 8 1 3 7 7 8 9 2 9 8

6 4 5 8 7 5 4 9 6 3 7 5 6 9 8 6 5 1 7 4 8 6 7 1 9 7 6 2 8 5 9 7 8 2 1 8 7 3 9 6 1 8 9 3 2 9 8 4 1 7

4 5 3 6 4 6 2 8 5 4 5 6 4 7 5 7 3 9 6 5 6 7 5 8 6 8 4 1 7 6 7 8 6 9 7 9 5 2 8 7 8 9 7 1 8 1 6 3 9 8

5 6 4 4 3 7 7 8 2 4 6 7 5 5 4 8 8 9 3 5 7 8 6 6 5 9 9 1 4 6 8 9 7 7 6 1 1 2 5 7 9 1 8 8 7 2 2 3 6 8

5 5 1 7 2 9 5 2 8 6 6 6 2 8 3 1 6 3 9 7 7 7 3 9 4 2 7 4 1 8 8 8 4 1 5 3 8 5 2 9 9 9 5 2 6 4 9 6 3 1

5 7 3 5 7 2 7 1 2 6 6 8 4 6 8 3 8 2 3 7 7 9 5 7 9 4 9 3 4 8 8 1 6 8 1 5 1 4 5 9 9 2 7 9 2 6 2 5 6 1

6 5 7 1 9 5 5 7 6 3 7 6 8 2 1 6 6 8 7 4 8 7 9 3 2 7 7 9 8 5 9 8 1 4 3 8 8 1 9 6 1 9 2 5 4 9 9 2 1 7

7 1 4 8 4 7 5 9 1 4 8 2 5 9 5 8 6 1 2 5 9 3 6 1 6 9 7 2 3 6 1 4 7 2 7 1 8 3 4 7 2 5 8 3 8 2 9 4 5 8

2 8 1 7 8 5 2 5 5 5 3 9 2 8 9 6 3 6 6 6 4 1 3 9 1 7 4 7 7 7 5 2 4 1 2 8 5 8 8 8 6 3 5 2 3 9 6 9 9 9

5 7 5 4 5 6 3 5 7 2 6 8 6 5 6 7 4 6 8 3 7 9 7 6 7 8 5 7 9 4 8 1 8 7 8 9 6 8 1 5 9 2 9 8 9 1 7 9 2 6

5 7 9 4 4 5 6 8 6 5 6 8 1 5 5 6 7 9 7 6 7 9 2 6 6 7 8 1 8 7 8 1 3 7 7 8 9 2 9 8 9 2 4 8 8 9 1 3 1 9

7 5 6 9 8 6 5 1 7 4 8 6 7 1 9 7 6 2 8 5 9 7 8 2 1 8 7 3 9 6 1 8 9 3 2 9 8 4 1 7 2 9 1 4 3 1 9 5 2 8

5 6 4 7 5 7 3 9 6 5 6 7 5 8 6 8 4 1 7 6 7 8 6 9 7 9 5 2 8 7 8 9 7 1 8 1 6 3 9 8 9 1 8 2 9 2 7 4 1 9

6 7 5 5 4 8 8 9 3 5 7 8 6 6 5 9 9 1 4 6 8 9 7 7 6 1 1 2 5 7 9 1 8 8 7 2 2 3 6 8 1 2 9 9 8 3 3 4 7 9

'**************************************************'

[(49, 49), (48, 49), (47, 49), (46, 49), (45, 49), (45, 48), (45, 47), (44, 47), (43, 47), (42, 47), (42, 46), (41, 46), (41, 45), (41, 44), (41, 43), (40, 43), (39, 43), (38, 43), (37, 43), (37, 42), (37, 41), (37, 40), (37, 39), (36, 39), (35, 39), (34, 39), (34, 38), (34, 37), (33, 37), (33, 36), (32, 36), (32, 35), (32, 34), (31, 34), (30, 34), (29, 34), (29, 33), (28, 33), (27, 33), (27, 32), (27, 31), (27, 30), (26, 30), (25, 30), (24, 30), (24, 29), (23, 29), (22, 29), (22, 28), (21, 28), (20, 28), (19, 28), (19, 27), (19, 26), (19, 25), (18, 25), (17, 25), (16, 25), (16, 24), (16, 23), (16, 22), (15, 22), (15, 21), (14, 21), (14, 20), (14, 19), (13, 19), (12, 19), (12, 18), (11, 18), (10, 18), (9, 18), (9, 17), (9, 16), (8, 16), (7, 16), (6, 16), (5, 16), (4, 16), (3, 16), (3, 15), (2, 15), (2, 14), (2, 13), (2, 12), (1, 12), (0, 12), (0, 11), (0, 10), (0, 9), (0, 8), (0, 7), (0, 6), (0, 5), (0, 4), (0, 3), (0, 2), (0, 1), (0, 0)]
315

At this point, something worth pointing out, once the path comes off of the left side, my path goes 3->2->4->1->7->2->1. But the example given selects a slightly different path, 3->2->4->1->5->4->1. In this case the 5+4 is the same cost as going 7+2, so either path is valid. If the requirement needed us to know what the actual path was. But what we've found is that there are several equivalent paths.

Anyway, lets give it a try on the production data.

I'm not going to render this one, because the production data was significantly bigger than the test data and when expanded 5 times in each direction it will be far less interesting.

grid = expandgrid(grid_from_lines([line.strip() for line in open("day15.txt")]))

path = find_path(grid)
# Exclude the start from the path, which is the last item as our path is backwards
print(sum([grid.get_cell(coord) for coord in path[:-1]]))

3040