Day 21 spoilers
https://github.com/massung/advent2021/blob/main/day21/day21.lisp
I enjoyed this one considerably more than the past few days. I had the solution pretty quick, but coding it up properly took longer than I’d thought it would.
For anyone looking for actual spoilers or who may have done part 2 differently than I did, mine runs in 3s and I put a fairly detailed comment above the primary function that solves it and how I reduced the scope.
If anyone has any additional tricks, I’d love to hear about them!
I’m sad. I ported @massung’s solution to Racket and threw in all the unsafe operations I could think of, and it still takes 2.5–3min (not 3s, though that could be hardware difference). Surely Racket can compete with CL here? If any racketeer can spot more optimization here, I’d be grateful :slightly_smiling_face: I normally stick to clear functional solutions in spite of occasional performance problems, but since I’m using mutable vectors here I figured I might as well go all in.
I’m running on an M1 MBP for a HW comparison
2015 MBP (so 2.5GHz i7).
My opinion on FP vs. mutation: within a function you can be as mutable as you want with the internal state of the function. Who cares? the function itself is still “pure”.
After all, that’s what actually happens anyway. The computer doesn’t magically create new registers during execution. :wink:
Agreed! The code is just super messy with all the unsafe- nonsense :slightly_smiling_face: I actually used a mutable queue to implement one of the previous days internally; I have no trouble with that when it’s the right option. I really only used the mutable queue because there wasn’t an immutable one in the stdlib, though; mutation isn’t necessary in that case.
My Intcode simulator from a few years back was entirely immutable, though. I never finished that year, but there was a problem or two where I was looking forward to being able to try different inputs from a given state, since each time you give it input you get a brand new universe back, and you can hang on to the original to keep feeding it different inputs.
Hmm.. looking at my code, something that might be a small time savings:
Instead of (dotimes (i 7) ... and looking up the *die-combs* array, instead just iterate over *die-combs*? I don’t know how fast/slow array lookup is in Racket:
(for ([die *die-combs*] #:when (> die 0)) ...)
I’m just thinking that the internals of Racket’s for might be more optimized.
Oh, good point. I can use in-vector there to get a boost.
vectors should be constant-time access though
sure, but between bounds checking, error handling, etc. All that extra stuff won’t be in the internals of for loops, which will just be down in C code
unsafe or not, there’s still checks being done
I’m pretty sure all the unsafe stuff disables the bounds checking, but we’ll try it. I’m going to have to get the logic right for the indexes, now, though :slightly_smiling_face:
Very unscientifically, that appears to have shaved 10s off 150. I have a feeling there’s something bigger I’m missing, but I can’t see it
I didn’t feel like unifying the parts today: <https://github.com/lojic/LearningRacket/blob/master/advent-of-code–2021/solutions/day21/day21-part1.rkt|Part 1> <https://github.com/lojic/LearningRacket/blob/master/advent-of-code–2021/solutions/day21/day21-part2.rkt|Original Part 2> - that happened to work the first time, as soon as I finished coding! <https://github.com/lojic/LearningRacket/blob/master/advent-of-code–2021/solutions/day21/day21-part2-performance.rkt|Fast Part 2> - that’s 180x faster than the original :) A guy in our local slack mentioned caching, and that led me down the right path to get it fast. Finishes part 2 in 65 ms.
Hmm… I used unsafe stuff, but that only dropped it from 68ms to 65ms (at best), so I’m going to take it out to clean up…
…done. I just left in the define-inline for the turn function.
Here’s <https://github.com/lojic/LearningRacket/blob/master/advent-of-code–2021/solutions/day21/day21-hyper-neutrino.rkt|a port of a Python version> that is super simple, and runs in 50ms