Advent of Code 2022 Day 20
Tags: adventofcode, rust
Published: 2022-12-21 00:27:24

---
title: "Advent of Code 2022 Day 20"
published: true
description: "Advent of Code 2022 Day 20: Grove Positioning System"
tags: 
- "adventofcode"
- "rust"
series: "Advent of Code 2022"
canonical_url: "https://nickymeuleman.netlify.app/garden/aoc2022-day20"
---
## Day 20: Grove Positioning System

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

> TL;DR: [my solution in Rust](https://github.com/NickyMeuleman/scrapyard/blob/main/advent_of_code/2022/src/day_20.rs)

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

```txt
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.

```rust
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](https://nickymeuleman.netlify.app/blog/affine-cipher#modulo)

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

```rust
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

```rust
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

```rust
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()
}
```