DEV Community

Cover image for Advent of Code 2022 - Day 20
Eric Burden
Eric Burden

Posted on • Originally published at ericburden.work on

Advent of Code 2022 - Day 20

It’s that time of year again! Just like last year, I’ll be posting my solutions to the Advent of Code puzzles. This year, I’ll be solving the puzzles in Rust. I’ll post my solutions and code to GitHub as well. After finishing last year (and 2015-2019) in Julia, I needed to spend some time with Rust again! If you haven’t given AoC a try, I encourage you to do so along with me!

Day 20 - Grove Positioning System

Find the problem description HERE.

The Input - Just Some Numbers

Our input file for today’s puzzle is a list of numbers. Some of them are even negative. Fancy, right?

const INPUT: &str = include_str!("../../input/20/input.txt");

fn read() -> Vec<i64> {
    INPUT.lines().flat_map(|l| l.parse::<i64>()).collect()
}

Enter fullscreen mode Exit fullscreen mode

Part One - Make Mine a Double (Linked List)

Now that we’re all done collecting obsidian, we need to calculate the coordinates of the star fruit grove. This still sounds suspiciously like what we’d need to do to effectively use a nether portal, so I assume that’s the point of this exercise. I mean, surely we’re not about to just walk, right? At least we can count on the elves for interesting encryption algorithms. Not good_encryption algorithms mind you, but that’s working in our favor today. The code below may look a bit odd, but the key insight is that we can _simulate a doubly-linked list using vectors, which is made easier because we aren’t actually adding anything, just moving things around.

use std::collections::HashMap;
use std::ops::{Add, AddAssign, Index, IndexMut};

/// Solve Day 20, Part 1
fn solve(input: &[i64]) -> i64 {
    // Make a decryptor!
    let mut decryptor = MixingDecryptor::from(input.clone());
    decryptor.mix();

    // Just like that!
    decryptor.grove_coordinates_sum()
}

/// Really just a convenient struct for bundling together the three vectors
/// we'll use to solve this puzzle. Who needs an actual linked list when you
/// can just simulate one! The three vectors here will serve as a
/// pseudo-doubly-linked-list, with the values in `nodes`, the pointers to
/// next values in `forward_links`, and the pointers ot previous values
/// in `backward_links`.
#[derive(Debug)]
struct MixingDecryptor {
    nodes: Vec<i64>,
    forward_links: Vec<usize>,
    backward_links: Vec<usize>,
}

impl From<Vec<i64>> for MixingDecryptor {
    fn from(nodes: Vec<i64>) -> Self {
        // The forward links are the indices of the nodes that come after the
        // node at the same index as the link. So, `forward_links[node[0]]`
        // in the unmixed list would be `1`.
        let forward_links: Vec<_> = (1..nodes.len())
            .into_iter()
            .chain(std::iter::once(0))
            .collect();

        // The backward links are the indices of the nodes that come before the
        // node at the same index as the link.
        let backward_links: Vec<_> = std::iter::once(nodes.len() - 1)
            .chain(0..(nodes.len() - 1))
            .collect();

        MixingDecryptor {
            nodes,
            forward_links,
            backward_links,
        }
    }
}

impl MixingDecryptor {
    /// Mix up that list!
    fn mix(&mut self) {
        let Self {
            nodes,
            forward_links,
            backward_links,
        } = self;
        for (moved_node_idx, moved_node) in nodes.iter().copied().enumerate() {
            // If the value of the node is zero, don't move anything.
            if moved_node == 0 {
                continue;
            }

            // We calculate the number of skips such that we never
            // wrap fully around the list of nodes. We do this by taking
            // the absolute value of the node mod the length of the list
            // minus one. Why minus one? Because we don't count the node
            // we're moving.
            let skips = (moved_node.unsigned_abs() as usize) % (nodes.len() - 1);

            // Find the index of the node we'll displace by following the links from
            // the current node a number of times indicated by the value of the node.
            // Follow forward links for positive numbers and backward links for
            // negative numbers.
            let mut displaced_node_idx = moved_node_idx;
            for _ in (0..skips) {
                if moved_node > 0 {
                    displaced_node_idx = forward_links[displaced_node_idx];
                }
                if moved_node < 0 {
                    displaced_node_idx = backward_links[displaced_node_idx];
                }
            }

            // Move backwards one more time if the value of the node is negative,
            // since the displaced node is always displaced to the left.
            if moved_node < 0 {
                displaced_node_idx = backward_links[displaced_node_idx];
            }

            // Get the indices of other nodes we'll need to adjust links for
            let moved_node_next = forward_links[moved_node_idx];
            let moved_node_prev = backward_links[moved_node_idx];
            let displaced_node_next = forward_links[displaced_node_idx];

            // Close the gap left by the moved node
            forward_links[moved_node_prev] = moved_node_next;
            backward_links[moved_node_next] = moved_node_prev;

            // Insert the moved node after the displaced node
            forward_links[moved_node_idx] = displaced_node_next;
            backward_links[moved_node_idx] = displaced_node_idx;

            // Update the links for the displaced node
            forward_links[displaced_node_idx] = moved_node_idx;
            backward_links[displaced_node_next] = moved_node_idx;
        }
    }

    /// Get the index of the zero value.
    fn find_zero_index(&self) -> usize {
        // This is safe because the puzzle tells us that there's a zero in the
        // input. Otherwise, unwrapping here would be a bad idea.
        self.nodes.iter().position(|x| *x == 0).unwrap()
    }

    /// Find and sum the 1000th, 2000th, and 3000th values in order starting
    /// from the zero value, wrapping around the list as necessary.
    fn grove_coordinates_sum(&self) -> i64 {
        let mut current_index = self.find_zero_index();
        let mut total = 0;

        // Similar to how we mixed the lists, we can just follow links through
        // the `forward_links` vector to move forward in the list.
        for positions_after in 1..=3000 {
            current_index = self.forward_links[current_index];
            if positions_after % 1000 == 0 {
                total += self.nodes[current_index];
            }
        }
        total
    }
}

Enter fullscreen mode Exit fullscreen mode

There’s a good amount of code here, but it mostly just amounts to taking the target number out of the list, closing up the hole it left behind, and inserting it between the two numbers where it belongs.

Part Two - Sir Mix-A-Lot

Oh, of course! We forgot the random large prime number! Happens all the time. I’m actually more impressed that we apparently remember this number correctly. I guess all this problem-solving has really paid off in mental acuity, or something like that. Oh, and we need to do way more mixing, because of course we do!

/// Solve Day 20, Part 2
///
/// No real changes here, other than multiplying each value by some hefty
/// prime-looking number and mixing the list ten times. Just call me
/// Sir Mix-A-Lot.
pub fn solve(input: &Input) -> Output {
    let mod_input: Vec<_> = input.iter().map(|x| x * 811589153).collect();
    let mut decryptor = MixingDecryptor::from(mod_input);
    (0..10).for_each(|_| decryptor.mix());
    decryptor.grove_coordinates_sum().into()
}
Enter fullscreen mode Exit fullscreen mode

Thankfully, we paid some attention to efficiency in part one, so part two runs in an acceptable time. Huzzah for premature engineering, I guess.

Wrap Up

Today’s puzzle was suspiciously similar to a certain cup game I recall from a couple of years ago. Thankfully, that memory served as the inspiration and reminder that many Vecs can make one Linked List, and run pretty fast, too! With that experience in hand, today was mostly a matter of good variable naming in order to keep the operations straight. I’m getting started on catching up with my blog posts now that holiday travels are mostly over, and this puzzle was a nice “slow” one for a breather in between complicate graph algorithm puzzles.

Top comments (0)