Grove Positioning System
Tags: adventofcode, algorithms, javascript, programming
Published: 2022-12-24 20:08:41

## [Advent of Code 2022 Day 20](https://adventofcode.com/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:
```js
let order = [1, 2, -3, 3, -2, 0, 4]
```

I need to move the first item.

The `indexOf()` the first number, `1`, is `0`:
```js
numbers.indexOf(order.shift()) // 0
```

I need to move it `1` forward.

```js
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:

```js
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
```js
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:
```js
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.