Robert Mion

Posted on

Grove Positioning System

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.