Re:Adventures in Advent of Code
by sokoloff on Saturday December 03, 2022 @05:27PM
(#33848114)
Hat tip if you did 2021:14:2 under this constraint. I didn’t find the trick to allow that type of performance.
[ Parent
| on HN ]
Re:Adventures in Advent of Code
by mtlmtlmtlmtl on Saturday December 03, 2022 @06:10PM
(#33848466)
I don't think I did the 2021 one, but I did do 2020.
Re:Adventures in Advent of Code
by forrestthewoods on Saturday December 03, 2022 @06:19PM
(#33848536)
Is that the right day? My code for 2021:14 runs in 440 microseconds for both parts. 2021:23:2 is the only day I couldn't get under 1 second.
https://github.com/forrestthewoods/aoc2021/blob/master/rust/...
I struggled with that one; thanks for linking your code; I’ll have a look and see the trick I missed.
The key is you didn’t need to keep track of the strings, just the counts.
I have a writeup of my 2021 solutions at https://programsareproofs.com/articles/aoc_2021.html. I got day 23 down to 31ms using Rust.
My 2021 day 23 runs in 5 milliseconds for both parts using A* with a custom heuristic: https://github.com/orlp/aoc2021/blob/master/src/bin/day23.rs
Day 22 (https://adventofcode.com/2021/day/22) is the one that nearly killed me in 2021. I did get it using a technique of breaking any overlaps into smaller and smaller rectangles, but it took like 30s to run. I looked on the AoC reddit, and honestly I still don't understand what I needed to do to make it better, but visualizing 3d spaces has always been a weakness for me.
Re:Adventures in Advent of Code
by tialaramex on Saturday December 03, 2022 @08:13PM
(#33849456)
My target is usually 1 second each, because that feels about right for my patience, rather than 1 second overall target.
My 2021 (Rust) solutions all meet that, but some only do so when optimized, and day 22 was one of those where without the optimizer I'm waiting 2-3 seconds for an answer.
IIRC the trick was to compact the indices, so e.g instead of thinking about X values of 120203 494302 and 109383 you call those 1, 2, 0. Do all the working out of which cells within the resulting tiny structure are on or off, and then expand the 1x1 cells you're talking about to their true size based on the real values instead of indices.
My day 22 solution runs in <10ms: https://github.com/orlp/aoc2021/blob/master/src/bin/day22.rs
The trick I used was to represent signed volumes, compute the intersection and then store the 'negative cube' instead of splitting up cubes.
Yeah same! It really was a tricky one for me: https://github.com/sordina/advent2021/blob/solutions/src/Adv...