Advent of Code 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:

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