## DEV Community

Nicky Meuleman

Posted on • Originally published at nickymeuleman.netlify.app

# Advent of Code 2022 Day 20

## Day 20: Grove Positioning System

TL;DR: my solution in Rust

Remember we were going to a grove on day 1?

You decide to meet up with the elves there.
Your device has the grove's coordinates, but they are encrypted.

Your puzzle input countains the encryped coordinates.

It's a bunch of numbers in a circular list.

To decrypt it, mix it.

Mixing:
For each number in the list, move it back or forwards a number of positions equal to the value of that number.

• `5` moves forwards 5 positions
• `-10` moves backwards 10 positions

Remember, it's a circular list, so moving off one end means appearing at the other.

An example input looks like this (but each blueprint is on a single line in the real input):

``````1
2
-3
3
-2
0
4
``````

The moving operations happen in the order of the original list.

In this example:

• the original list:
`1, 2, -3, 3, -2, 0, 4`

• 1 moves 1 position to the right:
`2, 1, -3, 3, -2, 0, 4`

• 2 moves 2 positions to the right:
`1, -3, 2, 3, -2, 0, 4`

• -3 moves 3 positions to the left:
`1, 2, 3, -2, -3, 0, 4`

• ...

• 4 moves 4 positions to the right:
`1, 2, -3, 4, 0, 3, -2`

The sneaky thing here is that the real input has duplicate numbers.
We should treat every number like it's unique.

## Parsing

Probably doesn't need to be a seperate function, but I've been applying this pattern for a couple of days now.
It works, I'm sticking with it.

Parse the input into a list of numbers.

``````fn parse() -> Vec<i64> {
input.lines().map(|line| line.parse().unwrap()).collect()
}
``````

## Part 1

The grove coordinates can be found by looking at the 1000th, 2000th, and 3000th numbers after the value 0, wrapping around the list as necessary.

The question asks what the sum of the 3 grove coordinates is.

So after the *mixing process, we get a sick beat the position of the 0 in the mixed list of numbers.

Keep the original list of numbers seperately.

Create a `mixed` list of indexes to the corresponding number in the original list.
This is the key to treating every number in the list as a unique number even if there are repeats.

This is the list that will be operated on during the mixing process.

We loop over every index/number combo in the original list, and apply the mixing step for each one.

We first find the index in mixed where the current number's index into `nums` is.

Yes, lots of "index" today. It's a bit mindbendy.

• `nums` holds the original numbers
• `mixed` holds indexes to a number in the `nums` list

• Remove the item at the found index in the `mixed` list

• Add the current `num` to that index

• Insert the item back into `mixed` at that new index, wrapping around the list if necessary.

This is a good place to repeat that MODULUS IS NOT REMAINDER!
The `%` operator behaves differently depending on the programming language you use.

You want the non-negative remainder, also called Euclidian remainder.

I talk more about how modulo works in a post about the affine-cipher

After that loop is done and the mixing is over, find the index of the 0 in the original list.
The item in `mixed` with that index represents the 0.

Then, apply the 1000, 2000, and 3000 offset to that number in the mixed list.
Remember, `mixed` holds indexes into `nums`. So the number we actually want is in `nums`,
indexed by whatever we just found by applying the offset to a number in `mixed`.

Finish by summing those numbers.

### Final code

``````pub fn part_1() -> i64 {
let nums = parse();
// indexes into nums
let mut mixed: Vec<_> = (0..nums.len()).collect();
for (idx, &num) in nums.iter().enumerate() {
// find mixed that corresponds to the number in nums
let mixed_idx = mixed.iter().position(|&mix_num| mix_num == idx).unwrap();
// remove that index from mixed
mixed.remove(mixed_idx);
let new_mixed_idx = (mixed_idx as i64 + num).rem_euclid(mixed.len() as i64) as usize;
mixed.insert(new_mixed_idx, idx);
}

let zero_idx = nums.iter().position(|&num| num == 0).unwrap();
let zero_mixed_idx = mixed
.iter()
.position(|&mix_num| mix_num == zero_idx)
.unwrap();

[1000, 2000, 3000]
.iter()
.map(|offset| {
let mixed_idx = (zero_mixed_idx + offset) % mixed.len();
let nums_idx = mixed[mixed_idx];
nums[nums_idx]
})
.sum()
}
``````

