## Advent of Code 2017 Day 17

## Part 1

- This seems familiar...
- 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

- Oh yeah, saw that coming
- 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 - 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:

```
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!

## Top comments (0)