It's not my proudest work, but it gets the answer in 15 seconds or less on my machine which, while far slower than pretty much any other day, is a huge improvement over my initial attempts that took 30+ minutes. There is a lot of low-hanging fruit that could be used to improve this runtime, mostly around filtering possible moves and the Amphipod hashing function for memoization, but I am spending that time prepping for day 24 (and eventually finishing day 21 part 2...).
My "coordinate" system is hideous and I feel bad about it, as is my handling of part 2 vs part 1 w.r.t. adding two new rows. But I didn't want to manufacture some kind of 2d grid that had a bunch of closed-off spaces, so I just made this awful thing work instead. I have an easier time thinking in discrete "1d" chunks than I do thinking in 2d graphs anyway. I would also love to add a stack to be able to replay the moves that got us to a solution, but again, I'm trying to move on! :)
I would have had this done last night, but... _unintelligible muttering about key[0] being '#' in the real input and '.' in the sample...
Day 19 is...still vexing me. Maybe I'll get back to it later.
I have a very strong feeling that I massively over-complicated this, but it works. I spent a ton of time making sure each component of the problem was implemented correctly so I could quickly identify where things went wrong, and that setup was convenient enough that I just formalized it and left it in. Maybe it'll be useful for another day...
Honestly I think I have an error somewhere in the part 2 logic because my final output characters weren't exactly correct, but they were close enough that my first guess for each letter was right. So I may revisit this to find and fix the logic bug, but apparently it's Close Enough™ to be done for the night.
This was my initial solution I used to submit the puzzle answer. Runtime for part 2 on my input set was around a second, so now I'm going to find optimization targets. I'm sure there's a lot I could be doing much better.
Pretty happy with this one overall. I tripped myself up on part 2 and caused a huge headache by not realizing that I was passing the already-modified array from part 1 into part 2. I left some code to copy the 2d array because that was my original solution (and it's not straightforward to copy jagged arrays), but then realized that the synchronized flash doesn't happen until after step 100 (at least for my input and the demo input) so we can just account for that in part 2 and pick up where part 1 left off.
As always, plenty of room for improvement, but I'm reasonably satisfied with the core implementation. I'm honestly not sure why the Distinct is needed in the GetBasinSize() result as it's supposed to not even add the point if the point is already in there, but it's late so I'll check that out later.
I hate almost everything about this solution. It's all awful and a product of constantly adjusting how I was solving the problem to try and get the correct answer, so there are vestigial pieces of each road I headed down. Then I ended up using some combination of all of those pieces to get the actual answer, and...well it just needs to be overhauled dramatically. But it works, so I guess mission accomplished.
I'm reasonably happy with this one. I'm sure there's an easier way to determine the smallest distance, at least for part 1, but this works fast enough for me.
There is a lot to be disliked here, starting with the Line Length calculation, which I'm sure I'm just totally overthinking or otherwise being dumb about, to the way I'm picking the next point while moving along the line.
Also, TIL how much of a difference a good GetHashCode() override can make when comparing/equating custom struct instances. Not implementing GetHashCode() on this solution resulted in ~250ms runtime on my PC. Implementing a "bad" GetHashCode() (which was `return x.GetHashCode() | y.GetHashCode();` which seemed fine to me ¯\_(ツ)_/¯) resulted in >1s runtime on my PC. Using this implementation (HashCode.Combine()) results in ~25ms runtime on my PC. Those numbers are with nothing changing other than the implementation of GetHashCode() on struct Point.
I also disabled nullability in my quest to improve performance here. The compiler was complaining that my Equals() override wasn't equivalent because of nullability, so it had to be `object? obj` which I didn't care for since this was a value type and not a reference type.
I have no idea what I'm doing in Rust, and I definitely don't understand
borrowing yet, so this is a hideous solution on multiple fronts. I'm not
sure that I'll be sticking with Rust as AoC doesn't feel like a
conducive environment to learn it in.
