Discussion on: AoC Day 11: Chronal Charge

[Tiago Romero Garcia]

Javascript solution

I was able to optimize Part 2 using dynamic programming! It went from 146 to 21 seconds!

Basically, for a given (x,y) coordinate, as we increment the square size in 1, the result of the new square total is simply the result of the previous square total + the leftmost column + the bottommost row (and make sure not to sum the last cell twice).

For instance, let's suppose the coordinates are (90,244), and square size is 3 so on brute force we would have to sum this:

const totalForSquareSize3 = 
   grid[90][244] + grid[90][245] + grid[90][246] + 
   grid[91][244] + grid[91][245] + grid[91][246] + 
   grid[92][244] + grid[92][245] + grid[92][246];

With dynamic programming, we would have saved the total for square size 2 in a cache, and then this step would be simply retrieving that and summing the last column and last row minus last cell:

const totalForSquareSize2 = 
   grid[90][244] + grid[90][245] 
   grid[91][244] + grid[91][245];

cache.set('90,244,2', totalForSquareSize2);

...

const totalForSquareSize3 = 
   cache.get('90,244,2') +         grid[90][246] +
                                   grid[91][246] +
   grid[92][244] + grid[92][245] + grid[92][246];

cache.set('90,244,3', totalForSquareSize3);

... 

So we are taking advantage of the previous calculations here.

11-common.js

const buildCell = (x, y, serialNumber) => {
    const rackId = x + 10;
    const powerLevel = ( rackId * y + serialNumber ) * rackId;
    const digit = Math.trunc(powerLevel % 1000 / 100) - 5; 
    return digit;
};

const buildGrid = serialNumber => {
    const grid = Array.from({length:301}, row => Array.from({length:301}));

    for (let i = 1; i <= 300; i++) {
        for (let j = 1; j <= 300; j++) {
            grid[i][j] = buildCell(i, j, serialNumber);
        }
    }

    return grid;
};

const findPowerSquare = (grid, squareSize, cache = new Map()) => {
    let squarePower;
    let top = 0;
    let left = 0;

    for (let i = 1; i <= 300 - squareSize; i++) {
        for (let j = 1; j <= 300 - squareSize; j++) {
            let power = 0;

            const previousKey = `${i},${j},${squareSize-1}`;
            const currentKey = `${i},${j},${squareSize}`;
            if (cache.has(previousKey)) {
                power = cache.get(previousKey);
                for (let k = i; k < i + squareSize - 1; k++) {
                    power += grid[k][j + squareSize - 1];
                }
                for (let k = j; k < j + squareSize; k++) {
                    power += grid[i + squareSize - 1][k];
                }
                cache.set(currentKey, power);
            }
            else {
                for (let k = i; k < i + squareSize; k++) {
                    for (let l = j; l < j + squareSize; l++) {
                        power += grid[k][l];
                    }
                }
                cache.set(currentKey, power);
            }
            if (squarePower === undefined || power > squarePower) {
                top = i;
                left = j;
                squarePower = power;
            }
        }
    }

    return [top, left, squarePower];
};

module.exports = {
    buildGrid,
    findPowerSquare
};

11a.js

const {
    buildGrid,
    findPowerSquare
} = require('./11-common');

(() => {
    const serialNumber = 5719;
    const grid = buildGrid(serialNumber);
    const [top, left, squarePower] = findPowerSquare(grid, 3);

    console.log(`The X,Y coordinate is ${top},${left} and total power is ${squarePower}`);
})();

11b.js

const {
    buildGrid,
    findPowerSquare
} = require('./11-common');

const findPowerSquareOfAnySize = grid => {
    let squarePower;
    let top = 0;
    let left = 0;
    let size = 0;

    const cache = new Map();
    for (let i = 1; i <= 300; i++) {
        const [x, y, power] = findPowerSquare(grid, i, cache);

        if (squarePower === undefined || power > squarePower) {
            top = x;
            left = y;
            size = i;
            squarePower = power;
        }
    }

    return [top, left, size, squarePower];
}

(() => {
    const serialNumber = 5719;
    const grid = buildGrid(serialNumber);    

    const [top, left, size, squarePower] = findPowerSquareOfAnySize(grid);

    console.log(`The X,Y,size is ${top},${left},${size} and total power is ${squarePower}`);
})();

[Ryan Palo]

Ah! Nice! I thought it seemed like caching would really speed things up, but I was too lazy to figure it out. Very cool.