Project Euler — Problem 81 Solution

Problem

In the 5 by 5 matrix below, the min­i­mal path sum from the top left to the bot­tom right, by only mov­ing to the right and down, is indi­cat­ed in bold red and is equal to 2427.

image

Find the min­i­mal path sum, in matrix.txt (right click and ‘Save Link/Target As…’), a 31K text file con­tain­ing a 80 by 80 matrix, from the top left to the bot­tom right by only mov­ing right and down.

Solution

I took a sim­i­lar approach to the one I used for prob­lem 18 and iter­a­tive­ly work out what’s the short­est path sum lead­ing up to each of the cells in the matrix.

Con­sid­er­ing that a brute force approach will need to walk through the 80 x 80 matrix a total of 92045125813734238026462263037378063990076729140 times…so that’s clear­ly not an option! So instead, for each cell (x, y) in the matrix, we con­sid­er the two pos­si­bil­i­ties:

  1. the path has tra­versed down from cell (x-1, y)
  2. the path has tra­versed right from cell (x, y-1)

the short­est path sum from top left to (x, y), let’s call it sps(x, y) will be equal to the less­er of sps(x-1, y) + (x, y) and sps(x, y-1) + (x, y). Obvi­ous­ly there are some spe­cial cas­es, such as when x = 0 and when y = 0, as you can see the dif­fer­ent han­dling in the match pat­tern.