The first hint that I find is to use an array where the value at a given index is the next cup after the cup labelled with that index. This is actually so helpful that in the end I think I may have spoiled myself more than I wanted to.
- This is actually a sort of linked list in disguise, so actually my idea earlier was on the right track.
- By storing the linked list elements contiguously in an array, you can eliminate the search for the destination cup altogether.
Since with this scheme, we do need to store the current cup as part of the state, I decide to make a struct. I also change the data type of the cups once more, to usize , since the cup numbers are going to be used as array indices.
I run the program and this time the progress bar suggests it will be done in 21 minutes. That’s still a long time, but I decide I will just wait. If I get the wrong answer at the end, then I’ll spend time to profile it and make it faster. But when it finishes, the website tells me the answer is correct, so I move on.
Day 20, Part 2 (Again)
Back to the difficult puzzle from Day 20! In the meantime, a plan is forming; the plan seems clunky enough that it makes me think I am probably missing a more elegant solution, but I have gotten tired of this puzzle by now and I want to be done with it! What I will try to do, is to separate the tiles into a group of four corner tiles with two connections each, a group of edge tiles with three connections each, and a group of center tiles with four connections each. By the number of tiles in each group I should be able to figure out how big the total picture is.
I can then pick one of the corner tiles, determine which two sides don’t connect to any other tiles, place it in the correct orientation in the top left corner, and then start connecting edge tiles to it. Once I have the edge all connected, then I should be able to place all the center tiles correctly.
Here’s what I have written at this point, which I think is overly long and clunky and could use some refactoring:
This isn’t done yet , I haven’t gotten to the point of scanning for sea monsters either, so I’ll have to tack that on to one of the final posts. It took me quite a long time to get this far, because of two bugs that I got stuck on:
- When deciding which borders connect to each other, the border on one tile actually has to equal the bit-reversed border on the other tile. I didn’t notice this in Part 1, but it didn’t affect the answer, so it was in sort of a blind spot.
- I was looking at ndarray::stack() in an old version of the ndarray docs on without realizing it. In more recent versions, the stack() function was renamed to concatenate() , and stack() now does something else, and I couldn’t figure out why my result was wrong until I saw the tiny “? Go to latest version” label in the corner. It would be nice if would redirect you to the latest version when coming from search engines!
Three of the four puzzles in this post went very smoothly. The final one got me to the point where I had to look for a hint, and I think this is another of those places where better knowledge of computer science fundamentals such as algorithms and data structures would have helped me; but on the other hand maybe not, since it is a puzzle after all, not a textbook problem. At least, it is nice that I at least had an idea (linked list) that was in the right direction, I don’t think it would have been enough to get there without the hint of storing the elements contiguously. These puzzles are challenging, but I still have to say that I’ve rarely, possibly never, faced a situation in my professional career where I’ve been hampered by missing knowledge such as this!Posted by