Hackbright Code Challenges

Staircase Steps: Solution

Staircase Steps: Solution

Problem

Staircase Steps

Challenge

Harder

Concepts

Recursion, Dynamic Programming

Download

staircase-steps-solution.zip


First, imagine the problem of a staircase with 1 step. You can clearly climb it 1 way.

Now, imagine the problem of a staircase with 2 steps. You can climb is 2 ways:

  • climbing 2 steps at once (“2”)

  • climbing 1 step, then 1 more step (“11”)

For 3 steps:

  • “111”

  • “12”

  • “21

  • “3”

At any point, you can climb 1, 2, or 3 steps – so we can develop a recursive algorithm that tries taking 1 step from where we are, 2 steps from where are, and 3 steps from where we are. If that path is successful, we’ll count it.

For a staircase with 1 step:

digraph step { rankdir=LR start -> {a1, a2, a3}; a1 -> works1; a2 -> nowork1; a3 -> nowork2; start [label="S T A R T" shape="rect"]; a1 [ label="1"]; a2 [ label="2"]; a3 [ label="3"]; works1 [label="=1 +1" fontcolor="darkgreen" color="darkgreen"]; nowork1 [label="=2 +0" fontcolor="firebrick" color="firebrick"]; nowork2 [label="=3 +0" fontcolor="firebrick" color="firebrick"]; }

For a staircase with 2 steps:

digraph step { rankdir=LR start -> {a1, a2, b3}; a1 -> b1 -> works1; a1 -> b2 -> nowork1; a1 -> a3 -> nowork2; a2 -> works2; b3 -> nowork3; start [label="S T A R T" shape="rect"]; a1 [ label="1"]; b1 [ label="1"]; b2 [ label="2"]; b3 [ label="3"]; a2 [ label="2"]; a3 [ label="3"]; works1 [label="=2 +1" fontcolor="darkgreen" color="darkgreen"]; works2 [label="=2 +1" fontcolor="darkgreen" color="darkgreen"]; nowork1 [label="=3 +0" fontcolor="firebrick" color="firebrick"]; nowork2 [label="=4 +0" fontcolor="firebrick" color="firebrick"]; nowork3 [label="=3 +0" fontcolor="firebrick" color="firebrick"]; }

For a staircase with 3 steps:

digraph step { rankdir=LR start -> {a1, b2, a3}; a1 -> b1 -> c1 -> works1; b1 -> c2 -> nowork1; b1 -> b3 -> nowork2; a1 -> a2 -> works2; a1 -> d3 -> nowork5; b2 -> e1 -> works3; b2 -> d2 -> nowork3; b2 -> c3 -> nowork4; a3 -> works4; start [label="S T A R T" shape="rect"]; a1 [ label="1"]; b1 [ label="1"]; b2 [ label="2"]; b3 [ label="3"]; a2 [ label="2"]; a3 [ label="3"]; c1 [ label="1"]; c2 [ label="2"]; c3 [ label="3"]; d2 [ label="2"]; d3 [ label="3"]; e1 [ label="1"]; works1 [label="=3 +1" fontcolor="darkgreen" color="darkgreen"]; works2 [label="=3 +1" fontcolor="darkgreen" color="darkgreen"]; works3 [label="=3 +1" fontcolor="darkgreen" color="darkgreen"]; works4 [label="=3 +1" fontcolor="darkgreen" color="darkgreen"]; nowork1 [label="=4 +0" fontcolor="firebrick" color="firebrick"]; nowork2 [label="=5 +0" fontcolor="firebrick" color="firebrick"]; nowork5 [label="=4 +0" fontcolor="firebrick" color="firebrick"]; nowork3 [label="=4 +0" fontcolor="firebrick" color="firebrick"]; nowork4 [label="=5 +0" fontcolor="firebrick" color="firebrick"]; }

Solution

steps.py
def steps(n):
    """How many different ways can you climb a staircase of `n` steps?

    You can climb 1, 2, or 3 steps at a time.
    """

    # START SOLUTION

    # Base case:
    #
    # It might seem strange to think there's a way to take zero
    # staircase-steps --- but this is really a saying "this path of recursion"
    # is successful, since it ended up using exactly the right number
    # of staircase-steps

    if n == 0:
        return 1

    # If we overshoot, this was not a successful path
    if n < 1:
        return 0

    # The way to take n number of staircase-steps is the way to take
    # n - 1 staircase-steps, n - 2 staircase-steps, and n - 3 staircase-steps,
    # all added up (since we can always take 1, 2, or 3 more staircase-steps
    # afterwards)

    return steps(n - 1) + steps(n - 2) + steps(n - 3)

Memoization

There’s a lot of repetition in what it has to calculate. A more advanced solution can use a concept called “memoization” to remember the solution to already-solved problems.

This moves the problem from being just a recursive solution to one using “dynamic programming” — a good intermediate concept to learn about!

A dynamic programming version is similar, and lets use computer much, much larger staircases:

steps.py
def steps_cache(n):
    """How many different ways can you climb a staircase of `num` steps?

    You can climb 1, 2, or 3 steps at a time.

    In this version, we're caching previous work, so we can do much
    longer calculations.

    For 100 steps: 180,396,380,815,100,901,214,157,639 different ways!

        >>> steps_cache(100)
        180396380815100901214157639

    """

    # Cache previous work, so we don't keep having to re-calculate
    # answers we've already derived. This changes the runtime from
    # O(3**n) to the much, much better O(3n)
    #
    # ``cache`` will hold the results of taking each number of staircase-steps

    cache = [None] * (n + 1)

    def _steps(n):
        """How many ways are there to take `n` steps?"""

        # Base case:
        #
        # It might seem strange to think there's a way to take zero
        # staircase-steps --- but this is really a saying "this path of recursion"
        # is successful, since it ended up using exactly the right number
        # of staircase-steps
        if n == 0:
            return 1

        # If we overshoot, this was not a successful path
        if n < 1:
            return 0

        # If we haven't already cached this work, do so
        if cache[n] is None:
            cache[n] = _steps(n - 1) + _steps(n - 2) + _steps(n - 3)

        return cache[n]

    return _steps(n)