# 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 = { {...} };

/* 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];
while(row < 80) {
if (matrix[row] < curr) {
curr = matrix[row];
}
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
for row in xrange(1,80):
if matrix[row] < min:
min = matrix[row]
return min

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