This was an amazing problem. A naive approach gives absolutely terrible performance and memory characteristics in any language, and the best approach is amazingly fast. I landed somewhere in the middle.
I started in Rust of course, with a naive approach of building new vectors for each move:
My estimate is this was going to take 20-24h to run part 2 however. So I switched to linked lists. In Rust's strict ownership model this is pretty tricky and an exercise for another day so I switched to C:
There is an even simpler approach however which I didn't realise until later. Each cup can be modelled by simply the index to the next cup. So you just need one huge vector of indices - each cup can be found by id by looking up a position in the vector, and the ordering can be adjusted by reassigning next indices just like how the linked list works. I'll aim to do that in Rust.
This was an amazing problem. A naive approach gives absolutely terrible performance and memory characteristics in any language, and the best approach is amazingly fast. I landed somewhere in the middle.
I started in Rust of course, with a naive approach of building new vectors for each move:
My estimate is this was going to take 20-24h to run part 2 however. So I switched to linked lists. In Rust's strict ownership model this is pretty tricky and an exercise for another day so I switched to C:
There is an even simpler approach however which I didn't realise until later. Each cup can be modelled by simply the index to the next cup. So you just need one huge vector of indices - each cup can be found by id by looking up a position in the vector, and the ordering can be adjusted by reassigning next indices just like how the linked list works. I'll aim to do that in Rust.
And here we are. Setting up the initial array was the hardest bit. And it's faster than the C pointer version.