Skip to content

Latest commit

 

History

History
311 lines (273 loc) · 9.24 KB

24b.md

File metadata and controls

311 lines (273 loc) · 9.24 KB

Day 24 Part Two - Code

After careful analysis, one thing is certain: you have no idea where all these bugs are coming from.

Then, you remember: Eris is an old Plutonian settlement! Clearly, the bugs are coming from recursively-folded space.

This 5x5 grid is only one level in an infinite number of recursion levels. The tile in the middle of the grid is actually another 5x5 grid, the grid in your scan is contained as the middle tile of a larger 5x5 grid, and so on. Two levels of grids look like this:


     |     |         |     |     
     |     |         |     |     
     |     |         |     |     
-----+-----+---------+-----+-----
     |     |         |     |     
     |     |         |     |     
     |     |         |     |     
-----+-----+---------+-----+-----
     |     | | | | | |     |     
     |     |-+-+-+-+-|     |     
     |     | | | | | |     |     
     |     |-+-+-+-+-|     |     
     |     | | |?| | |     |     
     |     |-+-+-+-+-|     |     
     |     | | | | | |     |     
     |     |-+-+-+-+-|     |     
     |     | | | | | |     |     
-----+-----+---------+-----+-----
     |     |         |     |     
     |     |         |     |     
     |     |         |     |     
-----+-----+---------+-----+-----
     |     |         |     |     
     |     |         |     |     
     |     |         |     |

(To save space, some of the tiles are not drawn to scale.) Remember, this is only a small part of the infinitely recursive grid; there is a 5x5 grid that contains this diagram, and a 5x5 grid that contains that one, and so on. Also, the ? in the diagram contains another 5x5 grid, which itself contains another 5x5 grid, and so on.

The scan you took (your puzzle input) shows where the bugs are on a single level of this structure. The middle tile of your scan is empty to accommodate the recursive grids within it. Initially, no other levels contain bugs.

Tiles still count as adjacent if they are directly up, down, left, or right of a given tile. Some tiles have adjacent tiles at a recursion level above or below its own level. For example:

     |     |         |     |     
  1  |  2  |    3    |  4  |  5  
     |     |         |     |     
-----+-----+---------+-----+-----
     |     |         |     |     
  6  |  7  |    8    |  9  |  10 
     |     |         |     |     
-----+-----+---------+-----+-----
     |     |A|B|C|D|E|     |     
     |     |-+-+-+-+-|     |     
     |     |F|G|H|I|J|     |     
     |     |-+-+-+-+-|     |     
 11  | 12  |K|L|?|N|O|  14 |  15 
     |     |-+-+-+-+-|     |     
     |     |P|Q|R|S|T|     |     
     |     |-+-+-+-+-|     |     
     |     |U|V|W|X|Y|     |     
-----+-----+---------+-----+-----
     |     |         |     |     
 16  | 17  |    18   |  19 |  20 
     |     |         |     |     
-----+-----+---------+-----+-----
     |     |         |     |     
 21  | 22  |    23   |  24 |  25 
     |     |         |     |
  • Tile 19 has four adjacent tiles: 14, 18, 20, and 24.
  • Tile G has four adjacent tiles: B, F, H, and L.
  • Tile D has four adjacent tiles: 8, C, E, and I.
  • Tile E has four adjacent tiles: 8, D, 14, and J.
  • Tile 14 has eight adjacent tiles: 9, E, J, O, T, Y, 15, and 19.
  • Tile N has eight adjacent tiles: I, O, S, and five tiles within the sub-grid marked ?. The rules about bugs living and dying are the same as before.

For example, consider the same initial state as above:

....#
#..#.
#.?##
..#..
#....

The center tile is drawn as ? to indicate the next recursive grid. Call this level 0; the grid within this one is level 1, and the grid that contains this one is level -1. Then, after ten minutes, the grid at each level would look like this:

Depth -5:
..#..
.#.#.
..?.#
.#.#.
..#..

Depth -4:
...#.
...##
..?..
...##
...#.

Depth -3:
#.#..
.#...
..?..
.#...
#.#..

Depth -2:
.#.##
....#
..?.#
...##
.###.

Depth -1:
#..##
...##
..?..
...#.
.####

Depth 0:
.#...
.#.##
.#?..
.....
.....

Depth 1:
.##..
#..##
..?.#
##.##
#####

Depth 2:
###..
##.#.
#.?..
.#.##
#.#..

Depth 3:
..###
.....
#.?..
#....
#...#

Depth 4:
.###.
#..#.
#.?..
##.#.
.....

Depth 5:
####.
#..#.
#.?#.
####.
.....

In this example, after 10 minutes, a total of 99 bugs are present.

Starting with your scan, how many bugs are present after 200 minutes?

Your puzzle answer was 2109.

Solution

There's actually not much recursion involved in the solution:

  • Maintain an array of grids, where grids[0] is the inner-most grid thus far, and grids[grids.length - 1] is the outer-most grid thus far.
    • Initially, grids = [initialGrid]
  • For every minute,
    • go through every level, starting from the inner-most level, updating its bugs and empty spaces by looking at the grid right below and above it.
    • Once you're done going through every level,
      • Check if the inner-most level (grids[0]) has any bugs at the inner circle where a level below the inner-most level would develop bugs. I.e., 
        00000
