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.
-
5moves forwards 5 positions -
-10moves 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, 41 moves 1 position to the right:
2, 1, -3, 3, -2, 0, 42 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.
-
numsholds the original numbers mixedholds indexes to a number in thenumslistRemove the item at the found index in the
mixedlistAdd the current
numto that indexInsert the item back into
mixedat 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()
}
Top comments (0)