DEV Community: Nicky Meuleman

Advent of Code 2023 Day 18

Nicky Meuleman — Mon, 18 Dec 2023 18:52:49 +0000

Day 18: Lavaduct Lagoon

https://adventofcode.com/2023/day/18

The factory needs so much lava to work through its backlog, that the elves are digging a collection pool right in front of the entrance.

Today's input is a list of instructions to dig the perimeter of the pool.

An example input looks like this:

R 6 (#70c710)
D 5 (#0dc571)
L 2 (#5713f0)
D 2 (#d2c081)
R 2 (#59c680)
D 2 (#411b91)
L 5 (#8ceee2)
U 2 (#caa173)
L 1 (#1b58a2)
U 2 (#caa171)
R 2 (#7807d2)
U 3 (#a77fa3)
L 2 (#015232)
U 2 (#7a21e3)

Each instruction tells the digger to move to a different point, and dig every tile it passes through.

When followed, it results in a closed loop of trench being dug.

Part 1

The first letter in an instruction is the direction the digger should move in next:

U up
D down
L left
R right

The number tells the digger how far it should move in that direction.

That hexcode looking thing is not used in part1.

Every tile the loop enloses should also be dug out.

The question asks how many tiles are dug out.

I broke this up into 2 parts:

Parsing an instruction per line
Calculating the area when following the instructions

Helpers

I represented each instruction as an Instr:

struct Instr {
    dir: Dir,
    amount: i64,
}

Each direction is a Dir:

enum Dir {
    Up,
    Down,
    Left,
    Right,
}

The parsing:

let instructions = input.lines().map(|line| {
    let (instr, _) = line.split_once(" (").unwrap();
    let (dir, amount) = instr.split_once(" ").unwrap();
    let dir = match dir {
        "U" => Dir::Up,
        "D" => Dir::Down,
        "L" => Dir::Left,
        "R" => Dir::Right,
        _ => panic!("wrong dir"),
    };
    let amount = amount.parse().unwrap();
    Instr { dir, amount }
});

If you follow each instruction, the trench is a polygon with square edges.
The question is asking for the area of that polygon.

That polygon has a bunch of coordinates at its edges that are specified by following the instructions.
So I made a Coord:

struct Coord {
    x: i64,
    y: i64,
}

I used the shoelace formula to calculate its area.

More information about polygon coordinates and areas

Calculating the area, a function that takes the list of instructions:

fn calc_area(instructions: impl Iterator<Item = Instr>) -> i64 {
    let (area, perimeter, _) = instructions.fold(
        (0, 0, Coord { x: 0, y: 0 }),
        |(area, perimeter, pos), Instr { dir, amount }| {
            let new_pos = pos.advance(&dir, amount);
            let new_area = area + (pos.x * new_pos.y - new_pos.x * pos.y);
            let new_perimeter = (new_pos.x - pos.x).abs() + (new_pos.y - pos.y).abs() + perimeter;
            (new_area, new_perimeter, new_pos)
        },
    );

    (area.abs() + perimeter) / 2 + 1
}

That function uses a helper that lets a coordinate move in a direction for an amount of steps:

impl Coord {
    pub fn advance(&self, direction: &Dir, amount: i64) -> Self {
        match direction {
            Dir::Up => Self {
                x: self.x + amount,
                y: self.y,
            },
            Dir::Down => Self {
                x: self.x - amount,
                y: self.y,
            },
            Dir::Left => Self {
                x: self.x,
                y: self.y - amount,
            },
            Dir::Right => Self {
                x: self.x,
                y: self.y + amount,
            },
        }
    }
}

Code

pub fn part_1(input: &str) -> i64 {
    let instructions = input.lines().map(|line| {
        let (instr, _) = line.split_once(" (").unwrap();
        let (dir, amount) = instr.split_once(" ").unwrap();
        let dir = match dir {
            "U" => Dir::Up,
            "D" => Dir::Down,
            "L" => Dir::Left,
            "R" => Dir::Right,
            _ => panic!("wrong dir"),
        };
        let amount = amount.parse().unwrap();
        Instr { dir, amount }
    });

    calc_area(instructions)
}

Part 2

Oops! The instructions should be interpreted differently.

Each hexadecimal code is six digits long.

The first five hexadecimal digits encode the distance in meters as a five-digit hexadecimal number.
The last hexadecimal digit encodes the direction to dig: 0 means R, 1 means D, 2 means L, and 3 means U.

The question asks how many tiles are dug out.

Only the parsing logic changes.

Code

pub fn part_2(input: &str) -> i64 {
    let instructions = input.lines().map(|line| {
        let line = line.strip_suffix(")").unwrap();
        let (_, hex) = line.split_once("(#").unwrap();
        let (amount, dir) = hex.split_at(5);
        let amount = i64::from_str_radix(amount, 16).unwrap();
        let dir = match dir {
            "3" => Dir::Up,
            "1" => Dir::Down,
            "2" => Dir::Left,
            "0" => Dir::Right,
            _ => panic!("wrong dir"),
        };
        Instr { dir, amount }
    });

    calc_area(instructions)
}

Final code

struct Coord {
    x: i64,
    y: i64,
}

impl Coord {
    pub fn advance(&self, direction: &Dir, amount: i64) -> Self {
        match direction {
            Dir::Up => Self {
                x: self.x + amount,
                y: self.y,
            },
            Dir::Down => Self {
                x: self.x - amount,
                y: self.y,
            },
            Dir::Left => Self {
                x: self.x,
                y: self.y - amount,
            },
            Dir::Right => Self {
                x: self.x,
                y: self.y + amount,
            },
        }
    }
}

struct Instr {
    dir: Dir,
    amount: i64,
}

enum Dir {
    Up,
    Down,
    Left,
    Right,
}

fn calc_area(instructions: impl Iterator<Item = Instr>) -> i64 {
    let (area, perimeter, _) = instructions.fold(
        (0, 0, Coord { x: 0, y: 0 }),
        |(area, perimeter, pos), Instr { dir, amount }| {
            let new_pos = pos.advance(&dir, amount);
            let new_area = area + (pos.x * new_pos.y - new_pos.x * pos.y);
            let new_perimeter = (new_pos.x - pos.x).abs() + (new_pos.y - pos.y).abs() + perimeter;
            (new_area, new_perimeter, new_pos)
        },
    );

    (area.abs() + perimeter) / 2 + 1
}

pub fn part_1(input: &str) -> i64 {
    let instructions = input.lines().map(|line| {
        let (instr, _) = line.split_once(" (").unwrap();
        let (dir, amount) = instr.split_once(" ").unwrap();
        let dir = match dir {
            "U" => Dir::Up,
            "D" => Dir::Down,
            "L" => Dir::Left,
            "R" => Dir::Right,
            _ => panic!("wrong dir"),
        };
        let amount = amount.parse().unwrap();
        Instr { dir, amount }
    });

    calc_area(instructions)
}

pub fn part_2(input: &str) -> i64 {
    let instructions = input.lines().map(|line| {
        let line = line.strip_suffix(")").unwrap();
        let (_, hex) = line.split_once("(#").unwrap();
        let (amount, dir) = hex.split_at(5);
        let amount = i64::from_str_radix(amount, 16).unwrap();
        let dir = match dir {
            "3" => Dir::Up,
            "1" => Dir::Down,
            "2" => Dir::Left,
            "0" => Dir::Right,
            _ => panic!("wrong dir"),
        };
        Instr { dir, amount }
    });

    calc_area(instructions)
}

Advent of Code 2023 Day 17

Nicky Meuleman — Sun, 17 Dec 2023 21:20:55 +0000

Day 17: Clumsy Crucible

https://adventofcode.com/2023/day/17

The lava starts flowing down to Metal Island.

There, elves are busy taking the lava to the factory in big crucibles (cups for molten stuff).

They want to get the crucibles to the factory as fast as possible to lose the least amount of heat.

Figuring out the ideal route to take is your job.

The elves prepared a map that list how much heat is lost if you enter a tile.
The starting location is in the top-left, the ending location in the bottom-right.

An example input looks like this:

2413432311323
3215453535623
3255245654254
3446585845452
4546657867536
1438598798454
4457876987766
3637877979653
4654967986887
4564679986453
1224686865563
2546548887735
4322674655533

Parsing

A 2D list of digits:

fn parse(input: &str) -> Vec<Vec<u8>> {
    input
        .lines()
        .map(|line| {
            line.chars()
                .map(|c| c.to_digit(10).unwrap() as u8)
                .collect()
        })
        .collect()
}

Part 1

The crucibles are unwieldy, pretty hard to "drive" (is that the right word? Hard to move.)

They cannot move in a straight line for more than 3 tiles.
They cannot reverse direction

The question asks for the minimum amount of heatloss when you reach the destination.

This is a shortest path problem, time to pull out the Dijkstra.

Helpers

To do some Dijkstra's algorithm, I need a priority queue.
In Rust, I'll use a BinaryHeap for this.

Some skeleton/pseudo-code I want to work towards:

pub fn part_1(input: &str) -> u32 {
    let grid = parse(input);
    let goal = Coord {
        row: grid.len() - 1,
        col: grid[0].len() - 1,
    };

    let mut pq = BinaryHeap::new();

    // push the initial 2 directions the crucible can move onto the pq
    pq.push(initial_crucibles);

    // loop until the goal is reached, or the pq is empty
    while let Some(crucible) = pq.pop() {
        if crucible.pos == goal {
            return crucible.cost;
        }
        // determine the next possible crucibles and push them onto the pq
        for successor in node.successors(&grid) {
            pq.push(successor);
        }
    }
}

The things I'll push onto that queue and pop off it are my own data structures, Crucible:

struct Crucible {
    cost: u32,
    pos: Coord,
    dir: Direction,
    moves_in_dir: u8,
}

The position it has is tracked by a Coord:

struct Coord {
    row: usize,
    col: usize,
}

The direction the crucible is moving in is a Direction:

enum Direction {
    Up,
    Down,
    Left,
    Right,
}

Now, to handle the soring of the Crucibles in that priority queue, I specified how they should be sorted, by cost, from low to high.
That way, every time I pop from the queue, I get the crucible with the lowest cost.

// The priority queue holds Crucible
// We define an ordering trait so the one with the lowest cost gets popped from the pq first.
// We do this by flipping the ordering on cost (comparing "other to self" instead of "self to other")
// that way, nodes with a lower cost will compare as Ordering::Greater, and get sent to the front of the pq
impl Ord for Crucible {
    fn cmp(&self, other: &Self) -> Ordering {
        other.cost.cmp(&self.cost)
    }
}

// Ensure partialOrd is consistent with Ord. From the docs:
// > If Ord is also implemented for Self and Rhs, it must also be consistent with partial_cmp (see the documentation of that trait for the exact requirements).
// > It’s easy to accidentally make them disagree by deriving some of the traits and manually implementing others.
// tl;dr: implement PartialOrd in terms of the Ord we just specified to ensure correctness. Letting it be automatically determined is wrong sometimes.
impl PartialOrd for Crucible {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        Some(self.cmp(other))
    }
}

The next step is the function that determines the successors (a fancy word for the next possible crucibles).
It tries to move in every direction, and only does so if the rules from the question pass:

impl Crucible {
    fn successors(&self, grid: &Vec<Vec<u8>>) -> Vec<Self> {
        let rows = grid.len();
        let cols = grid[0].len();

        let mut successors = Vec::new();
        for dir in [
            Direction::Up,
            Direction::Down,
            Direction::Left,
            Direction::Right,
        ] {
            if self.dir == dir && self.moves_in_dir == 3 {
                // already moved 3 tiles in a straight line, can't move further
                continue;
            }
            if self.dir.opposite() == dir {
                // can't move in opposite direction
                continue;
            }
            // simulate a move inside the bounds
            if let Some(pos) = self.pos.forward(&dir, rows, cols) {
                // calculate the total cost to get to that neighbour
                // it's the total cost to get to the current node + the cost to travel to the neighbour
                let cost = self.cost + grid[pos.row][pos.col] as u32;

                // increment straight_moves if we went straight, else we moved 1 tile in the current direction
                let moves_in_dir = if self.dir == dir {
                    self.moves_in_dir + 1
                } else {
                    1
                };

                successors.push(Crucible {
                    pos,
                    cost,
                    dir,
                    moves_in_dir,
                })
            }
        }

        successors
    }
}

This handles some of the rules crucibles must adhere to, like:

Not moving more than 3 tiles in a straight line
Not reversing direction

The not reversing direction rule uses another helper:

impl Direction {
    fn opposite(&self) -> Self {
        match self {
            Direction::Up => Direction::Down,
            Direction::Down => Direction::Up,
            Direction::Left => Direction::Right,
            Direction::Right => Direction::Left,
        }
    }
}

It also makes sure a crucible doesn't go off the map with that forward helper, it only adds a new crucible if it's inside the grid.
That's because that forward helper only returns a valid coordinate if it's inside the grid:

impl Coord {
    fn forward(&self, dir: &Direction, rows: usize, cols: usize) -> Option<Self> {
        let coord = match dir {
            Direction::Up if self.row > 0 => Coord {
                row: self.row - 1,
                col: self.col,
            },
            Direction::Down if self.row < (rows - 1) => Coord {
                row: self.row + 1,
                col: self.col,
            },
            Direction::Left if self.col > 0 => Coord {
                row: self.row,
                col: self.col - 1,
            },
            Direction::Right if self.col < (cols - 1) => Coord {
                row: self.row,
                col: self.col + 1,
            },
            _ => return None,
        };
        Some(coord)
    }
}

Code

This worked, but went very slow, so I kept track of previous crucibles in a HashSet.
Only tracking the Crucible position is not enough, as it matters which direction the crucible is travelling in, and how far it already has in a straight line.

So every time I want to add a successor to the priority queue, I check if that (coord, dir, moves_in_dir) triplet has already been seen.
If it hasn't, I add that crucible to the queue, and that triplet to the seen cache.

pub fn part_1(input: &str) -> u32 {
    let grid = parse(input);
    let goal = Coord {
        row: grid.len() - 1,
        col: grid[0].len() - 1,
    };

    let mut pq = BinaryHeap::new();
    let mut seen = HashSet::new();

    let right = Crucible {
        cost: grid[0][1] as u32,
        dir: Direction::Right,
        pos: Coord { row: 0, col: 1 },
        moves_in_dir: 1,
    };
    pq.push(right);

    let down = Crucible {
        cost: grid[1][0] as u32,
        dir: Direction::Down,
        pos: Coord { row: 1, col: 0 },
        moves_in_dir: 1,
    };
    pq.push(down);

    while let Some(crucible) = pq.pop() {
        if crucible.pos == goal {
            return crucible.cost;
        }
        for crucible in crucible.successors(&grid) {
            if seen.insert((crucible.pos, crucible.dir, crucible.moves_in_dir)) {
                pq.push(crucible);
            }
        }
    }

    panic!("No path found")
}

Part 2

It's not going fast enough, to remedy this, the elves brought bigger crucibles, ultracrucibles.

They can move more lava, but are also even more unwieldy.

They need to move a minimum of 4 tiles in a single direction before they can turn or stop.

They can't go further than 10 tiles in a single direction before they have to turn.

The question asks for the minimum amount of heatloss when you reach the destination.

Helpers

The nodes that go into the priority queue now are UltraCrucibles:

struct UltraCrucible {
    cost: u32,
    pos: Coord,
    dir: Direction,
    moves_in_dir: u8,
}

The same logic is used to order them:

impl Ord for UltraCrucible {
    fn cmp(&self, other: &Self) -> Ordering {
        other.cost.cmp(&self.cost)
    }
}

impl PartialOrd for UltraCrucible {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        Some(self.cmp(other))
    }
}

And now, for the part that is different between part1 and part2, the successors:

impl UltraCrucible {
    fn successors(&self, grid: &Vec<Vec<u8>>) -> Vec<Self> {
        let rows = grid.len();
        let cols = grid[0].len();

        let mut successors = Vec::new();
        for dir in [
            Direction::Up,
            Direction::Down,
            Direction::Left,
            Direction::Right,
        ] {
            // Once an ultra crucible starts moving in a direction, it needs to move a minimum of four blocks in that direction before it can turn
            if self.moves_in_dir < 4 && dir != self.dir {
                continue;
            }
            // an ultra crucible can move a maximum of ten consecutive blocks without turning.
            if self.dir == dir && self.moves_in_dir == 10 {
                // already moved 3 tiles in a straight line, can't move further
                continue;
            }
            if self.dir.opposite() == dir {
                // can't move in opposite direction
                continue;
            }
            // simulate a move inside the bounds
            if let Some(pos) = self.pos.forward(&dir, rows, cols) {
                // calculate the total cost to get to that neighbour
                // it's the total cost to get to the current node + the cost to travel to the neighbour
                let cost = self.cost + grid[pos.row][pos.col] as u32;

                // increment straight_moves if we went straight, else we moved 1 tile in the current direction
                let moves_in_dir = if self.dir == dir {
                    self.moves_in_dir + 1
                } else {
                    1
                };

                successors.push(UltraCrucible {
                    pos,
                    cost,
                    dir,
                    moves_in_dir,
                })
            }
        }

        successors
    }
}

This function encodes the movement rules laid out by the question.

The only other minor change is the check to see if the destination has been reached in the loop.
Since an UltraCrucible can't stop immediately, I added a check to see if it has been moving for at least 4 tiles.

Code

pub fn part_2(input: &str) -> u32 {
    let grid = parse(input);
    let goal = Coord {
        row: grid.len() - 1,
        col: grid[0].len() - 1,
    };

    let mut pq = BinaryHeap::new();
    let mut seen = HashSet::new();

    let right = UltraCrucible {
        cost: grid[0][1] as u32,
        dir: Direction::Right,
        pos: Coord { row: 0, col: 1 },
        moves_in_dir: 1,
    };
    pq.push(right);

    let down = UltraCrucible {
        cost: grid[1][0] as u32,
        dir: Direction::Down,
        pos: Coord { row: 1, col: 0 },
        moves_in_dir: 1,
    };
    pq.push(down);

    while let Some(ultra_crucible) = pq.pop() {
        if ultra_crucible.pos == goal && ultra_crucible.moves_in_dir >= 4 {
            return ultra_crucible.cost;
        }
        for ultra_crucible in ultra_crucible.successors(&grid) {
            if seen.insert((
                ultra_crucible.pos,
                ultra_crucible.dir,
                ultra_crucible.moves_in_dir,
            )) {
                pq.push(ultra_crucible);
            }
        }
    }

    panic!("No path found")
}

Final code

use std::{
    cmp::Ordering,
    collections::{BinaryHeap, HashSet},
};

#[derive(Debug, PartialEq, Eq, PartialOrd, Ord, Hash, Clone, Copy)]
struct Coord {
    row: usize,
    col: usize,
}

impl Coord {
    fn forward(&self, dir: &Direction, rows: usize, cols: usize) -> Option<Self> {
        let coord = match dir {
            Direction::Up if self.row > 0 => Coord {
                row: self.row - 1,
                col: self.col,
            },
            Direction::Down if self.row < (rows - 1) => Coord {
                row: self.row + 1,
                col: self.col,
            },
            Direction::Left if self.col > 0 => Coord {
                row: self.row,
                col: self.col - 1,
            },
            Direction::Right if self.col < (cols - 1) => Coord {
                row: self.row,
                col: self.col + 1,
            },
            _ => return None,
        };
        Some(coord)
    }
}

#[derive(Debug, PartialEq, Eq, PartialOrd, Ord, Hash, Clone, Copy)]
enum Direction {
    Up,
    Down,
    Left,
    Right,
}

impl Direction {
    fn opposite(&self) -> Self {
        match self {
            Direction::Up => Direction::Down,
            Direction::Down => Direction::Up,
            Direction::Left => Direction::Right,
            Direction::Right => Direction::Left,
        }
    }
}

#[derive(Debug, PartialEq, Eq, Hash, Clone, Copy)]
struct Crucible {
    cost: u32,
    pos: Coord,
    dir: Direction,
    moves_in_dir: u8,
}

// The priority queue holds Nodes
// We define an ordering trait so the one with the lowest cost gets popped from the pq first.
// We do this by flipping the ordering on cost (comparing "other to self" instead of "self to other")
// that way, nodes with a lower cost will compare as Ordering::Greater, and get sent to the front of the pq
impl Ord for Crucible {
    fn cmp(&self, other: &Self) -> Ordering {
        other.cost.cmp(&self.cost)
    }
}

// Ensure partialOrd is consistent with Ord. If you #[derive(PartialOrd)] this it might not be the same as that implementation uses a top-down ordering on the Node struct fields
// in this case, it would order by idx first (as that field occurs first in the source code where Node is defined) and would not be consistent.
// From the docs:
// > If Ord is also implemented for Self and Rhs, it must also be consistent with partial_cmp (see the documentation of that trait for the exact requirements).
// > It’s easy to accidentally make them disagree by deriving some of the traits and manually implementing others.
impl PartialOrd for Crucible {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        Some(self.cmp(other))
    }
}

impl Crucible {
    fn successors(&self, grid: &Vec<Vec<u8>>) -> Vec<Self> {
        let rows = grid.len();
        let cols = grid[0].len();

        let mut successors = Vec::new();
        for dir in [
            Direction::Up,
            Direction::Down,
            Direction::Left,
            Direction::Right,
        ] {
            if self.dir == dir && self.moves_in_dir == 3 {
                // already moved 3 tiles in a straight line, can't move further
                continue;
            }
            if self.dir.opposite() == dir {
                // can't move in opposite direction
                continue;
            }
            // simulate a move inside the bounds
            if let Some(pos) = self.pos.forward(&dir, rows, cols) {
                // calculate the total cost to get to that neighbour
                // it's the total cost to get to the current node + the cost to travel to the neighbour
                let cost = self.cost + grid[pos.row][pos.col] as u32;

                // increment straight_moves if we went straight, else we moved 1 tile in the current direction
                let moves_in_dir = if self.dir == dir {
                    self.moves_in_dir + 1
                } else {
                    1
                };

                successors.push(Crucible {
                    pos,
                    cost,
                    dir,
                    moves_in_dir,
                })
            }
        }

        successors
    }
}

fn parse(input: &str) -> Vec<Vec<u8>> {
    input
        .lines()
        .map(|line| {
            line.chars()
                .map(|c| c.to_digit(10).unwrap() as u8)
                .collect()
        })
        .collect()
}

pub fn part_1(input: &str) -> u32 {
    let grid = parse(input);
    let goal = Coord {
        row: grid.len() - 1,
        col: grid[0].len() - 1,
    };

    let mut pq = BinaryHeap::new();
    let mut seen = HashSet::new();

    let right = Crucible {
        cost: grid[0][1] as u32,
        dir: Direction::Right,
        pos: Coord { row: 0, col: 1 },
        moves_in_dir: 1,
    };
    pq.push(right);

    let down = Crucible {
        cost: grid[1][0] as u32,
        dir: Direction::Down,
        pos: Coord { row: 1, col: 0 },
        moves_in_dir: 1,
    };
    pq.push(down);

    while let Some(crucible) = pq.pop() {
        if crucible.pos == goal {
            return crucible.cost;
        }
        for crucible in crucible.successors(&grid) {
            if seen.insert((crucible.pos, crucible.dir, crucible.moves_in_dir)) {
                pq.push(crucible);
            }
        }
    }

    panic!("No path found")
}

#[derive(Debug, PartialEq, Eq, Hash, Clone, Copy)]
struct UltraCrucible {
    cost: u32,
    pos: Coord,
    dir: Direction,
    moves_in_dir: u8,
}

impl Ord for UltraCrucible {
    fn cmp(&self, other: &Self) -> Ordering {
        other.cost.cmp(&self.cost)
    }
}

impl PartialOrd for UltraCrucible {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        Some(self.cmp(other))
    }
}

impl UltraCrucible {
    fn successors(&self, grid: &Vec<Vec<u8>>) -> Vec<Self> {
        let rows = grid.len();
        let cols = grid[0].len();

        let mut successors = Vec::new();
        for dir in [
            Direction::Up,
            Direction::Down,
            Direction::Left,
            Direction::Right,
        ] {
            // Once an ultra crucible starts moving in a direction, it needs to move a minimum of four blocks in that direction before it can turn
            if self.moves_in_dir < 4 && dir != self.dir {
                continue;
            }
            // an ultra crucible can move a maximum of ten consecutive blocks without turning.
            if self.dir == dir && self.moves_in_dir == 10 {
                // already moved 3 tiles in a straight line, can't move further
                continue;
            }
            if self.dir.opposite() == dir {
                // can't move in opposite direction
                continue;
            }
            // simulate a move inside the bounds
            if let Some(pos) = self.pos.forward(&dir, rows, cols) {
                // calculate the total cost to get to that neighbour
                // it's the total cost to get to the current node + the cost to travel to the neighbour
                let cost = self.cost + grid[pos.row][pos.col] as u32;

                // increment straight_moves if we went straight, else we moved 1 tile in the current direction
                let moves_in_dir = if self.dir == dir {
                    self.moves_in_dir + 1
                } else {
                    1
                };

                successors.push(UltraCrucible {
                    pos,
                    cost,
                    dir,
                    moves_in_dir,
                })
            }
        }

        successors
    }
}

pub fn part_2(input: &str) -> u32 {
    let grid = parse(input);
    let goal = Coord {
        row: grid.len() - 1,
        col: grid[0].len() - 1,
    };

    let mut pq = BinaryHeap::new();
    let mut seen = HashSet::new();

    let right = UltraCrucible {
        cost: grid[0][1] as u32,
        dir: Direction::Right,
        pos: Coord { row: 0, col: 1 },
        moves_in_dir: 1,
    };
    pq.push(right);

    let down = UltraCrucible {
        cost: grid[1][0] as u32,
        dir: Direction::Down,
        pos: Coord { row: 1, col: 0 },
        moves_in_dir: 1,
    };
    pq.push(down);

    while let Some(ultra_crucible) = pq.pop() {
        if ultra_crucible.pos == goal && ultra_crucible.moves_in_dir >= 4 {
            return ultra_crucible.cost;
        }
        for ultra_crucible in ultra_crucible.successors(&grid) {
            if seen.insert((
                ultra_crucible.pos,
                ultra_crucible.dir,
                ultra_crucible.moves_in_dir,
            )) {
                pq.push(ultra_crucible);
            }
        }
    }

    panic!("No path found")
}

Advent of Code 2023 Day 16

Nicky Meuleman — Sun, 17 Dec 2023 21:18:40 +0000

Day 16: The Floor Will Be Lava

https://adventofcode.com/2023/day/16

The light is focussed somewhere.

It goes into a big cavern with a bunch of mirrors and splitters in it.

Today's input is a map of the cavern.

An example input looks like this:

.|...\....
|.-.\.....
.....|-...
........|.
..........
.........\
..../.\\..
.-.-/..|..
.|....-|.\
..//.|....

. empty space
'\' left mirror
'/' right mirror
'-' horizontal splitter
'|' vertical splitter

If a beam hits an empty space, it keeps going like nothing happened (Because it didn't you see? Nothing. It happened.)

If a beam hits a mirror, it is reflected 90 degrees according to the angle of the mirror it hit.

If a beam hits a splitter on the pointy end, it passes through like nothing happened.

If a beam hits a splitter on the flat end, it gets split and exits through the 2 pointy ends.

Beams do not interact, they pass right through eachother.

Parsing

I represent the cave as a 2D list of Tile:

enum Tile {
    Empty,
    SplitHoriz,
    SplitVert,
    MirrorForward,
    MirrorBack,
}

fn parse(s: &str) -> Vec<Vec<Tile>> {
    s.lines()
        .map(|line| {
            line.chars()
                .map(|c| match c {
                    '\\' => Tile::MirrorBack,
                    '/' => Tile::MirrorForward,
                    '.' => Tile::Empty,
                    '-' => Tile::SplitHoriz,
                    '|' => Tile::SplitVert,
                    _ => panic!("at the disco"),
                })
                .collect()
        })
        .collect()
}

Part 1

The beam enters the cave from the top left, going right.

The question asks how many tiles are energized (1 or more beams pass through it).

Helpers

A Beam struct represents a beam of light:

struct Beam {
    pos: Coord,
    dir: Direction,
}

The position of a beam is stored as a Coord:

struct Coord {
    x: usize,
    y: usize,
}

And the direction a beam is currently travelling in as Direction:

enum Direction {
    Up,
    Down,
    Left,
    Right,
}

Some skeleton-code I want to work towards:

pub fn part_1(input: &str) -> usize {
    let grid = parse(input);
    let start = Beam {
        pos: Coord { x: 0, y: 0 },
        dir: Direction::Right,
    };
    energized(start, &grid)
}

The main logic is in the energized helper.

It keeps track of a set of energized coordinates.
At the end, it returns how large that set is.

It starts by pushing a starting Beam onto a queue.

Then it pops a beam off that queue until it's empty.
For each beam, it determines the next positions and directions, and adds those to the queue.

To prevent infinite loops (the beams might get trapped in the cave, going around forever), I keep track of every instance of Beam I saw so far.
If I pop a beam off the stack I have already seen, I know I'm in a loop and can ignore that beam.

For every beam I pop off the queue, I determine the next direction(s) it will travel in:
Either 1 direction if it reflects or keeps going, or 2 directions if the beam gets split.

For each direction, I try to move the beam in that direction.
If it didn't go off the sides of the map, I add a beam with that new direction and updated position to the queue.

fn energized(start: Beam, grid: &[Vec<Tile>]) -> usize {
    let rows = grid.len();
    let cols = grid[0].len();

    let mut q = VecDeque::new();
    let mut energized = HashSet::new();
    let mut seen = HashSet::new();
    q.push_back(start);

    while let Some(mut beam) = q.pop_front() {
        if seen.contains(&beam) {
            continue;
        }
        energized.insert(beam.pos);
        seen.insert(beam);

        let dirs = match (grid[beam.pos.y][beam.pos.x], beam.dir) {
            (Tile::Empty, _)
            | (Tile::SplitHoriz, Direction::Left)
            | (Tile::SplitHoriz, Direction::Right)
            | (Tile::SplitVert, Direction::Up)
            | (Tile::SplitVert, Direction::Down) => vec![beam.dir],
            (Tile::SplitHoriz, _) => {
                vec![Direction::Left, Direction::Right]
            }
            (Tile::SplitVert, _) => {
                vec![Direction::Up, Direction::Down]
            }
            (Tile::MirrorForward, Direction::Up) | (Tile::MirrorBack, Direction::Down) => {
                vec![Direction::Right]
            }
            (Tile::MirrorForward, Direction::Down) | (Tile::MirrorBack, Direction::Up) => {
                vec![Direction::Left]
            }
            (Tile::MirrorForward, Direction::Left) | (Tile::MirrorBack, Direction::Right) => {
                vec![Direction::Down]
            }
            (Tile::MirrorForward, Direction::Right) | (Tile::MirrorBack, Direction::Left) => {
                vec![Direction::Up]
            }
        };
        for dir in dirs {
            beam.dir = dir;
            if let Some(beam) = beam.forward(rows, cols) {
                q.push_back(beam);
            }
        }
    }
    energized.len()
}

The forward helper that only returns a beam if it didn't go off the edges of the map:

impl Beam {
    fn forward(mut self, rows: usize, cols: usize) -> Option<Self> {
        match self.dir {
            Direction::Up if self.pos.y > 0 => self.pos.y -= 1,
            Direction::Down if self.pos.y < rows - 1 => self.pos.y += 1,
            Direction::Left if self.pos.x > 0 => self.pos.x -= 1,
            Direction::Right if self.pos.x < cols - 1 => self.pos.x += 1,
            _ => return None,
        }
        Some(self)
    }
}

Code

pub fn part_1(input: &str) -> usize {
    let grid = parse(input);
    let start = Beam {
        pos: Coord { x: 0, y: 0 },
        dir: Direction::Right,
    };
    energized(start, &grid)
}

Part 2

The beam can enter the cave from any position along the edges (heading directly away from that edge).

The question asks for the maximum amount of tiles that can be energized.

I brute forced this.
I looped through every possible starting configuration, calculated the amount of energized tiles, and took the maximum.

Code

    let grid = parse(input);
    let from_left = (0..grid.len()).map(|row| Beam {
        dir: Direction::Right,
        pos: Coord { x: 0, y: row },
    });
    let from_right = (0..grid.len()).map(|row| Beam {
        dir: Direction::Left,
        pos: Coord {
            x: grid[0].len() - 1,
            y: row,
        },
    });
    let from_up = (0..grid[0].len()).map(|col| Beam {
        dir: Direction::Down,
        pos: Coord { x: col, y: 0 },
    });
    let from_down = (0..grid[0].len()).map(|col| Beam {
        dir: Direction::Up,
        pos: Coord {
            x: col,
            y: grid.len() - 1,
        },
    });

    from_left
        .chain(from_right)
        .chain(from_up)
        .chain(from_down)
        .map(|start| energized(start, &grid))
        .max()
        .unwrap()

Final code

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

#[derive(Debug, PartialEq, Eq, PartialOrd, Ord, Clone, Copy, Hash)]
enum Direction {
    Up,
    Down,
    Left,
    Right,
}

#[derive(Debug, PartialEq, Eq, PartialOrd, Ord, Clone, Copy, Hash)]
struct Coord {
    x: usize,
    y: usize,
}

#[derive(Debug, PartialEq, Eq, PartialOrd, Ord, Clone, Copy, Hash)]
struct Beam {
    pos: Coord,
    dir: Direction,
}

impl Beam {
    fn forward(mut self, rows: usize, cols: usize) -> Option<Self> {
        match self.dir {
            Direction::Up if self.pos.y > 0 => self.pos.y -= 1,
            Direction::Down if self.pos.y < rows - 1 => self.pos.y += 1,
            Direction::Left if self.pos.x > 0 => self.pos.x -= 1,
            Direction::Right if self.pos.x < cols - 1 => self.pos.x += 1,
            _ => return None,
        }
        Some(self)
    }
}

#[derive(Debug, PartialEq, Eq, PartialOrd, Ord, Clone, Copy, Hash)]
enum Tile {
    Empty,
    SplitHoriz,
    SplitVert,
    MirrorForward,
    MirrorBack,
}

fn parse(s: &str) -> Vec<Vec<Tile>> {
    s.lines()
        .map(|line| {
            line.chars()
                .map(|c| match c {
                    '\\' => Tile::MirrorBack,
                    '/' => Tile::MirrorForward,
                    '.' => Tile::Empty,
                    '-' => Tile::SplitHoriz,
                    '|' => Tile::SplitVert,
                    _ => panic!("at the disco"),
                })
                .collect()
        })
        .collect()
}

fn energized(start: Beam, grid: &[Vec<Tile>]) -> usize {
    let rows = grid.len();
    let cols = grid[0].len();

    let mut q = VecDeque::new();
    let mut energized = HashSet::new();
    let mut seen = HashSet::new();
    q.push_back(start);

    while let Some(mut beam) = q.pop_front() {
        if seen.contains(&beam) {
            continue;
        }
        energized.insert(beam.pos);
        seen.insert(beam);

        let dirs = match (grid[beam.pos.y][beam.pos.x], beam.dir) {
            (Tile::Empty, _)
            | (Tile::SplitHoriz, Direction::Left)
            | (Tile::SplitHoriz, Direction::Right)
            | (Tile::SplitVert, Direction::Up)
            | (Tile::SplitVert, Direction::Down) => vec![beam.dir],
            (Tile::SplitHoriz, _) => {
                vec![Direction::Left, Direction::Right]
            }
            (Tile::SplitVert, _) => {
                vec![Direction::Up, Direction::Down]
            }
            (Tile::MirrorForward, Direction::Up) | (Tile::MirrorBack, Direction::Down) => {
                vec![Direction::Right]
            }
            (Tile::MirrorForward, Direction::Down) | (Tile::MirrorBack, Direction::Up) => {
                vec![Direction::Left]
            }
            (Tile::MirrorForward, Direction::Left) | (Tile::MirrorBack, Direction::Right) => {
                vec![Direction::Down]
            }
            (Tile::MirrorForward, Direction::Right) | (Tile::MirrorBack, Direction::Left) => {
                vec![Direction::Up]
            }
        };
        for dir in dirs {
            beam.dir = dir;
            if let Some(beam) = beam.forward(rows, cols) {
                q.push_back(beam);
            }
        }
    }
    energized.len()
}

pub fn part_1(input: &str) -> usize {
    let grid = parse(input);
    let start = Beam {
        pos: Coord { x: 0, y: 0 },
        dir: Direction::Right,
    };
    energized(start, &grid)
}

pub fn part_2(input: &str) -> usize {
    let grid = parse(input);
    let from_left = (0..grid.len()).map(|row| Beam {
        dir: Direction::Right,
        pos: Coord { x: 0, y: row },
    });
    let from_right = (0..grid.len()).map(|row| Beam {
        dir: Direction::Left,
        pos: Coord {
            x: grid[0].len() - 1,
            y: row,
        },
    });
    let from_up = (0..grid[0].len()).map(|col| Beam {
        dir: Direction::Down,
        pos: Coord { x: col, y: 0 },
    });
    let from_down = (0..grid[0].len()).map(|col| Beam {
        dir: Direction::Up,
        pos: Coord {
            x: col,
            y: grid.len() - 1,
        },
    });

    from_left
        .chain(from_right)
        .chain(from_up)
        .chain(from_down)
        .map(|start| energized(start, &grid))
        .max()
        .unwrap()
}

Advent of Code 2023 Day 15

Nicky Meuleman — Fri, 15 Dec 2023 16:43:27 +0000

Day 15: Lens Library

https://adventofcode.com/2023/day/15

You arrive at the facility the mirrors are pointing at.

Inside, some more calibration work is needed.

Today's input is a bunch of instructions.

An example input looks like this:

rn=1,cm-,qp=3,cm=2,qp-,pc=4,ot=9,ab=5,pc-,pc=6,ot=7

The line with instructions is separated by commas.

Part 1

A hashing algorithm turns every instruction into a number.

Determine the ASCII code for the current character of the string.
Increase the current value by the ASCII code you just determined.
Set the current value to itself multiplied by 17.
Set the current value to the remainder of dividing itself by 256.

The question asks for the sum of all instruction hashes.

Helpers

The hash function!

fn hash(s: &str) -> u32 {
    s.bytes().fold(0, |mut acc, byte| {
        acc += byte as u32;
        acc *= 17;
        acc % 256
    })
}

By using some properties of modular arithmetic, and the fact that a 8 bytes can store 256 decimal numbers (0 to 255).

// https://www.khanacademy.org/computing/computer-science/cryptography/modarithmetic/a/modular-addition-and-subtraction
// (A + B) mod C = (A mod C + B mod C) mod C
// https://www.khanacademy.org/computing/computer-science/cryptography/modarithmetic/a/modular-multiplication
// (A * B) mod C = (A mod C * B mod C) mod C
// combining those two rules:
// ((A + B) * C) mod D = (((A + B) mod D) * C) mod D
fn hash(s: &str) -> u8 {
    s.bytes()
        .fold(0, |acc, byte| acc.wrapping_add(byte).wrapping_mul(17))
}

Code

fn hash(s: &str) -> u8 {
    s.bytes()
        .fold(0, |acc, byte| acc.wrapping_add(byte).wrapping_mul(17))
}

pub fn part_1(input: &str) -> u32 {
    input.trim().split(',').map(|s| hash(s) as u32).sum()
}

Part 2

Now the question tells us what each instruction means.

Each instruction starts with a label (the letters).

The labels are for lenses.

There are 2 types of instruction:

An instruction ending in a minus - means "remove the lens with this label from its box".
An instructing with an equals sign = means "update the box with this lens"

To find the box for a label, apply the hashing function from part1 to it.
eg. The rn=1 instruction has a label of rn, hashing that gives 0.
So this instruction tells us to update box 0.

There are 256 boxes in total, this maps perfectly to what the hash function from part1 can return!

Now, the specifics of both instructions.

The remove instruction:
- If the label you are searching for is not inside its box, do nothing.
- If the label you are searching for is present, remove it and shift all other lenses forward.
The add instruction:
- If a lens with the label you are searching for is present, update its focal length (the number right of the = in the instruction).
- If a lens with the label you are searching for is not present, add the lens to the end of the box.

The question asks for the total focusing power after all instructions are applied.

The focusing power of a single lens is the result of multiplying together:

One plus the box number of the lens in question. (boxes start at 0!)
The slot number of the lens within the box: 1 for the first lens, 2 for the second lens, and so on. (slots start 1!)
The focal length of the lens.

Helpers

I represented each instruction as an enum.

enum Instruction<'a> {
    Remove(&'a str),
    Add(Lens<'a>),
}

A Lens here:

struct Lens<'a> {
    label: &'a str,
    focal: u8,
}

Again, don't mind the 'a stuff, those are Rust lifetimes that let me use the labels from the input.

Then I created a way to turn a piece of the input into a real Instruction.

impl<'a> Instruction<'a> {
    fn new(s: &'a str) -> Self {
        if let Some(label) = s.strip_suffix('-') {
            Self::Remove(label)
        } else {
            let (label, focal) = s.split_once('=').unwrap();
            let focal = focal.parse().unwrap();
            let lens = Lens { label, focal };
            Self::Add(lens)
        }
    }
}

I loop over the input, turn each instruction into an Instruction and apply it.

I represented the 256 boxes as an array.
Each box can hold several lenses, so each box is represented as a list itself.

For every instruction, I calculate the hash of its label.

Then I apply the instruction according to the rules described in the problem statement.

At the end, I loop through all boxes and calculate the sum of the focusing power.
The sum of all those sums is what the question is asking for.

Code

enum Instruction<'a> {
    Remove(&'a str),
    Add(Lens<'a>),
}

impl<'a> Instruction<'a> {
    fn new(s: &'a str) -> Self {
        if let Some(label) = s.strip_suffix('-') {
            Self::Remove(label)
        } else {
            let (label, focal) = s.split_once('=').unwrap();
            let focal = focal.parse().unwrap();
            let lens = Lens { label, focal };
            Self::Add(lens)
        }
    }
}

struct Lens<'a> {
    label: &'a str,
    focal: u8,
}

fn hash(s: &str) -> u8 {
    s.bytes()
        .fold(0, |acc, byte| acc.wrapping_add(byte).wrapping_mul(17))
}

pub fn part_2(input: &str) -> usize {
    const BOX: Vec<Lens> = Vec::new();
    let mut boxes = [BOX; 256];

    for instr in input.trim_end().split(',').map(Instruction::new) {
        match instr {
            Instruction::Remove(label) => {
                let hash = hash(label);
                boxes[hash as usize].retain(|item| item.label != label);
            }
            Instruction::Add(lens) => {
                let hash = hash(lens.label);
                let lenses = &mut boxes[hash as usize];
                if let Some(old) = lenses.iter_mut().find(|item| lens.label == item.label) {
                    // update focal length of lens with this label
                    old.focal = lens.focal;
                } else {
                    // add lens to end of box
                    lenses.push(lens);
                }
            }
        }
    }

    boxes
        .into_iter()
        .enumerate()
        .map(|(box_idx, lenses)| {
            let box_focusing_power: usize = lenses
                .into_iter()
                .enumerate()
                .map(|(lens_idx, lens)| (box_idx + 1) * (lens_idx + 1) * lens.focal as usize)
                .sum();
            box_focusing_power
        })
        .sum()
}

Final code

enum Instruction<'a> {
    Remove(&'a str),
    Add(Lens<'a>),
}

impl<'a> Instruction<'a> {
    fn new(s: &'a str) -> Self {
        if let Some(label) = s.strip_suffix('-') {
            Self::Remove(label)
        } else {
            let (label, focal) = s.split_once('=').unwrap();
            let focal = focal.parse().unwrap();
            let lens = Lens { label, focal };
            Self::Add(lens)
        }
    }
}
struct Lens<'a> {
    label: &'a str,
    focal: u8,
}

fn hash(s: &str) -> u8 {
    s.bytes()
        .fold(0, |acc, byte| acc.wrapping_add(byte).wrapping_mul(17))
}

pub fn part_1(input: &str) -> u32 {
    input.trim().split(',').map(|s| hash(s) as u32).sum()
}

pub fn part_2(input: &str) -> usize {
    const BOX: Vec<Lens> = Vec::new();
    let mut boxes = [BOX; 256];

    for instr in input.trim_end().split(',').map(Instruction::new) {
        match instr {
            Instruction::Remove(label) => {
                let hash = hash(label);
                boxes[hash as usize].retain(|item| item.label != label);
            }
            Instruction::Add(lens) => {
                let hash = hash(lens.label);
                let lenses = &mut boxes[hash as usize];
                if let Some(old) = lenses.iter_mut().find(|item| lens.label == item.label) {
                    // update focal length of lens with this label
                    old.focal = lens.focal;
                } else {
                    // add lens to end of box
                    lenses.push(lens);
                }
            }
        }
    }

    boxes
        .into_iter()
        .enumerate()
        .map(|(box_idx, lenses)| {
            let box_focusing_power: usize = lenses
                .into_iter()
                .enumerate()
                .map(|(lens_idx, lens)| (box_idx + 1) * (lens_idx + 1) * lens.focal as usize)
                .sum();
            box_focusing_power
        })
        .sum()
}

Advent of Code 2023 Day 14

Nicky Meuleman — Thu, 14 Dec 2023 21:30:51 +0000

Day 14: Parabolic Reflector Dish

https://adventofcode.com/2023/day/14

Turns out the mirrors from yesterday are used to power a concentrated solar mirror thingamajig.
The mirrors are not calibrated correctly, that must be why the lava isn't being made.

It being an advent of code elven mirror, it's calibrated in the most convoluted way possible.

It uses a bunch of rocks to put pressure on the mirrors.

Today's input is the arrangement of the calibration device (so, plane with a bunch of rocks on it).

An example input looks like this:

O....#....
O.OO#....#
.....##...
OO.#O....O
.O.....O#.
O.#..O.#.#
..O..#O..O
.......O..
#....###..
#OO..#....

O is a round rock
# is a square rock
. is empty space

You can tilt the calibration device.

The round rocks roll, the square rocks stay put.

Parsing

An enum to keep track of what a tile holds:

enum Tile {
    Round,
    Square,
    Empty,
}

A function to parse the input into a 2D list of Tile:

fn parse(input: &str) -> Vec<Vec<Tile>> {
    input
        .lines()
        .map(|line| {
            line.chars()
                .map(|c| match c {
                    '.' => Tile::Empty,
                    '#' => Tile::Square,
                    'O' => Tile::Round,
                    _ => panic!("at the disco"),
                })
                .collect()
        })
        .collect()
}

Part 1

The question asks how much total load would be on the north support beams after sliding the rocks north.

The load is determined by the location of the rounded rocks.

Each rounded rock contributes a load equal to the number of rows from the rock to the south edge of the platform, including the row the rock is on.

Helpers

A function that slides all round rocks to the north:

fn slide_north(grid: &mut Vec<Vec<Tile>>) {
    for col in 0..grid[0].len() {
        let mut empty_or_round_row = 0;
        for row in 0..grid.len() {
            let curr = grid[row][col];
            match curr {
                Tile::Square => empty_or_round_row = row + 1,
                Tile::Round => {
                    // swap the current tile with the empty_or_round one
                    let replace_with = std::mem::replace(&mut grid[empty_or_round_row][col], curr);
                    let _ = std::mem::replace(&mut grid[row][col], replace_with);
                    empty_or_round_row += 1;
                }
                Tile::Empty => (),
            }
        }
    }
}

A function that calculated the total weight of a grid:

fn weight(grid: &Vec<Vec<Tile>>) -> usize {
    grid.iter()
        .rev()
        .enumerate()
        .map(|(i, row)| {
            let round_rocks = row.iter().filter(|tile| **tile == Tile::Round).count();
            round_rocks * (i + 1)
        })
        .sum()
}

Combining these helpers makes the final code for part1 very short.

Code

pub fn part_1(input: &str) -> usize {
    let mut grid = parse(input);
    slide_north(&mut grid);
    weight(&grid)
}

Part 2

The platform has a "spin cycle" button.

It slides the rocks: north, the west, then south, then east.

If you do that enough times, the mirrors will surely be calibrated.

The question asks what the total load is after 1000000000 cycles.

So, Advent of Code, huge number of cycles, that must mean a cycle detection problem.

First, I'll code enough to try this problem brute-force, but I'm not getting my hopes up.

Helpers

First, a function that applies a full cycle to a grid (tilting north, west, south, east).

Tilting north, west, south, east means tilting in a counterclockwise pattern.

That's the same as:

Tilt north
Turn grid clockwise
Tilt north
Turn grid clockwise
Tilt north
Turn grid clockwise
Tilt north
Turn grid clockwise

fn cycle(mut grid: Vec<Vec<Tile>>) -> Vec<Vec<Tile>> {
    for _ in 0..4 {
        slide_north(&mut grid);
        let rotated = clockwise(&grid);
        grid = rotated;
    }
    grid
}

So the next helper is the one that turns a grid clockwise.
To do that, change every (x, y) coordinate to an (y, -x) coordinate.

// rotate 90 degrees clockwise: (x, y) -> (y, -x)
fn clockwise(grid: &Vec<Vec<Tile>>) -> Vec<Vec<Tile>> {
    let size = grid.len();
    let mut rotated = vec![vec![Tile::Empty; size]; size];
    for row in 0..size {
        for col in 0..size {
            rotated[col][size - 1 - row] = grid[row][col];
        }
    }
    rotated
}

As I suspected, brute-forcing is a no-go.
Time to put on the cycle-detecting hat! (It's a regular hat, my ears are cold.)

I keep track of every grid pattern I saw so far.
Each time I cycle the grid, I check if the new pattern exists in that list.

If the pattern appeared before, I hit the start of a new cycle.
The length of a cycle is the total length of the list - the index where the repeat happened.

Using that length, figure out the index of the pattern the entire loop will end on.

Code

pub fn part_2(input: &str) -> usize {
    let mut grid = parse(input);
    let mut seen = vec![grid.clone()];

    loop {
        grid = cycle(grid);
        // check if the cycled map has already been seen
        if let Some(idx) = seen.iter().position(|x| x == &grid) {
            // figure out length of cycle (watch out: a cycle might only start after a number of steps)
            let cycle_len = seen.len() - idx;
            // use cycle length to figure out the index of the final step in the seen list
            let final_idx = idx + (1_000_000_000 - idx) % cycle_len;
            return weight(&seen[final_idx]);
        }
        seen.push(grid.clone());
    }
}

Final code

#[derive(Debug, Clone, Copy, PartialEq)]
enum Tile {
    Round,
    Square,
    Empty,
}

fn parse(input: &str) -> Vec<Vec<Tile>> {
    input
        .lines()
        .map(|line| {
            line.chars()
                .map(|c| match c {
                    '.' => Tile::Empty,
                    '#' => Tile::Square,
                    'O' => Tile::Round,
                    _ => panic!("at the disco"),
                })
                .collect()
        })
        .collect()
}

fn slide_north(grid: &mut Vec<Vec<Tile>>) {
    for col in 0..grid[0].len() {
        let mut empty_or_round_row = 0;
        for row in 0..grid.len() {
            let curr = grid[row][col];
            match curr {
                Tile::Square => empty_or_round_row = row + 1,
                Tile::Round => {
                    // swap the current tile with the empty_or_round one
                    let replace_with = std::mem::replace(&mut grid[empty_or_round_row][col], curr);
                    let _ = std::mem::replace(&mut grid[row][col], replace_with);
                    empty_or_round_row += 1;
                }
                Tile::Empty => (),
            }
        }
    }
}

fn weight(grid: &Vec<Vec<Tile>>) -> usize {
    grid.iter()
        .rev()
        .enumerate()
        .map(|(i, row)| {
            let round_rocks = row.iter().filter(|tile| **tile == Tile::Round).count();
            round_rocks * (i + 1)
        })
        .sum()
}

// rotate 90 degrees clockwise: (x, y) -> (y, -x)
fn clockwise(grid: &Vec<Vec<Tile>>) -> Vec<Vec<Tile>> {
    let size = grid.len();
    let mut rotated = vec![vec![Tile::Empty; size]; size];
    for row in 0..size {
        for col in 0..size {
            rotated[col][size - 1 - row] = grid[row][col];
        }
    }
    rotated
}

fn cycle(mut grid: Vec<Vec<Tile>>) -> Vec<Vec<Tile>> {
    for _ in 0..4 {
        slide_north(&mut grid);
        let rotated = clockwise(&grid);
        grid = rotated;
    }
    grid
}

pub fn part_1(input: &str) -> usize {
    let mut grid = parse(input);
    slide_north(&mut grid);
    weight(&grid)
}

pub fn part_2(input: &str) -> usize {
    let mut grid = parse(input);
    let mut seen = vec![grid.clone()];

    loop {
        grid = cycle(grid);
        // check if the cycled map has already been seen
        if let Some(idx) = seen.iter().position(|x| x == &grid) {
            // figure out length of cycle (watch out: a cycle might only start after a number of steps)
            let cycle_len = seen.len() - idx;
            // use cycle length to figure out the index of the final step in the seen list
            let final_idx = idx + (1_000_000_000 - idx) % cycle_len;
            return weight(&seen[final_idx]);
        }
        seen.push(grid.clone());
    }
}

Advent of Code 2023 Day 13

Nicky Meuleman — Thu, 14 Dec 2023 21:29:10 +0000

Day 13: Point of Incidence

https://adventofcode.com/2023/day/13

You arrive at Lava Island.
There is a distinct lack of lava for an island named "Lava Island".

The place you arrived at is full of mirrors.
It's hard to see where they are -because of their mirrorness, you see-.

Your input today are several patterns of what you see as you walk.

An example input looks like this:

#.##..##.
..#.##.#.
##......#
##......#
..#.##.#.
..##..##.
#.#.##.#.

#...##..#
#....#..#
..##..###
#####.##.
#####.##.
..##..###
#....#..#

# are tiles of ash
. are tiles of rocks

By analyzing the patterns, you can figure out where the mirrors are.

Parsing

An enum to keep track of what a tile holds:

enum Tile {
    Ash,
    Rock,
}

Because that enum has 2 variants, I assume many people chose booleans for this, or even flipping on/off bits in a list of numbers (or even better, one number!).

The input represents a list of 2D grids:

fn parse(input: &str) -> Vec<VecDeque<Vec<Tile>>> {
    input
        .split("\n\n")
        .map(|block| {
            block
                .lines()
                .map(|line| {
                    line.chars()
                        .map(|c| match c {
                            '.' => Tile::Ash,
                            '#' => Tile::Rock,
                            _ => panic!("at the disco"),
                        })
                        .collect()
                })
                .collect()
        })
        .collect()
}

I chose to represent rows as a VecDeque as opposed to a Vec, more on why later.

Non Rustacean friends reading this: basically, it's a list you can reverse.
Chances are you don't even have to think about this in a language like Python or JavaScript.

Part 1

To find the reflection in each pattern, you need to find a perfect reflection across either a horizontal line between two rows or across a vertical line between two columns.

A reflection line does not have to be perfectly in the middle.
If one half of the reflection is larger than the other half (in other words: it has nowhere to reflect onto), those extra lines can be ignored.

In the example, the first pattern has a vertical reflection line between column 5 and 6:

123456789
    ><   
#.##..##.
..#.##.#.
##......#
##......#
..#.##.#.
..##..##.
#.#.##.#.
    ><   
123456789

Each pattern has a numerical value, to find it:

If the pattern has a vertical reflection:

the number of columns to the left of that line

If the pattern has a horizontal reflection:

the number of rows above that line multiplied by 100

The question asks for the sum of all number values for a pattern.

So, some skeleton code that uses the parsing logic above:

let grid = parse(input);
grid.iter()
    .map(/* get number for each pattern */)
    .sum()

Helpers

I use a helper that returns the offset a 2D grid reflects at horizontally.

A grid is not guaranteed to have a reflection point, so I express that as an Option<usize>.
Either it has a reflection line, and I return its offset, or it doesn't reflect, and I return nothing.

This finds the first offset where a grid is perfectly mirrorred.

First, I divide the grid into 2 halves.
Then I check if those two halves are identical, making sure to take into account the length of the smallest half.

This helper is also why I chose a VecDeque earlier, I reverse the first half, so I can easier compare the two halves.
A normal Vec wouldn't let me do that.

fn reflects_at(grid: &VecDeque<Vec<Tile>>) -> Option<usize> {
    (1..grid.len()).find(|&offset| {
        let half1 = grid.iter().take(offset).rev();
        let half2 = grid.iter().skip(offset);
        let mut combined = half1.zip(half2); // the shortest half determines how long this is!
        combined.all(|(row1, row2)| row1 == row2)
    })
}

So, if I pass a regular grid into this, I get the row offset it reflects at.
To check which offset it reflects at vertically, I pass a 2D grid of columns into that same function.

Now, for each pattern I can check if it has a vertical mirrorring point.
If it doesn't, I transform the grid of rows into a grid of columns and do the check again.

Code

se std::collections::VecDeque;

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
enum Tile {
    Ash,
    Rock,
}

// parse input to a list of 2D grids
fn parse(input: &str) -> Vec<VecDeque<Vec<Tile>>> {
    input
        .split("\n\n")
        .map(|block| {
            block
                .lines()
                .map(|line| {
                    line.chars()
                        .map(|c| match c {
                            '.' => Tile::Ash,
                            '#' => Tile::Rock,
                            _ => panic!("at the disco"),
                        })
                        .collect()
                })
                .collect()
        })
        .collect()
}

fn reflects_at(grid: &VecDeque<Vec<Tile>>) -> Option<usize> {
    (1..grid.len()).find(|&offset| {
        let half1 = grid.iter().take(offset).rev();
        let half2 = grid.iter().skip(offset);
        let mut combined = half1.zip(half2); // the shortest half determines how long this is!
        combined.all(|(row1, row2)| row1 == row2)
    })
}

pub fn part_1(input: &str) -> usize {
    let grid = parse(input);
    grid.iter()
        .map(|grid| {
            // check horizontal
            if let Some(i) = reflects_at(grid) {
                return i * 100;
            }

            // check vertical
            let cols = (0..grid[0].len())
                .map(|i| grid.iter().map(|row| row[i]).collect())
                .collect();
            if let Some(i) = reflects_at(&cols) {
                return i;
            }

            // no reflection found
            0
        })
        .sum()
}

Part 2

Each mirror has one smudge.
Exactly one # or # should be the opposite type.

Helpers

The reflects_at helper changes a bit.

Instead of checking for a perfect mirrorring, I now check for exactly 1 different tile in the two halves.

I count how many differences a potential mirror has, that amount should be exactly 1.

fn reflects_at(grid: &VecDeque<Vec<Tile>>) -> Option<usize> {
    (1..grid.len()).find(|&offset| {
        let half1 = grid.iter().take(offset).rev();
        let half2 = grid.iter().skip(offset);
        let combined = half1.zip(half2); // the shortest half determines how long this is!
        let differences: usize = combined
            .map(|(row1, row2)| row1.iter().zip(row2.iter()).filter(|(a, b)| a != b).count())
            .sum();

        differences == 1
    })
}

Code

use std::collections::VecDeque;

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
enum Tile {
    Ash,
    Rock,
}

fn parse(input: &str) -> Vec<VecDeque<Vec<Tile>>> {
    input
        .split("\n\n")
        .map(|block| {
            block
                .lines()
                .map(|line| {
                    line.chars()
                        .map(|c| match c {
                            '.' => Tile::Ash,
                            '#' => Tile::Rock,
                            _ => panic!("at the disco"),
                        })
                        .collect()
                })
                .collect()
        })
        .collect()
}

fn reflects_at(grid: &VecDeque<Vec<Tile>>) -> Option<usize> {
    (1..grid.len()).find(|&offset| {
        let half1 = grid.iter().take(offset).rev();
        let half2 = grid.iter().skip(offset);
        let combined = half1.zip(half2); // the shortest half determines how long this is!
        let differences: usize = combined
            .map(|(row1, row2)| row1.iter().zip(row2.iter()).filter(|(a, b)| a != b).count())
            .sum();

        differences == 1
    })
}

pub fn part_2(input: &str) -> usize {
    let grid = parse(input);
    grid.iter()
        .map(|grid| {
            // check horizontal
            if let Some(i) = reflects_at(grid) {
                return i * 100;
            }

            // check vertical
            let cols = (0..grid[0].len())
                .map(|i| grid.iter().map(|row| row[i]).collect())
                .collect();
            if let Some(i) = reflects_at(&cols) {
                return i;
            }

            // no reflection found
            0
        })
        .sum()
}

The differences between part1 and part2 are minor, so I made that helper function take a variable amount of smudges.

Final code

use std::collections::VecDeque;

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
enum Tile {
    Ash,
    Rock,
}

// parse input to a list of 2D grids
fn parse(input: &str) -> Vec<VecDeque<Vec<Tile>>> {
    input
        .split("\n\n")
        .map(|block| {
            block
                .lines()
                .map(|line| {
                    line.chars()
                        .map(|c| match c {
                            '.' => Tile::Ash,
                            '#' => Tile::Rock,
                            _ => panic!("at the disco"),
                        })
                        .collect()
                })
                .collect()
        })
        .collect()
}

fn reflects_at(grid: &VecDeque<Vec<Tile>>, smudges: usize) -> Option<usize> {
    (1..grid.len()).find(|&offset| {
        let half1 = grid.iter().take(offset).rev();
        let half2 = grid.iter().skip(offset);
        let combined = half1.zip(half2); // the shortest half determines how long this is!
        let found_smudges: usize = combined
            .map(|(row1, row2)| row1.iter().zip(row2.iter()).filter(|(a, b)| a != b).count())
            .sum();

        found_smudges == smudges
    })
}

pub fn part_1(input: &str) -> usize {
    let grid = parse(input);
    grid.iter()
        .map(|grid| {
            // check horizontal
            if let Some(i) = reflects_at(grid, 0) {
                return i * 100;
            }

            // check vertical
            let cols = (0..grid[0].len())
                .map(|i| grid.iter().map(|row| row[i]).collect())
                .collect();
            if let Some(i) = reflects_at(&cols, 0) {
                return i;
            }

            // no reflection found
            0
        })
        .sum()
}

pub fn part_2(input: &str) -> usize {
    let grid = parse(input);
    grid.iter()
        .map(|grid| {
            // check horizontal
            if let Some(i) = reflects_at(grid, 1) {
                return i * 100;
            }

            // check vertical
            let cols = (0..grid[0].len())
                .map(|i| grid.iter().map(|row| row[i]).collect())
                .collect();
            if let Some(i) = reflects_at(&cols, 1) {
                return i;
            }

            // no reflection found
            0
        })
        .sum()
}

Advent of Code 2023 Day 12

Nicky Meuleman — Thu, 14 Dec 2023 21:27:18 +0000

Day 12: Hot Springs

https://adventofcode.com/2023/day/12

You arrive at the hot springs.

They're regular springs now, because they're not so hot -a characteristic that is quite important for hot springs-.
It's because the lava stopped flowing, you should go take a look why.

You should be able to find a spring that is springy enough to launch you up to the place lava comes from here.

But they have fallen into disrepair, many of them are damaged.
You get a map of the hotsprings condition, per hotspring it lists if it is;

# damaged
. operational

The map itself is also damaged, causing a bunch of hot springs to have an unknown condition:

? unknown

Luckily, the elf with you helps you with a different format that lists the size of contiguous groups of damaged springs for every line.

This list always accounts for every damaged spring.
Each number is the entire size of its contiguous group (that is, groups are always separated by at least one operational spring: #### would always be 4, never 2,2).

An example of an undamaged input would look like this:

#.#.### 1,1,3
.#...#....###. 1,1,3
.#.###.#.###### 1,3,1,6
####.#...#... 4,1,1
#....######..#####. 1,6,5
.###.##....# 3,2,1

An example of the real, damaged input looks like this:

???.### 1,1,3
.??..??...?##. 1,1,3
?#?#?#?#?#?#?#? 1,3,1,6
????.#...#... 4,1,1
????.######..#####. 1,6,5
?###???????? 3,2,1

Parsing

I represented every record as a struct with a list of springs and a list of counts:

struct Record {
    springs: Vec<Spring>,
    counts: Vec<usize>,
}

I represented each spring as an enum variant:

enum Spring {
    Unknown,
    Damaged,
    Operational,
}

The parsing function returns a list of Records:

fn parse(input: &str) -> impl Iterator<Item = Record> + '_ {
    input.lines().map(|line| {
        let (springs, counts) = line.split_once(' ').unwrap();
        let springs = springs
            .chars()
            .map(|c| match c {
                '.' => Spring::Operational,
                '#' => Spring::Damaged,
                '?' => Spring::Unknown,
                _ => panic!("at the disco"),
            })
            .collect();
        let counts = counts.split(',').map(|s| s.parse().unwrap()).collect();

        Record { springs, counts }
    })
}

Part 1

It is your job to figure out how many different arrangements of operational and broken springs fit the given criteria in each row.

The question asks for the sum of valid arrangements for each line in your input.

some skeleton/pseudo-code:

parse(input).map(/* turn record into a count of valid arrangements */).sum()

Helpers

To check the amount of valid arrangements for a record, I used recursion.

If the argument to the function (a record) has an unknown spring in its list of springs, I replace it:

As a damaged spring
As an operational spring

For those 2 options, I calculate the amount of valid arrangements and sum them.

If the argument to the function (a record) has NO unknown springs in its list of springs, I check its validity.
If it's valid, it has 1 valid arrangement (because there are no unknown springs left), if it's invalid, it has 0.

impl Record {
    fn valid_arrangements(&self) -> usize {
        if let Some(index) = self
            .springs
            .iter()
            .position(|spring| *spring == Spring::Unknown)
        {
            // treat unknown spring as damaged
            let mut as_damaged_spring = self.springs.clone();
            as_damaged_spring[index] = Spring::Damaged;
            let as_damaged = Record {
                springs: as_damaged_spring,
                counts: self.counts.to_vec(),
            };

            // treat unknown spring as operational
            let mut as_operational_spring = self.springs.clone();
            as_operational_spring[index] = Spring::Operational;
            let as_operational = Record {
                springs: as_operational_spring,
                counts: self.counts.to_vec(),
            };

            as_damaged.valid_arrangements() + as_operational.valid_arrangements()
        } else {
            if self.is_valid() {
                1
            } else {
                0
            }
        }
    }
}

This helper checks if an arrangement of springs (one with no unknown springs in it) is valid by calculating the list of counts that arrangement would have.
If the calculated counts match the given counts completely, it was a valid arrangement.

impl Record {
    fn is_valid(&self) -> bool {
        self.springs
            .iter()
            .group_by(|item| *item)
            .into_iter()
            .filter_map(|(key, group)| {
                if *key == Spring::Damaged {
                    Some(group.count())
                } else {
                    None
                }
            })
            .eq(self.counts.iter().copied())
    }
}

Putting it all together, the pseudocode works perfectly.

Code

use itertools::Itertools;

#[derive(Debug, PartialEq, Eq, Clone, Copy)]
enum Spring {
    Unknown,
    Damaged,
    Operational,
}

struct Record {
    springs: Vec<Spring>,
    counts: Vec<usize>,
}

impl Record {
    fn is_valid(&self) -> bool {
        self.springs
            .iter()
            .group_by(|item| *item)
            .into_iter()
            .filter_map(|(key, group)| {
                if *key == Spring::Damaged {
                    Some(group.count())
                } else {
                    None
                }
            })
            .eq(self.counts.iter().copied())
    }

    fn valid_arrangements(&self) -> usize {
        if let Some(index) = self
            .springs
            .iter()
            .position(|spring| *spring == Spring::Unknown)
        {
            // treat unknown spring as damaged
            let mut as_damaged_spring = self.springs.clone();
            as_damaged_spring[index] = Spring::Damaged;
            let as_damaged = Record {
                springs: as_damaged_spring,
                counts: self.counts.to_vec(),
            };

            // treat unknown spring as operational
            let mut as_operational_spring = self.springs.clone();
            as_operational_spring[index] = Spring::Operational;
            let as_operational = Record {
                springs: as_operational_spring,
                counts: self.counts.to_vec(),
            };

            as_damaged.valid_arrangements() + as_operational.valid_arrangements()
        } else {
            if self.is_valid() {
                1
            } else {
                0
            }
        }
    }
}

fn parse(input: &str) -> impl Iterator<Item = Record> + '_ {
    input.lines().map(|line| {
        let (springs, counts) = line.split_once(' ').unwrap();
        let springs = springs
            .chars()
            .map(|c| match c {
                '.' => Spring::Operational,
                '#' => Spring::Damaged,
                '?' => Spring::Unknown,
                _ => panic!("at the disco"),
            })
            .collect();
        let counts = counts.split(',').map(|s| s.parse().unwrap()).collect();

        Record { springs, counts }
    })
}

pub fn part_1(input: &str) -> usize {
    parse(input).map(|record| record.valid_arrangements()).sum()
}

Part 2

Turns out you were holding it wrong.

The map was folded up, it is much larger.

To unfold the records, on each row, replace the list of spring conditions with five copies of itself (separated by ?) and replace the list of contiguous groups of damaged springs with five copies of itself (separated by ,).

So, this row:

.# 1
Would become:
.#?.#?.#?.#?.# 1,1,1,1,1

The first line of the above example would become:
???.###????.###????.###????.###????.### 1,1,3,1,1,3,1,1,3,1,1,3,1,1,3

This makes the runtime of the code above too large to complete in a reasonable time.
I tried doing what's called a pro gamer move and throw some memoization on it,
but alas,
I couldn't get it to work before I had to do other stuff.

I fiddled a bit with some code from GitHub user crazytieguy.
It completes much, much faster.

The part that was nearly identical, was the unfolding of the map:

parse(input)
    .map(|(mut springs, mut counts)| {
        springs = springs
            .iter()
            .copied()
            .chain([Spring::Unknown])
            .cycle()
            .take(springs.len() * 5 + 4)
            .collect();
        counts = counts
            .iter()
            .copied()
            .cycle()
            .take(counts.len() * 5)
            .collect();

        (springs, counts)
    })

Here it is with some minor changes.

Code

#[derive(Debug, PartialEq, Eq, Clone, Copy, Hash)]
enum Spring {
    Unknown,
    Damaged,
    Operational,
}

fn parse(input: &str) -> impl Iterator<Item = (Vec<Spring>, Vec<usize>)> + '_ {
    input.lines().map(|line| {
        let (springs, counts) = line.split_once(' ').unwrap();
        let springs: Vec<Spring> = springs
            .chars()
            .map(|c| match c {
                '.' => Spring::Operational,
                '#' => Spring::Damaged,
                '?' => Spring::Unknown,
                _ => panic!("at the disco"),
            })
            .collect();
        let counts: Vec<usize> = counts.split(',').filter_map(|s| s.parse().ok()).collect();

        (springs, counts)
    })
}

fn count_possible_arangements(mut springs: Vec<Spring>, counts: Vec<usize>) -> u64 {
    // to make the Damaged recursion case simpler
    springs.push(Spring::Operational);
    let mut cache = vec![vec![None; springs.len()]; counts.len()];
    count_possible_arangements_inner(&springs, &counts, &mut cache)
}

fn count_possible_arangements_inner(
    springs: &[Spring],
    counts: &[usize],
    cache: &mut [Vec<Option<u64>>],
) -> u64 {
    if counts.is_empty() {
        return if springs.contains(&Spring::Damaged) {
            // Too many previous unknowns were counted as damaged
            0
        } else {
            // All remaining unknowns are operational
            1
        };
    }
    if springs.len() < counts.iter().sum::<usize>() + counts.len() {
        // Not enough space for remaining numbers
        return 0;
    }
    if let Some(cached) = cache[counts.len() - 1][springs.len() - 1] {
        return cached;
    }
    let mut arangements = 0;
    if springs[0] != Spring::Damaged {
        // Assume operational
        arangements += count_possible_arangements_inner(&springs[1..], counts, cache);
    }
    let next_group_size = counts[0];
    if !springs[..next_group_size].contains(&Spring::Operational)
        && springs[next_group_size] != Spring::Damaged
    {
        // Assume damaged
        arangements +=
            count_possible_arangements_inner(&springs[next_group_size + 1..], &counts[1..], cache);
    }
    cache[counts.len() - 1][springs.len() - 1] = Some(arangements);
    arangements
}

pub fn part_2(input: &str) -> u64 {
    parse(input)
        .map(|(mut springs, mut counts)| {
            springs = springs
                .iter()
                .copied()
                .chain([Spring::Unknown])
                .cycle()
                .take(springs.len() * 5 + 4)
                .collect();
            counts = counts
                .iter()
                .copied()
                .cycle()
                .take(counts.len() * 5)
                .collect();

            count_possible_arangements(springs, counts)
        })
        .sum()
}

Final code

#[derive(Debug, PartialEq, Eq, Clone, Copy, Hash)]
enum Spring {
    Unknown,
    Damaged,
    Operational,
}

fn parse(input: &str) -> impl Iterator<Item = (Vec<Spring>, Vec<usize>)> + '_ {
    input.lines().map(|line| {
        let (springs, counts) = line.split_once(' ').unwrap();
        let springs: Vec<Spring> = springs
            .chars()
            .map(|c| match c {
                '.' => Spring::Operational,
                '#' => Spring::Damaged,
                '?' => Spring::Unknown,
                _ => panic!("at the disco"),
            })
            .collect();
        let counts: Vec<usize> = counts.split(',').filter_map(|s| s.parse().ok()).collect();

        (springs, counts)
    })
}

pub fn part_1(input: &str) -> u64 {
    parse(input)
        .map(|(springs, counts)| count_possible_arangements(springs, counts))
        .sum()
}

pub fn part_2(input: &str) -> u64 {
    parse(input)
        .map(|(mut springs, mut counts)| {
            springs = springs
                .iter()
                .copied()
                .chain([Spring::Unknown])
                .cycle()
                .take(springs.len() * 5 + 4)
                .collect();
            counts = counts
                .iter()
                .copied()
                .cycle()
                .take(counts.len() * 5)
                .collect();

            count_possible_arangements(springs, counts)
        })
        .sum()
}

fn count_possible_arangements(mut springs: Vec<Spring>, counts: Vec<usize>) -> u64 {
    // to make the Damaged recursion case simpler
    springs.push(Spring::Operational);
    let mut cache = vec![vec![None; springs.len()]; counts.len()];
    count_possible_arangements_inner(&springs, &counts, &mut cache)
}

fn count_possible_arangements_inner(
    springs: &[Spring],
    counts: &[usize],
    cache: &mut [Vec<Option<u64>>],
) -> u64 {
    if counts.is_empty() {
        return if springs.contains(&Spring::Damaged) {
            // Too many previous unknowns were counted as damaged
            0
        } else {
            // All remaining unknowns are operational
            1
        };
    }
    if springs.len() < counts.iter().sum::<usize>() + counts.len() {
        // Not enough space for remaining numbers
        return 0;
    }
    if let Some(cached) = cache[counts.len() - 1][springs.len() - 1] {
        return cached;
    }
    let mut arangements = 0;
    if springs[0] != Spring::Damaged {
        // Assume operational
        arangements += count_possible_arangements_inner(&springs[1..], counts, cache);
    }
    let next_group_size = counts[0];
    if !springs[..next_group_size].contains(&Spring::Operational)
        && springs[next_group_size] != Spring::Damaged
    {
        // Assume damaged
        arangements +=
            count_possible_arangements_inner(&springs[next_group_size + 1..], &counts[1..], cache);
    }
    cache[counts.len() - 1][springs.len() - 1] = Some(arangements);
    arangements
}

Advent of Code 2023 Day 11

Nicky Meuleman — Thu, 14 Dec 2023 21:25:13 +0000

Day 11: Cosmic Expansion

https://adventofcode.com/2023/day/11

You meet a researcher studying space.
You want to help with today's analysis.

It's a 2D map of space.

An example input looks like this:

...#......
.......#..
#.........
..........
......#...
.#........
.........#
..........
.......#..
#...#.....

a # represents a galaxy
a . represents empty space

Parsing

I represented every point in the grid as a Tile and stored them in a 2D list.

enum Tile {
    Galaxy,
    Empty,
}

fn parse(input: &str) -> Vec<Vec<Tile>> {
    input
        .lines()
        .map(|line| {
            line.chars()
                .map(|c| match c {
                    '.' => Tile::Empty,
                    '#' => Tile::Galaxy,
                    _ => panic!("at the disco"),
                })
                .collect()
        })
        .collect()
}

Part 1

The researcher is trying to figure out the sum of the lengths of the shortest path between every pair of galaxies.

But because the universe is expanding, the readings are out of date.

Because of ✨✨reasons✨✨ only some space expands.

Any rows or columns that contain no galaxies should all actually be twice as big.

The question asks for the sum of all distances between each pair galaxies.

some skeleton/pseudo-code:

let grid = parse(input);
let galaxies = galaxy_coordinates(&grid);

galaxies
    .iter()
    .combinations(2)
    .map(/* distance between those 2 galaxies */)
    .sum()

Helpers

I represent each point as a Coord

struct Coord {
    row: usize,
    col: usize,
}

Because it's a 2D list, the distance between 2 points can be calculated with the Manhattan distance.

impl Coord {
    fn manhattan_dist(&self, other: &Self) -> usize {
        self.row.abs_diff(other.row) + self.col.abs_diff(other.col)
    }
}

Next is the helper that turns the 2D grid into a list of Coord of galaxies.
Because of that expansion rule, I can't loop over the original grid and use those coordinates, so I keep track of them manually.

Each time I come across an empty row or column, I increment the corresponding coordinate appropriately.
If I come across a galaxy during my loop, I add the current coordinates to a list.

fn galaxy_coordinates(grid: &[Vec<Tile>]) -> Vec<Coord> {
    let empty_rows = empty_rows(&grid);
    let empty_cols = empty_cols(&grid);

    let mut galaxies = Vec::new();
    let mut curr_row = 0;
    let mut curr_col = 0;

    for (row_idx, row) in grid.iter().enumerate() {
        if empty_rows.contains(&row_idx) {
            curr_row += 2;
            continue;
        }
        for (col_idx, c) in row.iter().enumerate() {
            if empty_cols.contains(&col_idx) {
                curr_col += 2;
                continue;
            }
            if *c == Tile::Galaxy {
                galaxies.push(Coord {
                    row: curr_row,
                    col: curr_col,
                });
            }
            curr_col += 1
        }
        curr_col = 0;
        curr_row += 1;
    }

    galaxies
}

This function uses 2 helper functions to keep track of indexes for empty rows or empty columns.

fn empty_rows(grid: &[Vec<Tile>]) -> Vec<usize> {
    grid.iter()
        .enumerate()
        .filter_map(|(idx, row)| {
            if !row.contains(&Tile::Galaxy) {
                Some(idx)
            } else {
                None
            }
        })
        .collect()
}

fn empty_cols(grid: &[Vec<Tile>]) -> Vec<usize> {
    // this song and dance is only here so I can loop over columns
    let mut cols: Vec<Vec<Tile>> = vec![vec![Tile::Empty; grid.len()]; grid[0].len()];
    for (row_idx, row) in grid.iter().enumerate() {
        for (col_idx, c) in row.iter().enumerate() {
            cols[col_idx][row_idx] = *c;
        }
    }

    empty_rows(&cols)
}

Time to put it all together.

Code

use itertools::Itertools;

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
enum Tile {
    Galaxy,
    Empty,
}

#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
struct Coord {
    row: usize,
    col: usize,
}

impl Coord {
    fn manhattan_dist(&self, other: &Self) -> usize {
        self.row.abs_diff(other.row) + self.col.abs_diff(other.col)
    }
}

fn parse(input: &str) -> Vec<Vec<Tile>> {
    input
        .lines()
        .map(|line| {
            line.chars()
                .map(|c| match c {
                    '.' => Tile::Empty,
                    '#' => Tile::Galaxy,
                    _ => panic!("at the disco"),
                })
                .collect()
        })
        .collect()
}

fn empty_rows(grid: &[Vec<Tile>]) -> Vec<usize> {
    grid.iter()
        .enumerate()
        .filter_map(|(idx, row)| {
            if !row.contains(&Tile::Galaxy) {
                Some(idx)
            } else {
                None
            }
        })
        .collect()
}

fn empty_cols(grid: &[Vec<Tile>]) -> Vec<usize> {
    // this song and dance is only here so I can loop over columns
    let mut cols: Vec<Vec<Tile>> = vec![vec![Tile::Empty; grid.len()]; grid[0].len()];
    for (row_idx, row) in grid.iter().enumerate() {
        for (col_idx, c) in row.iter().enumerate() {
            cols[col_idx][row_idx] = *c;
        }
    }

    empty_rows(&cols)
}

fn galaxy_coordinates(grid: &[Vec<Tile>]) -> Vec<Coord> {
    let empty_rows = empty_rows(&grid);
    let empty_cols = empty_cols(&grid);

    let mut galaxies = Vec::new();
    let mut curr_row = 0;
    let mut curr_col = 0;

    for (row_idx, row) in grid.iter().enumerate() {
        if empty_rows.contains(&row_idx) {
            curr_row += 2;
            continue;
        }
        for (col_idx, c) in row.iter().enumerate() {
            if empty_cols.contains(&col_idx) {
                curr_col += 2;
                continue;
            }
            if *c == Tile::Galaxy {
                galaxies.push(Coord {
                    row: curr_row,
                    col: curr_col,
                });
            }
            curr_col += 1
        }
        curr_col = 0;
        curr_row += 1;
    }

    galaxies
}

pub fn part_1(input: &str) -> usize {
    let grid = parse(input);
    let galaxies = galaxy_coordinates(&grid);

    galaxies
        .iter()
        .combinations(2)
        .map(|pair| pair[0].manhattan_dist(pair[1]))
        .sum()
}

Part 2

Turns out the galaxies are much further apart.

Any rows or columns that contain no galaxies should all actually be one million times as big.

The question asks for the sum of all distances between each pair galaxies.

Code

The galaxy_coordinates jumped 2 steps when it found an empty line in part1, it jumps 1_000_000 steps in part2.

I normally don't do this Advent of Code, but I generalized a helper function so it can be used for part 1 and part 2.

use itertools::Itertools;

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
enum Tile {
    Galaxy,
    Empty,
}

#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
struct Coord {
    row: usize,
    col: usize,
}

impl Coord {
    fn manhattan_dist(&self, other: &Self) -> usize {
        self.row.abs_diff(other.row) + self.col.abs_diff(other.col)
    }
}

fn parse(input: &str) -> Vec<Vec<Tile>> {
    input
        .lines()
        .map(|line| {
            line.chars()
                .map(|c| match c {
                    '.' => Tile::Empty,
                    '#' => Tile::Galaxy,
                    _ => panic!("at the disco"),
                })
                .collect()
        })
        .collect()
}

fn empty_rows(grid: &[Vec<Tile>]) -> Vec<usize> {
    grid.iter()
        .enumerate()
        .filter_map(|(idx, row)| {
            if !row.contains(&Tile::Galaxy) {
                Some(idx)
            } else {
                None
            }
        })
        .collect()
}

fn empty_cols(grid: &[Vec<Tile>]) -> Vec<usize> {
    // this song and dance is only here so I can loop over columns
    let mut cols: Vec<Vec<Tile>> = vec![vec![Tile::Empty; grid.len()]; grid[0].len()];
    for (row_idx, row) in grid.iter().enumerate() {
        for (col_idx, c) in row.iter().enumerate() {
            cols[col_idx][row_idx] = *c;
        }
    }

    empty_rows(&cols)
}

fn galaxy_coordinates(grid: &[Vec<Tile>], expansion: usize) -> Vec<Coord> {
    let empty_rows = empty_rows(&grid);
    let empty_cols = empty_cols(&grid);

    let mut galaxies = Vec::new();
    let mut curr_row = 0;
    let mut curr_col = 0;

    for (row_idx, row) in grid.iter().enumerate() {
        if empty_rows.contains(&row_idx) {
            curr_row += expansion;
            continue;
        }
        for (col_idx, c) in row.iter().enumerate() {
            if empty_cols.contains(&col_idx) {
                curr_col += expansion;
                continue;
            }
            if *c == Tile::Galaxy {
                galaxies.push(Coord {
                    row: curr_row,
                    col: curr_col,
                });
            }
            curr_col += 1
        }
        curr_col = 0;
        curr_row += 1;
    }

    galaxies
}

pub fn part_2(input: &str) -> usize {
    let grid = parse(input);
    let galaxies = galaxy_coordinates(&grid, 1_000_000);

    galaxies
        .iter()
        .combinations(2)
        .map(|pair| pair[0].manhattan_dist(pair[1]))
        .sum()
}

Final code

use itertools::Itertools;

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
enum Tile {
    Galaxy,
    Empty,
}

#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
struct Coord {
    row: usize,
    col: usize,
}

impl Coord {
    fn manhattan_dist(&self, other: &Self) -> usize {
        self.row.abs_diff(other.row) + self.col.abs_diff(other.col)
    }
}

fn parse(input: &str) -> Vec<Vec<Tile>> {
    input
        .lines()
        .map(|line| {
            line.chars()
                .map(|c| match c {
                    '.' => Tile::Empty,
                    '#' => Tile::Galaxy,
                    _ => panic!("at the disco"),
                })
                .collect()
        })
        .collect()
}

fn empty_rows(grid: &[Vec<Tile>]) -> Vec<usize> {
    grid.iter()
        .enumerate()
        .filter_map(|(idx, row)| {
            if !row.contains(&Tile::Galaxy) {
                Some(idx)
            } else {
                None
            }
        })
        .collect()
}

fn empty_cols(grid: &[Vec<Tile>]) -> Vec<usize> {
    // this song and dance is only here so I can loop over columns
    let mut cols: Vec<Vec<Tile>> = vec![vec![Tile::Empty; grid.len()]; grid[0].len()];
    for (row_idx, row) in grid.iter().enumerate() {
        for (col_idx, c) in row.iter().enumerate() {
            cols[col_idx][row_idx] = *c;
        }
    }

    empty_rows(&cols)
}

fn galaxy_coordinates(grid: &[Vec<Tile>], expansion: usize) -> Vec<Coord> {
    let empty_rows = empty_rows(&grid);
    let empty_cols = empty_cols(&grid);

    let mut galaxies = Vec::new();
    let mut curr_row = 0;
    let mut curr_col = 0;

    for (row_idx, row) in grid.iter().enumerate() {
        if empty_rows.contains(&row_idx) {
            curr_row += expansion;
            continue;
        }
        for (col_idx, c) in row.iter().enumerate() {
            if empty_cols.contains(&col_idx) {
                curr_col += expansion;
                continue;
            }
            if *c == Tile::Galaxy {
                galaxies.push(Coord {
                    row: curr_row,
                    col: curr_col,
                });
            }
            curr_col += 1
        }
        curr_col = 0;
        curr_row += 1;
    }

    galaxies
}

pub fn part_1(input: &str) -> usize {
    let grid = parse(input);
    let galaxies = galaxy_coordinates(&grid, 2);

    galaxies
        .iter()
        .combinations(2)
        .map(|pair| pair[0].manhattan_dist(pair[1]))
        .sum()
}

pub fn part_2(input: &str) -> usize {
    let grid = parse(input);
    let galaxies = galaxy_coordinates(&grid, 1_000_000);

    galaxies
        .iter()
        .combinations(2)
        .map(|pair| pair[0].manhattan_dist(pair[1]))
        .sum()
}

Advent of Code 2023 Day 10

Nicky Meuleman — Thu, 14 Dec 2023 21:22:18 +0000

Day 10: Pipe Maze

https://adventofcode.com/2023/day/10

You go up to a metal island with a hang glider.

There, you see an animal run into a maze of pipes.

You scan the maze of pipes, that scan is today's input.

An example input looks like this:

..F7.
.FJ|.
SJ.L7
|F--J
LJ...

The pipes are arranged in a two-dimensional grid of tiles:

| is a vertical pipe connecting north and south.
- is a horizontal pipe connecting east and west.
L is a 90-degree bend connecting north and east.
J is a 90-degree bend connecting north and west.
7 is a 90-degree bend connecting south and west.
F is a 90-degree bend connecting south and east.
. is ground; there is no pipe in this tile.
S is the starting position of the animal; there is a pipe on this tile, but your sketch doesn't show what shape the pipe has.

The pipe the animal ran into is a large, continuous loop.

There are other pipes in your scan that are not connected to the main loop.

Parsing

I decided to represent each type of input as a Tile enum.

enum Tile {
    // | is a vertical pipe connecting north and south.
    NorthSouth,
    // - is a horizontal pipe connecting east and west.
    EastWest,
    // L is a 90-degree bend connecting north and east.
    NorthEast,
    // J is a 90-degree bend connecting north and west.
    NorthWest,
    // 7 is a 90-degree bend connecting south and west.
    SouthWest,
    // F is a 90-degree bend connecting south and east.
    SouthEast,
    // . is ground; there is no pipe in this tile.
    Ground,
    // S is the starting position of the animal; there is a pipe on this tile, but your sketch doesn't show what shape the pipe has.
    Start,
}

A helper to turn characters into variants of that enum:

impl Tile {
    fn from(c: char) -> Self {
        match c {
            '|' => NorthSouth,
            '-' => EastWest,
            'L' => NorthEast,
            'J' => NorthWest,
            '7' => SouthWest,
            'F' => SouthEast,
            '.' => Ground,
            'S' => Start,
            _ => panic!(),
        }
    }
}

I keep track of a coordinate in the 2D grid with Coord:

struct Coord {
    row_idx: usize,
    col_idx: usize,
}

From the input, I parse the coordinate of the start position, and a 2D list of Tiles:

fn parse(input: &str) -> (Vec<Vec<Tile>>, Coord) {
    let mut start = Coord::new(0, 0);
    let map = input
        .lines()
        .enumerate()
        .map(|(row_idx, line)| {
            line.chars()
                .enumerate()
                .map(|(col_idx, c)| {
                    let tile = Tile::from(c);
                    if tile == Start {
                        start = Coord::new(row_idx, col_idx)
                    }
                    tile
                })
                .collect()
        })
        .collect();
    (map, start)
}

Part 1

You want to look at the animal that ran into the pipes.
You decide to wait for the animal at the spot that's the most steps along the loop away from the start, regardless of which direction it took.

The question asks how many steps along the loop it takes to get from the starting position to the point farthest from the starting position?

In other words, you wait at the coordinate that marks the middle of the loop.

Some skeleton/pseudo-code I want to work towards:

let (map, start) = parse(input);
let loop_coords = build_loop(start, &map);
loop_coords.len() / 2

Helpers

The function that turns the map into a set of coordinates that belong to the main loop:

fn build_loop(start: Coord, map: &[Vec<Tile>]) -> HashSet<Coord> {
    let mut loop_coords = HashSet::new();
    loop_coords.insert(start);
    let mut to_visit = start.valid_neighbours(map);

    while let Some(curr_pos) = to_visit.pop() {
        for neighbour in curr_pos.valid_neighbours(map) {
            if !loop_coords.contains(&neighbour) {
                to_visit.push(neighbour);
                loop_coords.insert(neighbour);
            }
        }
    }

    loop_coords
}

That function used a helper that returns the coordinates of the pipes that are directly connected to the current pipe.
This is the main logic of this problem, it's a huge decision-tree.

It figures out which type of Tile I am currently on.
Based on that, it figures out which types of Tile are allowed to connect to that.
The coordinates a valid connecting tiles are returned by this function.

example: An L pipe (NorthWest in our Tile enum), can only accept a connecting tile in the north, or the west.

It looks in the north location, and if a valid pipe is there, it marks that location as a valid neighbour
It looks in the west location, and if a valid pipe is there, it marks that location as a valid neighbour

#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
struct Coord {
    row_idx: usize,
    col_idx: usize,
}

impl Coord {
    fn new(row_idx: usize, col_idx: usize) -> Self {
        Self { row_idx, col_idx }
    }

    fn valid_neighbours(&self, map: &[Vec<Tile>]) -> Vec<Coord> {
        let mut neighbours = vec![];
        let max_height = map.len() - 1;
        let max_width = map[0].len() - 1;

        match map[self.row_idx][self.col_idx] {
            Ground => (),
            Start => {
                // north
                if self.row_idx > 0 {
                    let tile = map[self.row_idx - 1][self.col_idx];
                    if matches!(tile, NorthSouth | SouthWest | SouthEast) {
                        neighbours.push(Coord::new(self.row_idx - 1, self.col_idx));
                    }
                }
                // south
                if self.row_idx < max_height {
                    let tile = map[self.row_idx + 1][self.col_idx];
                    if matches!(tile, NorthSouth | NorthWest | NorthEast) {
                        neighbours.push(Coord::new(self.row_idx + 1, self.col_idx))
                    }
                }
                // west
                if self.col_idx > 0 {
                    let tile = map[self.row_idx][self.col_idx - 1];
                    if matches!(tile, EastWest | SouthEast | NorthEast) {
                        neighbours.push(Coord::new(self.row_idx, self.col_idx - 1))
                    }
                }
                // east
                if self.col_idx < max_width {
                    let tile = map[self.row_idx][self.col_idx + 1];
                    if matches!(tile, EastWest | NorthWest | SouthWest) {
                        neighbours.push(Coord::new(self.row_idx, self.col_idx + 1))
                    }
                }
            }
            NorthSouth => {
                // north
                if self.row_idx > 0 {
                    match map[self.row_idx - 1][self.col_idx] {
                        NorthSouth => neighbours.push(Coord::new(self.row_idx - 1, self.col_idx)),
                        SouthWest => neighbours.push(Coord::new(self.row_idx - 1, self.col_idx)),
                        SouthEast => neighbours.push(Coord::new(self.row_idx - 1, self.col_idx)),
                        Start => neighbours.push(Coord::new(self.row_idx - 1, self.col_idx)),
                        _ => (),
                    }
                }
                // south
                if self.row_idx < max_height && map[self.row_idx + 1][self.col_idx] != Ground {
                    match map[self.row_idx + 1][self.col_idx] {
                        NorthSouth => neighbours.push(Coord::new(self.row_idx + 1, self.col_idx)),
                        NorthWest => neighbours.push(Coord::new(self.row_idx + 1, self.col_idx)),
                        NorthEast => neighbours.push(Coord::new(self.row_idx + 1, self.col_idx)),
                        Start => neighbours.push(Coord::new(self.row_idx + 1, self.col_idx)),
                        _ => (),
                    }
                }
            }
            EastWest => {
                // west
                if self.col_idx > 0 {
                    match map[self.row_idx][self.col_idx - 1] {
                        EastWest => neighbours.push(Coord::new(self.row_idx, self.col_idx - 1)),
                        SouthEast => neighbours.push(Coord::new(self.row_idx, self.col_idx - 1)),
                        NorthEast => neighbours.push(Coord::new(self.row_idx, self.col_idx - 1)),
                        Start => neighbours.push(Coord::new(self.row_idx, self.col_idx - 1)),
                        _ => (),
                    }
                }
                // east
                if self.col_idx < max_width {
                    match map[self.row_idx][self.col_idx + 1] {
                        EastWest => neighbours.push(Coord::new(self.row_idx, self.col_idx + 1)),
                        NorthWest => neighbours.push(Coord::new(self.row_idx, self.col_idx + 1)),
                        SouthWest => neighbours.push(Coord::new(self.row_idx, self.col_idx + 1)),
                        Start => neighbours.push(Coord::new(self.row_idx, self.col_idx + 1)),
                        _ => (),
                    }
                }
            }
            NorthEast => {
                // north
                if self.row_idx > 0 {
                    match map[self.row_idx - 1][self.col_idx] {
                        NorthSouth => neighbours.push(Coord::new(self.row_idx - 1, self.col_idx)),
                        SouthWest => neighbours.push(Coord::new(self.row_idx - 1, self.col_idx)),
                        SouthEast => neighbours.push(Coord::new(self.row_idx - 1, self.col_idx)),
                        Start => neighbours.push(Coord::new(self.row_idx - 1, self.col_idx)),
                        _ => (),
                    }
                }
                // east
                if self.col_idx < max_width {
                    match map[self.row_idx][self.col_idx + 1] {
                        EastWest => neighbours.push(Coord::new(self.row_idx, self.col_idx + 1)),
                        NorthWest => neighbours.push(Coord::new(self.row_idx, self.col_idx + 1)),
                        SouthWest => neighbours.push(Coord::new(self.row_idx, self.col_idx + 1)),
                        Start => neighbours.push(Coord::new(self.row_idx, self.col_idx + 1)),
                        _ => (),
                    }
                }
            }
            NorthWest => {
                // north
                if self.row_idx > 0 {
                    match map[self.row_idx - 1][self.col_idx] {
                        NorthSouth => neighbours.push(Coord::new(self.row_idx - 1, self.col_idx)),
                        SouthWest => neighbours.push(Coord::new(self.row_idx - 1, self.col_idx)),
                        SouthEast => neighbours.push(Coord::new(self.row_idx - 1, self.col_idx)),
                        Start => neighbours.push(Coord::new(self.row_idx - 1, self.col_idx)),
                        _ => (),
                    }
                }
                // west
                if self.col_idx > 0 {
                    match map[self.row_idx][self.col_idx - 1] {
                        EastWest => neighbours.push(Coord::new(self.row_idx, self.col_idx - 1)),
                        SouthEast => neighbours.push(Coord::new(self.row_idx, self.col_idx - 1)),
                        NorthEast => neighbours.push(Coord::new(self.row_idx, self.col_idx - 1)),
                        Start => neighbours.push(Coord::new(self.row_idx, self.col_idx - 1)),
                        _ => (),
                    }
                }
            }
            SouthWest => {
                // south
                if self.row_idx < max_height {
                    match map[self.row_idx + 1][self.col_idx] {
                        NorthSouth => neighbours.push(Coord::new(self.row_idx + 1, self.col_idx)),
                        NorthWest => neighbours.push(Coord::new(self.row_idx + 1, self.col_idx)),
                        NorthEast => neighbours.push(Coord::new(self.row_idx + 1, self.col_idx)),
                        Start => neighbours.push(Coord::new(self.row_idx + 1, self.col_idx)),
                        _ => (),
                    }
                }
                // west
                if self.col_idx > 0 {
                    match map[self.row_idx][self.col_idx - 1] {
                        EastWest => neighbours.push(Coord::new(self.row_idx, self.col_idx - 1)),
                        SouthEast => neighbours.push(Coord::new(self.row_idx, self.col_idx - 1)),
                        NorthEast => neighbours.push(Coord::new(self.row_idx, self.col_idx - 1)),
                        Start => neighbours.push(Coord::new(self.row_idx, self.col_idx - 1)),
                        _ => (),
                    }
                }
            }
            SouthEast => {
                // south
                if self.row_idx < max_height {
                    match map[self.row_idx + 1][self.col_idx] {
                        NorthSouth => neighbours.push(Coord::new(self.row_idx + 1, self.col_idx)),
                        NorthWest => neighbours.push(Coord::new(self.row_idx + 1, self.col_idx)),
                        NorthEast => neighbours.push(Coord::new(self.row_idx + 1, self.col_idx)),
                        Start => neighbours.push(Coord::new(self.row_idx + 1, self.col_idx)),
                        _ => (),
                    }
                }
                // east
                if self.col_idx < max_width {
                    match map[self.row_idx][self.col_idx + 1] {
                        EastWest => neighbours.push(Coord::new(self.row_idx, self.col_idx + 1)),
                        NorthWest => neighbours.push(Coord::new(self.row_idx, self.col_idx + 1)),
                        SouthWest => neighbours.push(Coord::new(self.row_idx, self.col_idx + 1)),
                        Start => neighbours.push(Coord::new(self.row_idx, self.col_idx + 1)),
                        _ => (),
                    }
                }
            }
        }

        neighbours
    }
}

Code

The reused code is not listed here, because otherwise this post would become huge.

pub fn part_1(input: &str) -> usize {
    let (map, start) = parse(input);
    let loop_coords = build_loop(start, &map);
    loop_coords.len() / 2
}

Part 2

The animal did not emerge.
Its nest is probably within an area that's enclosed by the loop.

This is an example loop with only pipes that are part of the main loop.

...........
.S-------7.
.|F-----7|.
.||.....||.
.||.....||.
.|L-7.F-J|.
.|..|.|..|.
.L--J.L--J.
...........

There are 4 tiles that are completely inside the loop, marked as I below.
The tiles marked as O are not inside.

...........
.S-------7.
.|F-----7|.
.||OOOOO||.
.||OOOOO||.
.|L-7OF-J|.
.|II|O|II|.
.L--JOL--J.
.....O.....

The animal is small, and can squeeze between 2 pipes, even if there isn't a . tile in between!

Here O tiles are still not inside the loop, and I tiles are:

..........
.S------7.
.|F----7|.
.||OOOO||.
.||OOOO||.
.|L-7F-J|.
.|II||II|.
.L--JL--J.
..........

The question asks how many tiles are enclosed by the loop.

Option 1: flood fill

Because of that rule where the animal can fit between 2 pipes, a regular floodfill approach will not work.
You would end up also counting tiles that are still accessible from the outside.

However, if you expend every tile into a 3x3 grid of tiles, there are guaranteed to be gaps between tiles, where floodfill can pass.

In ASCII:
| turns into:

.#.
.#.
.#.

- turns into:

...
###
...

J turns into:

..#
..#
###

and so forth...

Start the floodfill at an empty tile.
The tiles that are still empty at the end are inside the loop.
Remember to account for the fact that 1 empty tile turned into a 3x3 grid of empty tiles when you first expanded the grid.

Option 2: even-odd rule

This is the solution I ended up coding.

Get the coordinates of the loop
Clean the map:
1. Replace that starting coordinate with a segment of pipe
2. Only keep segments of pipe that are part of the main loop
Apply the even-odd rule to the clean map

in pseudo-code:

let (map, start) = parse(input);
let loop_coords = build_loop(start, &map);
let clean_map = clean_map(start, &loop_coords, map);
let count = count_enclosed_tiles(clean_map);
count

Helpers

The helpers that takes the initial map, and returns a cleaned up map:

It only hold pieces of pipe that are part of the main loop, all other coordinates are ground tiles.
It replaces that start position with a valid piece of pipe

/// replace start with a valid pipe segment, and only keep pipe segments that are part of the loop
fn clean_map(start: Coord, loop_coords: &HashSet<Coord>, map: Vec<Vec<Tile>>) -> Vec<Vec<Tile>> {
    let start_pipe = get_start_pipe(&map, start);

    map.into_iter()
        .enumerate()
        .map(|(row_idx, line)| {
            line.into_iter()
                .enumerate()
                .map(|(col_idx, tile)| match tile {
                    Start => start_pipe,
                    pipe if loop_coords.contains(&Coord::new(row_idx, col_idx)) => pipe,
                    _ => Ground,
                })
                .collect()
        })
        .collect()
}

That function used another helper to figure out which piece of pipe is located at the start coordinates:

fn get_start_pipe(map: &Vec<Vec<Tile>>, start: Coord) -> Tile {
    let neighbours = start.valid_neighbours(map);
    let north = neighbours
        .iter()
        .find(|coord| coord.row_idx < start.row_idx)
        .is_some();
    let south = neighbours
        .iter()
        .find(|coord| coord.row_idx > start.row_idx)
        .is_some();
    let west = neighbours
        .iter()
        .find(|coord| coord.col_idx < start.col_idx)
        .is_some();
    let east = neighbours
        .iter()
        .find(|coord| coord.col_idx > start.col_idx)
        .is_some();

    match (north, west, south, east) {
        (true, true, _, _) => NorthWest,
        (true, _, true, _) => NorthSouth,
        (true, _, _, true) => NorthEast,
        (_, true, true, _) => SouthWest,
        (_, _, true, true) => SouthEast,
        (_, true, _, true) => EastWest,
        _ => panic!("No valid tile to replace Start with was found"),
    }
}

With a clean map, I used the even-odd rule to count the amount of tiles that are enclosed by that loop.

Code

The reused code is not listed here, because otherwise this post would become huge.

pub fn part_2(input: &str) -> usize {
    let (map, start) = parse(input);
    let loop_coords = build_loop(start, &map);
    let map = clean_map(start, &loop_coords, map);
    // scan from top to bottom and left to right, counting how many tiles are inside the loop.
    // keep track of a boolean that tells me if I'm inside the loop
    // every time I cross a vertical pipe that does not horizontally block the top (the place where I am in the loop), flip that state
    let mut inside = false;
    map.into_iter()
        .flatten()
        .filter(|tile| match tile {
            Ground => inside,
            NorthSouth | NorthWest | NorthEast => {
                inside = !inside;
                false
            }
            _ => false,
        })
        .count()
}

Final code

use std::collections::HashSet;

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
enum Tile {
    // | is a vertical pipe connecting north and south.
    NorthSouth,
    // - is a horizontal pipe connecting east and west.
    EastWest,
    // L is a 90-degree bend connecting north and east.
    NorthEast,
    // J is a 90-degree bend connecting north and west.
    NorthWest,
    // 7 is a 90-degree bend connecting south and west.
    SouthWest,
    // F is a 90-degree bend connecting south and east.
    SouthEast,
    // . is ground; there is no pipe in this tile.
    Ground,
    // S is the starting position of the animal; there is a pipe on this tile, but your sketch doesn't show what shape the pipe has.
    Start,
}
use Tile::*;
impl Tile {
    fn from(c: char) -> Self {
        match c {
            '|' => NorthSouth,
            '-' => EastWest,
            'L' => NorthEast,
            'J' => NorthWest,
            '7' => SouthWest,
            'F' => SouthEast,
            '.' => Ground,
            'S' => Start,
            _ => panic!(),
        }
    }
}

#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
struct Coord {
    row_idx: usize,
    col_idx: usize,
}

impl Coord {
    fn new(row_idx: usize, col_idx: usize) -> Self {
        Self { row_idx, col_idx }
    }

    fn valid_neighbours(&self, map: &[Vec<Tile>]) -> Vec<Coord> {
        let mut neighbours = vec![];
        let max_height = map.len() - 1;
        let max_width = map[0].len() - 1;

        match map[self.row_idx][self.col_idx] {
            Ground => (),
            Start => {
                // north
                if self.row_idx > 0 {
                    let tile = map[self.row_idx - 1][self.col_idx];
                    if matches!(tile, NorthSouth | SouthWest | SouthEast) {
                        neighbours.push(Coord::new(self.row_idx - 1, self.col_idx));
                    }
                }
                // south
                if self.row_idx < max_height {
                    let tile = map[self.row_idx + 1][self.col_idx];
                    if matches!(tile, NorthSouth | NorthWest | NorthEast) {
                        neighbours.push(Coord::new(self.row_idx + 1, self.col_idx))
                    }
                }
                // west
                if self.col_idx > 0 {
                    let tile = map[self.row_idx][self.col_idx - 1];
                    if matches!(tile, EastWest | SouthEast | NorthEast) {
                        neighbours.push(Coord::new(self.row_idx, self.col_idx - 1))
                    }
                }
                // east
                if self.col_idx < max_width {
                    let tile = map[self.row_idx][self.col_idx + 1];
                    if matches!(tile, EastWest | NorthWest | SouthWest) {
                        neighbours.push(Coord::new(self.row_idx, self.col_idx + 1))
                    }
                }
            }
            NorthSouth => {
                // north
                if self.row_idx > 0 {
                    match map[self.row_idx - 1][self.col_idx] {
                        NorthSouth => neighbours.push(Coord::new(self.row_idx - 1, self.col_idx)),
                        SouthWest => neighbours.push(Coord::new(self.row_idx - 1, self.col_idx)),
                        SouthEast => neighbours.push(Coord::new(self.row_idx - 1, self.col_idx)),
                        Start => neighbours.push(Coord::new(self.row_idx - 1, self.col_idx)),
                        _ => (),
                    }
                }
                // south
                if self.row_idx < max_height && map[self.row_idx + 1][self.col_idx] != Ground {
                    match map[self.row_idx + 1][self.col_idx] {
                        NorthSouth => neighbours.push(Coord::new(self.row_idx + 1, self.col_idx)),
                        NorthWest => neighbours.push(Coord::new(self.row_idx + 1, self.col_idx)),
                        NorthEast => neighbours.push(Coord::new(self.row_idx + 1, self.col_idx)),
                        Start => neighbours.push(Coord::new(self.row_idx + 1, self.col_idx)),
                        _ => (),
                    }
                }
            }
            EastWest => {
                // west
                if self.col_idx > 0 {
                    match map[self.row_idx][self.col_idx - 1] {
                        EastWest => neighbours.push(Coord::new(self.row_idx, self.col_idx - 1)),
                        SouthEast => neighbours.push(Coord::new(self.row_idx, self.col_idx - 1)),
                        NorthEast => neighbours.push(Coord::new(self.row_idx, self.col_idx - 1)),
                        Start => neighbours.push(Coord::new(self.row_idx, self.col_idx - 1)),
                        _ => (),
                    }
                }
                // east
                if self.col_idx < max_width {
                    match map[self.row_idx][self.col_idx + 1] {
                        EastWest => neighbours.push(Coord::new(self.row_idx, self.col_idx + 1)),
                        NorthWest => neighbours.push(Coord::new(self.row_idx, self.col_idx + 1)),
                        SouthWest => neighbours.push(Coord::new(self.row_idx, self.col_idx + 1)),
                        Start => neighbours.push(Coord::new(self.row_idx, self.col_idx + 1)),
                        _ => (),
                    }
                }
            }
            NorthEast => {
                // north
                if self.row_idx > 0 {
                    match map[self.row_idx - 1][self.col_idx] {
                        NorthSouth => neighbours.push(Coord::new(self.row_idx - 1, self.col_idx)),
                        SouthWest => neighbours.push(Coord::new(self.row_idx - 1, self.col_idx)),
                        SouthEast => neighbours.push(Coord::new(self.row_idx - 1, self.col_idx)),
                        Start => neighbours.push(Coord::new(self.row_idx - 1, self.col_idx)),
                        _ => (),
                    }
                }
                // east
                if self.col_idx < max_width {
                    match map[self.row_idx][self.col_idx + 1] {
                        EastWest => neighbours.push(Coord::new(self.row_idx, self.col_idx + 1)),
                        NorthWest => neighbours.push(Coord::new(self.row_idx, self.col_idx + 1)),
                        SouthWest => neighbours.push(Coord::new(self.row_idx, self.col_idx + 1)),
                        Start => neighbours.push(Coord::new(self.row_idx, self.col_idx + 1)),
                        _ => (),
                    }
                }
            }
            NorthWest => {
                // north
                if self.row_idx > 0 {
                    match map[self.row_idx - 1][self.col_idx] {
                        NorthSouth => neighbours.push(Coord::new(self.row_idx - 1, self.col_idx)),
                        SouthWest => neighbours.push(Coord::new(self.row_idx - 1, self.col_idx)),
                        SouthEast => neighbours.push(Coord::new(self.row_idx - 1, self.col_idx)),
                        Start => neighbours.push(Coord::new(self.row_idx - 1, self.col_idx)),
                        _ => (),
                    }
                }
                // west
                if self.col_idx > 0 {
                    match map[self.row_idx][self.col_idx - 1] {
                        EastWest => neighbours.push(Coord::new(self.row_idx, self.col_idx - 1)),
                        SouthEast => neighbours.push(Coord::new(self.row_idx, self.col_idx - 1)),
                        NorthEast => neighbours.push(Coord::new(self.row_idx, self.col_idx - 1)),
                        Start => neighbours.push(Coord::new(self.row_idx, self.col_idx - 1)),
                        _ => (),
                    }
                }
            }
            SouthWest => {
                // south
                if self.row_idx < max_height {
                    match map[self.row_idx + 1][self.col_idx] {
                        NorthSouth => neighbours.push(Coord::new(self.row_idx + 1, self.col_idx)),
                        NorthWest => neighbours.push(Coord::new(self.row_idx + 1, self.col_idx)),
                        NorthEast => neighbours.push(Coord::new(self.row_idx + 1, self.col_idx)),
                        Start => neighbours.push(Coord::new(self.row_idx + 1, self.col_idx)),
                        _ => (),
                    }
                }
                // west
                if self.col_idx > 0 {
                    match map[self.row_idx][self.col_idx - 1] {
                        EastWest => neighbours.push(Coord::new(self.row_idx, self.col_idx - 1)),
                        SouthEast => neighbours.push(Coord::new(self.row_idx, self.col_idx - 1)),
                        NorthEast => neighbours.push(Coord::new(self.row_idx, self.col_idx - 1)),
                        Start => neighbours.push(Coord::new(self.row_idx, self.col_idx - 1)),
                        _ => (),
                    }
                }
            }
            SouthEast => {
                // south
                if self.row_idx < max_height {
                    match map[self.row_idx + 1][self.col_idx] {
                        NorthSouth => neighbours.push(Coord::new(self.row_idx + 1, self.col_idx)),
                        NorthWest => neighbours.push(Coord::new(self.row_idx + 1, self.col_idx)),
                        NorthEast => neighbours.push(Coord::new(self.row_idx + 1, self.col_idx)),
                        Start => neighbours.push(Coord::new(self.row_idx + 1, self.col_idx)),
                        _ => (),
                    }
                }
                // east
                if self.col_idx < max_width {
                    match map[self.row_idx][self.col_idx + 1] {
                        EastWest => neighbours.push(Coord::new(self.row_idx, self.col_idx + 1)),
                        NorthWest => neighbours.push(Coord::new(self.row_idx, self.col_idx + 1)),
                        SouthWest => neighbours.push(Coord::new(self.row_idx, self.col_idx + 1)),
                        Start => neighbours.push(Coord::new(self.row_idx, self.col_idx + 1)),
                        _ => (),
                    }
                }
            }
        }

        neighbours
    }
}

fn parse(input: &str) -> (Vec<Vec<Tile>>, Coord) {
    let mut start = Coord::new(0, 0);
    let map = input
        .lines()
        .enumerate()
        .map(|(row_idx, line)| {
            line.chars()
                .enumerate()
                .map(|(col_idx, c)| {
                    let tile = Tile::from(c);
                    if tile == Start {
                        start = Coord::new(row_idx, col_idx)
                    }
                    tile
                })
                .collect()
        })
        .collect();
    (map, start)
}

fn build_loop(start: Coord, map: &[Vec<Tile>]) -> HashSet<Coord> {
    let mut loop_coords = HashSet::new();
    loop_coords.insert(start);
    let mut to_visit = start.valid_neighbours(map);

    while let Some(curr_pos) = to_visit.pop() {
        for neighbour in curr_pos.valid_neighbours(map) {
            if !loop_coords.contains(&neighbour) {
                to_visit.push(neighbour);
                loop_coords.insert(neighbour);
            }
        }
    }

    loop_coords
}

pub fn part_1(input: &str) -> usize {
    let (map, start) = parse(input);
    let loop_coords = build_loop(start, &map);
    loop_coords.len() / 2
}

fn get_start_pipe(map: &Vec<Vec<Tile>>, start: Coord) -> Tile {
    let neighbours = start.valid_neighbours(map);
    let north = neighbours
        .iter()
        .find(|coord| coord.row_idx < start.row_idx)
        .is_some();
    let south = neighbours
        .iter()
        .find(|coord| coord.row_idx > start.row_idx)
        .is_some();
    let west = neighbours
        .iter()
        .find(|coord| coord.col_idx < start.col_idx)
        .is_some();
    let east = neighbours
        .iter()
        .find(|coord| coord.col_idx > start.col_idx)
        .is_some();

    match (north, west, south, east) {
        (true, true, _, _) => NorthWest,
        (true, _, true, _) => NorthSouth,
        (true, _, _, true) => NorthEast,
        (_, true, true, _) => SouthWest,
        (_, _, true, true) => SouthEast,
        (_, true, _, true) => EastWest,
        _ => panic!("No valid tile to replace Start with was found"),
    }
}

/// replace start with a valid pipe segment, and only keep pipe segments that are part of the loop
fn clean_map(start: Coord, loop_coords: &HashSet<Coord>, map: Vec<Vec<Tile>>) -> Vec<Vec<Tile>> {
    let start_pipe = get_start_pipe(&map, start);

    map.into_iter()
        .enumerate()
        .map(|(row_idx, line)| {
            line.into_iter()
                .enumerate()
                .map(|(col_idx, tile)| match tile {
                    Start => start_pipe,
                    pipe if loop_coords.contains(&Coord::new(row_idx, col_idx)) => pipe,
                    _ => Ground,
                })
                .collect()
        })
        .collect()
}

pub fn part_2(input: &str) -> usize {
    let (map, start) = parse(input);
    let loop_coords = build_loop(start, &map);
    let map = clean_map(start, &loop_coords, map);
    // scan from top to bottom and left to right, counting how many tiles are inside the loop.
    // keep track of a boolean that tells me if I'm inside the loop
    // every time I cross a vertical pipe that does not horizontally block the top (the place where I am in the loop), flip that state
    let mut inside = false;
    map.into_iter()
        .flatten()
        .filter(|tile| match tile {
            Ground => inside,
            NorthSouth | NorthWest | NorthEast => {
                inside = !inside;
                false
            }
            _ => false,
        })
        .count()
}

Advent of Code 2023 Day 9

Nicky Meuleman — Sat, 09 Dec 2023 18:58:12 +0000

Day 9: Mirage Maintenance

https://adventofcode.com/2023/day/9

You got out of the sandstorm and arrive at an oasis.

You gather some data on the oasis by tracking some datapoints, that's today's input.

An example input looks like this:

0 3 6 9 12 15
1 3 6 10 15 21
10 13 16 21 30 45

Each line in the report contains the history of a single value

Part 1

You want to predict the next value for each datapoint.

The question asks what the sum is of all next values.

To extrapolate the next value of a line, you start by making a new sequence with the difference at each step.
You do this until all numbers in the new sequence are zeroes.

In the example input, for the first line:

0   3   6   9  12  15
  3   3   3   3   3
    0   0   0   0

Now to find the next value in the original sequence, start by adding a zero to the end of the last line.

This lets you figure out the last value on every previous line, until you get to the very first line (Nicky's note: I smell recursion).

Also, I recognize this from math class! Pascal's triangle.
I don't remember if there is a clever way to determine a specific value though, so I'm going to code up a brute-force solution and see how that works out.
(spoiler: it worked out)

Option 1: imperatively

I gather each line into a list of numbers.
For each line, I figure out what the next number would be.
I sum those numbers.

It's the second step that's the interesting part.

It's in an infinite loop.

In that loop I build the new sequence of differences from a starting sequence (it starts as line in the input).

If all numbers in that new sequence are 0, I'm done and break out of the loop.
If not, I set the starting sequence to the sequence of differences, and do it all again!

I keep track of all numbers at the end of a sequence while looping.
The next number in a sequence is the sum of its last number + all last numbers in sequences it generates.

To demonstrate, the example for line 3 in the example input:

10  13  16  21  30  45  68
   3   3   5   9  15  23
     0   2   4   6   8
       2   2   2   2
         0   0   0

Pointing your attention to the last number on every line.
And checking what I've said above: "The next number in a sequence is the sum of its last number + all last numbers in sequences it generates."

68 = 45 + 15 + 6 + 2
23 = 15 + 6 + 2
8 = 6 + 2
2 = 2 + 0
0 = 0

Code

pub fn part_1(input: &str) -> i32 {
    input
        .lines()
        .map(|line| {
            let mut nums: Vec<i32> = line
                .split_whitespace()
                .filter_map(|s| s.parse().ok())
                .collect();

            let mut edge: Vec<i32> = Vec::new();
            loop {
                let differences: Vec<i32> = nums
                    .iter()
                    .tuple_windows()
                    .map(|(left, right)| right - left)
                    .collect();

                edge.push(*nums.last().unwrap());

                if differences.iter().all(|&x| x == 0) {
                    let sum: i32 = edge.iter().sum();
                    break sum;
                } else {
                    // prepare for next loop
                    nums = differences;
                }
            }
        })
        .sum()
}

Bonus: reuse memory

The same code, but keeping some variables around and reusing them.
And indexing into arrays.
The result is slightly faster code that uses less memory.

Code

pub fn part_1(input: &str) -> i32 {
    let mut nums: Vec<i32> = Vec::new();
    let mut differences: Vec<i32> = Vec::new();
    let mut edge: Vec<i32> = Vec::new();

    input
        .lines()
        .map(|line| {
            nums.clear();
            for num in line.split_ascii_whitespace() {
                nums.push(num.parse().unwrap());
            }

            edge.clear();

            loop {
                differences.clear();
                for i in nums.windows(2) {
                    differences.push(i[1] - i[0]);
                }
                edge.push(nums[nums.len() - 1]);
                if differences.iter().all(|&x| x == 0) {
                    let sum: i32 = edge.iter().sum();
                    break sum;
                }
                std::mem::swap(&mut nums, &mut differences);
            }
        })
        .sum()
}

Option 2: recursion

The solution I wrote first, shame it's significantly slower than the imperative versions, because it reads so nice.

Helpers

A function that takes a line of numbers as a string, and turns it into a vector of integers:

fn nums(s: &str) -> Vec<i32> {
    s.split_whitespace()
        .filter_map(|s| s.parse().ok())
        .collect()
}

A function that returns a list of all differences in a sequence:

use itertools::Itertools;

fn differences(nums: &[i32]) -> Vec<i32> {
    nums.iter()
        .tuple_windows()
        .map(|(left, right)| right - left)
        .collect()
}

The interesting part, the recursive part!
A function that returns the next number in a sequence.

If all numbers in the original sequence are 0, the next number is 0 and I break.
This is the base case that stops the recursion.

Otherwise, I calculate the list of differences.
The next number is the next number in that list of differences plus the last number in the sequence that was passed in.

fn next_num(nums: &[i32]) -> i32 {
    if nums.iter().all(|&n| n == 0) {
        return 0;
    }
    let differences: Vec<i32> = differences(nums);
    next_num(&differences) + nums.iter().last().unwrap()
}

Code

use itertools::Itertools;

fn differences(nums: &[i32]) -> Vec<i32> {
    nums.iter()
        .tuple_windows()
        .map(|(left, right)| right - left)
        .collect()
}

fn next_num(nums: &[i32]) -> i32 {
    if nums.iter().all(|&n| n == 0) {
        return 0;
    }
    let differences: Vec<i32> = differences(nums);
    next_num(&differences) + nums.iter().last().unwrap()
}

pub fn part_1(input: &str) -> i32 {
    input.lines().map(|line| next_num(&nums(line))).sum()
}

Part 2

If we can figure out the next number in a sequence, how about the previous number?

The question asks what the sum is of all previous values.

Some copy pasting, some minor changes, and voila!

Now a previous number is the difference between a first number and the previous number from the next line.

The third line in the example again, with special attention to the first number of each line:

5  10  13  16  21  30  45
  5   3   3   5   9  15
   -2   0   2   4   6
      2   2   2   2
        0   0   0

5 = 10 - 5
5 = 3 - -2
-2 = 0 - 2
0 = 0

Option 1: imperative

I only coded the version that reuses memory, the other one is trivial to make from this one.

Code

pub fn part_1(input: &str) -> i32 {
    let mut nums: Vec<i32> = Vec::new();
    let mut differences: Vec<i32> = Vec::new();
    let mut edge: Vec<i32> = Vec::new();

    input
        .lines()
        .map(|line| {
            nums.clear();
            for num in line.split_ascii_whitespace() {
                nums.push(num.parse().unwrap());
            }

            edge.clear();

            loop {
                differences.clear();
                for i in nums.windows(2) {
                    differences.push(i[1] - i[0]);
                }
                edge.push(nums[nums.len() - 1]);
                if differences.iter().all(|&x| x == 0) {
                    let sum: i32 = edge.iter().sum();
                    break sum;
                }
                std::mem::swap(&mut nums, &mut differences);
            }
        })
        .sum()
}

Option 2: recursive

The nums helper gets reused.
The differences helper gets reused.
The next_num helper gets replaced by a prev_num one.

Code

use itertools::Itertools;

fn nums(s: &str) -> Vec<i32> {
    s.split_whitespace()
        .filter_map(|s| s.parse().ok())
        .collect()
}

fn prev_num(nums: &[i32]) -> i32 {
    if nums.iter().all(|&n| n == 0) {
        return 0;
    }
    let differences = differences(nums);
    nums[0] - prev_num(&differences)
}

pub fn part_2(input: &str) -> i32 {
    input.lines().map(|line| prev_num(&nums(line))).sum()
}

Final code

Imperative

pub fn part_1(input: &str) -> i32 {
    let mut nums: Vec<i32> = Vec::new();
    let mut differences: Vec<i32> = Vec::new();
    let mut edge: Vec<i32> = Vec::new();

    input
        .lines()
        .map(|line| {
            nums.clear();
            for num in line.split_ascii_whitespace() {
                nums.push(num.parse().unwrap());
            }

            edge.clear();

            loop {
                differences.clear();
                for i in nums.windows(2) {
                    differences.push(i[1] - i[0]);
                }
                edge.push(nums[nums.len() - 1]);
                if differences.iter().all(|&x| x == 0) {
                    let sum: i32 = edge.iter().sum();
                    break sum;
                }
                std::mem::swap(&mut nums, &mut differences);
            }
        })
        .sum()
}

pub fn part_2(input: &str) -> i32 {
    let mut nums: Vec<i32> = Vec::new();
    let mut differences: Vec<i32> = Vec::new();
    let mut edge: Vec<i32> = Vec::new();

    input
        .lines()
        .map(|line| {
            nums.clear();
            for num in line.split_ascii_whitespace() {
                nums.push(num.parse().unwrap());
            }

            edge.clear();

            loop {
                differences.clear();
                for i in nums.windows(2) {
                    differences.push(i[0] - i[1]);
                }
                edge.push(nums[0]);
                if differences.iter().all(|&x| x == 0) {
                    let sum: i32 = edge.iter().sum();
                    break sum;
                }
                std::mem::swap(&mut nums, &mut differences);
            }
        })
        .sum()
}

Recursion

use itertools::Itertools;

fn nums(s: &str) -> Vec<i32> {
    s.split_whitespace()
        .filter_map(|s| s.parse().ok())
        .collect()
}

fn differences(nums: &[i32]) -> Vec<i32> {
    nums.iter()
        .tuple_windows()
        .map(|(left, right)| right - left)
        .collect()
}

fn next_num(nums: &[i32]) -> i32 {
    if nums.iter().all(|&n| n == 0) {
        return 0;
    }
    let differences: Vec<i32> = differences(nums);
    next_num(&differences) + nums.iter().last().unwrap()
}

pub fn part_1(input: &str) -> i32 {
    input.lines().map(|line| next_num(&nums(line))).sum()
}

fn prev_num(nums: &[i32]) -> i32 {
    if nums.iter().all(|&n| n == 0) {
        return 0;
    }
    let differences = differences(nums);
    nums[0] - prev_num(&differences)
}

pub fn part_2(input: &str) -> i32 {
    input.lines().map(|line| prev_num(&nums(line))).sum()
}

Advent of Code 2023 Day 8

Nicky Meuleman — Fri, 08 Dec 2023 23:20:53 +0000

Day 8: Haunted Wasteland

https://adventofcode.com/2023/day/8

You are still riding a camel on Desert Island.
A sandstorm is coming and you need to make yourself scarce, quickly.

Your guide just finished warning you about ghosts too, very spooky an not at all foreshadowing, nuh-uh.

Your puzzle input today is a piece of paper labeled "maps", you use those maps to get out of there.

The first line is a list of left/right instructions.

The following block are a bunch of key = value pairs where a value is written as (left, right).

An example input looks like this:

RL

AAA = (BBB, CCC)
BBB = (DDD, EEE)
CCC = (ZZZ, GGG)
DDD = (DDD, DDD)
EEE = (EEE, EEE)
GGG = (GGG, GGG)
ZZZ = (ZZZ, ZZZ)

The first line in the input tells you to go right first, then left.

The letter combinations in the map are locations.
Each location leads to two other locations, one if you go left, and one if you go right.

Part 1

You start at location AAA and want to go to location ZZZ.

If you follow the instructions over and over, you will get to ZZZ eventually.

The question asks how many steps it takes to get to ZZZ if you start at AAA.

I chose to parse the input into Rust structs again.
The top line of the input turns into a list of Instruction.

enum Instruction {
    Left,
    Right,
}

The map in the input turns into a HashMap with a position as key, and a Destinations struct as value.

struct Destinations<'a> {
    left: &'a str,
    right: &'a str,
}

The actual logic for this part was straightforward.
I kept track of a curr variable that stores the location I'm currently at, it starts at "AAA".

Then I loop until my current location is "ZZZ".

For every iteration, I pull an instruction from the initial list of instructions I made repeat endlessly.
I apply that instruction and update the step count.

Code

use std::collections::HashMap;

enum Instruction {
    Left,
    Right,
}

struct Destinations<'a> {
    left: &'a str,
    right: &'a str,
}

pub fn part_1(input: &str) -> u32 {
    let (instructions, map) = input.split_once("\n\n").unwrap();
    let instructions = instructions.chars().map(|c| match c {
        'L' => Instruction::Left,
        'R' => Instruction::Right,
        _ => panic!("at the disco"),
    });
    let map: HashMap<&str, Destinations> = map
        .lines()
        .map(|line| {
            let (source, destinations) = line.split_once(" = ").unwrap();
            let destinations = destinations
                .strip_prefix("(")
                .unwrap()
                .strip_suffix(")")
                .unwrap();
            let destinations = destinations.split_once(", ").unwrap();
            (
                source,
                Destinations {
                    left: destinations.0,
                    right: destinations.1,
                },
            )
        })
        .collect();

    let mut instructions = instructions.cycle();
    let mut steps = 0;
    let mut curr = "AAA";

    while curr != "ZZZ" {
        let ins = instructions.next().unwrap();
        let Destinations { left, right } = map.get(curr).unwrap();
        curr = match ins {
            Instruction::Left => left,
            Instruction::Right => right,
        };
        steps += 1;
    }

    steps
}

Part 2

The map isn't for people, it's for ghosts!

The number of nodes with names ending in A is equal to the number ending in Z!

If you were a ghost, you would start at all nodes ending with an A simultaneously and follow each path until they all end in a Z at the same time.

Each ghost has a different starting point
Each ghost follows the same instruction

In the example:

LR

11A = (11B, XXX)
11B = (XXX, 11Z)
11Z = (11B, XXX)
22A = (22B, XXX)
22B = (22C, 22C)
22C = (22Z, 22Z)
22Z = (22B, 22B)
XXX = (XXX, XXX)

There are 2 ghosts:

Starts at 11A
Starts at 22A

Following the instructions until all ghosts end up at a location ending in Z:

Step 0: You are at 11A and 22A.
Step 1: You choose all of the left paths, leading you to 11B and 22B.
Step 2: You choose all of the right paths, leading you to 11Z and 22C.
Step 3: You choose all of the left paths, leading you to 11B and 22Z.
Step 4: You choose all of the right paths, leading you to 11Z and 22B.
Step 5: You choose all of the left paths, leading you to 11B and 22C.
Step 6: You choose all of the right paths, leading you to 11Z and 22Z.

The question asks how many steps it takes before all ghosts are on nodes that end with Z?

I attempted to use the same code as in part1, and slightly modify it, but alas.
Today is a day that is not going to be solved by brute-force in any reasonable time.

It turns out today's input is specially crafted.
The guiding text gives us some hints, but the specifics remain for us to discover (or, if you're like me, look up).

It looks like part2 is the traditional cycle detection problem! Advent of Code has one every year. (or most years anyway)

Like AoC 2022 day 17 part 2, which I also have a blogpost on
Or AoC 2017 day 16 part 2, my solution code

Back to how the input is special, and how you can use that fact.

The first clue is in the guiding text:

The number of steps it takes for a ghost to get to the end is a clean multiple of the instruction length for every ghost.

Each ghost has a seperate ending point, and never visits other ending points.

All ghosts loop back around to their starting point, and then to their starting point, and then their ending point, until infinity.

Every last location leads to the second location that ghost ever visited.
That means every loop a ghost does is identical in length.

tl;dr: Every ghost is on their own loop, they go round, and round, eventually all standing on a location that ends in a Z.

All this put together means that, for every ghost you figure out how long it takes until they reach their ending location.
A time where all ghosts are at their ending location at the same time is the least common multiple of all those numbers.

To find that, I first found the greatest common divisor using the Euclidian algorithm

In code, I kept track of how many full instruction lines were executed.

Every time I execute a full set of instructions (the first line of the input without repeating),
I check if any ghosts are at their ending, and keep track of how many sets of instructions it took.

Code

use std::collections::HashMap;

enum Instruction {
    Left,
    Right,
}

struct Destinations<'a> {
    left: &'a str,
    right: &'a str,
}

struct Ghost<'a> {
    pos: &'a str,
    cycles: Option<u64>,
}

fn gcd(mut a: u64, mut b: u64) -> u64 {
    while b != 0 {
        let tmp = a;
        a = b;
        b = tmp % b;
    }
    a
}

fn lcm(a: u64, b: u64) -> u64 {
    a * b / gcd(a, b)
}

pub fn part_2(input: &str) -> u64 {
    let (instructions, map) = input.split_once("\n\n").unwrap();
    let instructions: Vec<Instruction> = instructions
        .chars()
        .map(|c| match c {
            'L' => Instruction::Left,
            'R' => Instruction::Right,
            _ => panic!("at the disco"),
        })
        .collect();
    let map: HashMap<&str, Destinations> = map
        .lines()
        .map(|line| {
            let (source, destinations) = line.split_once(" = ").unwrap();
            let destinations = destinations
                .strip_prefix("(")
                .unwrap()
                .strip_suffix(")")
                .unwrap();
            let destinations = destinations.split_once(", ").unwrap();
            (
                source,
                Destinations {
                    left: destinations.0,
                    right: destinations.1,
                },
            )
        })
        .collect();

    let mut cycle_count = 0;
    let mut ghosts: Vec<Ghost> = map
        .keys()
        // start from all positions ending in 'A'
        .filter(|source| source.ends_with('A'))
        // map every location to a location with a cycle count
        .map(|pos| Ghost { pos, cycles: None })
        .collect();

    while ghosts.iter().any(|ghost| ghost.cycles.is_none()) {
        // Do a full cycle of instructions
        for ins in &instructions {
            for Ghost { pos, cycles } in ghosts.iter_mut() {
                if cycles.is_some() {
                    // this loop already has a known cycle length, no need to simulate further
                    continue;
                }
                let Destinations { left, right } = map.get(pos).unwrap();
                *pos = match ins {
                    Instruction::Left => left,
                    Instruction::Right => right,
                };
            }
        }
        cycle_count += 1;

        // after a full cycle of instructions, save any found cycles (ghosts that arrived at a destination)
        for Ghost { pos, cycles: cycle } in ghosts.iter_mut() {
            if cycle.is_some() {
                // already has a known cycle, no need to update
                continue;
            }
            if pos.ends_with('Z') {
                *cycle = Some(cycle_count);
            }
        }
    }

    let min_shared_cycles = ghosts
        .into_iter()
        .filter_map(|ghost| ghost.cycles)
        .fold(1, |acc, item| lcm(acc, item));

    min_shared_cycles * instructions.len() as u64
}

Final code

use std::collections::HashMap;

enum Instruction {
    Left,
    Right,
}

struct Destinations<'a> {
    left: &'a str,
    right: &'a str,
}

pub fn part_1(input: &str) -> u32 {
    let (instructions, map) = input.split_once("\n\n").unwrap();
    let instructions = instructions.chars().map(|c| match c {
        'L' => Instruction::Left,
        'R' => Instruction::Right,
        _ => panic!("at the disco"),
    });
    let map: HashMap<&str, Destinations> = map
        .lines()
        .map(|line| {
            let (source, destinations) = line.split_once(" = ").unwrap();
            let destinations = destinations
                .strip_prefix("(")
                .unwrap()
                .strip_suffix(")")
                .unwrap();
            let destinations = destinations.split_once(", ").unwrap();
            (
                source,
                Destinations {
                    left: destinations.0,
                    right: destinations.1,
                },
            )
        })
        .collect();

    let mut instructions = instructions.cycle();
    let mut steps = 0;
    let mut curr = "AAA";

    while curr != "ZZZ" {
        let ins = instructions.next().unwrap();
        let Destinations { left, right } = map.get(curr).unwrap();
        curr = match ins {
            Instruction::Left => left,
            Instruction::Right => right,
        };
        steps += 1;
    }

    steps
}

struct Ghost<'a> {
    pos: &'a str,
    cycles: Option<u64>,
}

fn gcd(mut a: u64, mut b: u64) -> u64 {
    while b != 0 {
        let tmp = a;
        a = b;
        b = tmp % b;
    }
    a
}

fn lcm(a: u64, b: u64) -> u64 {
    a * b / gcd(a, b)
}

pub fn part_2(input: &str) -> u64 {
    let (instructions, map) = input.split_once("\n\n").unwrap();
    let instructions: Vec<Instruction> = instructions
        .chars()
        .map(|c| match c {
            'L' => Instruction::Left,
            'R' => Instruction::Right,
            _ => panic!("at the disco"),
        })
        .collect();
    let map: HashMap<&str, Destinations> = map
        .lines()
        .map(|line| {
            let (source, destinations) = line.split_once(" = ").unwrap();
            let destinations = destinations
                .strip_prefix("(")
                .unwrap()
                .strip_suffix(")")
                .unwrap();
            let destinations = destinations.split_once(", ").unwrap();
            (
                source,
                Destinations {
                    left: destinations.0,
                    right: destinations.1,
                },
            )
        })
        .collect();

    let mut cycle_count = 0;
    let mut ghosts: Vec<Ghost> = map
        .keys()
        // start from all positions ending in 'A'
        .filter(|source| source.ends_with('A'))
        // map every location to a location with a cycle count
        .map(|pos| Ghost { pos, cycles: None })
        .collect();

    while ghosts.iter().any(|ghost| ghost.cycles.is_none()) {
        // Do a full cycle of instructions
        for ins in &instructions {
            for Ghost { pos, cycles } in ghosts.iter_mut() {
                if cycles.is_some() {
                    // this loop already has a known cycle length, no need to simulate further
                    continue;
                }
                let Destinations { left, right } = map.get(pos).unwrap();
                *pos = match ins {
                    Instruction::Left => left,
                    Instruction::Right => right,
                };
            }
        }
        cycle_count += 1;

        // after a full cycle of instructions, save any found cycles (ghosts that arrived at a destination)
        for Ghost { pos, cycles: cycle } in ghosts.iter_mut() {
            if cycle.is_some() {
                // already has a known cycle, no need to update
                continue;
            }
            if pos.ends_with('Z') {
                *cycle = Some(cycle_count);
            }
        }
    }

    let min_shared_cycles = ghosts
        .into_iter()
        .filter_map(|ghost| ghost.cycles)
        .fold(1, |acc, item| lcm(acc, item));

    min_shared_cycles * instructions.len() as u64
}

Advent of Code 2023 Day 7

Nicky Meuleman — Thu, 07 Dec 2023 23:54:43 +0000

Day 7: Camel Cards

https://adventofcode.com/2023/day/7

You arrive at Desert Island, an elf is there waiting to take you to your destination.
A trip by camel!

The elf wants to play a game while travelling appropriately named camel cards.

It's similar to poker, but a bit simpler, because that makes it easier to play while riding a camel.

You get a list of hands of cards.
You need to order those hands based on the strength of each hand.

A hand consists of five cards.

The cards are all one of:

Each hand of 5 cards has a type of:

Five of a kind

All cards have the same label.

eg: AAAAA
Four of a kind

Four cards have the same label.

eg: AA8AA
Full House

Three cards have the same label, the two other cards have the same label.

eg: 23332
Three of a kind

Three cards have the same label.

eg: TTT98
Two pair

Two cards have the same label.

Two other cards also have the same label.

eg: 23432
One pair

Two cards have the same label.

eg: A23A4
High card

All card labels are different.

eg: 23456

Each hand has a bid associated with it, it number.

If two hands have the same type, their order is determined by looking which hand has a stronger card first.

eg: hand1 is 33332, and hand2 is 2AAAA.

Both hands have the same type (four of a kind).
33332 is stronger because the first card is stronger.
If the first card is identical, the second card is compared, and so forth until one hand is stronger (two hands being completely identical never happens in the input).

Today's input is a list of hands with their corresponding bids.

An example input looks like this:

32T3K 765
T55J5 684
KK677 28
KTJJT 220
QQQJA 483

Part 1

Order the hands in the input.

The weakest hand gets rank 1, the next one rank 2, and so on.

For each hand, multiply its rank by its bid to determine the hands winnings.

The question asks you determine the total winnings for all hands.

Option 1: lots of functions

Starting with some pseudo/skeleton-code again:

input
    .lines()
    .map(/* turn a line into a (cards, bid) pair*/)
    .sorted()
    .map(/* multiply rank with bid */)
    .sum()

Helpers

I chose to represent the value of a single card as a number, ordered like the question specifies.

fn card_value(c: char) -> usize {
    "23456789TJQKA".chars().position(|card| card == c).unwrap()
}

To score a single hand, I used a list of 2 sorted numbers:

The amount of cards that appear the most often
The amount of cards that appears the 2nd most often

Some examples:

[3, 2] represents a hand with 3 cards of equal value, and 2 cards with a different identical value
[3, 1] represents a hand with 3 cards of equal value, and 1 card with a different value. (not represented is the last card that also has a different value)
[5, 0] represents a hand with 5 cards of equal value.
[2, 2] represents a hand with 2 pairs.

fn hand_score(hand: &str) -> [u8; 2] {
    let mut faces = [0_u8; 13];
    for c in hand.chars() {
        faces[card_value(c)] += 1;
    }
    faces.sort_unstable();
    let mut score: [u8; 2] = faces[11..].try_into().unwrap();
    score.reverse();
    score
}

And finally, using those building blocks, a way to compare 2 hands and determine which one is stronger.

fn compare_hands(a: &str, b: &str) -> Ordering {
    hand_score(a).cmp(&hand_score(b)).then_with(|| {
        let (a, b) = a
            .chars()
            .zip(b.chars())
            .find(|(a, b)| a != b)
            .expect("hands are completely identical");

        card_value(a).cmp(&card_value(b))
    })
}

Code

use itertools::Itertools;
use std::cmp::Ordering;

pub fn part_1(input: &str) -> usize {
    input
        .lines()
        .map(|line| {
            let (hand, bid) = line.split_once(" ").unwrap();
            (hand, bid)
        })
        .sorted_by(|(a, _), (b, _)| compare_hands(a, b))
        .enumerate()
        .map(|(idx, (_, bid))| (idx + 1) * bid.parse::<usize>().unwrap())
        .sum()
}

fn compare_hands(a: &str, b: &str) -> Ordering {
    hand_score(a).cmp(&hand_score(b)).then_with(|| {
        let (a, b) = a
            .chars()
            .zip(b.chars())
            .find(|(a, b)| a != b)
            .expect("hands are completely identical");

        card_value(a).cmp(&card_value(b))
    })
}

fn hand_score(hand: &str) -> [u8; 2] {
    let mut faces = [0_u8; 13];
    for c in hand.chars() {
        faces[card_value(c)] += 1;
    }
    faces.sort_unstable();
    let mut score: [u8; 2] = faces[11..].try_into().unwrap();
    score.reverse();
    score
}

fn card_value(c: char) -> usize {
    "23456789TJQKA".chars().position(|card| card == c).unwrap()
}

Option 2: structures

I like to put data in neat structures.
Rust structs are great.

Because the input is a string, I store references to that string in those structures.
Those need a lifetime, and that's that 'a stuff you see all over the place.

I'm not going deep into what that means in this post, but in a nutshell it means "this string is valid while this structure exists".

By Implementing Ord we tell Rust those structures can be ordered.

Code

use itertools::Itertools;
use std::cmp::Ordering;

#[derive(PartialEq, Eq)]
struct Hand<'a> {
    cards: &'a str,
    bid: u32,
}

impl<'a> Hand<'a> {
    fn score(&self) -> [u8; 2] {
        let mut faces = [0; 13];
        for c in self.cards.chars() {
            faces[card_value(c)] += 1;
        }
        faces.sort_unstable();
        let mut score: [u8; 2] = faces[11..].try_into().unwrap();
        score.reverse();
        score
    }
}

impl<'a> PartialOrd for Hand<'a> {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        Some(self.cmp(other))
    }
}

impl<'a> Ord for Hand<'a> {
    fn cmp(&self, other: &Self) -> Ordering {
        self.score().cmp(&other.score()).then_with(|| {
            let (a, b) = self
                .cards
                .chars()
                .zip(other.cards.chars())
                .find(|(a, b)| a != b)
                .expect("hands are completely identical");

            card_value(a).cmp(&card_value(b))
        })
    }
}

pub fn part_1(input: &str) -> u32 {
    input
        .lines()
        .map(|line| {
            let (cards, bid) = line.split_once(" ").unwrap();
            Hand {
                cards,
                bid: bid.parse().unwrap(),
            }
        })
        .sorted_unstable()
        .enumerate()
        .map(|(idx, turn)| (idx as u32 + 1) * turn.bid)
        .sum()
}

Option 3: getting shifty

I didn't implement this but you can also represent a hand as a single number.

4 bits represent each card.
The starting bits represent the type of hand (from five of a kind to high card).

This would work by determining the value of each card, and shifting bits to represent that value onto a number.
Then, shift a value representing the type of the hand onto the front of the same number.

Sorting those numbers would apply the sorting logic described where it sorts based on the type of hand first, and on the individual cards next.

Part 2

There is a second way to play this game.

The J cards are now jokers, wildcards that can act like any other card.

You can use these jokers in a hand to make a stronger type of hand.

To balance this, the J card is now the weakest card.

This causes a few adjustments to the code from part1.

Helpers

The function to determine the value of a single card:

fn card_value2(c: char) -> usize {
    "J23456789TQKA".chars().position(|card| card == c).unwrap()
}

The function to score a hand:

fn hand_score2(hand: &str) -> [u8; 2] {
    let mut faces = [0; 13];
    let mut jokers = 0;
    for c in hand.chars() {
        if c == 'J' {
            jokers += 1;
        } else {
            faces[card_value2(c)] += 1;
        }
    }
    faces.sort_unstable();
    let mut score: [u8; 2] = faces[11..].try_into().unwrap();
    score.reverse();
    // add the amount of jokers to the counts of the card that occurs the most already to increase the hand score
    score[0] += jokers;
    score
}

The function to compare 2 hands:

fn compare_hands2(a: &str, b: &str) -> Ordering {
    hand_score2(a).cmp(&hand_score2(b)).then_with(|| {
        let (a, b) = a
            .chars()
            .zip(b.chars())
            .find(|(a, b)| a != b)
            .expect("hands are completely identical");

        card_value2(a).cmp(&card_value2(b))
    })
}

The result is nearly identical code to part one.
It would be trivial to implement a boolean flag and combine these 2 version into one, but I had somewhere to go and copy-pasting was faster.

Code

use itertools::Itertools;
use std::cmp::Ordering;

pub fn part_2(input: &str) -> usize {
    input
        .lines()
        .map(|line| {
            let (hand, bid) = line.split_once(" ").unwrap();
            (hand, bid)
        })
        .sorted_by(|(a, _), (b, _)| compare_hands2(a, b))
        .enumerate()
        .map(|(idx, (_, bid))| (idx + 1) * bid.parse::<usize>().unwrap())
        .sum()
}

fn compare_hands2(a: &str, b: &str) -> Ordering {
    hand_score2(a).cmp(&hand_score2(b)).then_with(|| {
        let (a, b) = a
            .chars()
            .zip(b.chars())
            .find(|(a, b)| a != b)
            .expect("hands are completely identical");

        card_value2(a).cmp(&card_value2(b))
    })
}

fn hand_score2(hand: &str) -> [u8; 2] {
    let mut faces = [0; 13];
    let mut jokers = 0;
    for c in hand.chars() {
        if c == 'J' {
            jokers += 1;
        } else {
            faces[card_value2(c)] += 1;
        }
    }
    faces.sort_unstable();
    let mut score: [u8; 2] = faces[11..].try_into().unwrap();
    score.reverse();
    // add the amount of jokers to the counts of the card that occurs the most already to increase the hand score
    score[0] += jokers;
    score
}

fn card_value2(c: char) -> usize {
    "J23456789TQKA".chars().position(|card| card == c).unwrap()
}

Final code

use itertools::Itertools;
use std::cmp::Ordering;

#[derive(PartialEq, Eq)]
struct Hand<'a> {
    cards: &'a str,
    bid: u32,
}

impl<'a> Hand<'a> {
    fn score(&self) -> [u8; 2] {
        let mut faces = [0; 13];
        for c in self.cards.chars() {
            faces[card_value(c)] += 1;
        }
        faces.sort_unstable();
        let mut score: [u8; 2] = faces[11..].try_into().unwrap();
        score.reverse();
        score
    }
}

impl<'a> PartialOrd for Hand<'a> {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        Some(self.cmp(other))
    }
}

impl<'a> Ord for Hand<'a> {
    fn cmp(&self, other: &Self) -> Ordering {
        self.score().cmp(&other.score()).then_with(|| {
            let (a, b) = self
                .cards
                .chars()
                .zip(other.cards.chars())
                .find(|(a, b)| a != b)
                .expect("hands are completely identical");

            card_value(a).cmp(&card_value(b))
        })
    }
}

pub fn part_1(input: &str) -> u32 {
    input
        .lines()
        .map(|line| {
            let (cards, bid) = line.split_once(" ").unwrap();
            Hand {
                cards,
                bid: bid.parse().unwrap(),
            }
        })
        .sorted_unstable()
        .enumerate()
        .map(|(idx, turn)| (idx as u32 + 1) * turn.bid)
        .sum()
}

#[derive(PartialEq, Eq)]
struct Hand2<'a> {
    cards: &'a str,
    bid: u32,
}

