DEV Community

loading...

[Advent of Code 2020] Day 11 Tutorial (TypeScript)

kais_blog profile image Kai Originally published at kais.blog ・6 min read

This post was originally published at kais.blog. It is part of a series of step-by-step tutorials about the Advent of Code 2020 event.

If you like my content and you want to see more, please follow me on Twitter!

Questions, feedback or just wanna chat? Come and join my Discord!

Prerequisites

I assume you've put your puzzle input into an array called plan where each array item is a line of the input text file. It's up to you to either parse the text file or create an array by hand.

const plan = [
  "LLLLLL.LLLLLLLLLLL.LLLLLLLLLLLLLLLLLLL.LLLLLLL.LLLLLLL.LLLLLL.LLLLLLLLLLLLLL.LLLLL.LLLLLL.LLLLLLL",
  "......L.L.L...LLLL.L....L...LL....LL.LL..L.L..L..L..LL.....L..LL...LLL...L.LL.L.L...L.L.......L..",
  "LLLLLL.LLLLLLLLLLL.LLLLLLLLL.LLLLLLLLL.LLLLLLL.LLLLLLLLLLLLLL.LLLLLLLLLLLLLL.LLLLLLLLLLLLLLLLLLLL",
  
];
Enter fullscreen mode Exit fullscreen mode

Solution

Preface

Starting with Day 10, I'll just publish my solution for both parts without explaining every single step. Unfortunately, I can't continue providing full step-by-step tutorials for each day. The concepts used get more difficult day by day. So, I've concluded that it's better if I wrote separate blog posts about these concepts later.

Also, it's holiday season. This makes it much more difficult creating well-thought-out tutorials. However, I'll try to annotate my code examples a little. This way, you might understand what I've done.

I will now move on to sharing useful tips for web developers regularly. These should help you become a better developer. Also, the shared tips should help with solving problems like those we encounter in Advent of Code. Here's my first post:
14 Awesome JavaScript Array Tips You Should Know About

Puzzle

Just to make sure, you know what I'm talking about, take a look at today's puzzle:

Day 11: Seating System

Part 1

For part 1, we should make sure to track whether changes occurred. Then, we keep looping until there are no more changes. While looping, let's copy the current seating plan (plan) and apply changes to the copy (newPlan). After each iteration, we replace the current plan with our copy.

Changes might occur for empty and occupied seats. For both, we should check how many adjacent seats are occupied. Therefore, I've created the occupiedSeatsAdjacentTo function. An empty seat changes to occupied, if there are no occupied seats adjacent to it. Also, an occupied seat changes back to empty if there are no more than 4 occupied seats adjacent to it. We'll have to change the plan according to these rules, until there are no more changes detected.

Then, we can simply sum the occupied seats, and we've found our solution:

// Find `maxRow` and `maxColumn`.
// This way, we know when to stop looping.
const maxRow = plan.length - 1;
const maxColumn = plan[0].length - 1;

let hasChanges = false;

// Keep looping until no more changes are detected.
do {
  // Copy our initial plan. Seats change simultaneously.
  // So, we have to look at our initial plan and apply
  // changed to our new plan.
  const newPlan = plan.slice();

  // `true` if changes were necessary.
  hasChanges = false;

  // Check all seats in every row and column.
  for (let row = 0; row <= maxRow; row++) {
    for (let column = 0; column <= maxColumn; column++) {
      const seat = plan[row][column];

      // Floor (.) never changes.
      if (seat === ".") {
        continue;
      }

      const occupiedSeats = occupiedSeatsAdjacentTo(row, column, plan);

      // Check if a seat is empty (L) and there are no occupied seats adjacent to it.
      if (seat === "L" && occupiedSeats === 0) {
        hasChanges = true;
        toggleSeat(row, column, newPlan);
        continue;
      }

      // Check if a seat is occupied (#) and four or more seats adjacent to it are also occupied.
      if (seat === "#" && occupiedSeats >= 4) {
        hasChanges = true;
        toggleSeat(row, column, newPlan);
      }
    }
  }

  // Our new plan becomes our current plan for the next loop.
  plan = newPlan;
} while (hasChanges);

