GitHub Repository Submission

When using GitHub mode, paste your repository URL below and click Save URL to store it. The saved URL will be automatically included with every message you send until you choose to clear it. Learn more

Your GitHub repository URL is saved. LSBot will automatically fetch your latest code from this repository for each message. To change the URL, clear it first and save a new one.

Exercise 3

Top-down: Write the optimized solution code for the "Chaos in the Grid with Cats" problem using a top-down approach.

Solution

Now with a Map as a cache:

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

  function helper(row, col) {
    if (row < 0 || col < 0 || grid[row][col] === "C") {
      return 0;
    }
    if (row === 0 && col === 0) {
      return 1;
    }

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

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

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

    cache.set(key, paths);

    return paths;
  }

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

Finally, the solution with a nested array as a cache:

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

  const cache = new Array(rows).fill().map(() => new Array(cols).fill(0));

  function helper(row, col) {
    if (row < 0 || col < 0 || grid[row][col] === "C") {
      return 0;
    }
    if (row === 0 && col === 0) {
      return 1;
    }

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

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

    return cache[row][col];
  }

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

// Test Cases:

const grid1 = [
  ["", "C"],
  ["", ""],
];
const grid2 = [["", "C"]];
const grid3 = [
  ["", "", ""],
  ["", "C", ""],
  ["", "", ""],
];
const grid4 = [
  ["", "", "", "", "C"],
  ["", "C", "", "", ""],
  ["", "", "", "C", ""],
];
const grid5 = [
  ["", "", "", "", "C", ""],
  ["", "C", "", "", "", ""],
  ["", "", "", "", "", ""],
  ["", "", "", "C", "", ""],
  ["", "C", "", "", "", ""],
  ["", "", "", "", "", ""],
];

console.log(chaosInTheGridWithCats(grid1) === 1);
console.log(chaosInTheGridWithCats(grid2) === 0);
console.log(chaosInTheGridWithCats(grid3) === 2);
console.log(chaosInTheGridWithCats(grid4) === 2);
console.log(chaosInTheGridWithCats(grid5) === 43);
// All test cases should log true

Hi! I'm LSBot. I can help you think through the selected exercise by giving you hints and guidance without revealing the solution. Your code from the editor will be automatically detected. Want to know more? Refer to the LSBot User Guide .

Detected solution
Loading...

Submit your solution for LSBot review.

 Hi! I'm LSBot. Your code from the editor will be automatically detected. I'll review your solution and provide feedback to help you improve. Ask questions about your solution or request a comprehensive code review. Want to know more? Refer to the LSBot User Guide .

Detected solution
Loading...