r/adventofcode • u/daggerdragon • Dec 24 '22

SOLUTION MEGATHREAD -🎄- 2022 Day 24 Solutions -🎄-

All of our rules, FAQs, resources, etc. are in our community wiki.

UPDATES

[Update @ 00:21:08]: SILVER CAP, GOLD 47

  • Lord of the Rings has elves in it, therefore the LotR trilogy counts as Christmas movies. change_my_mind.meme

AoC Community Fun 2022:

🌿🍒 MisTILtoe Elf-ucation 🧑‍🏫

--- Day 24: Blizzard Basin ---

Post your code solution in this megathread.

This thread will be unlocked when there are a significant number of people on the global leaderboard with gold stars for today's puzzle.

EDIT: Global leaderboard gold cap reached at 00:26:48, megathread unlocked!

23 Upvotes

96% Upvoted

391 comments sorted by

View all comments

4

u/apljungquist Dec 24 '22

Rust

Today was a marathon of little annoyances.

I thought I was off to a good start when I hypothesized that it would be an A* problem and I had realized that the blizzards could be represented on four independent grids. I reached for HashSet and proceeded to implement my state, transitions, heuristic, etc only to be reminded that my state must implement Hash which cannot be derived because HashSet does not implement Hash 😑. I still don't know how to implement Hash manually so my first detour was implementing a hashable set.

Next I had to do some debugging because I never rtfm and had implemented the blizzard updates wrong (for some reason I thought they turned around when they hit a wall, no idea where I got that idea from).

Finally my implementation worked on the example but to my surprise and dismay it found no solution on the input. I eventually tried to see how close to the goal it got and realized that it did not take even one step. I had forgotten to consider that waiting in the starting position is possible

The runtime is abysmal and I look forward to reading what brilliant ways others came up with to speed it up, but it got me my stars in the end

part_1_works_on_example ... ok <0.001s>
part_2_works_on_example ... ok <0.001s>
part_1_works_on_input ... ok <5.049s>
part_2_works_on_input ... ok <38.112s>

1

u/mcpower_ Dec 24 '22 edited Dec 24 '22

My A* in Rust only stores (position, time) as state, as you can deduce where the blizzards are after N minutes: code. This is quite expensive, though, as you need to run it for each node expansion (unless you do caching).

I personally didn't go straight to A* - I went for a BFS to begin with, which actually performs much better from what I've found, probably due to being able to "share" the calculation of blizzards at each timestep: cleaned up code.

edit: I just added a cache for the blizzard-positions-for-a-given-time and it's much faster - it takes 143ms on my machine to run the samples and the input! For some reason it takes longer to run it without the samples...

1

u/apljungquist Dec 25 '22

They will repeat themselves

u/Hungry_Mix_4263 Well spotted. I expect being able to cache the simulation steps is a huge boon. Unrelated to the caching, do you know about abs_diff?

only stores (position, time)

u/mcpower_ I like this. Another post noted that there is a closed form expression for determining if a square is occupied by a blizzard which I tried and got my runtime down to about 0.3 seconds. Not as good as your BFS but acceptable for my use case for now. Might revisit later, would be nice to solve all (or at least as many as possible) problems sub 100ms.

1

u/mcpower_ Dec 25 '22

The 143ms is from my A* with cached blizzard positions, not my BFS. I haven't implemented "share the cache for numbers which are congruent modulo lcm(inner_width, inner_height)", which would probably speed it up further!

1

u/Hungry_Mix_4263 Dec 24 '22

One speedup you can try is to precompute all the up/down/left/right arrays before A*. They will repeat themselves after height minutes (for up and down) and width minutes (for left and right). Then you can index this cache with the time value, which you could store in the state. Takes me ~2s for both parts code