### AoC Day 11: Chronal Charge

#### Ryan Palo on December 11, 2018

Day 11, and we find ourselves falling further back in time. Our wearable time-machine is running low on juice, and we need to figure out how to ...
[Read Full]

Day 11, and we find ourselves falling further back in time. Our wearable time-machine is running low on juice, and we need to figure out how to ...
[Read Full]

lolol this is incredibly slow, but I noticed a pattern and was able to easy escape based on it. I think using numpy is the way to go in order to speed this up.

A speed up I can suggest: pre-compute another grid, say

`sumGrid`

where`sumGrid[x][y] = sum(grid[i][j]`

where`i`

is in`range(x, N)`

and`j`

in`range(y, N)`

So, each element in this new

`sumGrid`

is the sum of all elements below and right to it, including itself.Then

`sum(x,y,size)`

is now just:As an example,

`sum(3,2,5)`

would look like this:We need to add that 4th last term

`sumGrid[x+size][y+size]`

since we have subtracted it twice as part of terms 2 and 3. The solution now avoids two inner`for`

loops — making it much faster :)what was the pattern?

It increased to the high point then decreased from there! After it went negative it stayed negative.

And it kept going negative even after you switched block sizes? Huh, cool.

yup! positive up to a point, then all negative!

Brute force for

part 1and brute force with slight optimization forpart 2(~70 seconds is acceptable so I'm leaving it as is ;)Damn, so I learned today that Julia has both the

`/`

operator AND the`÷`

operator! The`/`

operator will produce a float, regardless of the types of the inputs (so`2/5`

returns`2.5`

) but`÷`

does integer division! So`2÷5`

returns`2`

.Anyways, Part 1 was brute-forceable, on my machine it ran in <0.5 seconds.

But when I attempted to brute-force Part 2...well, it ran in 2 minutes 45 seconds. It works, I guess? I can't help thinking there's a smarter solution to this.

Anyways, my part 2 code:

Python

Part 1

Part 2

Nice use of Numpy! I think you proved @aspittel right. :)

Brute force was enough for part 1:

Part 2 was running for several hours, so I decided to optimize it. Using smaller squares and only adding the right and bottom edge reduced the time to 4m 10s which was good enough for me.

## Kotlin Solution

`<brag type="unseemly">`

I took a night off on Saturday (#9), and ceded my top spot to @tech31842. However, it looks like I'm back in business!`</brag>`

## Part 1

Simple enough... a brute force check was fractions of a second.

## Part 2

This one took some luck I think. I had it chunking through these as fast as I could, but it was still was going to take a few minutes. Luckily I had it printing out the results for each size, and I tried the point where it seemed to find the first maximum. I tried figuring out if I could detect this more easily, but I lost interest. I think I'll get some sleep tonight instead!

## 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.Finished just in time for the next day!

The first part was not too bad, mostly just making sure my code lined up with the algorithm provided and then checking all the squares.

The second part was super duper slow. I think you could probably cache the calculations or use previous calculations of smaller size to speed up calculating the bigger sizes. However, I'm sleepy, and I noticed that the example problems both had maximum totals at relatively low numbers (12 and 16), so I just checked squares with sizes up to 30 in the hopes that I'd get lucky. I did, since my answer was in that range! So, high five for optimization-by-laziness!

I'm also really

reallyproud of my sum-calculating code inside the nested loop. It feels very Rust-like, making use of iterators, take, skip, and flat_map. I did a little wiggle when I finally got it to compile. :)