## Advent of Code 2022 Day 20

## Part 1

- Never been so happy to go in circles
- The hard part: tracking original location
- Step by step: working with the example input
- 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.

## Top comments (0)