Advent of Code 2017

[NobbZ]

And day 13 is solved as well.

Part 1 was is straight forward. Walk down the list, accumulate the severity, and do not forget to update the list when on an empty field

---

Part 2 is easy as well, I thought… Well, in fact the theory is easy: generate a stream of all possible firewall configurations, attach the delay that fits this config, reject those where we were caught on the first field, and then find one where we have a severity of 0 with the walker from part 1.

This would probably work, but didn’t get me any result after about 10 minutes (went downstairs with co-workers and we talked while they were having a cigarette). So I cancelled the run and added a second walker, which does not keep book about severity but cancels as soon as it is caught and returns false then, true if it reaches the end. I used that to filter the stream of all firewalls, took the first one and returned its delay.

PS: my current solution to part 2 does still take 25 to 30 seconds on my office VM with MIX_ENV=prod. My laptop at home running the code natively and on a current OTP (20 vs 19) is doing it in 20 to 25 seconds.

NB: Office host has an i5-6600K @ 3.50GHz, laptop at home an i5-4210M @ 2.60, I’m wondering if OTP version or running native has a bigger impact on those times…

---

Solution | Input

[sasajuric]

I’m quite happy with the simplicity of my solution for day 13. The running time of ~20sec makes me somewhat unhappy, although the desired delay is quite large. I wonder how much would I gain by replacing streams with recursion, but don’t have the time to try it out

[NobbZ]

Thanks @sasajuric, based on your code, I was able to get down to 6 - 8 seconds on my office VM, and 4.5 to 5.5 at home…

An important step, additionaly to use your way to represent the firewall, was to replace s |> Enum.take_while(&not_empty?/1) |> Enum.count() by s |> Enum.reduce_while(0, &(if not_empty(&1), do: {:halt, &2}, else: {:cont, &2 + 1})) (rough transcriptions of actual code)

Just using take_while/2 and count/1 were even slower on my office VM than my previous code.

[sasajuric]

That’s strange. I just tried out your solution locally, and I get no performance improvement. In other words, I observe no significant perf difference between Stream.take_while |> Enum.count and Enum.reduce_while. In both cases, I get about 20sec of execution time.

[NobbZ]

Thats really funny…

For me (only tested in office) applying the following diff, calculation took ~34-36 seconds, 5 times in a row… Before the patch it was in the range of 6 to 8…

diff --git a/lib/aoc/11-15/day13.ex b/lib/aoc/11-15/day13.ex
index e8c46d2..e016d4c 100644
--- a/lib/aoc/11-15/day13.ex
+++ b/lib/aoc/11-15/day13.ex
@@ -22,9 +22,8 @@ defmodule AoC.Day13 do
     0
     |> Stream.iterate(&(&1 + 1))
     |> Stream.transform(prepare(input), fn n, fw -> {[severities(fw, n)], fw} end)
-    |> Enum.reduce_while(0, fn sevs, acc ->
-      if Enum.empty?(sevs), do: {:halt, acc}, else: {:cont, acc + 1}
-    end)
+    |> Enum.take_while(&(not Enum.empty?(&1)))
+    |> Enum.count()
   end
 
   defp prepare(input) do

[sasajuric]

You have Enum.take_while, in my solution I used Stream.take_while, so that might explain it.

[NobbZ]

Yeah, I realized it right after submitting, with Stream.take_while/2, its ~7 seconds through 3 runs now.

[sasajuric]

Yeah, that makes much more sense, since with Enum you generate a huge list (my result was close to 4 millions).

[NobbZ]

@sasajuric

(my result was close to 4 millions).

Mine as well, ~3.8.

[sasajuric]

Using this monstrosity, I was able to shave it off by some 40%. The code is quite ugly, but the idea is fairly simple, based on sieves. I’m generating failed positions in sorted order, and then stop when the difference between two consecutive positions is > 1. Not sure if the code is 100% correct, but it gives the same output for my input

[mitja]

This is my solution. It works quite fast, it solves the second part in about 750ms.

[JEG2]

My Day 13 solution for Part 2 takes 1.5 seconds on my computer for my input.

The trick I used is to sort the firewall so I try smaller ranges first. They will more often disqualify a specific delay, so short circuiting the instant one fails skips a lot of work. I feel the code is still pretty easy to follow, since I just used Enum.any?/2 to handle the checks.

[petecorey]

TIL about :gb_trees.

Here are my day 12 and day 13 solutions. Nothing notable here. My naive day 13 solution takes ~26 seconds on my machine.

[mitja]

Yeah, I used any? as well and it helps a lot. It terms of simplicity as well as performance.

Good idea with the sorting! I added it to my solution and it shaved off about 10%.

[sasajuric]

This one is quite beautiful and to the point. Great job!

The funny thing is that my published solution uses the same approach, but it’s done in a lazy way through streams. I did expect some penalty for that, but not so much (more than 10x on my machine).

[mitja]

Thanks!

It would be interesting to see how much faster it would be with any? instead of filter. I think it should help a lot since for this problem only 1 out of 4M iterations goes through the whole list

[sasajuric]

The problem is not in the filter, I’m using Stream.filter with Enum.empty?, so this stops as soon as we find the first severity for the given delay. The number of inner comparisons should in fact be the same. However in my solution there are three indirections in the inner loop (Stream.filter, Stream.map, and Enum.empty?), and this is where I guess the problem is. With the loop being tight and long, and inner calculation very simple, the overhead of streams seems to dominate a lot.

[petecorey]

Here’s my day 14 solution. Ignore the old KnotHash module pasted in at the top.

[sasajuric]

Here’s what I came up with.

[NobbZ]

And day 15.

Those who know about Streams and especially about the fact that one can create them from thin air and does not need to have an Enumerable.t() to feed them, should be done in no time with this.

What bugs me a little is, that simply generating thus many numbers takes a lot of time.

Part a takes about 30 to 35 seconds and Part b 14 to 16.

Im wondering if handcrafting generator functions would sped up everything at least a little bit. It would remove some of the indirections of Stream, but introduces its own…

By generator function I mean functions that return a tuple with the next value and a function to generate the next tuple, roughly like this one:

iex(1)> defmodule M do
...(1)>   def gen(input \\ 0), do: {input, fn -> gen(input) end}
...(1)> end
iex(2) {_, f} = M.gen()
{0, #Function<...>}
iex(3) {_, f} = f.()
{1, #Function<...>}
iex(4) {_, f} = f.()
{2, #Function<...>}

---

Solution | Input