Skip to content

Latest commit

 

History

History
139 lines (114 loc) · 4.74 KB

24.md

File metadata and controls

139 lines (114 loc) · 4.74 KB
Raw

Day 24: Planet of Discord - Code

You land on Eris, your last stop before reaching Santa. As soon as you do, your sensors start picking up strange life forms moving around: Eris is infested with bugs! With an over 24-hour roundtrip for messages between you and Earth, you'll have to deal with this problem on your own.

Eris isn't a very large place; a scan of the entire area fits into a 5x5 grid (your puzzle input). The scan shows bugs (#) and empty spaces (.).

Each minute, The bugs live and die based on the number of bugs in the four adjacent tiles:

  • A bug dies (becoming an empty space) unless there is exactly one bug adjacent to it.
  • An empty space becomes infested with a bug if exactly one or two bugs are adjacent to it.

Otherwise, a bug or empty space remains the same. (Tiles on the edges of the grid have fewer than four adjacent tiles; the missing tiles count as empty space.) This process happens in every location simultaneously; that is, within the same minute, the number of adjacent bugs is counted for every tile first, and then the tiles are updated.

Here are the first few minutes of an example scenario:

Initial state:
....#
#..#.
#..##
..#..
#....

After 1 minute:
#..#.
####.
###.#
##.##
.##..

After 2 minutes:
#####
....#
....#
...#.
#.###

After 3 minutes:
#....
####.
...##
#.##.
.##.#

After 4 minutes:
####.
....#
##..#
.....
##...

To understand the nature of the bugs, watch for the first time a layout of bugs and empty spaces matches any previous layout. In the example above, the first layout to appear twice is:

.....
.....
.....
#....
.#...

To calculate the biodiversity rating for this layout, consider each tile left-to-right in the top row, then left-to-right in the second row, and so on. Each of these tiles is worth biodiversity points equal to increasing powers of two: 1, 2, 4, 8, 16, 32, and so on. Add up the biodiversity points for tiles with bugs; in this example, the 16th tile (32768 points) and 22nd tile (2097152 points) have bugs, a total biodiversity rating of 2129920.

What is the biodiversity rating for the first layout that appears twice?

Solution

I decided to use a number to represent the grid, where each bit was 1 if a bug at its index existed; otherwise, the bit was 0. Index ranges from [0, 24] inclusively. Index [0, 4] is the first row, and [20, 24] is last row.

The important stuff:

// const bugAt = makeBugAt(grid) returns 1 if there's a bug at index i; 0 otherwise.
export const makeBugAt = (grid: number) => (i: number) => (grid & (1 << i)) >> i;
export const makeHasBugAt = (grid: number) => {
    const bugAt = makeBugAt(grid);
    return (i: number) => bugAt(i) === 1;
};

export const makeGetNumberOfAdjBugs = (grid: number) => (index: number) => {
    let count = 0;
    const bugAt = makeBugAt(grid);
    if (index >= sideLength)
        count += bugAt(index - sideLength); // top
    if (index < sideLength * sideLength - sideLength) // if index < 20
        count += bugAt(index + sideLength); // bottom
    if (Math.floor(index / 5) === Math.floor((index - 1) / 5))
        count += bugAt(index - 1); // left
    if (Math.floor(index / 5) === Math.floor((index + 1) / 5))
        count += bugAt(index + 1); // right
    return count;
};
// alt kill: grid & ~(1 << index). E.g., if index is 2, then 1 << 2
// equals 100, and complement of that is 11..111011, and doing an AND
// with that will unset that bit in grid.
export const kill = (grid: number, index: number) => grid - (1 << index);
// alt infest: grid | (1 << index)
export const infest = (grid: number, index: number) => grid + (1 << index);

// if you want to toggle a bit, you can do XOR (^) because 0 ^ 1 = 1, 1 ^ 1 = 0,
// so grid ^ (1 << index) will toggle it

export const afterOneMinute = (grid: number) => {
    const hasBugAt = makeHasBugAt(grid);
    const getNumberOfAdjBugs = makeGetNumberOfAdjBugs(grid);
    for (let i = 0; i < sideLength * sideLength; i++) {
        const adjBugs = getNumberOfAdjBugs(i);
        if (hasBugAt(i) && adjBugs !== 1)
            grid = kill(grid, i);
        else if (!hasBugAt(i) && (adjBugs === 1 || adjBugs === 2))
            grid = infest(grid, i);
    }
    return grid;
};

export const getRepeatedGrid = (grid: number) => {
    const allGrids = new Set<number>();
    let curr = grid;
    while (!allGrids.has(curr)) {
        allGrids.add(curr);
        curr = afterOneMinute(curr);
    }
    return curr;
};

Why can't we assume the first one will be the first repeat, like in problem 12?

In problem 12, you can go backwards, and there is only solution when you go backwards.

In this problem, if you're at grid, say,

.....
.....
.....
.....
.#...

You could've arrived there from multiple previous configurations.