AoC 2017 Day 17: Spinlock

2017-12-17

Source: Spinlock1

Part 1: Start with a circular buffer containing [0] and current_position = 0. For n from 1 up to 2017:

  1. Step forward steps (puzzle input)
  2. Input the next value for n, set current_position to n, increment n
  3. 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 year2, 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.

via GIPHY

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 them3. 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.

  1. Don’t really have a better name than they do for once. ↩︎

  2. Or a few days ago. But who’s counting? ↩︎

  3. Imagine O(n)… ↩︎