Ask LSBot
Back to Open Book Shelf

Practice: Chaos in the Grid (Top-Down)

Now that you have seen a bottom-up solution, try implementing the recursive one on your own.

Be sure to utilize the PEDAC process for this problem. You should feel comfortable navigating a matrix, a nested array, with indices before you try to tackle the more difficult recursive step. If it helps, you can extract the matrix navigation work into helper functions. For example, a function that returns the coordinates (indices) associated with the square 'above' the input coordinates could make your main algorithm more declarative and easy to understand.

Feel free to check the walkthrough below if you get stuck.

Problem Description

// You are given a grid represented as a nested array filled
// with empty strings. Chaos, the puppy, is standing at the
// top-left corner of the grid and can move either down or right
// at any point in time. Determine the number of distinct paths
// Chaos can take to reach a bowl of treats placed at the
// bottom-right corner of the grid.

// Define a function `chaosInTheGrid` that, given a nested
// array, returns the number of unique paths that Chaos
// can take to reach the bottom-right corner.

// The grid will have at least 1 row and 1 column.

// Example:

// Given the following 2x3 grid:

const grid = [
  ["", "", ""],
  ["", "", ""],
];

// There are three distinct path Chaos can take:
// 1. Right -> Right -> Down
// 2. Right -> Down -> Right
// 3. Down -> Right -> Right

function chaosInTheGrid(grid) {
  // implementation
}

// Test cases

const grid1 = [[""]];
const grid2 = [
  ["", ""],
  ["", ""],
];
const grid3 = [
  ["", "", ""],
  ["", "", ""],
  ["", "", ""],
];
const grid4 = [
  ["", "", "", "", ""],
  ["", "", "", "", ""],
  ["", "", "", "", ""],
];
const grid5 = [
  ["", "", "", "", "", ""],
  ["", "", "", "", "", ""],
  ["", "", "", "", "", ""],
  ["", "", "", "", "", ""],
  ["", "", "", "", "", ""],
  ["", "", "", "", "", ""],
];
console.log(chaosInTheGrid(grid1) === 1);
console.log(chaosInTheGrid(grid2) === 2);
console.log(chaosInTheGrid(grid3) === 6);
console.log(chaosInTheGrid(grid4) === 15);
console.log(chaosInTheGrid(grid5) === 252);
// All test cases should log true

Exercises

  1. Write a base case, a recursive definition, and describe a way to cache the repeating subproblems.

    View Our Solution

    Base Case

    What could be the base case for this problem?

    Just like in the bottom-up approach, where we populated the first row and column with 1s, this can also serve as our base case in the top-down approach.

    Base Case: If we're considering a square in the first row (the first subarray in the grid) or the first column (the first element in each subarray in the grid), return 1.

    Recursive Definition

    What about the recursive definition? This is usually harder to come up with.

    Put yourself in Chaos's shoes. If he is standing at the bottom-right square and he knows the number of unique paths to get to all other squares, what is the number of unique paths to reach that bottom-right square?

    Recursive Definition: The number of unique paths to get to the bottom-right square is the sum of the number of paths to get to the square immediately above it plus the number of distinct paths to get to the square immediately to its left.

    Memoization

    Finally, what can we use to cache the repetitive computations? The Map could work, and that's what we'll use here. We know the value should be the number of distinct paths, but what should the keys be?

    In this case, the key can be the coordinates of the square. How can we represent those coordinates? Using an array wouldn't be a good choice as two arrays with the same values are not considered equal, so that wouldn't work with our Map. We can create a string from the coordinates separated by a space. For the first square, it would look like this:

    cache = {
  "0 0": 1
}

    Another option is to use a nested array as a cache, just like we did in the bottom-up approach, to fill in the values as we moved through the grid. In this case, we would initialize a cache as a nested array. We can fill it with zeroes since we know there is at least one path to the bowl of treats. If the value in the array is zero, it means it hasn't been cached yet.

  2. If you aren't feeling quite ready for the optimized solution, go ahead and implement a brute-force solution.

    View Our Solution

    Here's our brute-force solution:

    function chaosInTheGrid(grid) {
  const rows = grid.length;
  const cols = grid[0].length;

  function pathsToCoord(row, col) {
    if (row === 0 || col === 0) {
      return 1;
    }
    return pathsToCoord(row - 1, col) + pathsToCoord(row, col - 1);
  }

  return pathsToCoord(rows - 1, cols - 1);
}

  3. Implement an optimized solution with your memoization strategy of choice.

    View Our Solution

    Here's a solution using a Map for memoization:

    function chaosInTheGrid(grid) {
  const rows = grid.length;
  const cols = grid[0].length;
  const cache = new Map();

  function pathsToCoord(row, col) {
    if (row === 0 || col === 0) {
      return 1;
    }

    const key = `${row} ${col}`;

    if (cache.has(key)) {
      return cache.get(key);
    }

    const paths = pathsToCoord(row - 1, col) + pathsToCoord(row, col - 1);

    cache.set(key, paths);

    return paths;
  }

  return pathsToCoord(rows - 1, cols - 1);
}

    And here's a solution using a nested array as a cache.

    function chaosInTheGrid(grid) {
  const rows = grid.length;
  const cols = grid[0].length;

  // Initialize a cache as a nested array filled with zeroes
  const cache = new Array(rows).fill().map(() => new Array(cols).fill(0));

  function pathsToCoord(row, col) {
    if (row === 0 || col === 0) {
      return 1;
    }

    if (cache[row][col] !== 0) {
      return cache[row][col];
    }

    cache[row][col] = pathsToCoord(row - 1, col) + pathsToCoord(row, col - 1);

    return cache[row][col];
  }

  return pathsToCoord(rows - 1, cols - 1);
}

  4. Identify the time and space complexity for both the brute-force solution and the optimized solution.

    View Our Solution

    The brute force recursive approach's time complexity without memoization is exponential, O(2^(R + C)), as we have to explore overlapping subproblems many times. R stands for the number of rows, and C stands for the number of columns.

    The space complexity for this approach with memoization is O(R + C). This is because the maximum depth of the recursion stack occurs when the recursion follows a path from the top-left to the bottom-right corner, which is R + C - 1 deep.

    The time and space complexities are identical for the bottom-up and the top-down approaches, both with memoization. Every grid cell needs to be calculated once, and we are filling a cache object with the same number of values, so both the time and space complexities are O(R * C).

    Note that we don't use O(N^2) as we are dealing with two separate values here, rows and columns.

Previous:  Demo: Chaos in the Grid (Bottom-Up)
Next:  Top-Down vs. Bottom-Up Approach

Ask LSBot about: Practice: Chaos in the Grid (Top-Down)

Your questions are private and won't be used to evaluate your performance.

×
This conversation with LSBot is temporary. Sign up for free to save your conversations with LSBot.

Hi! I'm LSBot. I'm here to help you understand this chapter content with fast, focused answers.

Ask me about concepts, examples, or anything you'd like clarified from this chapter. I can explain complex topics, provide examples, or help connect ideas.

Want to know more? Refer to the LSBot User Guide.

Practice: Chaos in the Grid (Top-Down) - Exercise

Your questions are private and won't be used to evaluate your performance.

×
This conversation with LSBot is temporary. Sign up for free to save your conversations with LSBot.

Hi! I'm LSBot. I'm here to help you think through this exercise by providing hints and guidance, without giving away the solution.

You can ask me about your approach, request clarification on the problem, or seek help when you feel stuck.

Want to know more? Refer to the LSBot User Guide.