## Part 2

First, every number in the input has to be multiplied by an encryption key, `811589153`.

`let encryption_key = 811_589_153;`

Only then can the mixing begin.
And that mixing process has to do 10 full loops on those encrypted numbers.

The question asks what the sum of the 3 grove coordinates is again.

As a reminder, the grove coordinates can be found by looking at the 1000th, 2000th, and 3000th numbers after the value 0 in the mixed list.

It's a day where making the naive changes is enough, no exploding complexity today.

### Final code

``````pub fn part_2() -> i64 {
let decryption_key = 811_589_153;
let nums: Vec<_> = parse().iter().map(|num| num * decryption_key).collect();
// indexes into nums
let mut mixed: Vec<_> = (0..nums.len()).collect();
for _ in 0..10 {
for (idx, &num) in nums.iter().enumerate() {
// find mixed that corresponds to the number in nums
let mixed_idx = mixed.iter().position(|&mix_num| mix_num == idx).unwrap();
// remove that index from mixed
mixed.remove(mixed_idx);
let new_mixed_idx = (mixed_idx as i64 + num).rem_euclid(mixed.len() as i64) as usize;
mixed.insert(new_mixed_idx, idx);
}
}

let zero_idx = nums.iter().position(|&num| num == 0).unwrap();
let zero_mixed_idx = mixed
.iter()
.position(|&mix_num| mix_num == zero_idx)
.unwrap();

[1000, 2000, 3000]
.iter()
.map(|offset| {
let mixed_idx = (zero_mixed_idx + offset) % mixed.len();
let nums_idx = mixed[mixed_idx];
nums[nums_idx]
})
.sum()
}
``````

## Final code

``````fn parse() -> Vec<i64> {
input.lines().map(|line| line.parse().unwrap()).collect()
}

pub fn part_1() -> i64 {
let nums = parse();
// indexes into nums
let mut mixed: Vec<_> = (0..nums.len()).collect();
for (idx, &num) in nums.iter().enumerate() {
// find mixed that corresponds to the number in nums
let mixed_idx = mixed.iter().position(|&mix_num| mix_num == idx).unwrap();
// remove that index from mixed
mixed.remove(mixed_idx);
let new_mixed_idx = (mixed_idx as i64 + num).rem_euclid(mixed.len() as i64) as usize;
mixed.insert(new_mixed_idx, idx);
}

let zero_idx = nums.iter().position(|&num| num == 0).unwrap();
let zero_mixed_idx = mixed
.iter()
.position(|&mix_num| mix_num == zero_idx)
.unwrap();

[1000, 2000, 3000]
.iter()
.map(|offset| {
let mixed_idx = (zero_mixed_idx + offset) % mixed.len();
let nums_idx = mixed[mixed_idx];
nums[nums_idx]
})
.sum()
}

pub fn part_2() -> i64 {
let decryption_key = 811_589_153;
let nums: Vec<_> = parse().iter().map(|num| num * decryption_key).collect();
// indexes into nums
let mut mixed: Vec<_> = (0..nums.len()).collect();
for _ in 0..10 {
for (idx, &num) in nums.iter().enumerate() {
// find mixed that corresponds to the number in nums
let mixed_idx = mixed.iter().position(|&mix_num| mix_num == idx).unwrap();
// remove that index from mixed
mixed.remove(mixed_idx);
let new_mixed_idx = (mixed_idx as i64 + num).rem_euclid(mixed.len() as i64) as usize;
mixed.insert(new_mixed_idx, idx);
}
}

let zero_idx = nums.iter().position(|&num| num == 0).unwrap();
let zero_mixed_idx = mixed
.iter()
.position(|&mix_num| mix_num == zero_idx)
.unwrap();

[1000, 2000, 3000]
.iter()
.map(|offset| {
let mixed_idx = (zero_mixed_idx + offset) % mixed.len();
let nums_idx = mixed[mixed_idx];
nums[nums_idx]
})
.sum()
}
``````