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
byi
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)