// Find the count of occupied seats.
return plan.reduce((previousValue, currentValue) => {
  // Remove all empty seats and add number of occupied seats.
  return previousValue + currentValue.replace(/[^#]/g, "").length;
}, 0);
Enter fullscreen mode Exit fullscreen mode
const directions = [
  // up
  [-1, 0],
  // down
  [1, 0],
  // left
  [0, -1],
  // right
  [0, 1],
  // up-left
  [-1, -1],
  // up-right
  [-1, 1],
  // down-left
  [1, -1],
  // down-right
  [1, 1],
];
Enter fullscreen mode Exit fullscreen mode
function occupiedSeatsAdjacentTo(
  row: number,
  column: number,
  plan: string[]
): number {
  // Search in all directions.
  // Filter out directions where no occupied seat is adjacent.
  // After that, length of the array is the occupied seat count.
  return directions.filter(
    (direction) => plan[row + direction[0]]?.[column + direction[1]] === "#"
  ).length;
}
Enter fullscreen mode Exit fullscreen mode
function toggleSeat(row: number, column: number, plan: string[]): void {
  // Toggle a seat's state from occupied to empty or vice versa.
  const newRow = [...plan[row]];
  newRow[column] = newRow[column] === "#" ? "L" : "#";
  plan[row] = newRow.join("");
}
Enter fullscreen mode Exit fullscreen mode

Part 2

Part 2 is very similar to part 1. Almost everything stays the same. However, we'll have to modify the implementation for our change detection a little. Now this time, we have to check more than the adjacent seats. For each of the eight directions, we should check if there is an occupied seat visible.

Therefore, we'll use the occupiedSeatsVisibleFrom function I've implemented. The function checks each direction and keeps moving into that direction until it either finds an empty or an occupied seat (or moving on is impossible).

Now, again, we have to change the seating plan according to the rules from the puzzle description. Like in part 1, an empty seat changes to occupied, if there is no occupied seat visible. Also, an occupied seat changes to empty, if there are more than 5 occupied seats visible.

We keep applying this logic until no further changes are detected. Then, we simply sum up our occupied seats. So, we've solevd the puzzle:

// Find `maxRow` and `maxColumn`.
// This way, we know when to stop looping.
const maxRow = plan.length - 1;
const maxColumn = plan[0].length - 1;

let hasChanges = false;

// Keep looping until no more changes are detected.
do {
  // Copy our initial plan. Seats change simultaneously.
  // So, we have to look at our initial plan and apply
  // changed to our new plan.
  const newPlan = plan.slice();

  // `true` if changes were necessary.
  hasChanges = false;

  // Check all seats in every row and column.
  for (let row = 0; row <= maxRow; row++) {
    for (let column = 0; column <= maxColumn; column++) {
      const seat = plan[row][column];

      // Floor (.) never changes.
      if (seat === ".") {
        continue;
      }

      const occupiedSeats = occupiedSeatsVisibleFrom(row, column, plan);

      // Check if a seat is empty (L) and there are no occupied seats visible from it.
      if (seat === "L" && occupiedSeats === 0) {
        hasChanges = true;
        toggleSeat(row, column, newPlan);
        continue;
      }

      // Check if a seat is occupied (#) and five or more seats visible from it are also occupied.
      if (seat === "#" && occupiedSeats >= 5) {
        hasChanges = true;
        toggleSeat(row, column, newPlan);
      }
    }
  }

  // Our new plan becomes our current plan for the next loop.
  plan = newPlan;
} while (hasChanges);

// Find the count of occupied seats.
return plan.reduce((previousValue, currentValue) => {
  // Remove all empty seats and add number of occupied seats.
  return previousValue + currentValue.replace(/[^#]/g, "").length;
}, 0);
Enter fullscreen mode Exit fullscreen mode
const directions = [
  // up
  [-1, 0],
  // down
  [1, 0],
  // left
  [0, -1],
  // right
  [0, 1],
  // up-left
  [-1, -1],
  // up-right
  [-1, 1],
  // down-left
  [1, -1],
  // down-right
  [1, 1],
];
Enter fullscreen mode Exit fullscreen mode
function occupiedSeatsVisibleFrom(
  row: number,
  column: number,
  plan: string[]
): number {
  // Search in all directions.
  // Filter out directions where no occupied seat is visible.
  // After that, length of the array is the occupied seat count.
  return directions.filter((direction) => {
    let factor = 0;

    // Use factor to keep moving forward into the current direction.
    // This way, we can see if, somewhere along the way, there is an occupied seat.
    while (true) {
      factor++;
      const seat =
        plan[row + direction[0] * factor]?.[column + direction[1] * factor];

      if (!seat || seat === "L") {
        return false;
      }

      if (seat === "#") {
        return true;
      }
    }
  }).length;
}
Enter fullscreen mode Exit fullscreen mode
function toggleSeat(row: number, column: number, plan: string[]): void {
  // Toggle a seat's state from occupied to empty or vice versa.
  const newRow = [...plan[row]];
  newRow[column] = newRow[column] === "#" ? "L" : "#";
  plan[row] = newRow.join("");
}
Enter fullscreen mode Exit fullscreen mode

Conclusion

The puzzles are getting more and more complicated. Maybe you've found a more elegant solution. However, at least it works, and it was possible to solve this puzzle. I'm eager to see what the next days are bringing.

Thanks a lot for reading this post. Please consider sharing it with your friends and colleagues. See you tomorrow!

If you like my content and you want to see more, please follow me on Twitter!

Questions, feedback or just wanna chat? Come and join my Discord!

This post was originally published at kais.blog.

Discussion (0)

pic
Editor guide