DEV Community

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

Posted on • Originally published at ericburden.work on

Advent of Code 2022 - Day 23

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 23 - Unstable Diffusion

Find the problem description HERE.

The Input - Go for the Grove

No nom today, either, but a whole lot of input parsing anyway! The main thing here is that we’re going to need to keep up with which elves are going to be able to move and which ones aren’t because we have the same individuals from one round to the next. To try to keep run times down as much as possible, we’ve got one big struct for managing state that we’ll mutate from one round to the next, the Grove.

use std::collections::{HashMap, HashSet};
use std::iter::{Enumerate, Map};
use std::str::Chars;

/// Represents the position of an Elf in the Grove
#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
struct Position(isize, isize);

/// Some convenience functions for working with the newtype Position.
/// I'm giving this approach a test-drive, since I don't really love
/// how Rust needs you to make the struct members public in order to
/// make a new struct, like Position(x, y). This way, I can just make
/// a public function, instead.
impl Position {
    fn new(x: isize, y: isize) -> Self {
        Self(x, y)
    }

    fn inner(&self) -> (isize, isize) {
        (self.0, self.1)
    }
}

/// Represents the cardinal and secondary directions that matter for
/// today's puzzle.
#[derive(Debug, Clone, Copy)]
enum Direction {
    North,
    NorthEast,
    East,
    SouthEast,
    South,
    SouthWest,
    West,
    NorthWest,
}

/// Represents the presence/absence of other elves in the eight spaces
/// surrounding a given position. The middle element of the middle array
/// is pretty much ignored.
#[derive(Debug, Clone, Copy)]
struct Surroundings([[bool; 3]; 3]);

impl Surroundings {
    fn new(surroundings: [[bool; 3]; 3]) -> Self {
        Surroundings(surroundings)
    }

    fn inner(&self) -> [[bool; 3]; 3] {
        self.0
    }
}

/// Represents an indicator for which direction the elf should look when
/// determining which direction to move.
#[derive(Debug, Clone, Copy)]
enum Rule {
    North,
    South,
    East,
    West,
}

/// Represents the four rules in the order they should be considered.
#[derive(Debug, Clone)]
struct Rules([Rule; 4]);

impl Rules {
    fn new(rules: [Rule; 4]) -> Self {
        Rules(rules)
    }

    fn inner(&self) -> [Rule; 4] {
        self.0
    }

    fn inner_mut(&mut self) -> &mut [Rule; 4] {
        &mut self.0
    }
}

/// Represents the current status of a proposed move by an elf. When only one
/// elf has propsed to move to a particular Position, use the Move variant. If
/// two or more elves propose to move the the same space, use the Blocked
/// variant.
#[derive(Debug, Clone, Copy)]
enum Proposal {
    Move(usize),
    Blocked,
}

/// Represents the entire program state, the Grove that the elves are spreading
/// out in. Contains a mapping from elf ID to their current position, a set of
/// all the currently occupied positions, a mapping of positions to proposed moves,
/// and the rules for proposing moves in the order they should be considered.
#[derive(Debug, Clone)]
struct Grove {
    elves: HashMap<usize, Position>,
    occupied: HashSet<Position>,
    proposed: HashMap<Position, Proposal>,
    rules: Rules,
}

/// Our parsing function for today. Today's input seemed like it would be more
/// trouble to parse with `nom` that just by iterating over the characters.
impl<'a> From<&'a str> for Grove {
    fn from(input: &str) -> Self {
        // Build up the map of elf ID => elf position.
        let mut elves = HashMap::new();
        for (row_idx, row) in input.lines().enumerate() {
            for (col_idx, glyph) in row.chars().enumerate() {
                if glyph == '.' {
                    continue;
                }
                let position = Position(col_idx as isize, row_idx as isize);
                let elf_id = elves.len();
                elves.insert(elf_id, position);
            }
        }

        // The set of all occupied positions. This is the one we'll use to determine
        // what other elves are in the vicinity of each elf as it proposes its move.
        let occupied = elves.values().copied().collect::<HashSet<_>>();

        // The list of four rules in the initial order
        let rules = Rules([Rule::North, Rule::South, Rule::West, Rule::East]);

        // Maintaining a single list of proposed moves on the Grove
        let proposed = HashMap::with_capacity(occupied.len());

        Grove {
            elves,
            occupied,
            rules,
            proposed,
        }
    }
}

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

/// Parse the input!
fn read() -> Grove {
    Grove::from(INPUT)
}

Enter fullscreen mode Exit fullscreen mode

There definitely seems to be some opportunities to simplify a bit here, but not without spending a bunch more time or compromising readability. I toyed with the idea of some sort of 2-dimensional vector that can expand itself whenever an elf tries to move beyond the borders, but that seemed hard!

