Demo: Hopping Chaos I

In this assignment, we will explore how to use Dynamic Programming to solve a specific problem: Hopping Chaos.

Problem Description

// A puppy named Chaos is eager to reach a bowl of
// treats at the top of a series of n stacks of
// crates. Each stack is higher by one crate than
// the previous one, forming a structure similar
// to stairs. Each time, Chaos can hop either one
// stack or two stacks upward in his excitement. In
// how many distinct ways can Chaos reach the bowl?

// Write a function `hoppingChaos` that, given a
// number `N` as the input, determines the number
// of distinct ways Chaos can reach the bowl.

// The minimum amount of stacks is one, and the maximum is 50.

// Example 1:

    // Input: 2
    // Output: 2

    // Chaos can reach the top of the stack in two distinct ways:

    // 1. Hop 1 stack, then hop 1 more stack.
    // 2. Hop 2 stacks in one go.

// Example 2:

    // Input: 4
    // Output: 5

    // Chaos can reach the top of the stack in five distinct ways:

    // 1. Hop 1 stack, hop 1 stack, hop 1 stack, then hop 1 stack.
    // 2. Hop 1 stack, hop 1 stack, then hop 2 stacks in one go.
    // 3. Hop 1 stack, then hop 2 stacks in one go, then hop 1 stack.
    // 4. Hop 2 stacks in one go, hop 1 stack, then hop 1 stack.
    // 5. Hop 2 stacks in one go, then hop 2 stacks in one go again.

function hoppingChaos(n) {
  // implementation
}


console.log(hoppingChaos(2) === 2);
console.log(hoppingChaos(3) === 3);
console.log(hoppingChaos(4) === 5);
console.log(hoppingChaos(8) === 34);
console.log(hoppingChaos(13) === 377);
console.log(hoppingChaos(17) === 2584);
console.log(hoppingChaos(21) === 17711);
console.log(hoppingChaos(50) === 20365011074);
// All test cases should log true.

Top-Down Walkthrough

In this walkthrough, we will use a top-down, recursive approach with memoization.

Let's first visualize the problem. A puppy named Chaos is sitting in front of a series of stacks of crates. There are five stacks, and a bowl of treats is placed at the top of the last, highest stack.

If you remember from the Valid Palindrome Walkthrough assignment, to solve a recursive problem, we need to define a base case and a recursive definition. Let's revisit these terms again:

• Base Case - The simplest scenario in a recursive function where the solution is directly evident.
• Recursive Definition - A declarative description of the problem in English, explaining how the problem can be solved using smaller instances of the same problem for an input of N. In the recursive definition, we assume the problem is solved for all other inputs smaller than N.

---

Base Case

Let's begin with the base case, as this is usually the easier part of the problem. When thinking about the base case, consider what the input needs to be so that you can provide the solution instantly. If I tell you that the input is 5, you most likely can't do that, but what if the input is 1?

If there is only one stack with one crate, then there is only one way for Chaos to get there.

If we have two stacks of crates, Chaos can either hop one stack at a time or hop two stacks in one go to get to the top of the second one.

This leads us to our base case:

Base Case: There is one distinct way to get to the first stack and two distinct ways to get to the second stack.

You might be wondering why we didn't choose only one stack as the base case. Why not three? We haven't chosen only one stack because Chaos can hop two stacks at a time, so we would completely miss that possibility. Since Chaos can't hop three stacks at a time (yet 😊), we don't need that case, as it is already included in the previous two cases. We'll see this in the "Bottom-Up Approach" solution.

Recursive Definition

How do we figure out the recursive definition? It might be simplest to put yourself in Chaos's shoes and think about how many unique ways Chaos can reach the top if he knows the number of ways for all other stacks.

Important: We are counting unique (distinct) ways, NOT hops. Let's see this using the example of three stacks.

If Chaos takes one hop to stack one, then hops to stack three using a two-stack hop, this is considered one distinct way, even though he's made two hops.

Similarly, if he takes two single hops to get to stack two and then makes a third single hop, this is still one distinct way, just with one hop added.

Finally, if he initially makes a two-stack hop and then adds another hop, again, this is a single distinct way.

So, remember, we are counting the distinct ways to reach the top, not the individual hops.

The next important question we have to ask is: From where can Chaos reach the top? Since he can only take a one-stack hop and a two-stack hop, he can get to the top either from the stack N-1 or N-2.

Recursive Definition: The number of distinct ways to get to stack N is the number of distinct ways to get to stack N-1 plus the number of distinct ways to get to stack N-2.

If this looks similar to the Fibonacci problem we've discussed in the lesson about recursion, that's because it is a very similar problem, just phrased differently.

Interview Tip: In job interviews, you often get problems similar to ones you have already solved, just phrased differently.

Brute-force Solution

Now that we have a base case and a recursive definition, we can write a brute-force implementation:

function hoppingChaos(n) {
  if (n === 1) {
    return 1;
  }
  if (n === 2) {
    return 2;
  }
  return hoppingChaos(n - 1) + hoppingChaos(n - 2);
}

---

Adding Memoization

Now that we understand our recursive solution, the only thing left is memoizing repeated computations. Usually, in DP problems, we use a hashmap or an array for memoization. In this problem, this is not necessary, and we'll show you that solution as well, but to learn the process will start by using a Map.

When dealing with memoization, the main question is, what do you memoize (cache)? What can help you answer this question is asking yourself, what are we trying to find in the problem? That is usually written somewhere in the problem description and might be obvious, but it could sometimes be more elusive.

From the problem description, we can see that we are looking for the number of distinct ways to get to a stack N. So what can we cache? The stack number, whether a second stack, third stack, fourth stack, etc., seems like a good choice as a key, with the value as the number of distinct ways to get to that stack.

Now that we know what to cache, remember these two important rules about caching:

1. Always check if the value is already in the cache before performing any calculations. If it is, return the cached value.

2. If the value is not in the cache, calculate the value and then add it to the cache.

Memoized Solution

Here's the memoized version:

function hoppingChaos(n) {
  const memo = new Map();

  function waysToN(n) {
    if (n === 1) {
      return 1;
    }
    if (n === 2) {
      return 2;
    }
    if (memo.has(n)) {
      return memo.get(n);
    }
    const result = waysToN(n - 1) + waysToN(n - 2);
    memo.set(n, result);
    return result;
  }

  return waysToN(n);
}

Note that we have defined a helper function, waysToN, because we don't want to change the function signature of the original function by adding a cache, as we said in this assignment.

Time and Space Complexity

The time complexity for this problem, similar to that of the Fibonacci function that we've seen in this assignment, is exponential O(2^N) without memoization. If you tried to run the brute force solution against the test cases, you probably noticed that the final test case with 50 stacks didn't terminate, or you waited for a very long time. This is an excellent example of exponention growth in time complexity.

With memoization, we avoid repeated computations, and every subproblem is solved only once, resulting in a time complexity of O(N).

Since our cache stores the results for every subproblem, and there are N subproblems, the total amount of space required is also O(N).

As we mentioned earlier, this problem doesn't require an additional data structure, and we can solve it in constant space without recursion. We'll see that code implementation in the next assignment when we discuss the bottom-up approach.