00100
01?10
00100
00000
        If there's any bugs where the 1s are at, then there will be a new inner-most level that you need to evaluate the bug-life on in the same minute.
      • Check if the outer-most level (grids[grids.length - 1]) has any bugs at the outer circle where a level above the outer-most level would develop bugs. I.e., 
        11111
10001
10001
10001
11111
        If there's any bugs where the 1s are at, then there will be a new outer-most level that you need to evaluate the bug-life on in the same minute.

Ignoring the how to get number of neighboring bugs, here's the gist of the code:

const afterOneMinuteAtLvl = (grid: number, getNumOfAdjBugs: (index: number) => number) => {
    let working = grid;
    const hasBugAt = makeHasBugAt(grid);
    for (let i = 0; i < sideLength * sideLength; i++) {
        if (i === 12) // if at center
            continue;
        const adjBugs = getNumOfAdjBugs(i);
        if (hasBugAt(i) && adjBugs !== 1)
            working = kill(working, i);
        else if (!hasBugAt(i) && (adjBugs === 1 || adjBugs === 2))
            working = infest(working, i);
    }
    return working;
};

const afterOneMinute = (grids: number[]) => {
    const working = [...grids];
    const getNumberOfAdjBugs = makeGetNumberOfAdjBugsPlutonian(grids);
    for (let i = 0; i < grids.length; i++)
        working[i] = afterOneMinuteAtLvl(grids[i], getNumberOfAdjBugs(i));

    if (hasBugsAtInnerLvl(first(grids)))
        working.unshift(afterOneMinuteAtLvl(0, getNumberOfAdjBugs(-1)));
    if (hasBugsAtOuterLvl(last(grids)))
        working.push(afterOneMinuteAtLvl(0, getNumberOfAdjBugs(grids.length)));
    return working;
};

// counts the number of bits in grid
const toNumberOfBugs = (grid: number) => {
    let count = 0,
        leftoverGrid = grid;
    for (; leftoverGrid > 0; leftoverGrid >>= 1) // Equiv to leftoverGrid = leftOverGrid >> 1
        count += leftoverGrid & 1;
    return count;
};

export const bugsAfterXMinutes = (initGrid: number) => (mins: number) => {
    let grids = [initGrid];
    for (let i = 0; i < mins; i++) {
        grids = afterOneMinute(grids);
    }
    return grids.map(toNumberOfBugs).reduce((a, c) => a + c, 0);
};

Getting Number of Adjacent Bugs

Some bit masking and storing of which index around ? map to the indices of the inner grid.

/*
00000
00100
01?10
00100
00000
*/
const adjToInnerMask = 0b100010100010000000;
const hasBugsAtInnerLvl = (grid: number) => (grid & adjToInnerMask) > 0;

/*
11111
10001
10001
10001
11111
*/
const perimeterMask = 0b1111110001100011000111111;
const hasBugsAtOuterLvl = (grid: number) => (grid & perimeterMask) > 0;

const isAdjToInner = (index: number) => ((1 << index) & adjToInnerMask) > 0;
const isAdjToOuter = (index: number) => ((1 << index) & perimeterMask) > 0;

const indexToInnerAdjIndices = new Map([
    [7, [0, 1, 2, 3, 4]], // above ?
    [11, [0, 5, 10, 15, 20]], // left of ?
    [13, [4, 9, 14, 19, 24]], // right of ?
    [17, [20, 21, 22, 23, 24]] // below ?
]);

// inverse of indexToInnerAdjIndices, i.e.,
// 0 -> [7, 11]
// 1 -> [7]
// 4 -> [7, 13]
// etc.
const indexToOuterAdjIndices = Array.from(indexToInnerAdjIndices.entries()).map(([k, vs]) => vs.map(v => ({k, v})))
    .reduce((a, c) => a.concat(c), [] as {k: number; v: number}[])
    .reduce((m, e) => {
        const arr = m.get(e.v) ?? [];
        arr.push(e.k);
        return m.set(e.v, arr);
    }, new Map<number, number[]>());

const makeGetNumberOfAdjBugsPlutonian =
    (grids: number[]) => // 0th grid is inner-most
    (level: number) => // current level
    (index: number) => // info about index's neighbors at level
{
    const grid = grids[level] ?? 0;
    const innerGrid = grids[level - 1] ?? 0;
    const outerGrid = grids[level + 1] ?? 0;
    let count = makeGetNumberOfAdjBugs(grid)(index);

    if (innerGrid > 0 && isAdjToInner(index))
        count += indexToInnerAdjIndices.get(index)?.map(makeBugAt(innerGrid)).reduce((a, c) => a + c, 0) ?? 0;
    if (outerGrid > 0 && isAdjToOuter(index))
        count += indexToOuterAdjIndices.get(index)?.map(makeBugAt(outerGrid)).reduce((a, c) => a + c, 0) ?? 0;
    return count;
};