Euler Solution 82

From ProgSoc Wiki

Jump to: navigation, search

Solutions for Problem 82

Given an 80x80 matrix, find the lowest cost path moving from left to right and up or down as much as desired.

C by SanguineV

I had a bug in the C code so ported to python, found the bug while porting but figured I would post both solutions anyway.

Runtime: 6.091 ms

#include <stdio.h>

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

/* Search through the matrix updating the values along the way.
 * ALGORITHM:
 * 1. Start from the penultimate right hand column. For each row:
 * 2. Search down the column for the cheapest cost.
 * 3. Check the row above to see if it is cheaper.
 * 4. Take the cheapest path to the cell and add it to the cell value.
 * 5. Step one row left and start again. */
int main () {
  int col,row,iter;
  unsigned long curr,acc;
  col = 78;
  while (col >= 0) {
    row = 0;
    while (row < 80) {
      iter = row + 1;
      curr = matrix[row][col+1];
      acc = 0;
      while (iter < 80 && acc + matrix[iter][col] < curr) {
        if (acc + matrix[iter][col] + matrix[iter][col+1] < curr) {
          curr = acc + matrix[iter][col] + matrix[iter][col+1];
        }
        acc += matrix[iter][col];
        iter++;
      }
      if(row > 0 && matrix[row-1][col] < curr) {
        curr = matrix[row-1][col];
      }
      matrix[row][col] += curr;
      row++;
    }
    col--;
  }
  row = 1;
  curr = matrix[row][0];
  while(row < 80) {
    if (matrix[row][0] < curr) {
      curr = matrix[row][0];
    }
    row++;
  }
  printf("Minimum path costs: %u\n",curr);
  return 0;
}

Python by SanguineV

Runtime: 261.145 ms

# The matrix to check
matrix = [...]

# Search through and update - same algorithm as the C code above.
def process():
  col,row,iter,curr,acc = 78,0,0,0,0
  while col >= 0:
    row = 0
    while row < 80:
      iter,curr,acc = row + 1, matrix[row][col+1],0
      while iter < 80 and acc + matrix[iter][col] < curr:
        if acc + matrix[iter][col] + matrix[iter][col + 1] < curr:
          curr = acc + matrix[iter][col] + matrix[iter][col + 1]
        acc += matrix[iter][col]
        iter += 1
      if row > 0 and matrix[row - 1][col] < curr:
        curr = matrix[row - 1][col]
      matrix[row][col] += curr
      row += 1
    col -= 1

# Find the smallest value in the left hand colum.
def themin():
  min = matrix[0][0]
  for row in xrange(1,80):
    if matrix[row][0] < min:
      min = matrix[row][0]
  return min

# Process the matrix
process()
# Print the least cost.
print (themin())
Personal tools