Posts Tagged ‘prob67’

Problem 18 (and 67) – Bottoms Up

July 10, 2009

My first idea in simplifying problem 18 (finding a path with maximum sum through a given triangle) was to note that going left then right (LR), you’d end at the same place as going right then left (RL). So if you want maximum sums from some point, you should process the sums LL, LR=RL, and RR separately. I wrote up my first solution pretty quickly, and it gave the right answer for the small sample input. Then I wanted to test its answer on the larger input, so I wrote the brute-force solution that checks all paths. It turned out I made an error in my initial solution (it would never try LLR), and thinking about it a little more turned up what I believe is the correct (and quick) solution.

Instead of working from the top down, work from the bottom up, inductively. At any point of the bottom row, you know the best path to the bottom (since you’re already there). Moving up a row, at any index of the second row from the bottom, you should pick the max of going left or going right, and that’ll be the best path to the bottom. Inductively, if you know the best path starting at any point of some row, then you can easily compute the best path for each index in the next row up. Here’s my code:

from __future__ import with_statement

import sys, time

def readfile(filename):
    """ Read in a file, return a list of (lists of) integers """
    ret = []
    with open(filename) as file:
        for line in file:
            ret.append(map(int,line.split()))
    return ret

def solve(grid):
    """ Find the path with the maximum sum
    Returns: the sum, the path string of L and R, time taken
    """
    t = time.time()

    lowerrow = map(lambda n:(n,""), grid[-1])
    rowidx = len(grid) - 2

    while(rowidx >= 0):
        currow = []
        for col in xrange(0, len(grid[rowidx])):
            if(lowerrow[col][0] >= lowerrow[col + 1][0]):
                lowsum, lowstr = lowerrow[col]
                currow.append((lowsum + grid[rowidx][col], "L" + lowstr))
            else:
                lowsum, lowstr = lowerrow[col + 1]
                currow.append((lowsum + grid[rowidx][col], "R" + lowstr))
        lowerrow = currow
        rowidx -= 1

    rsum, rpath = lowerrow[0]

    t = time.time() - t
    return (rsum, rpath, t)

if __name__ == "__main__":
    print solve(readfile(sys.argv[1]))
Advertisements