DEV Community

Cover image for Spinlock
Robert Mion
Robert Mion

Posted on

Spinlock

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
Enter fullscreen mode Exit fullscreen mode

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]
}
Enter fullscreen mode Exit fullscreen mode

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
  }
}
Enter fullscreen mode Exit fullscreen mode
  • 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)