Robert Mion

Posted on

# Spinlock

## Part 1

1. This seems familiar...
2. This seems fairly simple...

### This seems familiar...

Where have I seen circular insertion puzzles before?

• 2017 Day 25 featured an infinitely long horizontal list
• 2018 Day 9 featured a similar puzzle
• 2018 Day 14 also featured a similar puzzle

That confirms my gut feeling that I recall seeing more of this puzzle type recently.

### This seems fairly simple...

``````Start with an array containing the value 0
For i from 1 to 2018 and current starting at 0
Without deleting anything...
...insert i at the location in the array...
...equivalent to:
- the remainder after dividing the sum of
- current and the puzzle input integer
- by the length of the array
- then adding 1
Then, update current to the location in the array of i

Return the integer at the location one greater than the location of the integer 2017
``````

That algorithm generates the correct answer for both the example input of `3` and my puzzle input!

However, I experienced a few bugs and seemingly lucky coincidences on my way to writing it:

• I originally used a loop to update `current`
• Not only that, but I was incorrectly incrementing `current` by `i` in each iteration of that loop
• Surprisingly, I was generating the correct answer using the example input of `3`!
• Which led me to question why the number I was generating with my puzzle input was `too high`

Thankfully, I resolved those issues.

And, I simplified, reduced, and condensed my algorithm to just over 5 lines of code!

Here's the JavaScript I wrote to solve Part 1:

``````const part1 = () => {
let input = 3, RA = [0]
for (let i = 1, curr = 0; i < 2018; i++) {
RA.splice((curr + 376) % i + 1, 0, i)
curr = RA.indexOf(i)
}
return RA[RA.indexOf(2017) + 1]
}
``````

## Part 2

1. Oh yeah, saw that coming
2. Update after publishing

### Oh yeah, saw that coming

• 50 million times, eh?
• Once again, I'm blocked from solving because I'm not familiar enough with linked lists...which are a far better performing data structure for this problem than an array

Hopefully I'll learn to use linked lists soon.

Then, I'll return to a few of the puzzles mentioned above and attempt to solve any Part 2s that required them.

### Update after publishing

#### Using a linked list

Here's my linked list main loop:

``````for (let i = 1, curr = 0; i < 2018; i++) {
let index = (curr + input) % i + 1
if (index > i - 1) {
list.insert(i)
curr = i - 1
} else {
list.insertAt(index, i)
curr = index
}
}
``````
• I then swapped 2018 for 50M and 2017 for 0, and ran it again
• It, too, seemed to go on forever

Bummer.

#### Hunting for a pattern

Maybe there's a pattern to the integer immediately to the right of 0 that I can extrapolate out to 50M?

• I added code that tracked any time the integer to the right of 0 changed
• I logged the new number: no apparent pattern
• I logged the difference between the new number and the previous number: no apparent pattern

Bummer.

## I did it!

• I solved Part 1!
• I consolidated my code to nearly 5 lines!
• I gained yet another reason to learn and practice using Linked Lists!
• Update: I used my first linked list library to re-create Part 1's answer!