Need Help Writing Recursive function that find cheapest route through a list of numbers

Question

So I've been working on this homework problem for a few hours, I'll do my best to explain it.

I need to write a program in python that takes a list and starts you at the first item in the list, you can either move forward one space or jump over an item and land on the other side of it, each item you land on costs the number on that location. The goal is to get to the end as cheaply as possible.

I wrote this function,

def player(cost, board, player_pos):
    if player_pos == (len(board)) - 1:    
        return cost
    if player_pos < (len(board)) - 2:     
        if board[player_pos + 1] > board[player_pos + 2]:
            return player(cost + board[player_pos + 2], board, player_pos + 2)
        else:
            return player(cost + board[player_pos + 1], board, player_pos + 1)
    elif player_pos == (len(board)) - 2:
        return (cost + board[player_pos] + board[player_pos + 1])

but it can't see past the next two positions, so it might make mistakes. A good example is this list [0,1,2,1000,0] my program outputs 3 because it picks 1 over 2, then 2 over a 1000, then 0. This adds up to 3, but the fastest way is jump to 2, then to 0.

In the homework it says it might take a long time to run long lists, I'm guessing they want me to try every possible combination of jumps and pick the cheapest one but I don't see how to do that with using recursion.

EDIT: So this is the improvement I made based off of the comments, It works with all the examples my prof. gave me except for one, this is the list it doesn't return what he said it should. [0, 98, 7, 44, 25, 3, 5, 85, 46, 4] He says it should return 87, but my adjusted program returns 124. Here's the new code:

def player(cost, board, player_pos):
    if player_pos == (len(board)) - 1:    
        return cost
    if player_pos < (len(board)) - 2:     
        if (player(cost + board[player_pos + 2], board, player_pos + 2)) < (player(cost + board[player_pos + 1], board, player_pos + 1)):
            return player(cost + board[player_pos + 2], board, player_pos + 2)
        else: return player(cost + board[player_pos + 1], board, player_pos + 1)
    elif player_pos == (len(board)) - 2:
        return (cost + board[player_pos] + board[player_pos + 1])

score 7 · Accepted Answer · edited Jun 20 '20 at 09:12

The following should work:

def player(l):
    a = b = l[0]
    for v in l[1:]:
        a, b = b, min(a, b) + v
    return b

Example:

>>> player([0, 98, 7, 44, 25, 3, 5, 85, 46, 4])
87

This can be actually considered a dynamic programming algorithm. If c(i) denotes the best cost for the subproblem that uses the first i entries then:

c(1) = cost of first element

c(2) = sum of costs of first two elements

For i > 2 either the best cost is either the best solution reaching the i - 1th element and then including the ith element or the best solution reaching the i - 2th element and then jumping to the ith element. So

c(i) = min(c(i - 1), c(i - 2)) + cost of ith element

The above relation explains the short loop in the code, where a, b are the currently last two best costs.

A recursive version would be like this:

def player(l):
    return min(player(l[:-1]), player(l[:-2])) + l[-1] if l else 0

This recursive program performs an operation to the previous 2 values of the function, in a similar way as the naive recursive function of fibonnaci. It's easy to claim that the above version needs also exponential time. To avoid it, we should use memoization, which means to cache the results of the intermediate recursive calls:

def player(l, cache=None):
    n = len(l)
    if cache is None:
        cache = [-1] * (n + 1)
    if cache[n] < 0:
        cache[n] = min(player(l[:-1], cache), player(l[:-2], cache)) + l[-1] if l else 0
    return cache[n]

It works but I literally have no idea how it works?! It doesn't appear to use recursion does it??? — Slizzard73, Apr 16 '15 at 21:44
really great mindset to break this math down to a function +1. Could you make adjustment cause OP requires **resursion** — Anzel, Apr 16 '15 at 21:56
@Anzel Thanks. If you check http://stackoverflow.com/questions/3323001/maximum-recursion-depth about 1000 is the maximum default recursion depth. I can't do much with this logic. But that's why recursion in general should be avoided in practice. — JuniorCompressor, Apr 16 '15 at 22:52
@JuniorCompressor, I rarely opt for recursive solution but I have been learning `Haskell` and their functional approach is exceptional so I was tempted to try out in Python :) — Anzel, Apr 16 '15 at 22:56

score 1 · Answer 2 · answered Apr 16 '15 at 22:05

This should work. And it's recursive! Basically, at each step, you ask whether you'll fare better going to the next place (and then proceeding optimally) or skipping the next place (and then proceeding optimally). Note that this assumes that you have the option of skipping the first element unless you're given a list of length 1.

def best_choice(l):
    if len(l) == 0:
        return 0
    elif len(l) == 1:
        return l[0]
    else: 
        return min(l[0] + best_choice(l[1:]), l[1] + best_choice(l[2:]))

I know the answer I selected is awesome but it flew right over my head with all the negative list indices, this answer I understood and I thank you! — Slizzard73, Apr 17 '15 at 12:10

score 0 · Answer 3 · answered Apr 16 '15 at 20:24

0

Your algorithm shouldn't discard the 0-->2 jump just because 0-->1 seems immediately better. It should explore both possibilities.

So your program branches, and the two branches explore the sub-problems [1, 2, 1000, 0] and [2, 1000, 0]. Then the second branch of the program will be able to find the 0-->2-->0 path.

answered Apr 16 '15 at 20:24

Mathias Ose

51
1
2

Can you explain how to make the program branch and check both? I'm stuck on that part. – Slizzard73 Apr 16 '15 at 20:29
You have the if statement "if board[player_pos + 1] > board[player_pos + 2]" where you do only one of two recursive. You want to do both those recursive calls, then return the smallest of the values. – Mathias Ose Apr 16 '15 at 20:34
How would I write code to check every possible route? I can only think of manually telling it to do both for every step it takes. – Slizzard73 Apr 16 '15 at 20:37
Not sure what you mean. You want to take your lines 6 and 8, and instead of having an if statement that returns one or the other, run both the recursive calls to get both their return values, then return the smaller of the two. – Mathias Ose Apr 16 '15 at 21:01
You always *pick* one of the two branches to recursively call instead of always calling both and returning the smallest of the two. You'll only have one return statement from the `if player_pos < (len(board)) -2:` block. – John Drouhard Apr 16 '15 at 21:02
Ignore that last comment, did what you said, edited my original post with new code, but one of the examples my prof. gave me doesn't work, I get a higher cost than his did. Any ideas? – Slizzard73 Apr 16 '15 at 21:31

Need Help Writing Recursive function that find cheapest route through a list of numbers

3 Answers3