The problem for Advent of Code Day 19 is specified as follows:
Elves numbered 1 to N sit in a circle. Each Elf brings a present. Then, starting with the first Elf, they take turns stealing all the presents from the Elf to their left. An Elf with no presents is removed from the circle and does not take turns. So, if N = 5, then:
- Elf 1 takes Elf 2's present.
- Elf 2 has no presents and is skipped
- Elf 3 takes Elf 4's present.
- Elf 4 has no presents and is also skipped.
- Elf 5 takes Elf 1's two presents.
- Neither Elf 1 nor Elf 2 have any presents, so both are skipped.
- Elf 3 takes Elf 5's three presents, ending the game.
Who ends up with all the presents for general case of N?
After solving these problems, I always like to look at other's solutions to learn some new tricks. One of those solutions I read through was Peter Norvig's solution here, and I noticed he mentions deleting from the list for each elf whose presents are taken is O(N^2).
Empirically this makes sense because that's basically what I did and my solution was painfully slow, but I thought that deleting from a list, assuming linked list, was O(N) (or specifically O(N) to iterate to the point of deletion, and O(1) for the actual deletion).
My knowledge here is obviously lacking and I would greatly appreciate if anybody could help me understand a bit better how this is O(N^2). I can kind of see how it would be the case if you are deleting, and then after each deletion, trying to search from the beginning of the list again for the next elf, because in that case you have a cost of N for each deletion and N again to search for the next elf so N^2 total. What I was doing though was keeping a counter of where I was in the list, deleting an elf, and then iterating the counter to the next position. In that case I would expect to incur N cost for deletion, but not for indexing (maybe this is where I'm wrong, the indexing cost).