Spinlock
Tags: adventofcode, algorithms, computerscience, programming
Published: 2022-07-26 00:52:00

## [Advent of Code 2017 Day 17](https://adventofcode.com/2017/day/17)

## 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:
```js
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
- I found an [`npm` library that provides a doubly linked list data structure](https://openbase.com/js/dbly-linked-list)
- I read the documentation and worked my way toward re-creating my solution for Part 1 using a linked list

Here's my linked list main loop:
```js
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](https://openbase.com/js/dbly-linked-list) to re-create Part 1's answer!