Path Sums
Note: all code can be found on my Github profile
Project Euler #81
Let’s take a look at the text of problem 81 on Project Euler:
In the 5 by 5 matrix below, the minimal path sum from the top left to the bottom right, by only moving to the right and down, is indicated in bold red and is equal to 2427.
131 673 234 103 18
201 96 342 965 150
630 803 746 422 111
537 699 497 121 956
805 732 524 37 331Find the minimal path sum from the top left to the bottom right by only moving right and down in matrix.txt (right click and "Save Link/Target As..."), a 31K text file containing an 80 by 80 matrix.
The best way for a relative beginner to approach a problem like is to dynamic problem. This means you simplify it into the simplest possible terms, and slowly expand the scope until you solve the whole problem. There are a two key pieces of information nestled in the text that will allow us to do that.
- A fixed start and end point (the top left and bottom right, respectively)
- Only move rightward or downward
In conjunction, this means that the path sum, or what I like to call the "cost," of traveling to the (4, 4) is derived from the cost of traveling to either the space just above (4, 3) or just to the left (3, 4). Find which of those is lower, and add the value of (4,4) to it. To find the cost of (4, 3), take the minimum of the costs of (4, 2) and (3, 3) and add the current value. If you continue to follow that recusrion, you will eventually get to (0,0), which has no where to go left or above, and therefore the cost is just the value in (0, 0).
With that conceptualization in mind, you can start building a result matrix with the minimum cost to travel to each item in the input matrix by iterating from (0, 0):
131 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0then
131 804 0 0 0
332 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0Continue until the whole matrix is full and the solution value will be in (4, 4).
Assuming that "input" is a two dimensional list of integers representing the sample matrix, the following python code implements the algorithm outlined above. The extra bits checking for x > 0 and y > 0 are to account for the edges which are missing either an upward or leftward path. Passing the full matrix provided by the problem text will output the answer Project Euler is looking for. I'm not giving the answer here. Try it out yourself!
def FindMinimalPath(input): results = [[0 for i in range(len(input))] for i in range(len(input))] for x in range(len(input)): for y in range(len(input)): weight = input[i][j] if(x > 0): if(y > 0): weight += min(results[x][y-1], results[x-1][y]) else: weight += results[x][y-1] else: weight += results[x-1][y] results[x][y] = weight return results[-1][-1]
Problem #83
Skip #82 for now. We're gonna look at #83 becuase the lessons learned there will be useful for #82.
#83 poses largely the same problem as #81: find the least cost to travel from the top left corner to the bottom right corner. However, it adds one additional wrinkle of complexity: you can move in any direction. Conceptualizing this as a dynamic problem makes me want to cry. You have to, in essence, find every possible route from (0, 0) to (4, 4) and calculate the sum of all of them. That's a lot of calculations to brute force. I'm not even going to bother investigating if that's feasible at the 5x5 scale because I'm certain that the 80x80 matix will not be feasible.
So how can we think about this as some other sort of problem? Where else do computers analyze the cost of travel? MAPPING SOFTWARE!! Do a little googling, or think back to that one algorithms class you took in college and find hints of something called Dijkstra's algorithm. Thanks to the beauty of reusable code, the details of the algorithm actually aren't all that important right now. All you need to know is that it efficiently finds the least expensive path between two nodes in a graph.
Wait, we have a matrix, right? That's not a graph, but we can turn it into one! Think of each item in the matrix as a node, with directed edges branching off in all four diretions, where the weight of those edges is the value of the node being traveled to. This is analogus to the addition step from problem #81. In cost to travel into a matrix item requires you to add the value of that matrix item.
So all we need to do is build that graph, and employ a standard implementation of Dijkstra's algorithm to find the best path, and then sum up the matrix values that correspond to that path.
Here's my code to do that. The function that your main method will call is FindShortestPathSum.
import functools, networkx as nx, itertools def CreateGraph(input): gr = nx.MultiDiGraph() for x in range(len(input)): for y in range(len(input)): node = (x, y) #add right if(x < len(input)-1): gr.add_edge(node, (x+1, y), weight=input[x+1][y]) #add left if(x > 0): gr.add_edge(node, (x-1, y), weight=input[x-1][y]) #add down if(dy < len(input)-1): gr.add_edge(node, (x, y+1), weight=input[x][y+1]) #add up if(y > 0): gr.add_edge(node, (x, y-1), weight=input[x][y-1]) return gr def Accumulate(path, input): return functools.reduce(lambda acc, node: acc + input[node[0]][node[1]], path, 0) def FindShortestPathSum(input): gr = CreateGraph(input, directions) path = nx.algorithms.shortest_paths.weighted.dijkstra_path(gr, (0,0), (len(input)-1, len(input)-1)) return Accumulate(path, input)
By adding Directions enum to indicate what the valid movement directions are, you can generalize this code to apply to #81 as well.
from enum import IntFlag import functools, networkx as nx, itertools class Direction(IntFlag): Unknown = 0 Right = 1 Left = 1 << 1 Up = 1<<2 Down = 1<<3 Two = Right | Down Three = Right | Up | Down All = Right | Left | Up | Down def CreateGraph(input, directions: Direction): gr = nx.MultiDiGraph() for x in range(len(input)): for y in range(len(input)): node = (x, y) #add right if(directions & Direction.Right and x < len(input)-1): gr.add_edge(node, (x+1, y), weight=input[x+1][y]) #add left if(directions & Direction.Left and x > 0): gr.add_edge(node, (x-1, y), weight=input[x-1][y]) #add down if(directions & Direction.Down and y < len(input)-1): gr.add_edge(node, (x, y+1), weight=input[x][y+1]) #add up if(directions & Direction.Up and y > 0): gr.add_edge(node, (x, y-1), weight=input[x][y-1]) return gr def Accumulate(path, input): return functools.reduce(lambda acc, node: acc + input[node[0]][node[1]], path, 0) def FindShortestPathSum(input, directions: Direction): gr = CreateGraph(input, directions) path = nx.algorithms.shortest_paths.weighted.dijkstra_path(gr, (0,0), (len(input)-1, len(input)-1)) return Accumulate(path, input)
Problem #83
Now let's look at the supposedly "medium" difficulty of these three. I think it's actually the hardest of them.
It asks you to find the shortest path from any item on the left to any item on the right, moving up, down, or ot the right. That non determinism of the start and end points adds a lot of complexity.
My approach is to treat it as a set of finite problems like #84, i.e. find the shortest path from (0, 0) to (0, 4), from (0, 0) to (1, 4), from (1, 0) to (0, 4), etc. The answer is the minimum of those. Adding just a few function calls to the above code will accomplish this.
def ShortestPathMulti(graph, input, yTarget): path = nx.algorithms.shortest_paths.weighted.multi_source_dijkstra(graph, [(0, i) for i in range(len(input))], (len(input)-1, yTarget)) return Accumulate(path[1], input) def FindShortestHorizontalPath(input): gr = CreateGraph(input, Direction.Three) return min(map(lambda i: ShortestPathMulti(gr, input, i), range(len(input))))
This works well enough for the 80x80 grid that the problem has you examine, but the calculation times grow exponentially as the grid sizes increase because you are looking at n squared
This works well enough for the 80x80 grid that the problem has you examine, but the calculation times grow exponentially as the grid sizes increase because you are looking at n2 possible start and end points for a matrix of size n by n. That's not good.
There is a faster way of calculating this which is similar to the initial approach from problem #81. Starting from the left side of the matrix, you know that the minimum cost to get to each space is just the value of that space. For each successive column, you know two things: the cost coming from the left, and the cost coming from above--0 in the case of the upper most, and as you work downward, you will have already figured out the cost of the previous item. So you need to figure out the cost of comign from below, from the perspective of the current item. You can do this recursively until you get to the end of the column, at which point there is no lower item to compare to, and therefore the cost is just the cost of coming from the left.
It's important to remember that during this recursive call, you're not calculating the actual minimum cost of each item, but rather the cost from the prespective of the cell above it. You're essentially temporarily eliminting one variable, just to see what the cost is when you do that. This gives you something to compare to when you add that other variable back in.
Here's the code:
def Minimum(*ints): result = float('inf') for n in ints: if(n == None): continue else: result = min(result, n) return result def FindWeight(x: int, y: int, result: list, input: list): if(y == len(input)-1): return input[x][y] + result[x-1][y] else: left = result[x-1][y] bottom = FindWeight(x, y+1, result, input) return min(left, bottom) + input[x][y] def FindMinimalPath(input): results = [input[0]] for x in range(1, len(input)): results.append([]) for y in range(len(input)): left = results[x-1][y] top = results[x][y-1] if y > 0 else None bottom = FindWeight(x, y+1, results, input) if y < len(input)-1 else None results[x].append(Minimum(left, top, bottom) + input[x][y]) return functools.reduce(min, results[-1])
I do not like this approach. It significantly diverges from the optimal approaches of the other two related problems. In a business scenario, I would sacrifice the performance gains for the better maintainability here, so long as the performance gains are not untenable. The problem at hand is an 80x80 matrix. If I had to deal with a 1000x1000 grid, I might make a different call.
