sfusato

sfusato

I was able to brute-force it and get my stars for Day 11 by only searching for grids with sizes between 3-30. Mine turned out to be 16 in size. This would run in some 120 seconds :crazy_face:

Learned about summed area table algorithm in here, watched James’s stream (:love_you_gesture:) and now part 2 runs in about 10 seconds for sizes 1-300 :clinking_glasses:

My solution is here.

0
Post #11
stefanchrobot

stefanchrobot

Sweet! Never heard of it before. Here’s the Wikipedia entry. I figured the same idea as @sasajuric, i.e. every even square can be split into 4 smaller ones and I’m memoizing that. The code for squares of odd sizes was considerably slower.

0
Post #13
— All posts loaded —