TheLazy.Dev
Portfolio GitHub

Blog

adventofcode |rust

Advent of Code 2022 Day 23

nickymeuleman

Nicky Meuleman

Posted on December 23, 2022

Advent of Code 2022 Day 23

Day 23: Unstable Diffusion

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

TL;DR: my solution in Rust

The grove that was supposed to be full of star fruit is barren.

The elves want to plant new seedlings.
The trees need space, so the elves should spread out.

Today's input is a 2D map of locations the elves are.

  • A # represents an elf
  • A . represents an empty space

The map is surrounded by an infinite amount of empty spaces off the sides.

An example input looks like this:

....#..
..###.#
#...#.#
.#...##
#.###..
##.#.##
.#..#..
Enter fullscreen mode Exit fullscreen mode

The map is printed so north is up.
(so if in elf moves north, it moves up)

It's an other day where indexes start at 1

Parsing

The Coord struct is like Gandalf's headbobbing, it just keeps going!

#[derive(PartialEq, Eq, Hash, Clone, Copy)]
struct Coord {
    row: i32,
    col: i32,
}
Enter fullscreen mode Exit fullscreen mode

I'm only keeping the positions an elf is in memory.
Every elf has a Coord, and the result of parsing the input as a set of them.

The Coord struct uses numbers that can go negative.
Because the elves can move off the map in the input to the top or to the left.

fn parse(input: &str) -> HashSet<Coord> {
    let mut elves = HashSet::new();
    for (row, line) in input.lines().enumerate() {
        for (col, c) in line.chars().enumerate() {
            if c == '#' {
                elves.insert(Coord {
                    row: row as i32,
                    col: col as i32,
                });
            }
        }
    }
    elves
}
Enter fullscreen mode Exit fullscreen mode

Part 1

The elves use a time-consuming method to spread out.

After 10 full rounds of this method, the elves like to check if they're on the right track.
Draw a box from the top-left elf to the bottom-right one.

The question asks how many empty spaces are in the box.

