Okay, a noticable speedgain by using the aforementioned generators…
Part a went to ~12 seconds (~3 times faster) and part b to ~6 (~2.5 times faster).
Since I linked to the files on master branch, following the link in my previous post will take you to the version using generators, the older version using streams is available in the history of that file (thats why I keep them in version control).
Since in day 13 I saw a huge performance overhead of streams in a tight long loop with simple inner steps, here I immediately decided to roll a plain recursion. It takes about 3 seconds for each part on my machine. Here’s my solution.
There is certainly more “stuff” happening with Streams compared to plain recursion. As you say, there is the closure indirection, and also there’s constant wrapping into and unwrapping out of :suspended tuples, and there’s manual iteration through all the composed functions. See Enumerabl impl for Stream for details.
My guess is that when the actual work in each iteration is fairly simple and short, the running time gets significantly dominated by the stream overhead. Two days ago, compared to my streaming approach, the recursive solution by @mitja reduced the running time by the factor of 20
TBH, I didn’t use streams a lot in real work, so I decided to practice them through AoC. I really like how they are highly composable, and how I get the stable memory usage just like with recursion. I think I’ll be using streams much more in the future.
That said, in the code which is highly CPU bound and performance critical, the penalty of streams can become too high, and falling back to plain-old recursion can help significantly.
I wasn’t talking about streams here, but about my generator approach which takes about twice as long as your solution and there aren’t much differences between our code.
Wow… That wasn’t expected… Part 1 was done pretty quickly, part 2 suffers from a massive performance problem… When I reduce the number of iterations to 1_000, I need ~20 seconds, and I’m not really fund of the idea to adjust the timeout… If its linear, I need to set it to roughly 232 days…
As I already have experimented with NIFs using :rustler for day 10/14 combo, I think I will use a NIF here as well, I really can’t come up with an idea to improve the performance by the factor ~500_000 otherwise…
I glanced your solution on my mobile, but I don’t get how or why it works right now…
I do have found a solution using rustler, but it is my personal goal to find a pure elixir solution for every day that fits into the ex_unit default timeout of 60 seconds…
In the meantime I talked to some other people, they used other languages and printed out every iteration, they reported it seems as if there were a repeating patttern, at least visually.
As I’m the only one of us 3 that actually solved part 2 so far, I might redo part 2 and look out for repetition.
Yes, I was pretty sure that brute-forcing won’t work here, so I felt there had to be some way to radically reduce the number of dances. I went down some wrong paths, before trying to the cycle, and there it was, after only 60 dances
I’m not very happy with this solution, as I’m not really sure about how long a cycle can be. I went to the reddit thread to see how others solved it. Most of them also went for the cycle detection. However, I discovered this solution which I find highly elegant, and it works very fast. It took me a bit to figure it out, but now that I do, I really like it. I didn’t have the time to code it in Elixir, but it shouldn’t be complicated.
Here’s my day 16 solution. The code itself isn’t too elegant, but I’m happy that I found a fast solution to part 2. That definitely took some outside of the box thinking, though.
Agreed, it was much easier than yesterday, as soon as you spot the trick for part 2 (which is IMO not all that hard, and there’s even a hint in the task description).
Here’s my take. After a bit of experiments, I also went for a basic recursion, as it provides fastest running times (~ 2sec on my machine).
Apparently I missed that hint. I spent more time thinking about a solution to day 17’s part two than day 16. Here’s the solution I landed on. I’m not sure if I took the best route (I’ll have to check out your solution), but mine takes ~7 seconds on my machine.
I’ve fallen a bit behind but managed to get back on track today.
For Day 14 part 2 I used the logic for counting groups from Day 12. I just had to create a list of connections for each disk space, so that I could use the Day 12 solution. It seems we can use some old solutions for other puzzles as well! I’m really liking how the whole Advent of code is thought out.
I accidentally stumbled upon the solution for Day 16 part II, because I was printing out the order of the programs after each application of dance moves. My dances began cycling at 30 already and on top of that the cycle started at the first move. I didn’t bother to implement a general solution since I guess that the cycling could start at some random repetition and not necessarily the first one.
Since printing out solutions of each step in Day 16 helped me find the solution I also started printing out the solutions for Day 17 and again this helped me spot the trick.