Project Euler 83: Find a minimum path sum in a matrix from the top left to the bottom right corners by moving up, down, left or right.

Project Euler 83 Problem Description

Project Euler 83 NOTE: This problem is a significantly more challenging version of Problem 81.

In the 5 by 5 matrix below, the minimal path sum from the top left to the bottom right, by moving left, right, up, and down, is indicated in bold red and is equal to 2297.

Find the minimal path sum, in matrix.txt (right click and “Save Link/Target As…”), a 31K text file containing a 80 by 80 matrix, from the top left to the bottom right by moving left, right, up, and down.

Analysis

This problem is more complex than problems 81 and 82. We are still trying to find a minimum path sum from the top-right corner to the bottom-left corner but are now allowed to move left in addition to up, down and right. This rules out a dynamic approach as we cannot look left.
Fortunately, we have a great package for Python call networkx. It allows us to build a directed graph of the matrix and specify a start location (source=(0,0)), a target location (target=(n-1,m-1)) and a method for solving (A-star or Dijkstra). The directions are up(-1,0), down(+1,0), right(0,+1) and left(0,-1) when valid.

Our solution is now reduced to:

1. Read the data into a matrix.
2. Setup a directed graph of the matrix (each cell points to its neighbors).
3. Calculate the path.
4. Print the results.

We read the data into a matrix from a URL resource as before and build a simple graph. The neighbors array is a device to list the neighbors for each cell and exclude any that lie outside the matrix. Edges are added for each cell with the contents used as a weight.
All that’s left is to send it to the package and await the result.

Project Euler 83 Solution

Afterthoughts

• See also, Project Euler 81 Solution:
  
• See also, Project Euler 82 Solution:
  
• Don’t forget to add the starting point (0,0) as it is not technically part of the path’s length.