Fork me on GitHub

Day 24 - Solutions

norman07:12:52 I did my state management a bit differently than I normally do and ended up messing up the co-ordinates several times because of it. Probably at least a solid 30 minutes of extra debugging because of it.

Miķelis Vindavs07:12:37

Missed my alarm clock and overlept for 90mins 😭 Today’s solution is the slowest one in terms of runtime for me, it takes 5 minutes to run. I wonder if I’m missing something real obvious about pruning the search space. @U0954HGDQ how fast does your solution run? it seems like you’re storing a collection of winds for each round, whereas I’m just storing the original position and checking whether a position is occupied by adding time modulo (lcm width, height) , but it’s a linear search over the winds. I wonder if your way could actually be faster

Miķelis Vindavs07:12:05

hmm i could memoize the occupied function

Miķelis Vindavs07:12:33

well that cut the runtime down to 2mins 😅


day24.main> (time (part2 full-input))
"Elapsed time: 6188.766655 msecs"

👍 1
Miķelis Vindavs08:12:58

nice! i think i don’t make enough assumptions about previously visited positions


The key point is we don’t care how we came in same position at a certain minute, so we can reduce the space by applying set.

Miķelis Vindavs09:12:24

but we do care, because the winds might be different?

Miķelis Vindavs09:12:03

they do repeat every lcm(width,height) steps, but besides that

Miķelis Vindavs09:12:06

i fixed my occupied function, now it all runs in 2s 😄

Miķelis Vindavs09:12:58

i was caching whether a position is occupied it at a particular time. instead it makes a lot more sense to cache the position of all blizzards at a particular time, because it can be reused for all positions at that time


For a certain minute wind is always the same, so if we came at position [2 2] by 10 ways, we can go with only one [2 2].

Miķelis Vindavs09:12:21

yep, but the cache key has to be [(mod time cycle-length) position] not just position

Miķelis Vindavs09:12:50

of course in norman’s solution all times are considered in the same iteration, so I think we’re actually talking about the same thing


Yeah, I’m polishing my solution, but basically it’s similar to @U0954HGDQ ’s

Miķelis Vindavs09:12:23

and actually a priority queue isn’t need either, so switching to a regular queue made it even faster 🎉


Exactly, first I thought I need something like astar

Miķelis Vindavs10:12:39

mod1 seems like a useful function


more memoization gives "Elapsed time: 2843.663069 msecs" since wind-map loops every 600 steps


My answer for part 3 is 4666929 minutes. It’s just 77782 hours, or approximately 8 years of dodging blizzards. Without sleep of course.


Slowly wrapping up AoC before vacation is over. I didn’t remap all the blizzards each time step. Instead I used modulo arithmetic to check if any blizzards would be at a certain spot at a certain time.