Python math game algorithm

Question

I have a list and it has (randomly) between 5 and 10 items in it. The first int in the list is always 0 and all others are a random positive number. It could look like this:

0 10 50 45 80 5 35

The goal for the program is to treat the items in the list like spaces, adding to a total sum when you move to the next one. The person starts at 0 and can always either move one space to the right or skip one and land on the next. For example, with the one above I could go from 0 to 10, or 0 to 50 for the first move. I could then do from 50 to 45 or from 50 to 80 and so on.

I want to figure out a recursive algorithm to go through these and find the way to get to the last item with the lowest total sum. Should I be going through every possible combination or is there an easier way to do this? Does it have something to do with checking the value of both possible moves each turn and choosing the lower value?

This is probably a question for cs.stackexchange.com. Regardless, you should look up shortest path algorithms for directed acyclic graphs (DAG). You can simply structure your sequence and allowable moves as a DAG and use any number of well documented algorithms. — andrew
– andrew, Commented Feb 13, 2018 at 19:06

SergGr · Accepted Answer · 2018-02-13 19:15:39Z

1

Yes, there is a more efficient way. This problem looks ideally suitable for dynamic programming. The idea is that you look at the problem in a reverse way: for every position P you may come to it either from the previous one, or from two positions behind. So to find the best route to position P you just need to know best routes to positions (P-1) and (P-2) and then compare them.

If I understand the logic behind the total sum calculation correctly, this is what you need:

def solve(values):
    prev1 = 0
    prev2 = 0
    for p in range(len(values)):
        cur = min(prev1, prev2) + values[p]
        prev2 = prev1
        prev1 = cur

    return cur

and

print(solve([0, 10, 50, 45, 80, 5, 35]))

outputs

95

answered Feb 13, 2018 at 19:15

SergGr

23.8k2 gold badges34 silver badges52 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Python math game algorithm

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related