trek.py

if False:
    LOC  = [4,8,12,16,20,24,28,32,36,40,44]
    COST = [4,9,4,6,9,2,6,5,4,8,3]
    DISTANCE = 50
else:
    LOC = [2, 6, 10, 11, 14, 16, 18, 22, 25, 27, 30, 32, 36, 40, 44, 48, 51, 55, 59, 61,
            65, 67, 70, 71, 74, 77, 80, 84, 87, 91, 93, 97]
    COST = [5, 7, 5, 8, 9, 8, 4, 4, 9, 2, 2, 5, 4, 1, 1, 3, 6, 1, 7, 3, 5, 1, 1, 2, 9, 9,
            9, 1, 8, 3, 6, 4,]
    DISTANCE = 100

# To make this work, we need two more locations: 0 and 100 (or whatever the end-point is),
# each with a cost of zero.
LOC  = [0] + LOC  + [DISTANCE]
COST = [0] + COST + [0]
N    = len(LOC)

# Set up the STATE array, where STATE[i] is the minimum cost to span all locations up to LOC[i].
# The first STATE value will remain zero, because that's the cost of going nowhere.
STATE = [0] * N

# We calculate STATE[i] where i starts at 1. Each calculation looks back to find the
# cheapest solution so far [within 10km] and adds to that. The best_so_far function helps
# with that.

def best_so_far(index):
    vals = []
    for i in range(index-1, -1, -1):
        if LOC[index] - LOC[i] > 10: break
        vals.append(STATE[i])
    return min(vals)

for i in range(1,N):
    STATE[i] = best_so_far(i) + COST[i]
    print(i, LOC[i], COST[i], STATE[i])

# Having calculated the best solution up to and including each potential camp, the best
# solution overall is simply the last one that we calculated.
print("Solution:", STATE[-1])