DEV Community

Robert Mion
Robert Mion

Posted on

2

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
Enter fullscreen mode Exit fullscreen mode

splice()ing and shift()ing

The numbers in original order are:

let order = [1, 2, -3, 3, -2, 0, 4]
Enter fullscreen mode Exit fullscreen mode

I need to move the first item.

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

numbers.indexOf(order.shift()) // 0
Enter fullscreen mode Exit fullscreen mode

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)
Enter fullscreen mode Exit fullscreen mode

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)
}
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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]
Enter fullscreen mode Exit fullscreen mode

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])
Enter fullscreen mode Exit fullscreen mode

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.

AWS Security LIVE!

Join us for AWS Security LIVE!

Discover the future of cloud security. Tune in live for trends, tips, and solutions from AWS and AWS Partners.

Learn More

Top comments (0)

👋 Kindness is contagious

Please leave a ❤️ or a friendly comment on this post if you found it helpful!

Okay