Advent of Code - Day 11

[JEG2]

Note: This topic is to talk about Day 11 of the Advent of Code.

For general discussion about the Advent of Code 2018 and links to topics of the other days, see this topic.

[JEG2]

Here’s my Day 11 solution:

JEG2/advent_of_code_2018/blob/master/day_11/chronal_charge.ex

The key idea is the use of a summed area table. You can watch a video of me struggling to learn this data structure (for the next 14 days):

[sasajuric]

I also did it using summed area table. My solution is here.

[simon]

I’d not heard of a summed area table before checking this thread (one of the perils of having a history degree rather than a maths or CS one I guess!) so my first attempt was done by brute-force but was so slow that I left it to run over-night. It did give me the right answer however.

This morning I refactored my code to use a summed area table and part 2 runs in around 5 seconds. I’m not sure if that’s good or not.

Anyway, my code is here and it’s probably very similar to the other solutions everyone has come up with.

[sasajuric]

Yeah, I didn’t know about summed area table before this task too

I first tried cooking up some homegrown algorithm based on prime factors. The idea was based on the fact that larger squares can be built from smaller ones. So e.g. if I compute 2x2 squares, I can use those result to build 4x4 squares. When I ran that, it looked like it might finish in some 10 minutes or so, but I wasn’t happy with that, so I aborted the execution.

AFAIK, all AoC challenges can be computed within reasonable time using the proper algorithm, so I knew that my approach is suboptimal. Unfortunately I couldn’t figure out the algorithm myself, so I gave up and went to the reddit thread to look for the right approach. There I found the mention of summed area tables, and then it was just a matter of reading wikipedia article, and implementing it

Btw. one particularity of my solution compared to yours and that of @JEG2 is that I’ve built a stream of all coordinates, which made it possible to avoid nested reduces. This actually made the execution somewhat slower, but it simplified the reducing code (example).

@simon

This morning I refactored my code to use a summed area table and part 2 runs in around 5 seconds. I’m not sure if that’s good or not.

I think that’s fine. My solution runs in about 3.5 secs, and I’m “cheating” by using concurrency. I think this is an example of a task where Erlang/Elixir perform visibly worse than languages like Go, Rust, or even Java, due to slow arithmetic operations and lack of mutability.

[simon]

I tried a similar thing with my own algorithm when calculating the totals for the different square sizes (and this would be most beneficial for larger ones). As you move across the grid you could subtract the total of the previous column of relevant rows and add the total of the newly included column of relevant rows and then do a similar thing for rows when doing the y-axis.

So, for a 3x3 square with an original of 0,0 you’d have a total made up from:

0,0  1,0  2,0
0,1  1,1  2,1
0,2  1,2  2,2

When the origin becomes 1,0 you could remove the sum of 0,0 0,1 and 0,2 and add 3,0 3,1 and 3,2.

However, because is was 2am at that point I decided to stop and just let it run over-night!

I like your stream idea and I must look into doing more with them.

And yes, I should add concurrency too to speed my code up.

[JEG2]

@sasajuric

Btw. one particularity of my solution compared to yours and that of @JEG2 is that I’ve built a stream of all coordinates, which made it possible to avoid nested reduces. This actually made the execution somewhat slower, but it simplified the reducing code (example ).

Genius. Thanks for sharing!

[sasajuric]

@simon

I like your stream idea and I must look into doing more with them.

Yeah, last year I used AoC to practice my streams skills. I think this was a nice gain for me and helped me improve my coding style. As a result, these days I tend to reach for streams more frequently than I used to before AoC

One caveat though: streams can add some significant overhead in large tight loops. IIRC, in this example I got around 1s penalty for converting to streams. I remember that last year on a few occasions I had to completely bypass all enums, and roll my own recursion to get some acceptable running time. But otherwise, yeah, streams are pretty cool

[simon]

@sasajuric

One caveat though: streams can add some significant overhead in large tight loops. IIRC, in this example I got around 1s penalty for converting to streams. I remember that last year on a few occasions I had to completely bypass all enums, and roll my own recursion to get some acceptable running time. But otherwise, yeah, streams are pretty cool

Thank for the info. I’ll go and do some learning and also go and read what you’ve said about them in Elixir in Action.

[sasajuric]

Streams don’t get a lot of treatment in EiA. Some basics are explained, but the area is not really examined in depth. This is one thing I’m considering doing in the 3rd edition

[simon]

You’re committed to writing it now after saying that!

[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

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

My solution is here.

[snewcomer]

Fun one!

snewcomer/advent-of-code-elixir/blob/master/day11/lib/day11.ex

[stefanchrobot]

@JEG2

The key idea is the use of a summed area table.

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.