(edited after remembering another bad idea, whoops)
I had one very good idea, one good idea, and quite a few bad ideas, including one very bad idea that held me up a long time.
The very good idea was to use modular arithmetic, so as to minimize the motion: no point in shifting a number around the list however many times. As a result, the solution to both parts takes only less than two seconds (using full optimization and inlining).
The good idea I don’t quite remember, sorry, but I had it in mind at one point.
One bad idea was to swap the value with the value at its final position, which completely forgets the shift. Fortunately, I caught that one quickly.
Another bad idea was to compute the net motion as the remainder of dividing by the list’s length. When an entry moves around the list, it moves around one fewer than the list’s length. Rather naughty of the example not to have a value that would illustrate that.
The very bad idea came while testing my code on the example. I forgot that the list is circular, and began tinkering with it so that each shift would end with the same starting value as what the website shows (which is almost always 1). Doing that complicates things, but if it’s a circular list, all that matters is that the values are in the correct order. The score depends on counting from 0’s position, and 0 is unique in the list, so it doesn’t really matter which element is first. I wasted over an hour on that stupid mistake…
At first, I tried using regular arrays and use slicing to move the elements around. Somehow my solution was wrong - even though I’m not sure what I messed up. The test data worked fine.
Next, I tried using Vectors and delete the element from old position and insert before the new. This again produced the exact same wrong solution. The test data worked fine, again.
After a while, I gave up on linear storage, and implemented my own ring buffer using access types and simply removing the current element, moving the current position by the modulo amount, and inserting it again. Since the length of the buffer was 1 shorter after removing, the modulo worked perfectly. This produced a correct solution.
Solving part 2 was simply changing the value type to Long_Long_Integer and multiplying the list by the decryption key.
I didn’t care about cleaning up the memory consumed by creating the buffer from part 1, but it’s only 5000 elements anyways.
Timing is about 0.08s for part 1, and 1.25s for part 1 + 2.
This sounds a little similar to my journey, but with a different ending. I went with vectors rather than arrays, then switched to the library’s doubly linked lists, which should have done the job, but didn’t for some reason. That might have been back before I realized the input data has non-unique entries, so an implementation that works on the example can still fail on the input. Yet another way the example was naughty… So maybe that was your issue, too.
When I discovered that, I switched to using two vectors: one that held the values, and the other which held the positions they’ve moved to. After getting past my worst bad idea above, things worked out.
I don’t think it was because of non-unique entries. I checked for duplicates in the data before starting to code. My element types have been records with values and a Boolean flag for my first tries. Later I replaced it with value plus input order, which was necessary for part 2, too.
The problem is reminiscent of the Crabs Cup puzzle (Day 23 in 2020).
I have used a doubly-linked list.
Banana skin: when the element to be moved is temporarily removed, the list has one element less (of course). But it means you skip complete cycles by doing mod (n-1), not mod n (where n is the data length).
Yuck, this one was a slog. I did end up just using an array and doing things less efficiently than it could have been, just to make it easier for me to reason about (removing the moved thing from the list first, then reinserting, shifting with array copying both times. Even with the really inefficient implementation, though, it still runs in less than half a second.
He does tend to reuse the basic ideas in a lot of problems, but I thought this one seemed especially familiar somehow, and maybe that’s it. At some point I also went through the 2019 puzzles, and I feel as if there was one from those that’s similar to this, too, but what I recall most distinctly was how that was the year of IntCode. As the calendar progressed, on every other day you added more features to a virtual machine that ran an “Intcode” instruction set. The coup de grace was that the Christmas puzzle required you to solve a text-based adventure game that ran on your Intcode computer. It was wonderful.
I was too busy / worn out last year to do the 2021 puzzle, but I do think of going back and doing some of the years I’ve missed. It’s just that they’re still pretty exhausting after the fact, too…
I will have to go back and see if I can re-implement my method as a doubly-linked list, because copying values is doutbless inefficient.
