Advent of Code 2022 Day 20

Day 20: Grove Positioning System

https://adventofcode.com/2022/day/20

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):

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> {
    let input = std::fs::read_to_string("src/day20.txt").unwrap();
    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);
        // add num offset to that number and add it back
        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);
            // add num offset to that number and add it back
            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> {
    let input = std::fs::read_to_string("src/day20.txt").unwrap();
    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);
        // add num offset to that number and add it back
        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);
            // add num offset to that number and add it back
            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()
}

Blog

Advent of Code 2022 Day 20

Nicky Meuleman

Day 20: Grove Positioning System

Parsing

Part 1

Final code

Part 2

Final code

Final code

Join Our Newsletter. No Spam, Only the good stuff.

Related