Reccurence algorithm: find position after n moves

Question

Introduction

I am trying to code the problem cited in Finding the position at n?. For this purpose I just used the formula that was posted in the question. I didn't go through the formulas and answers they are a little too complicated for me. I wrote the code in python and it is represented in here.

Description of the algorithm (copied)

This dance asks every performer to follow a precise sequence of steps:

• Stage 0 : First, get away from obstacles by setting up your starting point at position 0

• Stage 1 : Take one step forward (+1 step)

• Stage 2 : Take two steps backward (-2 steps)

• To follow, the steps as well as the direction you will have to take in your next move will each time be obtained thanks to a specific calculation: the number of steps you took on the previous stage minus the number of steps you took on the penultimate stage.

That is, on stage 3, a dancer will have to take 3 steps backwards (-2 - 1).

At stage 3, the dancer is at position -4.

stage(n) = stage(n-1) - stage(n-2)

pos(n) = pos(n-1) + stage(n)

At stage 4, the dancer is at position -5.

---

Source code

#!/usr/bin/python
if __name__=="__main__":
    s = [0, 1, -2]
    p = [0, 1, -1]
    for n in range(3, 5):
        diff = s[n - 1] - s[n - 2]
        s.append(diff)
        p.append(p[n - 1] + diff)
        print "Position at stage %s is %s" %(n, p[len(p) - 1])

---

Question

My problem is that suppose that we have more than 10 million stages. The lists p and s will grow and might cause a problem with the memory. Is there a way to solve that problem. I couldn't find another solution than using lists.

If I remove the first elements s.pop() p.pop() it is an index out of range exception. It is normal. Beyond that I can't figure out where to continue.

---

update

It was simpler thant I thought.

#!/usr/bin/python
if __name__=="__main__":
    last_move = -2
    penultimate_move = 1
    previous_position = -1
    for n in range(3, 5):
        #compute current move and position
        current_move = last_move - penultimate_move
        current_position = previous_position + current_move
        
        #do switch in here
        penultimate_move = last_move
        last_move = current_move
        previous_position = current_position

        print "current position %s" %current_position

Answer 1

There is a trivial solution to this: at stage 6, 7 and 8, the positions happen to be 0, 1 and -1 respectively, which are the same positions as the initial positions. As the next stage and position only depend on the previous pair of stages, and previous position, the same sequence is guaranteed to repeat.

And so the function to calculate the position for a given n, can just be:

def position(n):
    return [0, 1, -1, -4, -5, -3][n % 6]

And the function to calculate the stage with number n:

def stage(n):
    return [3, 1, -2, -3, -1, 2][n % 6]

Answer 2

For such kind of problems you must try finding solutions for some cases, may be you will find a pattern like I find which will help you to solve this problem in O(1) time and just a list of 6 elements.

Let's iterate it for few initial stages,

           Steps to take      New position
Stage 0        ---                0
Stage 1         1                 1
Stage 2        -2                -1
Stage 3        -3                -4
Stage 4        -1                -5
Stage 5         2                -3
Stage 6         3                 0
Stage 7         1                 1
Stage 8        -2                -1
Stage 9        -3                -4
Stage 10       -1                -5

So you can see that after Stage 6 the pattern repeats. So the following python code will help you solve this faster.

def getpos(n):
    '''Returns the position of the performer after nth stage.'''
    ls = [0, 1, -1, -4, -5, -3]
    return ls[n % 6]

def getstep(n):
    '''Returns the step taken at nth stage'''
    ls = [3, 1, -2, -3, -1, 2]
    if n == 0:
        return None
    return ls[n % 6]

The functions getpos() and getstep() are utility functions which you will need in this problem.

Answer 3

Okay; let's start with the recurrence definition:

stage(n) = stage(n-1) - stage(n-2)
pos(n) = pos(n-1) + stage(n)

Now, let's make our three variables:

pos is for pos(n)     -- position
ult is for stage(n-1) -- ultimate
pen is for stage(n-2) -- penultimate

The update is simple, given above. This initial values are given in the problem and your code:

pos = -1
ult = -2
pen = 1

Now, each time through the loop, update the values as given above.

stage_n = ult - pen
pos += stage_n

The last step is to prepare for the next iteration. When we take one more step, that becomes the ultimate for the next iteration; the current ultimate gets demoted to penultimate:

pen = ult
ult = stage_n

... and now we're ready to go back to the top of the loop.

Overall, it looks like this:

limit = <wherever you want to stop>

pos = -1
ult = -2
pen = 1

for n in range (3, limit):
    stage_n = ult - pen
    pos += stage_n

    pen = ult
    ult = stage_n

print "Step", limit, "is at position", pos