### Source: Spinlock^{1}

Part 1:Start with a circular buffer containing`[0]`

and`current_position = 0`

. For`n`

from`1`

up to`2017`

:

- Step forward
`steps`

(puzzle input)- Input the next value for
`n`

, set`current_position`

to`n`

, increment`n`

- Repeat
What is the value after 2017?

It’s a bit weird to describe, but the given example helps (assume `steps = 3`

):

```
(0)
0 (1)
0 (2) 1
0 2 (3) 1
0 2 (4) 3 1
0 (5) 2 4 3 1
0 5 2 4 3 (6) 1
0 5 (7) 2 4 3 6 1
0 5 7 2 4 3 (8) 6 1
0 (9) 5 7 2 4 3 8 6 1
```

As we once did last year^{2}, a blist is going to be super handy here, since we’re constantly inserting into semi-arbitrary positions in the list.

```
lib.add_argument('--step', required = True, type = int, help = 'Number of steps')
lib.add_argument('--values', required = True, type = int, help = 'Number of values to insert')
lib.add_argument('--after', required = True, type = int, help = 'Print the value after this')
data = blist.blist([0])
step = lib.param('step')
current_position = 0
for i in range(1, 1 + lib.param('values')):
current_position = (current_position + step + 1) % len(data)
data.insert(current_position, i)
index_of_after = data.index(lib.param('after'))
print(data[(data.index(lib.param('after')) + 1) % len(data)])
```

At least it’s relatively short? That’s still an odd algorithm.

Part 2:Rather than identifying the value after 2017, find the value after`0`

… after 50 million iterations.

Again.

So, I doubt that keeping an array with 50 million elements in memory is going to go well. Even `O(log(n))`

inserts can take a while if you’re doing 50 million of them^{3}. But luckily, we can cheat. We know where the `0`

is. So all we actually have to keep track of is where the `0`

currently is (increment this when we insert an element before `0`

in the list) and what was the last character we inserted immediately after `0`

(this will only rarely change).

```
lib.add_argument('--step', required = True, type = int, help = 'Number of steps')
lib.add_argument('--values', required = True, type = int, help = 'Number of values to insert')
step = lib.param('step')
index_of_zero = 0
after_zero = None
current_position = 0
for i in range(1, 1 + lib.param('values')):
current_position = (current_position + step + 1) % i
lib.log(f'Inserting {i} at {current_position}')
if current_position < index_of_zero:
index_of_zero += 1
elif current_position == index_of_zero:
after_zero = i
print(after_zero)
```

It’s still not super fast, but it’s much faster than it would have been had we tried to use the original code for this:

```
$ python3 run-all.py day-17
day-17 python3 spinlock.py --values 2017 --step 329 --after 2017 0.4028189182281494 725
day-17 python3 spinlock-zero.py --values 50000000 --step 329 75.09986901283264 27361412
```

Technically, that’s outside of a minute, but I think I’m going to let it be for now. I’m not really sure how to optimize it much more at the moment.

- Don’t really have a better name than they do for once.
^{[return]} - Or a few days ago. But who’s counting?
^{[return]} - Imagine
`O(n)`

…^{[return]}