CODEWITHSUNDEEP
pythonrecursioncounter
asp97
asp97

Reputation: 13

Counting paths in a recursive call

The problem I'm working on is this, from Cracking the Coding Interview:

"A child is running up a staircase with n steps, and can hop either 1 step, 2 steps, or 3 steps at a time. Implement a method to count how many possible ways the child can run up the stairs."

Coming from C++ I know that a counter can be passed as reference, but in python you can't. I am also trying to track the step sequence that results in a success. I'm writing my code like this:

def __calculatePaths(currPathLength, paths, currSeries):
  if currPathLength == 0:
    print "successful series is", currSeries
    return 1
  elif currPathLength < 0: return 0

  for i in range(1, 4):
    newSeries = list(currSeries)  # make new series to track steps
    newSeries.append(i)
    paths += __calculatePaths(currPathLength - i, paths, newSeries)
  return paths

def calculatePaths(pathLength):
  paths = __calculatePaths(pathLength, 0, [])
  return paths

if __name__ == '__main__':
    calculatePaths(3)

The output for this call is:

successful series is [1, 1, 1]
successful series is [1, 2]
successful series is [2, 1]
successful series is [3]
6

I'm confused because my program gets the correct path sequences, but the wrong number of paths. How should I be incrementing my paths? I know how to do this without a global variable, but I can't figure it out without using one. Thank you!

Upvotes: 1

Views: 1067

Answers (3)

Bharel
Bharel

Reputation: 26900

This should be the most efficient way to do it computing-wise using your solution:

from collections import deque


def calculate_paths(length):
    count = 0  # Global count

    def calcuate(remaining_length):
        # 0 means success
        # 1 means only 1 option is available (hop 1)
        if remaining_length < 2:
            nonlocal count  # Refer to outer count
            count += 1
            return

        # Calculates, removing the length already passed.
        # For 1...4 or remaining_length+1 if it's less than 4.
        # deque(, maxlen=0) is the fastest way of consuming an iterator
        # without also keeping it's data. This is the most efficient both
        # memory-wise and clock-wise
        deque((calcuate(remaining_length-i)
              for i in range(1, min(4, remaining_length+1))), maxlen=0)

    calcuate(length)
    return count

>>> calculate_paths(2)
2
>>> calculate_paths(3)
4
>>> calculate_paths(4)
7

As you can see, there is no need to keep the path as only the remaining length matters.

@Prune's answer has better algorithm. Here it is implemented:

def calculate_paths(length):
    results = deque((1, 2, 4), maxlen=3)
    if length <= 3:
        return results[length-1]

    for i in range(3, length):
        results.append(sum(results))

    return results.pop()

Eliminating recursion also causes less frames to be used, and doesn't stop with max recursion.

Upvotes: 0

Prune
Prune

Reputation: 77837

Most important, realize that you don't have to determine those sequences: you need only to count them. For instance, there's only one way to finish from step N-1: hop 1 step. From N-2, there are two ways: hop both steps at once, or hop 1 step and finish from there. Our "ways to finish" list now looks like this, working backwards:

way = [1, 2, ...]

Now, watch what happens with step N-3. We finally have 3 choices:

  1. Hop 1 step and have 2 ways to finish
  2. Hop 2 steps and have 1 way to finish
  3. Hop 3 steps and be done.

That's a total of 2+1+1, or 4 ways to finish.

That initializes our algorithm. Now for the recurrence relationship. The initial list looks like this:

way = [1, 2, 4, ...]

From here on, we can't make a single hop to the top. Instead, we have to depend on the three steps above us. Our choices from step N-J are:

  1. Hop 1 step and have way[J-1] ways to finish
  2. Hop 2 steps and have way[J-2] ways to finish
  3. Hop 3 steps and have way[J-3] ways to finish

Thus, for all j >= 3:

way[j] = way[j-1] + way[j-2] + way[j-3]

This gives you the solution in O(N) time.

Upvotes: 1

Vinay Lodha
Vinay Lodha

Reputation: 211

In your function __calculatePaths, you have to set paths = 0, before the for loop. Otherwise it is add the values to the global instance of paths and that's why you are getting wrong answer.

def __calculatePaths(currPathLength, paths, currSeries):
  if currPathLength == 0:
    print "successful series is", currSeries
    return 1
  elif currPathLength < 0: return 0
  paths = 0
  for i in range(1, 4):
    newSeries = list(currSeries)  # make new series to track steps
    newSeries.append(i)
    paths += __calculatePaths(currPathLength - i, paths, newSeries)
  return paths

def calculatePaths(pathLength):
  paths = __calculatePaths(pathLength, 0, [])
  return paths

if __name__ == '__main__':
    calculatePaths(3)

You can get the number of ways in much efficient manner. By using Dynamic Programming in O(N). And even more efficiently using matrix exponentiation O(logN).

Upvotes: 0

Related Questions