Advent of Code - adventofcode.com

Argh, I'm thankful the octopus thing is over.

https://github.com/owlz84/advent21/blob/d11p2/src/main/scala/org/stuart/advent21/Wildlife.scala

If I can get another three in tomorrow I'll have almost caught up 🙄😅

Now you've got no. 12 to look forward to...

I was so impressed with the folding puzzle yesterday! Beautifully made.

Have a look at 2018 Day 10 if you want a similarly lovely visual puzzle. (You can do any day from a previous year in isolation.)

Takes literally seconds to run. Can't see any obvious improvements? I guess I could get a marginal increase with a deque as I'm appending, reverse sorting and then popping from the back, where maybe append, sort, pop from front would reduce the sort time? But I suppose a neighbour of the current node should always be pretty close to the start of the node stack

https://github.com/jyates13/aoc2021/blob/main/d15/d15.py

Maybe I could prune some really terrible routes?

(Day 15)

Yeah, I ran out of time to fiddle with mine before I had to start work. My current thing runs in ~14s.

With only going down/right it takes 1.44s (still too long) but obviously doesn't get the right answer as the correct answer requires one up and one left move to find the lowest route.

Need to think about it a bit more when I get a chance (probably not until this evening).

Classic Dijkstra uses uses a priority queue which maintains the invariant faster than the sorted call.

So in practical terms, insert node instead of append and sort? And that'll be O(n) of queue size instead of O(n log n)?

Managed to sneak a bit of time whilst eating my lunch. Down to 1.8s (in perl).

I used an array of arrays to store the unvisited nodes by minimum tentative distance. That saves having to do any sorting.

After work I'll rewrite it in C to see if it that helps it get a lot faster.

That's the naive implementation, if you use a heap, then insertion is O(log n)

Perl is very slow when using arbitrary arrays.

Re-implemented in C:-

$ cat 15.inp | time ./15
part2: 2838
0.01user 0.00system 0:00.01elapsed 100%CPU (0avgtext+0avgdata 39408maxresident)k
0inputs+0outputs (0major+2498minor)pagefaults 0swaps

That'll do me. Will tidy up and post code later, need to do dinner...

Not particularly neat but it works quickly: https://gist.github.com/alexgreenbank/64942c2fa7263a4e9dcae0d56e9d63f5

Just managed to sneak day 16 in before I started work.

Definitely an exercise in reading before jumping in.

Tremendously ugly solution but it works. Will definitely clean it up (eventually) if this is going to be extended at some point (not sure, the spare bits in the version mean there could be more space for expansion...)

It definitely took me longer to parse the exercise than write the code...

https://gist.github.com/wence-/500e1bc4633192ac6fee67433aedd974#file-day16-py

Numpy completely fucked me today. My solution worked on all sample inputs but quietly overflowed on the real input. I thought dtype=int would've ensured it worked (as native int never overflows) but apparently not.

I only used it to save time writing the product operation 😭

Day 17: Made it tougher for myself than it needed to be by reusing a variable name and therefore throwing off one part of my code.

Just did enough to get the answers, need to think about it some more to work out how to optimise it properly.

I've had two days this year where scala let me do something stupid with integers. I guess that's the price you pay for these 'anything-goes' statically typed, compiled languages. They just lack the rigour and battle-testedness of python.

Dvnqk.

Tried to make sense of Day 18 by reading it a few times but no chance. Will have another look in the morning when sober.

All the square brackets...

https://github.com/jyates13/aoc2021/blob/main/d18/d18.py

First time I've broken 200 lines* today. And first time I've beaten everyone on the forum I think (although that seems to be nothing more than a function of free time given I didn't start til 1 😄)

* absolutely no necessity to do this - I suffer from Overly Defensive Programming Syndrome thanks to 2019 intcode

Will have another look in the morning when sober.

Lying in bed and couldn't sleep as my slightly addled brain was whirring. Sobered up a bit and it was easier than expected (especially when I fixed the annoying problem of trying to apply splits when there were new explodes.)

(Being mildly dvnqk meant I did complete it using string processing and regex though. Ugh.)

Day 19 was a bit of fun.

My current solution (that I stopped hacking on when it gave the correct answers) runs in 2.65s for the example input and 292s for my input. But it is a slow thing written in perl - some optimisation work definitely required.

12.9s to do both parts for me. I found this to be an utter arse of a problem though, took me 3 hours probably

https://github.com/jyates13/aoc2021/blob/main/d19/d19.py

Definitely some improvements possible if I stopped rotating the values over and over. Also could maybe reduce the parameter space by removing already-matched beacons or similar

I definitely know there's a chunk of time to be saved as I'm doing 48 translations instead of the minimum 24 that are needed (I'm doing a bunch of invalid reflections too. See https://en.wikipedia.org/wiki/Chirality for more fun on that.) and the rest of the speed up would be implementing it in something like C or Python rather than perl.

I enjoyed this problem though, but my brain seems to prefer this type of visual problem.

I fixed the points from scanner 0 and then attempted to map each other set of scanner points onto the set of fixed points by trying each permutation/transformation against every possible pair of points from the fixed points and the permutation/transformation set, calculating the difference in x/y/z and then seeing how many points from the permutation/transformation set would map on to fixed points with this x/y/z diff. If it was more 12 or more then that was another scanner mapped, and its points were added to the set that had been fixed.

Will rewrite in C at some point in the next few days and see if I can make it fast. I've got a semi-serious plan to get the solution for all days to take under 1s in total (ideally in Go) but I won't have that done for Dec 25th. Day 19 is the only day that isn't under 0.02s though so far.

[EDIT] 192s now with a simple optimisation (of only checking ~half the possible points from each set as each scanner has ~26 beacons so if you need to find 12 that match then there's no point checking the last 10 if you haven't had more than 1 match so far.)

Day 20 was a bit of fun, I spotted the gotcha as I was pasting my input into a file.

Took me a bit of wrangling before I came up with a simpler way of dealing with the infiniteness and that made part 2 very easy.

Yeah that was a bit sneaky. Not too bad in the end though.

Day 21, nice twist for part 2, and didn't take me long to figure out how to do it sensibly. Not very optimised perl (since it uses hashes of strings) runs in ~0.4s. Reckon that would be <0.01s if I did it in C more efficiently.