Part One - I Just Need Some Space

Surprise, Christmas helpers! It’s me with my crew! Granted, it’s a crew of monkeys and elephants with dubious cross-species communication skills, but we’re here and we’re packing star fruit! We just need a few more and it looks like we can speed up the process by pre-calculating where each elf needs to plant their seed. So, Conway’s Game of Life it is! The major twist is that we need to keep up with each elf individually in case they decide not to move after all. Let’s make that happen.

use std::collections::HashMap;

/// Solve Day 23, Part 1
fn solve(input: &Grove) -> u32 {
    // Get a mutable Grove clone
    let mut grove = input.clone();

    // Advance to the next state ten times
    (0..10).for_each(|_| {
        grove.move_elves();
    });

    // Count the empty spaces and return the count
    grove.count_empty_spaces()
}

impl Grove {
    /// Get the Surroundings of a particular Position in the Grove. If there
    /// are no nearby elves, return None. Otherwise, return Some 3x3 array
    /// where each `true` value indicates the presence of a nearby elf.
    fn get_surroundings(&self, position: Position) -> Option<Surroundings> {
        use Direction::*;

        // Check each of the eight surrounding spaces for the presence
        // of another elf.
        let nw = self.occupied.contains(&position.offset(NorthWest));
        let no = self.occupied.contains(&position.offset(North));
        let ne = self.occupied.contains(&position.offset(NorthEast));
        let ea = self.occupied.contains(&position.offset(East));
        let se = self.occupied.contains(&position.offset(SouthEast));
        let so = self.occupied.contains(&position.offset(South));
        let sw = self.occupied.contains(&position.offset(SouthWest));
        let we = self.occupied.contains(&position.offset(West));
        let cr = true; // Used for the center space

        // If there are no nearby elves, return None
        if !(nw || no || ne || ea || se || so || sw || we) {
            return None;
        }

        // Otherwise, return the Surroundings
        Some(Surroundings::new([
            [nw, no, ne],
            [we, cr, ea],
            [sw, so, se],
        ]))
    }

    /// Gather all the proposals for moving from all the elves at the current
    /// state. Return a map of Positions and the Proposed action for each.
    fn make_proposals(&mut self) {
        // For each elf entry in the mapping of elf => position...
        for (elf, position) in self.elves.iter() {
            // If there are any nearby elves...
            let Some(surroundings) = self.get_surroundings(*position) else { continue; };

            // ...take the first valid proposal for moving the current elf...
            let Some(proposed) = self.rules.try_propose(position, &surroundings) else { continue; };

            // ..and try to add that proposal to the proposal mapping. If
            // this is the first elf proposing to move to the `proposed`
            // position, then add it as a Move proposal. If another elf
            // has already proposed to move to that position, block them
            // both.
            self.proposed
                .entry(proposed)
                .and_modify(|e| *e = Proposal::Blocked)
                .or_insert(Proposal::Move(*elf));
        }
    }

    /// Simulate the elves proposing to move to their new positions then move
    /// the elves where you can. Rotate the rules so that they'll be in the
    /// correct order for the next state change.
    fn move_elves(&mut self) -> bool {
        self.make_proposals();

        // We'll identify and return whether any elves moved during this state change.
        let mut any_moved = false;

        // For each position with a proposal...
        for (position, proposal) in self.proposed.iter() {
            // If the proposal hasn't been blocked, then...
            let Proposal::Move(elf) = proposal else { continue; };

            // Move the elf to the proposed position.
            self.occupied.remove(&self.elves[elf]);
            self.elves.insert(*elf, *position);
            self.occupied.insert(self.elves[elf]);

            // Set the indicator for any elves moved to `true`
            any_moved = true;
        }

        // Rotate the rules order
        self.rules.rotate_left();

        // Clear the proposals
        self.proposed.clear();

        // Return the indicator
        any_moved
    }

    /// Check the current arrangement of elves in the Grove and return two
    /// positions marking the bounds of the rectangle containing all the
    /// elves. The first Position is the top-left corner and the second
    /// Position is the bottom right corner.
    fn bounds(&self) -> (Position, Position) {
        let mut min_x = isize::MAX;
        let mut min_y = isize::MAX;
        let mut max_x = isize::MIN;
        let mut max_y = isize::MIN;

        for (xpos, ypos) in self.occupied.iter().map(|p| p.inner()) {
            min_x = min_x.min(xpos);
            max_x = max_x.max(xpos);
            min_y = min_y.min(ypos);
            max_y = max_y.max(ypos);
        }

        (Position::new(min_x, min_y), Position::new(max_x, max_y))
    }