The process consists of three phases per round:

  1. The consideration phase
  2. The movement phase
  3. The swappy-checky phase (I couldn't come up with a name, ok?)

The consideration phase

Each Elf considers their 8 adjactent neighbours.

A quick sidebar I like to call "we're making a data type".
It's the Direction enum!

enum Direction {
    North,
    NorthEast,
    East,
    SouthEast,
    South,
    SouthWest,
    West,
    NorthWest,
}
Enter fullscreen mode Exit fullscreen mode

If no other Elves are in one of those eight positions, the Elf does not do anything during this round.

Otherwise, the Elf looks in each of four directions in the following order and proposes moving one step in the first valid direction:

  1. If there is no Elf in the N, NE, or NW adjacent positions, the Elf proposes moving north one step.
  2. If there is no Elf in the S, SE, or SW adjacent positions, the Elf proposes moving south one step.
  3. If there is no Elf in the W, NW, or SW adjacent positions, the Elf proposes moving west one step.
  4. If there is no Elf in the E, NE, or SE adjacent positions, the Elf proposes moving east one step.

The movement phase

All at once, each Elf moves to their proposed destination tile if they were the only Elf to propose moving to that position.
If two or more Elves proposed moving to the same position, none of those Elves move.

The swappy-checky phase

This is the part that changes the order of those 4 checks in the consideration phase.

The first round starts by checking the cardinal directions as they appear in the text.
First North, then South, followed by West, and finally East.

Here, the first direction in that list moves to the back.
So the second round would start by checking South, then West, followed by East, and finally North.

Helpers

A few helpers for the Coord struct that let us take one step in a given Direction.
That's also handy to find a Coord's 8 neighbours.

impl Coord {
    fn neighbours(&self) -> [Self; 8] {
        use Direction::*;
        let n = self.add_dir(&North);
        let ne = self.add_dir(&NorthEast);
        let e = self.add_dir(&East);
        let se = self.add_dir(&SouthEast);
        let s = self.add_dir(&South);
        let sw = self.add_dir(&SouthWest);
        let w = self.add_dir(&West);
        let nw = self.add_dir(&NorthWest);
        [n, ne, e, se, s, sw, w, nw]
    }

    fn add_dir(&self, dir: &Direction) -> Self {
        use Direction::*;
        match dir {
            North => Coord {
                row: self.row - 1,
                col: self.col,
            },
            NorthEast => Coord {
                row: self.row - 1,
                col: self.col + 1,
            },
            East => Coord {
                row: self.row,
                col: self.col + 1,
            },
            SouthEast => Coord {
                row: self.row + 1,
                col: self.col + 1,
            },
            South => Coord {
                row: self.row + 1,
                col: self.col,
            },
            SouthWest => Coord {
                row: self.row + 1,
                col: self.col - 1,
            },
            West => Coord {
                row: self.row,
                col: self.col - 1,
            },
            NorthWest => Coord {
                row: self.row - 1,
                col: self.col - 1,
            },
        }
    }
}
Enter fullscreen mode Exit fullscreen mode

And a helper on Direction that, given a list of 8 neighbour occupation booleans says if the corresponding check succeeds.

The check from the consideration phase.
There's 1 check for North, 1 for South, 1 for West, and 1 for East.

impl Direction {
    fn check(&self, neighbours: &[bool; 8]) -> bool {
        // neighbours in form [n, ne, e, se, s, sw, w, nw]
        let [n, ne, e, se, s, sw, w, nw] = neighbours;
        // in these 4 conditions the question says OR, but it means AND
        match &self {
            // If there is no Elf in the N, NE, or NW adjacent positions, the Elf proposes moving north one step.
            Direction::North => !n && !ne && !nw,
            // If there is no Elf in the S, SE, or SW adjacent positions, the Elf proposes moving south one step.
            Direction::South => !s && !se && !sw,
            // If there is no Elf in the W, NW, or SW adjacent positions, the Elf proposes moving west one step.
            Direction::West => !w && !nw && !sw,
            // If there is no Elf in the E, NE, or SE adjacent positions, the Elf proposes moving east one step.
            Direction::East => !e && !ne && !se,
            // question doesn't specify, but I assume the elf doesn't propose anything
            _ => false,
        }
    }
}
Enter fullscreen mode Exit fullscreen mode

As a bonus, a function to print out the current map.

  • It gets the min and max value for the row coordinate of every elf.
  • It gets the min and max value for the col coordinate of every elf.

It then loops through the rows and cols. And prints something depending if an elf was found at that combination of row and col.

  • # if an elf is there
  • . if the space is open

Don't forget to print a newline after every row, or the output will be one big lne.

fn print(elves: &HashSet<Coord>) {
    let (minmax_row, minmax_col) = elves.iter().fold(
        ((i32::MAX, i32::MIN), (i32::MAX, i32::MIN)),
        |(minmax_row, minmax_col), Coord { row, col }| {
            (
                (minmax_row.0.min(*row), minmax_row.1.max(*row)),
                (minmax_col.0.min(*col), minmax_col.1.max(*col)),
            )
        },
    );
    for row in minmax_row.0..=minmax_row.1 {
        for col in minmax_col.0..=minmax_col.1 {
            if elves.contains(&Coord { row, col }) {
                print!("#")
            } else {
                print!(".")
            }
        }
        println!();
    }
}
Enter fullscreen mode Exit fullscreen mode

Skeleton code time!
Scratch that, with these helpers, implementation time!

Final code 

pub fn part_1(input: &str) -> usize {
    let mut elves = parse(input);
    let mut checks = [
        Direction::North,
        Direction::South,
        Direction::West,
        Direction::East,
    ];

    for round in 1.. {
        // key: proposed coordinate, val: list of old coordinates that proposed going there
        let mut proposals: HashMap<Coord, Vec<Coord>> = HashMap::new();

        // consideration phase
        for elf in &elves {
            let neighbours = elf.neighbours();
            // If no other Elves are in one of those eight positions, the Elf does not do anything during this round.
            if neighbours.iter().all(|coord| !elves.contains(coord)) {
                continue;
            }
            let neighbours = neighbours
                .iter()
                .map(|neighbour| elves.contains(neighbour))
                .collect::<Vec<_>>()
                .try_into()
                .unwrap();

            let proposed_dir = checks.iter().find(|dir| dir.check(&neighbours));
            if let Some(dir) = proposed_dir {
                let proposal = elf.add_dir(dir);
                proposals.entry(proposal).or_default().push(*elf);
            }
        }

        // movement phase
        for (new_coord, old_coords) in proposals {
            if old_coords.len() == 1 {
                elves.remove(&old_coords[0]);
                elves.insert(new_coord);
            }
        }

        // after round
        // println!("== End of Round {} ==", round);
        // print(&elves);
        // println!();

        checks.rotate_left(1);
        if round == 10 {
            let (minmax_row, minmax_col) = elves.iter().fold(
                ((i32::MAX, i32::MIN), (i32::MAX, i32::MIN)),
                |(minmax_row, minmax_col), Coord { row, col }| {
                    (
                        (minmax_row.0.min(*row), minmax_row.1.max(*row)),
                        (minmax_col.0.min(*col), minmax_col.1.max(*col)),
                    )
                },
            );
            return (minmax_row.0..=minmax_row.1)
                .cartesian_product(minmax_col.0..=minmax_col.1)
                .filter(|(row, col)| {
                    !elves.contains(&Coord {
                        row: *row,
                        col: *col,
                    })
                })
                .count();
        }
    }

    usize::MAX
}
Enter fullscreen mode Exit fullscreen mode

Part 2

Eventually, the elves come to a stop.

The question asks for the round number where no elf moves.

A moved boolean that starts at false, and flips to true every time an elf moves.
If it's still false at the end of a round, done!

Final code 

pub fn part_2(input: &str) -> i32 {
    let mut elves = parse(input);
    let mut checks = [
        Direction::North,
        Direction::South,
        Direction::West,
        Direction::East,
    ];

    for round in 1.. {
        let mut moved = false;
        // key: proposed coordinate, val: list of old coordinates that proposed going there
        let mut proposals: HashMap<Coord, Vec<Coord>> = HashMap::new();

        // consideration phase
        for elf in &elves {
            let neighbours = elf.neighbours();
            // If no other Elves are in one of those eight positions, the Elf does not do anything during this round.
            if neighbours.iter().all(|coord| !elves.contains(coord)) {
                continue;
            }
            let neighbours = neighbours
                .iter()
                .map(|neighbour| elves.contains(neighbour))
                .collect::<Vec<_>>()
                .try_into()
                .unwrap();

            let proposed_dir = checks.iter().find(|dir| dir.check(&neighbours));
            if let Some(dir) = proposed_dir {
                let proposal = elf.add_dir(dir);
                proposals.entry(proposal).or_default().push(*elf);
            }
        }

        // movement phase
        for (new_coord, old_coords) in proposals {
            if old_coords.len() == 1 {
                moved = true;
                elves.remove(&old_coords[0]);
                elves.insert(new_coord);
            }
        }

        // after round
        if !moved {
            return round;
        }
        checks.rotate_left(1);
    }

    i32::MAX
}
Enter fullscreen mode Exit fullscreen mode

Final code 

use std::collections::{HashMap, HashSet};

use itertools::Itertools;

#[derive(PartialEq, Eq, Hash, Clone, Copy)]
struct Coord {
    row: i32,
    col: i32,
}

enum Direction {
    North,
    NorthEast,
    East,
    SouthEast,
    South,
    SouthWest,
    West,
    NorthWest,
}

impl Direction {
    fn check(&self, neighbours: &[bool; 8]) -> bool {
        // neighbours in form [n, ne, e, se, s, sw, w, nw]
        let [n, ne, e, se, s, sw, w, nw] = neighbours;
        // in these 4 conditions the question says OR, but it means AND, right?
        match &self {
            // If there is no Elf in the N, NE, or NW adjacent positions, the Elf proposes moving north one step.
            Direction::North => !n && !ne && !nw,
            // If there is no Elf in the S, SE, or SW adjacent positions, the Elf proposes moving south one step.
            Direction::South => !s && !se && !sw,
            // If there is no Elf in the W, NW, or SW adjacent positions, the Elf proposes moving west one step.
            Direction::West => !w && !nw && !sw,
            // If there is no Elf in the E, NE, or SE adjacent positions, the Elf proposes moving east one step.
            Direction::East => !e && !ne && !se,
            // question doesn't specify, but I assume the elf doesn't propose anything
            _ => false,
        }
    }
}

impl Coord {
    fn neighbours(&self) -> [Self; 8] {
        use Direction::*;
        let n = self.add_dir(&North);
        let ne = self.add_dir(&NorthEast);
        let e = self.add_dir(&East);
        let se = self.add_dir(&SouthEast);
        let s = self.add_dir(&South);
        let sw = self.add_dir(&SouthWest);
        let w = self.add_dir(&West);
        let nw = self.add_dir(&NorthWest);
        [n, ne, e, se, s, sw, w, nw]
    }

    fn add_dir(&self, dir: &Direction) -> Self {
        use Direction::*;
        match dir {
            North => Coord {
                row: self.row - 1,
                col: self.col,
            },
            NorthEast => Coord {
                row: self.row - 1,
                col: self.col + 1,
            },
            East => Coord {
                row: self.row,
                col: self.col + 1,
            },
            SouthEast => Coord {
                row: self.row + 1,
                col: self.col + 1,
            },
            South => Coord {
                row: self.row + 1,
                col: self.col,
            },
            SouthWest => Coord {
                row: self.row + 1,
                col: self.col - 1,
            },
            West => Coord {
                row: self.row,
                col: self.col - 1,
            },
            NorthWest => Coord {
                row: self.row - 1,
                col: self.col - 1,
            },
        }
    }
}

fn parse(input: &str) -> HashSet<Coord> {
    let mut elves = HashSet::new();
    for (row, line) in input.lines().enumerate() {
        for (col, c) in line.chars().enumerate() {
            if c == '#' {
                elves.insert(Coord {
                    row: row as i32,
                    col: col as i32,
                });
            }
        }
    }
    elves
}

#[allow(unused)]
fn print(elves: &HashSet<Coord>) {
    let (minmax_row, minmax_col) = elves.iter().fold(
        ((i32::MAX, i32::MIN), (i32::MAX, i32::MIN)),
        |(minmax_row, minmax_col), Coord { row, col }| {
            (
                (minmax_row.0.min(*row), minmax_row.1.max(*row)),
                (minmax_col.0.min(*col), minmax_col.1.max(*col)),
            )
        },
    );
    for row in minmax_row.0..=minmax_row.1 {
        for col in minmax_col.0..=minmax_col.1 {
            if elves.contains(&Coord { row, col }) {
                print!("#")
            } else {
                print!(".")
            }
        }
        println!();
    }
}

pub fn part_1(input: &str) -> usize {
    let mut elves = parse(input);
    let mut checks = [
        Direction::North,
        Direction::South,
        Direction::West,
        Direction::East,
    ];

    for round in 1.. {
        // key: proposed coordinate, val: list of old coordinates that proposed going there
        let mut proposals: HashMap<Coord, Vec<Coord>> = HashMap::new();

        // consideration phase
        for elf in &elves {
            let neighbours = elf.neighbours();
            // If no other Elves are in one of those eight positions, the Elf does not do anything during this round.
            if neighbours.iter().all(|coord| !elves.contains(coord)) {
                continue;
            }
            let neighbours = neighbours
                .iter()
                .map(|neighbour| elves.contains(neighbour))
                .collect::<Vec<_>>()
                .try_into()
                .unwrap();

            let proposed_dir = checks.iter().find(|dir| dir.check(&neighbours));
            if let Some(dir) = proposed_dir {
                let proposal = elf.add_dir(dir);
                proposals.entry(proposal).or_default().push(*elf);
            }
        }

        // movement phase
        for (new_coord, old_coords) in proposals {
            if old_coords.len() == 1 {
                elves.remove(&old_coords[0]);
                elves.insert(new_coord);
            }
        }

        // after round
        // println!("== End of Round {} ==", round);
        // print(&elves);
        // println!();

        checks.rotate_left(1);
        if round == 10 {
            let (minmax_row, minmax_col) = elves.iter().fold(
                ((i32::MAX, i32::MIN), (i32::MAX, i32::MIN)),
                |(minmax_row, minmax_col), Coord { row, col }| {
                    (
                        (minmax_row.0.min(*row), minmax_row.1.max(*row)),
                        (minmax_col.0.min(*col), minmax_col.1.max(*col)),
                    )
                },
            );
            return (minmax_row.0..=minmax_row.1)
                .cartesian_product(minmax_col.0..=minmax_col.1)
                .filter(|(row, col)| {
                    !elves.contains(&Coord {
                        row: *row,
                        col: *col,
                    })
                })
                .count();
        }
    }

    usize::MAX
}

pub fn part_2(input: &str) -> i32 {
    let mut elves = parse(input);
    let mut checks = [
        Direction::North,
        Direction::South,
        Direction::West,
        Direction::East,
    ];

    for round in 1.. {
        let mut moved = false;
        // key: proposed coordinate, val: list of old coordinates that proposed going there
        let mut proposals: HashMap<Coord, Vec<Coord>> = HashMap::new();

        // consideration phase
        for elf in &elves {
            let neighbours = elf.neighbours();
            // If no other Elves are in one of those eight positions, the Elf does not do anything during this round.
            if neighbours.iter().all(|coord| !elves.contains(coord)) {
                continue;
            }
            let neighbours = neighbours
                .iter()
                .map(|neighbour| elves.contains(neighbour))
                .collect::<Vec<_>>()
                .try_into()
                .unwrap();

            let proposed_dir = checks.iter().find(|dir| dir.check(&neighbours));
            if let Some(dir) = proposed_dir {
                let proposal = elf.add_dir(dir);
                proposals.entry(proposal).or_default().push(*elf);
            }
        }

        // movement phase
        for (new_coord, old_coords) in proposals {
            if old_coords.len() == 1 {
                moved = true;
                elves.remove(&old_coords[0]);
                elves.insert(new_coord);
            }
        }

        // after round
        if !moved {
            return round;
        }
        checks.rotate_left(1);
    }

    i32::MAX
}
Enter fullscreen mode Exit fullscreen mode
💖 💪 🙅 🚩
nickymeuleman
Nicky Meuleman

Posted on December 23, 2022

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

Sign up to receive the latest update from our blog.

Related

Advent of Code 2023 Day 18
adventofcode Advent of Code 2023 Day 18

December 18, 2023

Advent of Code 2023 Day 17
adventofcode Advent of Code 2023 Day 17

December 17, 2023

Advent of Code 2023 Day 16
adventofcode Advent of Code 2023 Day 16

December 17, 2023

Advent of Code 2023 Day 15
adventofcode Advent of Code 2023 Day 15

December 15, 2023

Advent of Code 2023 Day 14
adventofcode Advent of Code 2023 Day 14

December 14, 2023