Advent of Code 2019 - Day 16

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

There is a private leaderboard for elixirforum members. You can join it by following this link and entering the following code:

39276-eeb74f9a

Literally magic. This is so slow, tests take 23 seconds to run (mostly due to the first part, which I probably could optimize, but eh…).

Interestingly, there is a part where using Stream.take instead of Enum.take causes wrong results (marked with # If you use Stream.take here, you get incorrect result comment in the code). I wonder if I did something wrong, or is it a bug in Elixir. My understanding is that Stream functions are like Enum functions, just lazy, the entire code I think is purely functional, so it’s a bit strange. But maybe I’m misunderstanding?

My solution for today here

Part 1 feels slow and it took me way too long to figure part 2, but it was fun

This is my solution for day 16. I’m not happy with part 2, because the solution only works if the requested sequence is in the second half. On the upside, part 1 is reasonably fast (about 400 ms on my machine).

1 Like

No fun at all doing the challenge today :frowning_face:

Part1 was okay. But I did not understand anything about the part 2 and the reverse partial sum algorithm I ended up stealing from reddit

If somebody is missing Stream solution of the part 2 today, here it is.

3 Likes

I think that the repeated sequence is always in the second half (that’s part of the gimmick). It has to do with how the matrix works out. How long does yours take to run (pt2)? Mine is super slow—50 seconds.

The trick here is that there is a pattern at the tail of the digits. It is hinted at by noticing that the last digit of the sequence never changes. Essentially, each digit change is based on the sum of everything to the right of it—and nothing is to the right of the last digit.

As noted, my part 2 takes 50s to run and I’m not sure how I’d make it faster? I was happy to use streams in pt1.

edit: I made part 2 down to 5s by removing unnecessary list operations.

What if the input starts with 0000000? :slight_smile:

370ms part 1
2.1s part 2

1 Like

Here is my solution.

I solved part 1 in the morning, but my program needed 17 seconds to find the answer.

That started my day of premature optimization. In hindsight, the problem with my original solution was probably that I used streams in a non-efficient way. I reimplemented part 1 with my own implementation of lazy lists. I hoped that it would be useful for part 2. It wasn’t.

When I saw that all examples and my input had offsets in second half of the input, I knew how to solve it. Unfortunately I did some more premature optimization and didn’t get it to work. I then took a look in the forum and saw all my premature optimizations were totally unnecessary. I wrote my own solution inspired by a quick look at @sasajuric’s solution.

My solution solves part 1 in 0.2 seconds and part 2 in about 3 seconds.

2 Likes

Yeah, in theory streams are a really good fit for today’s problem, but in practice they really aren’t :smiley:

I also started with a pure based stream solution which I really liked, but it was quite slow, so I switched to recursion.

That sums up my sentiment about streams vs recursion. Two years ago, when I started doing AoC, I was mostly uncomfortable with streams, and used either Enums, or classical recursion for anything more involved.

So, I decided to us streams as much as possible, and at this point my impression is that they can often be very expressive and combinatorial (see this tweet), but at the same time they might be too slow. This usually happens when the loop is long, while each step is short, which is exactly the case in today’s challenge. Falling back to a hand-stitched recursion significantly improved the running time (at the expense of readability IMO).

So tl;dr I’d still opt for streams in many cases, but if max performance is required I’d move to recursion.

1 Like

I think that they chose input which is past half only. Every report I’ve read has said this. The input is not random, from my understanding. If it is random, it’s possible to encode the information arbitrarily since the front doesn’t affect the problem at all.

Of course it doesn’t apply to all inputs, but that’s the challenge. We had to find the pattern and use it as an optimization. If the optimization is not available, then it has to be done by actually running the full pattern.

Here are some quotes from Eric Wastl on this topic. First one there he says that the input is part of the problem statement:

https://www.reddit.com/r/adventofcode/comments/bpgv7j/solutions_to_2018_day_20_seem_like_they_should_be/entjkt1/?context=3

Here is another there he says that a lot of work goes into making inputs similar enough to be fair:

https://www.reddit.com/r/adventofcode/comments/e7khy8/are_everyones_input_data_and_by_extension/fa0jhtv/?context=3

Day 16 really sucked.
I didn’t figure it out. I wouldn’t have figured it out. I just don’t know or didn’t recall the magical matrix properties I’d have needed to figure out from this specific input to make it work, so I spent a couple of hours floundering to get you this useless video that will teach nothing and that you should probably not watch:

I’m still bitter about this day being a damn loss of all my free time, it felt like failing a shitty whiteboard programming interview.

2 Likes