![](https://feddit.de/pictrs/image/650ccc9c-bb86-4a4b-bfec-b78144ef1d9a.png)
![](https://lemmy.ml/pictrs/image/q98XK4sKtw.png)
OpenSuse Slowroll does pretty much that, a slightly delayed rolling release.
OpenSuse Slowroll does pretty much that, a slightly delayed rolling release.
While reading the question I thought: “That’s not how Watts work”, but then this “answer” hit…
Why does it say “Texas” on it 6 times?
That’s GDPR coming through.
I really like kitty. It is fast and simple but gives me all the features I would want.
This is not cool of Twitter.
I simply check each starting position individually for Part 2, I don’t know if there are more clever solutions. Initially that approach ran in 180ms which is a lot more than any of the previous puzzles needed, so I tried if I could optimize it.
Initially I was using two hash sets, one for counting unique energized fields, and one for detecting cycles which also included the direction in the hash. Going from the default rust hasher to FxHash sped it up to 100ms. Seeing that, I thought that this point could be further improved upon, and ended up replacing both hash sets with boolean arrays, since their size is neatly bounded by the input field size. Now it runs in merely 30ms, meaning a 6x speedup just by getting rid of the hashing.
You can create an array filled with all the same values in Rust, but only if all values have the same memory representation because they will be copied. That just doesn’t work with Vec’s, because they must all have their own unique pointer. And to have uninitialized values at first (think NULL-pointers for every Vec) while creating each Vec, something like this is apparently needed.
The appropriate way would certainly have been to store the map as a Vec>
instead of an array, but I just wanted to see if could.
Part 1 was super simple with wrapping_add
and wrapping_mul
on a u8
. Building an actual hash map in Part 2 was nice.
The trick for part 2 is obviously to check when the pattern repeats itself and then jump ahead to 1000000000.
My code allocates an entire new grid for every tilt, some in-place procedure would probably be more efficient in terms of memory, but this seems good enough.
Part 2 turned out easier than I thought initially. My code assumes that there is only 1 mirror in each field which means I don’t have to remember where the smudge is, I just have to find a mirror line where the two halves differ at exactly one spot.
I don’t think there are many significant optimizations with regards to reducing the search tree. It took me long enough to get behind it, but the “solution” (not saying there aren’t other ways) to part 2 is to not calculate anything more than once. Instead put partial solutions in a dict indexed by the current state and use that cached value if you need it again.
It seems like you are actually constructing all rows with replaced ?
. This won’t be viable for part 2, your memory usage will explode. I have a recursive function that calls itself twice whenever a ?
is encountered, once assuming it’s a .
, and once a #
.
Took me way too long, but I’m happy with my solution now. I spent probably half an hour looking at my naive backtracking program churning away unsuccessfully before I thought of dynamic programming, meaning caching all intermediate results in a hashtable under their current state. The state is just the index into the spring array and the index into the range array, meaning there really can’t be too many different entries. Doing so worked very well, solving part 2 in 4ms.
Adding the caching required me to switch from a loop to a recursive function, which turned out way easier. Why did no one tell me to just go recursive from the start?
Yeah, not gonna do that.
I was unsure in Part 1 whether to actually expand the grid or just count the number of empty lanes in each ranges. I ended up doing the latter which was obviously the right choice for part 2, but I think it could have gone either way.
This one was tricky but interesting. In part 2 I basically did Breadth-First-Search starting at S
to find all spots within the ring. The trick for me was to move between fields, meaning each position is at the corner of four fields. I never cross the pipe ring, and if I hit the area bounds I know I started outside the ring not inside and start over at a different corner of S
.
Part 2 runs in 4ms.
Discrete derivatives!
I kind of agree, props for getting a general solution. I actually realized this issue only after I got both stars and didn’t feel like changing it again.
As others have shown, part 2 can be pretty simple if you allow one assumption: The distance from a start point to the nearest end point is always the same as cycling from that nearest end point back to itself. Under that assumption you can just take the lowest common multiple of these distances. And honestly, who can claim to understand ghost navigation and what you can and can’t assume? Empirical evidence suggests that this is how ghosts travel.
I knew that shell files, especially in build systems can get hard to read, but this was absolutely painful to look at from start to finish, even with the very helpful explanations in between. Of course the obfuscation is mostly done by design in this case.