impl<'a> Hand2<'a> {
    fn score(&self) -> [u8; 2] {
        let mut faces = [0; 13];
        let mut jokers = 0;
        for c in self.cards.chars() {
            if c == 'J' {
                jokers += 1;
            } else {
                faces[card_value2(c)] += 1;
            }
        }
        faces.sort_unstable();
        let mut score: [u8; 2] = faces[11..].try_into().unwrap();
        score.reverse();
        // add the amount of jokers to the counts of the card that occurs the most already to increase the hand score
        score[0] += jokers;
        score
    }
}

impl<'a> PartialOrd for Hand2<'a> {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        Some(self.cmp(other))
    }
}

impl<'a> Ord for Hand2<'a> {
    fn cmp(&self, other: &Self) -> Ordering {
        self.score().cmp(&other.score()).then_with(|| {
            let (a, b) = self
                .cards
                .chars()
                .zip(other.cards.chars())
                .find(|(a, b)| a != b)
                .expect("hands are completely identical");

            card_value2(a).cmp(&card_value2(b))
        })
    }
}

pub fn part_2(input: &str) -> u32 {
    input
        .lines()
        .map(|line| {
            let (cards, bid) = line.split_once(" ").unwrap();
            Hand2 {
                cards,
                bid: bid.parse().unwrap(),
            }
        })
        .sorted_unstable()
        .enumerate()
        .map(|(idx, turn)| (idx as u32 + 1) * turn.bid)
        .sum()
}

fn card_value(c: char) -> usize {
    "23456789TJQKA".chars().position(|card| card == c).unwrap()
}

fn card_value2(c: char) -> usize {
    "J23456789TQKA".chars().position(|card| card == c).unwrap()
}