(2 votes, average: 5.00 out of 5)

## 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.

 131 673 234 103 18 201 96 342 965 150 630 803 746 422 111 537 699 497 121 956 805 732 524 37 331

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

Runs < 0.130 seconds in Python 2.7.

Use this link to get the Project Euler 83 Solution Python 2.7 source.

#### Afterthoughts

Project Euler 83 Solution last updated