    /// Count all the empty spaces in the smallest rectangle containing all
    /// the elves.
    fn count_empty_spaces(&self) -> u32 {
        let (min_pos, max_pos) = self.bounds();
        let (min_x, min_y) = min_pos.inner();
        let (max_x, max_y) = max_pos.inner();

        let mut empty_spaces = 0;
        for xpos in min_x..=max_x {
            for ypos in min_y..=max_y {
                let position = Position::new(xpos, ypos);
                if self.occupied.contains(&position) {
                    continue;
                }
                empty_spaces += 1;
            }
        }
        empty_spaces
    }
}

impl Position {
    /// Offset the position by one space in any of the eight directions.
    fn offset(&self, direction: Direction) -> Position {
        let (mut x, mut y) = self.inner();
        match direction {
            Direction::North => y -= 1,
            Direction::East => x += 1,
            Direction::South => y += 1,
            Direction::West => x -= 1,

            Direction::NorthEast => {
                y -= 1;
                x += 1;
            }
            Direction::SouthEast => {
                y += 1;
                x += 1;
            }
            Direction::SouthWest => {
                y += 1;
                x -= 1;
            }
            Direction::NorthWest => {
                y -= 1;
                x -= 1;
            }
        };
        Position::new(x, y)
    }
}

impl Rules {
    /// Rotate the rules such that the current first rule is moved to the
    /// end and the other rules are all moved toward the front of the list.
    fn rotate_left(&mut self) {
        self.inner_mut().rotate_left(1);
    }
}

/// Since I had two structs that were both implementing a `try_propose()` method,
/// I decided to make it a Trait.
trait TryPropose {
    fn try_propose(&self, _: &Position, _: &Surroundings) -> Option<Position>;
}

impl TryPropose for Rule {
    /// Given this Rule and references to a Position and its Surroundings, identify
    /// whether the elf at Position should propose to move and to which Position
    /// he/she should propose to move. Return None if the elf should not propose
    /// to move according to the Rule.
    fn try_propose(&self, position: &Position, surroundings: &Surroundings) -> Option<Position> {
        let [[nw, n, ne], [w, x, e], [sw, s, se]] = surroundings.inner();
        let direction = match self {
            Rule::North if !(nw || n || ne) => Some(Direction::North),
            Rule::South if !(sw || s || se) => Some(Direction::South),
            Rule::East if !(ne || e || se) => Some(Direction::East),
            Rule::West if !(nw || w || sw) => Some(Direction::West),
            _ => None,
        }?;
        Some(position.offset(direction))
    }
}

impl TryPropose for Rules {
    /// Try to get the elf to propose to move by checking each Rule in order.
    /// If the elf can't move for any of the four rules, then return None.
    /// Otherwise, return the first Position that the elf should propose to
    /// move to.
    fn try_propose(&self, position: &Position, surroundings: &Surroundings) -> Option<Position> {
        self.inner()
            .iter()
            .flat_map(|rule| rule.try_propose(position, surroundings))
            .next()
    }
}

Enter fullscreen mode Exit fullscreen mode

Again, there’s probably room for improvement here around checking the surroundings for each elf, there’s probably some efficiency to be gained by not checking all eight spaces for each elf since that means we’re definitely checking some positions multiple times. Maybe something for future enhancement.

Part Two - Get Out of My Bubble

Oh, of course, we need to tell all the elves where they should end up at the end. Well, good news, we don’t actually need to change much to get to the goal.

/// Solve Day 23, Part 2
pub fn solve(input: &Grove) -> u32 {
    // Get a mutable clone of the Grove.
    let mut grove = input.clone();

    // Count the number of rounds it takes for the Grove to
    // reach a state where no elves need to move from one
    // state to the next.
    let mut rounds = 1;
    while grove.move_elves() {
        rounds += 1;
    }

    // Return the number of rounds taken.
    rounds
}

Enter fullscreen mode Exit fullscreen mode

There, now get out there and plant those seeds!

Wrap Up

Full disclosure: after finishing all 25 days, I checked the total runtime and today’s puzzle accounts for almost half of the time it takes to run all 25 days, input parsing and both parts. That feels sloooow, but I’m a bit at a loss for a major breakthrough to get massive speed gains. I need to spend some time thinking about it, but if I’m going to update any of these solutions after the New Year, it’ll probably be this one. Honestly, though, this is one of the things I really enjoy about Advent of Code: finding a solution I’m satisfied with. It’s one thing on a challenge like this one to write code that implements all the rules as written and gets you to the right answer, but it’s another to do so with readable code with optimized performance. It’s sort of that “last 20%” that we often get pressured into avoiding on software projects due to time or budget constraints. It’s nice to have an opportunity to spend a bit of time on the craft of writing code.

Top comments (0)