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:

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{buildGrid,findPowerSquare}=require('./11-common');(()=>{constserialNumber=5719;constgrid=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');constfindPowerSquareOfAnySize=grid=>{letsquarePower;lettop=0;letleft=0;letsize=0;constcache=newMap();for(leti=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];}(()=>{constserialNumber=5719;constgrid=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 is an engineer in the Sacramento Area with a focus in Python, Ruby, and Rust. Bash/Python Exercism mentor. Coding, physics, calculus, music, woodworking.
Message me on DEV!

Location

Elk Grove, CA

Education

M.S.C.S. Lewis University (Spring of 2021), B.S.M.E. Cal Poly (SLO)

## 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:

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:

So we are taking advantage of the previous calculations here.

## 11-common.js

## 11a.js

## 11b.js

Ah! Nice! I

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