Grove Positioning System

Advent of Code 2022 Day 20

Part 1

1. Never been so happy to go in circles
2. The hard part: tracking original location
3. Step by step: working with the example input
4. Back to the hard part

Never been so happy to go in circles

After 2D grids with areas in the trillions, search & graph algorithms, and a tetromino simulator...

...I'm happy to have this seemingly simpler task of moving items in an array!

The hard part: tracking original location

The examples are deceptive:

• The numbers are all different

My puzzle input is not so nice:

• Many numbers repeat two or more times

That means I can't use a method of tracking that utilizes a queue of the numbers in their original order and the indexOf() array method:

• A number that was later may have moved earlier, causing indexOf() to flag the wrong instance of the number

Hmm. How am I going to account for this?

Step by step: working with the example input

I know I'll need a strategy for tracking multiple instances of the same number.

But first, I'd like to ensure I can build an algorithm that works on a list of all different numbers, like in the example input list.

That list again is:

1
2
-3
3
-2
0
4

splice()ing and shift()ing

The numbers in original order are:

let order = [1, 2, -3, 3, -2, 0, 4]

I need to move the first item.

The indexOf() the first number, 1, is 0:

numbers.indexOf(order.shift()) // 0

I need to move it 1 forward.

let amount = order.shift()
let start = numbers.indexOf(amount)
numbers.splice(start, 1)
numbers.splice((start + amount) % numbers.length, 0, amount)

That worked for the first step!

Will it work for each subsequent step?

Enter: for loop

I think I can perform the four lines above on each number in the input:

for (let i = 0; i < numbers.length; i++) {
  let amount = order.shift()
  let start = numbers.indexOf(amount)
  numbers.splice(start, 1)
  numbers.splice((start + amount) % numbers.length, 0, amount)
}

Different order than shown, or it it?

The example shows the list like this after moving the -2:

-2 moves between 4 and 1:
1, 2, -3, 0, 3, 4, -2

My list has the -2 at the head instead of the tail.

At first I was concerned.

Then I remembered this is a circle.

As long as the -2 is between the 4 and 1, I'm good!

The last part is checking the numbers several thousand indices from that of 0.

My algorithm in JavaScript

let numbers = input.split('\n').map(Number)
let order = numbers.slice()
for (let i = 0; i < numbers.length; i++) {
  let amount = order.shift()
  let start = numbers.indexOf(amount)
  numbers.splice(start, 1)
  numbers.splice((start + amount) % numbers.length, 0, amount)
}
return numbers[(numbers.indexOf(0) + 1000) % numbers.length] +
  numbers[(numbers.indexOf(0) + 2000) % numbers.length] +
  numbers[(numbers.indexOf(0) + 3000) % numbers.length]

This generated the correct answer for the example input!

I'd love to swap puzzle inputs and run it, but I know it would be the wrong answer since my input has repeated numbers.

So, now it's back to devising a strategy for handling that.

Back to the hard part

To recap:

• My puzzle input has 5000 numbers, but many of them appear more than once
• Thus, I can't rely on indexOf() to find the correct instance of every number that is next in order
• So, what can I rely on instead?

Well, instead of storing just the number in order, I could store the number and it's current index:

let order = [1, 2, -3, 3, -2, 0, 4].map((n, i) => [n, i])

But now what?

• Each step, I'll need to update each number's index between the origin and destination index of the number that moved
• In my puzzle input, most numbers will move close to 10k indices
• That adds up to a ton of array access and updating
• Plus, I'll have to account for the direction of movement, and update indices by either +1 or -1
• Oh, and I'll have to account for an item moving from head to tail in my array, which isn't inherently circular

I might think to leverage a circular linked list, but with all the look-ups and edits I have to make, it doesn't seem very performant either.

Yet again, I'm stumped.

Another zero-star day

What a bummer!

I felt confident after reading this puzzle's description that I'd be able to crack it.

Sadly, the actual puzzle input threw a wrench in my plans with duplicate numbers.

Add this to the list of puzzles I'd love to try again some day.