From ProgSoc Wiki

Solutions for Problem 81

Given an 80x80 matrix, find the lowest cost path moving only right and down from the top left to bottom right corner.

C by SanguineV

Runtime: negligible.

#include <stdio.h>

// Declare the matrix as a two dimensional array.
unsigned long matrix[80][80] = { {...} };

int main () {
  // Iterators for the two dimesions.
  int i,j;
  // The edges have only a single path, so calculate those immediately.
  i = 78;
  while (i >= 0) {
    matrix[i][79] += matrix[i+1][79];
    matrix[79][i] += matrix[79][i+1];
    i--;
  }
  // For each node, the path is its cost plus the lesser of the right or down step
  // so iterate through the matrix and update all the node costs.
  i = 78;
  while (i >= 0) {
    j = 78;
    while (j >= 0) {
      if(matrix[i+1][j] < matrix[i][j+1]) {
        matrix[i][j] += matrix[i+1][j];
      }
      else {
        matrix[i][j] += matrix[i][j+1];
      }
      j--;
    }
    i--;
  }
  // Cheapest cost is now the top left cost, so print it.
  printf("Minimum path costs:%u\n",matrix[0][0]);
  return 0;
}

Same technique as used for problem 15 solutions, only now we have to have a local cost as well so need to work from the bottom right in reverse (or reverse all the matrix values, which is too much effort).

Python by Althalus

Runtime: 11ms

data = [....data here....]
#Let's deal with the edges seperate from the rest. Else we have to worry about handling out of bound errors
for i in range(78,-1,-1):
 data[79][i] += data[79][i+1]
 data[i][79] += data[i+1][79]

#For each cell, add which ever is lower, the cell to the right, or the cell below
for i in range(78,-1,-1):
 for j in range(78,-1,-1):
  data[i][j] += data[i][j+1] if (data[i][j+1] < data[i+1][j]) else data[i+1][j]

print data[0][0]
#print data
print time() - start