Introduction

This book will serve as a reference for the thought-process of each solution.

Hopefully I will be able to maintain at least a modicum of explanation for the solution of each day.

Day 1

Day 1 is mostly related to extracting numbers from a stream of chars.

Part One

This is a simple filter, iterating over the chars and getting those that can be parsed to digits.

#![allow(unused)]
fn main() {
use anyhow::{anyhow, Result};

fn parse_line(line: &str) -> Result<u32> {
    let mut numbers = line.chars().filter_map(|c| c.to_digit(10)).peekable();

    let first = *numbers
        .peek()
        .ok_or(anyhow!("Line {line} missing a number."))?;
    let last = numbers
        .last()
        .ok_or(anyhow!("Line {line} missing a number."))?;

    Ok(10 * first + last)
}
}

The only way to mess up the first part would be to do something like filtering out all values between the first and the last, because then things like akjsdk3ksdj would not become "33", but only "3" instead. But most organic solutions will naturally deal with this edge case.

Part Two

This part is more problematic than it appears. The first immediate thought is just replacing the spelled out names with the numbers, e.g. onelvjxcthree -> 1lvjxc3, and then proceeding with the first part.

However, this fails due to the main friction of part two: characters can be reused for different numbers, e.g. sevenine becomes 79.

So, the initial idea that I had was to replace the spelled out number with the spelled out number + the number itself. It wasn't apparently clear why it didn't work, but the very same example above should make it obvious: sevenine would become seven7ine in the first replacement, which would not generate the nine. Curiously, if 9 came before seven in the iteration of the replacemens, there would be no problem!

Then next idea would be to maybe put the number in the middle of the word, but that has some problems:

It relies fundamentally in happenstances of the English language which might have to result in refactorings in case we switched the language;
It creates new Strings every time we replace, with needless memory allocation.

Instead of doing that, I just ran a window through the string, capturing if it starts with a number, and pushed the numbers coming from those windows to one single Vec. If the window began with a char that is a number, I'd also add that to the Vec.

#![allow(unused)]
fn main() {
fn transform_line(line: &str) -> Vec<u32> {
    let mut numbers = Vec::new();

    // Adding gibberish at the end just to guarantee comfortable buffering.
    let fake_line = line.to_string() + "AAAAA";

    for i in 0..line.len() {
        for (j, spelled_out_number) in SPELLED_OUT_NUMBERS.iter().enumerate() {
            if fake_line[i..(i + 5)].starts_with(spelled_out_number) {
                numbers.push(j as u32 + 1);
                break;
            }
        }

        if let Some(x) = fake_line[i..(i + 5)]
            .chars()
            .next()
            .expect("Should not be empty given that it has AAAAA at the end")
            .to_digit(10)
        {
            numbers.push(x);
        }
    }

    numbers
}
}

This solves the problem, but let's make a change before moving on: the whole AAAAA addition together with windows of length five is completely unnecessary, of course. Also, using windows of length five couples our solution to english as well; indeed, "quatro", which is "four" in Portuguese, already would violate that.

#![allow(unused)]
fn main() {
fn transform_line(line: &str) -> Vec<u32> {
    let mut numbers = Vec::new();

    for i in 0..line.len() {
        for (j, spelled_out_number) in SPELLED_OUT_NUMBERS.iter().enumerate() {
            if line[i..].starts_with(spelled_out_number) {
                numbers.push(j as u32 + 1);
                break;
            }
        }

        if let Some(x) = line[i..]
            .chars()
            .next()
            .expect("Should not be empty given that i < line.len()")
            .to_digit(10)
        {
            numbers.push(x);
        }
    }

    numbers
}
}

Note that even though we are slicing for the whole rest of the &str, this does not give any performance deficit: we are dealing with references and starts_with only iterates on what it needs. Getting the first char also only goes into the very beginning of the slice.

Day 2

This is a great problem for setting up some structure!

First of all, our cubes have three colors: "red", "green" and "blue".

Those cubes are revealed as sets in a given game, where each game might have an arbitrary number of such sets.

Then, those games are communicated as lines in the following format:

Game 1: 3 blue, 4 red; 1 red, 2 green, 6 blue; 2 green
Game 2: 1 blue, 2 green; 3 green, 4 blue, 1 red; 1 green, 1 blue
Game 3: 8 green, 6 blue, 20 red; 5 blue, 4 red, 13 green; 5 green, 1 red
Game 4: 1 green, 3 red, 6 blue; 3 green, 6 red; 3 green, 15 blue, 14 red
Game 5: 6 red, 1 blue, 3 green; 2 blue, 1 red, 2 green

So we need some parsing as well. All in all, the idea is to build:

A Color enum
A Set struct containing information about the colors present in the Set
A Game struct with a vec of such sets
Parsing of each line

For point number 2 above, I decided to go with a HashMap directly for simplicity and in order to be able to think separately about the parsing and the rest, but there is no need for extra memory allocation: we should be able to handle this by embedding the count in the enum itself. Let's refactor this later, though, together with the error handling and for now let's show the submission how it was done.

Part One

Setting up the whole structure is the most problematic aspect of part one, as the logic is trivial: we want to check that the constraints are valid in each set of a game.

For the cubes, we have the following:

#![allow(unused)]
fn main() {
const RED_CUBES: usize = 12;
const GREEN_CUBES: usize = 13;
const BLUE_CUBES: usize = 14;

#[derive(Hash, PartialEq, Eq, Clone, Copy, Debug)]
enum Color {
    Red,
    Green,
    Blue,
}

impl FromStr for Color {
    type Err = anyhow::Error;

    fn from_str(s: &str) -> Result<Self> {
        match s {
            "red" => Ok(Self::Red),
            "green" => Ok(Self::Green),
            "blue" => Ok(Self::Blue),
            _ => Err(anyhow!("Invalid color")),
        }
    }
}

impl Color {
    fn get_max(&self) -> usize {
        match self {
            Self::Red => RED_CUBES,
            Self::Green => GREEN_CUBES,
            Self::Blue => BLUE_CUBES,
        }
    }
}
}

For the Set, we have this:

#![allow(unused)]

fn main() {
#[derive(Debug)]
struct Set {
    cubes: HashMap<Color, usize>,
}

impl Set {
    fn is_possible(&self) -> bool {
        self.cubes.iter().all(|(k, v)| v <= &k.get_max())
    }
}
}

And for the Game, this:

#![allow(unused)]
fn main() {
#[derive(Debug)]
struct Game<'a> {
    id: &'a str,
    sets: Vec<Set>,
}

impl<'a> Game<'a> {
    fn is_possible(&self) -> bool {
        self.sets.iter().all(|set| set.is_possible())
    }
}
}

The above structure seems sensible, but the parsing below could use some improvement so that the syntax required from the lines is more self-evident.

#![allow(unused)]
fn main() {
fn parse_line(line: &str) -> Game {
    let line: Vec<&str> = line.split(&[':', ';']).collect();

    let id = line[0].split(' ').nth(1).expect("Game should have id");

    let mut sets = Vec::new();

    for set in &line[1..] {
        let mut cubes = HashMap::new();
        let cubes_as_strings: Vec<&str> = set.split(", ").map(|x| x.trim()).collect();

        for cube in cubes_as_strings {
            let (number, color) = cube
                .split_once(' ')
                .expect("Should have pair number, color");

            let color: Color = color.parse().expect("Color should exist");
            let number: usize = number.parse().expect("Number of cubes should make sense");

            cubes.insert(color, number);
        }

        let set = Set { cubes };
        sets.push(set);
    }

    Game { id, sets }
}
}

With our structure set up, the solution to part one becomes the following self-explanatory function:

#![allow(unused)]
fn main() {
fn solve_part_one(contents: &str) -> usize {
    contents
        .lines()
        .map(parse_line)
        .filter(|game| game.is_possible())
        .map(|game| {
            game.id
                .parse::<usize>()
                .expect("Id should be convertible to int")
        })
        .sum()
}
}

Part Two

Due to our structure, extending the code to contemplate part two is simple:

We need to extend Game to be able to return a Set with the max of each color.
Set should have a calculation of power.

For 1., we create the following method:

#![allow(unused)]
fn main() {
fn get_max_of_each_set(&self) -> Set {
    let mut result = HashMap::new();
    let max_red = self
        .sets
        .iter()
        .map(|set| set.cubes.get(&Color::Red).unwrap_or(&0))
        .max()
        .unwrap_or(&0);
    let max_blue = self
        .sets
        .iter()
        .map(|set| set.cubes.get(&Color::Blue).unwrap_or(&0))
        .max()
        .unwrap_or(&0);
    let max_green = self
        .sets
        .iter()
        .map(|set| set.cubes.get(&Color::Green).unwrap_or(&0))
        .max()
        .unwrap_or(&0);

    result.insert(Color::Red, *max_red);
    result.insert(Color::Blue, *max_blue);
    result.insert(Color::Green, *max_green);

    Set { cubes: result }
}
}

It is a little verbose but straightforward.

For 2., we just add the following method to Set:

#![allow(unused)]
fn main() {
fn get_power(&self) -> usize {
    self.cubes.values().fold(1, |acc, e| acc * e) // Should just be .product().
}
}

And now for the solution we can just run:

#![allow(unused)]
fn main() {
fn solve_part_two(contents: &str) -> usize {
    contents
        .lines()
        .map(parse_line)
        .map(|game| game.get_max_of_each_set())
        .map(|set| set.get_power())
        .sum()
}
}

Refactoring Part Two

Let's now change the two points that I alluded to before:

Remove the HashMap.
Better error handling.

Before moving on, it is worth mentioning that removing the HashMap is a non-trivial trade-off. Indeed, if we ever needed to accept arbitrary color names at run time, we would need to go back to HashMap.

But getting rid of the HashMap allows us to reduce heap usage and optimize our code in general.

For the first part, we do the following changes:

#[derive(Hash, PartialEq, Eq, Clone, Copy, Debug)]
enum Color {
-    Red,
-    Green,
-    Blue,
+    Red(usize),
+    Green(usize),
+    Blue(usize),
}

We will encode the number of cubes, and parse the relevant strings into this format.

Indeed, this is our new parsing:

    fn from_str(s: &str) -> Result<Self> {
-        match s {
-            "red" => Ok(Self::Red),
-            "green" => Ok(Self::Green),
-            "blue" => Ok(Self::Blue),
-            _ => Err(anyhow!("Invalid color")),
-        }
+        let (num, color) = s
+            .split_once(' ')
+            .ok_or(anyhow!("Incorrect syntax for parsing {s}"))?;
+
+        let num = num.parse()?;
+
+        match color {
+            "red" => Ok(Self::Red(num)),
+            "green" => Ok(Self::Green(num)),
+            "blue" => Ok(Self::Blue(num)),
+            _ => Err(anyhow!("Invalid color")),
+        }
    }

And our set now changes to this:

#[derive(Debug)]
struct Set {
-    cubes: HashMap<Color, usize>,
+    red: usize,
+    green: usize,
+    blue: usize,
}

impl Set {
    fn is_possible(&self) -> bool {
-        self.cubes.iter().all(|(k, v)| v <= &k.get_max())
+        self.red <= RED_CUBES && self.green <= GREEN_CUBES && self.blue <= BLUE_CUBES
    }

    fn get_power(&self) -> usize {
-        self.cubes.values().product()
+        self.red * self.green * self.blue
    }
}

Our get_max_of_each_set changes to the the following:

    fn get_max_of_each_set(&self) -> Set {
-        let mut result = HashMap::new();
-        let max_red = self
-            .sets
-            .iter()
-            .map(|set| set.cubes.get(&Color::Red).unwrap_or(&0))
-            .max()
-            .unwrap_or(&0);
-        let max_blue = self
-            .sets
-            .iter()
-            .map(|set| set.cubes.get(&Color::Blue).unwrap_or(&0))
-            .max()
-            .unwrap_or(&0);
-        let max_green = self
-            .sets
-            .iter()
-            .map(|set| set.cubes.get(&Color::Green).unwrap_or(&0))
-            .max()
-            .unwrap_or(&0);
-
-        result.insert(Color::Red, *max_red);
-        result.insert(Color::Blue, *max_blue);
-        result.insert(Color::Green, *max_green);
-
-        Set { cubes: result }
+        let max_red = self.sets.iter().map(|set| set.red).max().unwrap_or(0);
+        let max_blue = self.sets.iter().map(|set| set.blue).max().unwrap_or(0);
+        let max_green = self.sets.iter().map(|set| set.green).max().unwrap_or(0);
+
+        Set {
+            red: max_red,
+            blue: max_blue,
+            green: max_green,
+        }
    }

And the bulk of our parsing changes like this:

    for set in &line[1..] {
-        let mut cubes = HashMap::new();
+        let mut red = 0;
+        let mut green = 0;
+        let mut blue = 0;

         let cubes_as_strings: Vec<&str> = set.split(", ").map(|x| x.trim()).collect();

         for cube in cubes_as_strings {
-            let (number, color) = cube
-                .split_once(' ')
-                .expect("Should have pair number, color");
-
-            let color: Color = color.parse().expect("Color should exist");
-            let number: usize = number.parse().expect("Number of cubes should make sense");
-
-            cubes.insert(color, number);
+            let color: Color = cube
+                .parse()
+                .expect("Cube should be a pair (number, color) but was {cube}");
+
+            match color {
+                Color::Red(x) => red = x,
+                Color::Green(x) => green = x,
+                Color::Blue(x) => blue = x,
+            }
        }

-        let set = Set { cubes };
+        let set = Set { red, green, blue };
         sets.push(set);
    }

For the error handling part, it is not very worth it to show the diffs, but it is worth it to mention that by flattening our iterators we avoid crashing during runtime. Errors are then logged so that we can see what may have gone wrong.

The whole code now reads as follows:

use std::str::FromStr;

use anyhow::{anyhow, Result};

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

const RED_CUBES: usize = 12;
const GREEN_CUBES: usize = 13;
const BLUE_CUBES: usize = 14;

#[derive(Debug)]
enum Color {
    Red(usize),
    Green(usize),
    Blue(usize),
}

impl FromStr for Color {
    type Err = anyhow::Error;

    fn from_str(s: &str) -> Result<Self> {
        let (num, color) = s
            .split_once(' ')
            .ok_or(anyhow!("Incorrect syntax for parsing {s}"))?;

        let num = num.parse()?;

        match color {
            "red" => Ok(Self::Red(num)),
            "green" => Ok(Self::Green(num)),
            "blue" => Ok(Self::Blue(num)),
            _ => Err(anyhow!("Invalid color")),
        }
    }
}

#[derive(Debug)]
struct Set {
    red: usize,
    green: usize,
    blue: usize,
}

impl Set {
    fn is_possible(&self) -> bool {
        self.red <= RED_CUBES && self.green <= GREEN_CUBES && self.blue <= BLUE_CUBES
    }

    fn get_power(&self) -> usize {
        self.red * self.green * self.blue
    }
}

#[derive(Debug)]
struct Game<'a> {
    id: &'a str,
    sets: Vec<Set>,
}

impl<'a> Game<'a> {
    fn is_possible(&self) -> bool {
        self.sets.iter().all(|set| set.is_possible())
    }

    fn get_max_of_each_set(&self) -> Set {
        let max_red = self.sets.iter().map(|set| set.red).max().unwrap_or(0);
        let max_blue = self.sets.iter().map(|set| set.blue).max().unwrap_or(0);
        let max_green = self.sets.iter().map(|set| set.green).max().unwrap_or(0);

        Set {
            red: max_red,
            blue: max_blue,
            green: max_green,
        }
    }
}

fn parse_line(line: &str) -> Result<Game> {
    let line: Vec<&str> = line.split(&[':', ';']).collect();

    let id = line[0]
        .split(' ')
        .nth(1)
        .ok_or(anyhow!("Error parsing id"))?;

    let mut sets = Vec::new();

    for set in &line[1..] {
        let mut red = 0;
        let mut green = 0;
        let mut blue = 0;

        let cubes_as_strings: Vec<&str> = set.split(", ").map(|x| x.trim()).collect();

        for cube in cubes_as_strings {
            let color: Color = cube.parse()?;

            match color {
                Color::Red(x) => red = x,
                Color::Green(x) => green = x,
                Color::Blue(x) => blue = x,
            }
        }

        let set = Set { red, green, blue };
        sets.push(set);
    }

    Ok(Game { id, sets })
}

pub fn solve_part_one(contents: &str) -> usize {
    contents
        .lines()
        .flat_map(|line| {
            parse_line(line).map_err(|e| {
                eprintln!("ERROR: Failed to parse line '{line}': {e}");
                e
            })
        })
        .filter(|game| game.is_possible())
        .flat_map(|game| {
            game.id.parse::<usize>().map_err(|e| {
                eprintln!("ERROR: Id '{}' can't be parsed into int: {e}", game.id);
                e
            })
        })
        .sum()
}

pub fn solve_part_two(contents: &str) -> usize {
    contents
        .lines()
        .flat_map(|line| {
            parse_line(line).map_err(|e| {
                eprintln!("ERROR: Failed to parse line '{line}': {e}");
                e
            })
        })
        .map(|game| game.get_max_of_each_set())
        .map(|game| game.get_power())
        .sum()
}
fn main() {
    println!("{}", solve_part_one(INPUT));
    println!("{}", solve_part_two(INPUT));
}

#[cfg(test)]
mod tests {
    use super::*;
    const TEST: &str = include_str!("../test_input.txt");

    #[test]
    fn it_works() {
        let line = "Game 1: 3 blue, 4 red; 1 red, 2 green, 6 blue; 2 green";
        println!("{:?}", parse_line(line));
    }

    #[test]
    fn part_one() {
        assert_eq!(solve_part_one(TEST), 8)
    }

    #[test]
    fn part_two() {
        assert_eq!(solve_part_two(TEST), 2286)
    }
}

Day 3

The code for this day ended up being very unwieldy and will require heavy refactoring.

Before displaying it, let's first think about the main problems/insights:

First of all, while building a matrix might seem like the first idea, it was much simpler to store the position of numbers and symbols separately.
Building the numbers from the parsing was a little bit uncomfortable, particularly considering that we wanted to parse everything: the numbers, the symbols and the empty spaces.
The full time complexity of the algorithm, if you simply disregard optimizing how we check who is close, is \(O(n^2)\). Gladly this was not a problem at all.

The next step is going to be refactoring the whole thing, both for performance and readability. This is the version of the code used for the submission itself:

use itertools::Itertools;

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

#[derive(Clone, Copy)]
enum Entry {
    Empty,
    Symbol(char),
    Digit(u32),
}

impl From<char> for Entry {
    fn from(value: char) -> Self {
        let parsed_value = value.to_digit(10);

        if let Some(x) = parsed_value {
            Self::Digit(x)
        } else {
            match value {
                '.' => Entry::Empty,
                x => Entry::Symbol(x),
            }
        }
    }
}

#[derive(Debug, Clone, Copy)]
struct PositionNumber {
    start_col: usize,
    line: usize,
    len: usize,
    number: u32,
}

impl PositionNumber {
    fn is_close(&self, symbol: &PositionSymbol) -> bool {
        for i in 0..self.len {
            if (self.start_col + i).abs_diff(symbol.col) <= 1
                && (self.line).abs_diff(symbol.line) <= 1
            {
                return true;
            }
        }

        false
    }
}

#[derive(Debug)]
struct PositionSymbol {
    col: usize,
    line: usize,
    symbol: char,
}

impl PositionSymbol {
    fn get_numbers_close(&self, pns: &[PositionNumber]) -> Vec<PositionNumber> {
        pns.iter().copied().filter(|pn| pn.is_close(self)).collect()
    }
}

#[derive(Debug)]
struct Schematic {
    numbers: Vec<PositionNumber>,
    symbols: Vec<PositionSymbol>,
}

impl Schematic {
    fn get_part_numbers(&self) -> Vec<PositionNumber> {
        self.numbers
            .iter()
            .copied()
            .filter(|pn| self.symbols.iter().any(|s| pn.is_close(s)))
            .collect()
    }
}

fn parse_contents(contents: &str) -> Schematic {
    let mut numbers = vec![];
    let mut symbols = vec![];

    for (i, line) in contents.lines().enumerate() {
        let entries = parse_line(line);

        let pos_symbols: Vec<PositionSymbol> = entries
            .iter()
            .enumerate()
            .filter(|(_, e)| matches!(e, Entry::Symbol(_)))
            .map(|(j, e)| {
                if let Entry::Symbol(x) = e {
                    PositionSymbol {
                        line: i,
                        col: j,
                        symbol: *x,
                    }
                } else {
                    unreachable!()
                }
            })
            .collect();

        let pos_numbers: Vec<PositionNumber> = entries
            .iter()
            .enumerate()
            .group_by(|(_, e)| matches!(e, Entry::Digit(_)))
            .into_iter()
            .flat_map(|(k, g)| {
                if !k {
                    None
                } else {
                    let g: Vec<(usize, &Entry)> = g.collect();
                    let n = g.len();

                    let mut g = g.iter().peekable();
                    let start_col = g.peek().unwrap().0;

                    let mut number = 0;
                    for (k, entry) in g.enumerate() {
                        match entry.1 {
                            Entry::Digit(x) => {
                                number += 10_usize.pow((n - k - 1) as u32) * *x as usize
                            }
                            _ => unreachable!(),
                        }
                    }

                    Some(PositionNumber {
                        len: n,
                        start_col,
                        line: i,
                        number: number as u32,
                    })
                }
            })
            .collect();

        numbers.extend(pos_numbers);
        symbols.extend(pos_symbols);
    }

    Schematic { numbers, symbols }
}

fn parse_line(line: &str) -> Vec<Entry> {
    line.chars().map(Entry::from).collect()
}

fn solve_part_one(contents: &str) -> u32 {
    let schematic = parse_contents(contents);

    schematic
        .get_part_numbers()
        .iter()
        .map(|pn| pn.number)
        .sum()
}

fn solve_part_two(contents: &str) -> u32 {
    let schematic = parse_contents(contents);

    let symbols = schematic.symbols;

    symbols
        .iter()
        .filter(|symbol| symbol.symbol == '*')
        .filter_map(|symbol| {
            let numbers_close = symbol.get_numbers_close(&schematic.numbers);

            if numbers_close.len() == 2 {
                Some(numbers_close)
            } else {
                None
            }
        })
        .map(|numbers_close| numbers_close.iter().map(|x| x.number).product::<u32>())
        .sum()
}

fn main() {
    println!("{}", solve_part_one(INPUT));
    println!("{}", solve_part_two(INPUT));
}

#[cfg(test)]
mod tests {
    use super::*;
    const TEST_INPUT: &str = include_str!("../test_input.txt");

    #[test]
    fn it_works() {
        assert_eq!(solve_part_one(TEST_INPUT), 4361);
    }

    #[test]
    fn it_works2() {
        assert_eq!(solve_part_two(TEST_INPUT), 467835);
    }
}

Refactoring

The refactored code is below.

use itertools::Itertools;

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

#[derive(Clone, Copy)]
enum Entry {
    Empty,
    Symbol(char),
    Digit(u32),
}

impl From<char> for Entry {
    fn from(value: char) -> Self {
        let parsed_value = value.to_digit(10);

        if let Some(x) = parsed_value {
            Self::Digit(x)
        } else {
            match value {
                '.' => Entry::Empty,
                x => Entry::Symbol(x),
            }
        }
    }
}

#[derive(Debug, Clone, Copy)]
struct PositionNumber {
    start_col: usize,
    line: usize,
    len: usize,
    number: u32,
}

impl PositionNumber {
    fn is_close(&self, symbol: &PositionSymbol) -> bool {
        for i in 0..self.len {
            if (self.start_col + i).abs_diff(symbol.col) <= 1
                && (self.line).abs_diff(symbol.line) <= 1
            {
                return true;
            }
        }

        false
    }
}

#[derive(Debug, Clone, Copy)]
struct PositionSymbol {
    col: usize,
    line: usize,
    symbol: char,
}

impl PositionSymbol {
    fn get_numbers_close(
        self,
        pns: &[PositionNumber],
    ) -> impl Iterator<Item = PositionNumber> + '_ {
        pns.iter().copied().filter(move |pn| pn.is_close(&self))
    }
}

#[derive(Debug)]
struct Schematic {
    numbers: Vec<PositionNumber>,
    symbols: Vec<PositionSymbol>,
}

impl Schematic {
    fn get_part_numbers(&self) -> impl Iterator<Item = PositionNumber> + '_ {
        self.numbers
            .iter()
            .copied()
            .filter(|pn| self.symbols.iter().any(|s| pn.is_close(s)))
    }
}

fn parse_contents(contents: &str) -> Schematic {
    let mut numbers = vec![];
    let mut symbols = vec![];

    let columns = contents
        .lines()
        .next()
        .expect("File should not be empty")
        .len();

    let mut digits_buffer = Vec::with_capacity(columns);

    for (i, line) in contents.lines().enumerate() {
        let entries = parse_line(line);

        let pos_symbols = entries.iter().enumerate().filter_map(|(j, e)| {
            if let Entry::Symbol(x) = e {
                Some(PositionSymbol {
                    line: i,
                    col: j,
                    symbol: *x,
                })
            } else {
                None
            }
        });

        let grouped_digits = entries
            .iter()
            .copied()
            .enumerate()
            .group_by(|(_, e)| matches!(e, Entry::Digit(_)));

        let pos_numbers = grouped_digits.into_iter().flat_map(|(k, g)| {
            if !k {
                None
            } else {
                digits_buffer.extend(g);

                let g = &digits_buffer;
                let n = g.len();

                let start_col = g[0].0;

                let mut number = 0;
                for (k, entry) in g.iter().enumerate() {
                    match entry.1 {
                        Entry::Digit(x) => number += 10_usize.pow((n - k - 1) as u32) * x as usize,
                        _ => unreachable!("Groups have been filtered to only contain digits"),
                    }
                }

                digits_buffer.clear();

                Some(PositionNumber {
                    len: n,
                    start_col,
                    line: i,
                    number: number as u32,
                })
            }
        });

        numbers.extend(pos_numbers);
        symbols.extend(pos_symbols);
    }

    Schematic { numbers, symbols }
}

fn parse_line(line: &str) -> Vec<Entry> {
    line.chars().map(Entry::from).collect()
}

fn solve_part_one(contents: &str) -> u32 {
    let schematic = parse_contents(contents);

    schematic.get_part_numbers().map(|pn| pn.number).sum()
}

fn solve_part_two(contents: &str) -> u32 {
    let schematic = parse_contents(contents);

    let symbols = schematic.symbols;

    symbols
        .iter()
        .filter(|symbol| symbol.symbol == '*')
        .filter_map(|symbol| {
            let numbers_close = symbol.get_numbers_close(&schematic.numbers);

            if let Some((x, y)) = numbers_close.collect_tuple() {
                Some((x, y))
            } else {
                None
            }
        })
        .map(|numbers_close| numbers_close.0.number * numbers_close.1.number)
        .sum()
}

fn main() {
    println!("{}", solve_part_one(INPUT));
    println!("{}", solve_part_two(INPUT));
}

#[cfg(test)]
mod tests {
    use super::*;
    const TEST_INPUT: &str = include_str!("../test_input.txt");

    #[test]
    fn it_works() {
        assert_eq!(solve_part_one(TEST_INPUT), 4361);
    }

    #[test]
    fn it_works2() {
        assert_eq!(solve_part_two(TEST_INPUT), 467835);
    }
}

I opted not to optimize for the time complexity as the runtime is negligible with the full input and it would require us to create the whole matrix, i.e. we would be doing a space-time complexity trade-off which is not even clear if it would be worth it for the use case.

But it might be worthwhile to say how we would accomplish this:

First, build a full matrix together with the empty entries.
When checking for who is close, we just iterate over of the matrix indices of the neighbors to check for numbers.

This reduces the complexity since get_numbers_close would now be \(O(1)\) instead of \(O(n)\).

If we decided to check adjacencies while parsing, we would be able to avoid the creation of the matrix, thus getting the time complexity improvement "for free". However, I want to keep the transformational aspect of the algorithm, i.e. preserve the transformation of input into internal data structure and only then processing it.

In the refactoring, however, we removed a lot of heap allocation and one unnecessary unreachable.

I ultimately wanted to remove the unreachable that is left, but I all solutions that I attempted by using the type system directly was obfuscating the solution much more than clarifying it. So I decided to leave as is. If someone has a better idea that is idiomatic, please let me know!

Extracting modules

To keep things cleaner, I decided to make another refactoring extracting parts of the code into modules.

Our main.rs became:

use itertools::Itertools;

mod parsing;
mod schematics;

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

fn solve_part_one(contents: &str) -> u32 {
    let schematic = parsing::parse_contents(contents);

    schematic.get_part_numbers().map(|pn| pn.number).sum()
}

fn solve_part_two(contents: &str) -> u32 {
    let schematic = parsing::parse_contents(contents);

    let symbols = schematic.symbols;

    symbols
        .iter()
        .filter(|symbol| symbol.symbol == '*')
        .filter_map(|symbol| {
            let numbers_close = symbol.get_numbers_close(&schematic.numbers);

            if let Some((x, y)) = numbers_close.collect_tuple() {
                Some((x, y))
            } else {
                None
            }
        })
        .map(|numbers_close| numbers_close.0.number * numbers_close.1.number)
        .sum()
}

fn main() {
    println!("{}", solve_part_one(INPUT));
    println!("{}", solve_part_two(INPUT));
}

#[cfg(test)]
mod tests {
    use super::*;
    const TEST_INPUT: &str = include_str!("../test_input.txt");

    #[test]
    fn it_works() {
        assert_eq!(solve_part_one(TEST_INPUT), 4361);
    }

    #[test]
    fn it_works2() {
        assert_eq!(solve_part_two(TEST_INPUT), 467835);
    }
}

Parsing functionalities were put into parsing.rs:

#![allow(unused)]
fn main() {
use itertools::Itertools;

use crate::schematics::{Entry, PositionNumber, PositionSymbol, Schematic};

pub(crate) fn parse_contents(contents: &str) -> Schematic {
    let mut numbers = vec![];
    let mut symbols = vec![];

    let columns = contents
        .lines()
        .next()
        .expect("File should not be empty")
        .len();

    let mut digits_buffer = Vec::with_capacity(columns);

    for (i, line) in contents.lines().enumerate() {
        let entries = parse_line(line);

        let pos_symbols = entries.iter().enumerate().filter_map(|(j, e)| {
            if let Entry::Symbol(x) = e {
                Some(PositionSymbol {
                    line: i,
                    col: j,
                    symbol: *x,
                })
            } else {
                None
            }
        });

        let grouped_digits = entries
            .iter()
            .copied()
            .enumerate()
            .group_by(|(_, e)| matches!(e, Entry::Digit(_)));

        let pos_numbers = grouped_digits.into_iter().flat_map(|(k, g)| {
            if !k {
                None
            } else {
                digits_buffer.extend(g);

                let g = &digits_buffer;
                let n = g.len();

                let start_col = g[0].0;

                let mut number = 0;
                for (k, entry) in g.iter().enumerate() {
                    match entry.1 {
                        Entry::Digit(x) => number += 10_usize.pow((n - k - 1) as u32) * x as usize,
                        _ => unreachable!("Groups have been filtered to only contain digits"),
                    }
                }

                digits_buffer.clear();

                Some(PositionNumber {
                    len: n,
                    start_col,
                    line: i,
                    number: number as u32,
                })
            }
        });

        numbers.extend(pos_numbers);
        symbols.extend(pos_symbols);
    }

    Schematic { numbers, symbols }
}

pub(crate) fn parse_line(line: &str) -> Vec<Entry> {
    line.chars().map(Entry::from).collect()
}
}

and things related to the schematics themselves were put into schematics.rs:

#![allow(unused)]
fn main() {
#[derive(Clone, Copy)]
pub(crate) enum Entry {
    Empty,
    Symbol(char),
    Digit(u32),
}

impl From<char> for Entry {
    fn from(value: char) -> Self {
        let parsed_value = value.to_digit(10);

        if let Some(x) = parsed_value {
            Self::Digit(x)
        } else {
            match value {
                '.' => Entry::Empty,
                x => Entry::Symbol(x),
            }
        }
    }
}

#[derive(Debug, Clone, Copy)]
pub(crate) struct PositionNumber {
    pub(crate) start_col: usize,
    pub(crate) line: usize,
    pub(crate) len: usize,
    pub(crate) number: u32,
}

impl PositionNumber {
    pub(crate) fn is_close(&self, symbol: &PositionSymbol) -> bool {
        for i in 0..self.len {
            if (self.start_col + i).abs_diff(symbol.col) <= 1
                && (self.line).abs_diff(symbol.line) <= 1
            {
                return true;
            }
        }

        false
    }
}

#[derive(Debug, Clone, Copy)]
pub(crate) struct PositionSymbol {
    pub(crate) col: usize,
    pub(crate) line: usize,
    pub(crate) symbol: char,
}

impl PositionSymbol {
    pub(crate) fn get_numbers_close(
        self,
        pns: &[PositionNumber],
    ) -> impl Iterator<Item = PositionNumber> + '_ {
        pns.iter().copied().filter(move |pn| pn.is_close(&self))
    }
}

#[derive(Debug)]
pub(crate) struct Schematic {
    pub(crate) numbers: Vec<PositionNumber>,
    pub(crate) symbols: Vec<PositionSymbol>,
}

impl Schematic {
    pub(crate) fn get_part_numbers(&self) -> impl Iterator<Item = PositionNumber> + '_ {
        self.numbers
            .iter()
            .copied()
            .filter(|pn| self.symbols.iter().any(|s| pn.is_close(s)))
    }
}
}

Day 4

Part One

Part one is straightforward: you just parse your card numbers and the numbers of the winning card and check to see which of your numbers are contained in the winning card.

Part Two

For part two, you just need to avoid increasing one by one and instead calculate directly how many will be added to the successive cards.

The full code can be seen below.

use anyhow::{anyhow, Result};

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

#[derive(Debug)]
struct Card {
    _id: i32,
    winning_numbers: Vec<i32>,
    my_numbers: Vec<i32>,
}

impl Card {
    fn get_my_winning(&self) -> Vec<i32> {
        self.my_numbers
            .iter()
            .copied()
            .filter(|my_number| self.winning_numbers.contains(my_number))
            .collect()
    }
}

fn parse_line(line: &str) -> Result<Card> {
    let (card_identification, numbers) = line
        .split_once(':')
        .ok_or(anyhow!("ERROR: Syntax error at line '{line}''"))?;

    let (_, id) = card_identification.split_once(' ').ok_or(anyhow!(
        "ERROR: Syntax error with identification '{card_identification}'"
    ))?;

    let _id: i32 = id.trim().parse()?;

    let (winning_numbers, my_numbers) = numbers.split_once('|').ok_or(anyhow!(
        "ERROR: Syntax error when splitting numbers '{line}'"
    ))?;

    let winning_numbers = winning_numbers
        .split_whitespace()
        .flat_map(|n| {
            n.parse().map_err(|e| {
                eprintln!("ERROR: Parse error when parsing {n} to i32");
                e
            })
        })
        .collect();

    let my_numbers = my_numbers
        .split_whitespace()
        .flat_map(|n| {
            n.parse().map_err(|e| {
                eprintln!("ERROR: Parse error when parsing {n} to i32");
                e
            })
        })
        .collect();

    Ok(Card {
        _id,
        winning_numbers,
        my_numbers,
    })
}

fn parse_contents(contents: &str) -> Result<Vec<Card>> {
    contents.lines().map(parse_line).collect()
}

fn solve_part_one(contents: &str) -> Result<u32> {
    let cards = parse_contents(contents)?;

    Ok(cards
        .iter()
        .map(|card| {
            let number_of_winning = card.get_my_winning().len();

            if number_of_winning == 0 {
                0
            } else {
                2_u32.pow(number_of_winning as u32 - 1)
            }
        })
        .sum())
}

fn solve_part_two(contents: &str) -> Result<u32> {
    let cards = parse_contents(contents)?;

    let mut cards_amounts: Vec<usize> = vec![1; cards.len()];

    for i in 0..cards.len() {
        let n = cards[i].get_my_winning().len();

        for j in 0..n.min(cards.len() - 1) {
            cards_amounts[(i + 1) + j] += cards_amounts[i];
        }
    }

    Ok(cards_amounts.iter().map(|x| *x as u32).sum())
}

fn main() -> Result<()> {
    println!("{}", solve_part_one(INPUT)?);
    println!("{}", solve_part_two(INPUT)?);

    Ok(())
}

#[cfg(test)]
mod tests {
    use super::*;
    const TEST_INPUT: &str = include_str!("../test_input.txt");

    #[test]
    fn part_one() {
        assert_eq!(solve_part_one(TEST_INPUT).unwrap(), 13)
    }

    #[test]
    fn part_two() {
        assert_eq!(solve_part_two(TEST_INPUT).unwrap(), 30)
    }
}

Day 5

Day 5 is essentially a problem about how to efficiently compose functions.

Part One

Each block determines a remapping of integers. Conveniently, the blocks are ordered correctly and thus simplify potentially having to path-find the correct steps of transition.

The time complexity for our implementation is \(O(n\cdot k \cdot p)\), where \(n\) is the number of seeds, \(k\) is the number of mappings and \(p\) is the maximum number of lines of each block.

The main parts of the algorithm are the block's implementation:

#![allow(unused)]
fn main() {
#[derive(Debug)]
struct BlockData<'a> {
    _from: &'a str,
    _to: &'a str,
    numbers: Vec<Numbers>,
}

impl<'a> BlockData<'a> {
    fn map(&self, from: i64) -> i64 {
        for number in &self.numbers {
            if from >= number.source && from < number.source + number.range as i64 {
                return from - number.source + number.destination;
            }
        }

        from
    }

    fn reverse_map(&self, to: i64) -> i64 {
        for number in &self.numbers {
            if to >= number.destination && to < number.destination + number.range as i64 {
                return to - number.destination + number.source;
            }
        }

        to
    }
}
}

and the following iteration:

#![allow(unused)]
fn main() {
pub fn solve_part_one(contents: &str) -> Result<i64> {
    let (seeds, blocks) = parse_contents(contents)?;

    let mut final_locations = Vec::new();

    for seed in seeds {
        let mut seed_mapping = seed;

        for block in &blocks {
            seed_mapping = block.map(seed_mapping);
        }

        final_locations.push(seed_mapping);
    }

    final_locations
        .iter()
        .copied()
        .min()
        .ok_or(anyhow!("Empty locations"))
}
}

Part Two

Part two flips the problem in its head by establishing that the "seeds" are actually pairs, where each first element is the start of a range and the second is the range length. This significantly increases the input size (i.e., \(n\) in our time complexity consideration), but does not change neither \(k\) or \(p\). For all intents and purposes, the algorithm is simply \(O(n)\).

Notice that our input is in the order of a few billions. Therefore, brute force should not be out of the picture. And indeed, we can run the following function

#![allow(unused)]
fn main() {
pub fn solve_part_two(contents: &str) -> Result<i64> {
    let (seeds, blocks) = parse_contents(contents)?;
    // let seeds = convert_seed_ranges_into_seeds(&seeds);

    let mut final_locations = i64::MAX;

    for seed_chunk in seeds.chunks_exact(2) {
        let (start, range) = seed_chunk
            .iter()
            .collect_tuple()
            .expect("Chunk should be two-sized");

        for i in 0..(*range as usize) {
            let seed = start + i as i64;
            let mut seed_mapping = seed;

            for block in &blocks {
                seed_mapping = block.map(seed_mapping);
            }

            if seed_mapping < final_locations {
                final_locations = seed_mapping
            }
        }
    }

    Ok(final_locations)
}
}

and get a solution in a few minutes. If we reverse the logic and try to find the first value that is the image of something in the input, we can get the response in a few seconds.

#![allow(unused)]
fn main() {
pub fn solve_part_two_reversing(contents: &str) -> Result<i64> {
    let (seeds, blocks) = parse_contents(contents)?;
    // let seeds = convert_seed_ranges_into_seeds(&seeds);

    let chunks: Vec<(i64, i64)> = seeds
        .chunks_exact(2)
        .map(|chunk| {
            chunk
                .iter()
                .copied()
                .collect_tuple()
                .expect("Chunk should be two-sized")
        })
        .collect();

    for i in 0.. {
        let mut attempt = i;

        for block in blocks.iter().rev() {
            attempt = block.reverse_map(attempt);
        }

        for (start, range) in &chunks {
            if attempt >= *start && attempt < start + range {
                return Ok(i);
            }
        }
    }

    Err(anyhow!("Unable to find best location"))
}
}

Day 6

This question is just a math problem.

Let \(h\) be how much time you hold the button and \(T\) be the total time you have. Then, since you leave at \(h\) speed, you walk for \(h\cdot (T-h)\) units of distance.

Now, for each pair \((T, d)\), you would need to find all values of \(t\) such that \(t \cdot (T-t) > d\).

If we want to just count (which is more than enough for the problem), we just need to filter in the range of \(0..T\) for those values and then count them.

However, the result can also be calculated explicitly. For that, we just need to find the values of \(t_1, t_2\) for which \(t \cdot (T-t) = d\), i.e. \(t \cdot (T-t) - d = 0\) and then the range will be the integral values that are between \(t_1\) and \(t_2\).

Day 7

Not really much to comment here in regards to the algorithm itself, other than the main idea being to define an ordering so that the solution becomes just sorting the hands at the end.

Part One

In hand.rs, we define the Hand and hand types

#![allow(unused)]
fn main() {
#[derive(Debug)]
pub(crate) struct Hand<T> {
    pub(crate) cards: [T; 5],
    pub(crate) bid: u64,
}

impl<T> Hand<T> {
    pub(crate) fn new(cards: [T; 5], bid: u64) -> Hand<T> {
        Hand { cards, bid }
    }
}

#[derive(PartialEq, PartialOrd, Eq, Ord, Clone, Copy, Debug)]
pub(crate) enum Type {
    HighCard,
    OnePair,
    TwoPair,
    ThreeOfAKind,
    FullHouse,
    FourOfAKind,
    FiveOfAKind,
}
}

In card.rs, we define things related to the cards themselves, including the ordering

#![allow(unused)]
fn main() {
use anyhow::anyhow;
use itertools::Itertools;

use crate::hand::{Hand, Type};

#[derive(PartialEq, PartialOrd, Eq, Ord, Clone, Copy, Debug, Hash)]
pub(crate) enum Card {
    Number(u64),
    T,
    J,
    Q,
    K,
    A,
}

fn get_type(cards: [Card; 5]) -> Type {
    if cards.iter().all(|c| *c == cards[0]) {
        return Type::FiveOfAKind;
    }

    if cards.iter().counts().values().any(|v| *v == 4) {
        return Type::FourOfAKind;
    }

    if let Some((x, y)) = cards.iter().counts().values().collect_tuple() {
        if (*x, *y) == (2, 3) || (*x, *y) == (3, 2) {
            return Type::FullHouse;
        }
    }

    if cards.iter().counts().values().any(|v| *v == 3) {
        return Type::ThreeOfAKind;
    }

    if cards.iter().counts().values().filter(|v| **v == 2).count() == 2 {
        return Type::TwoPair;
    }

    if cards.iter().counts().values().filter(|v| **v == 2).count() == 1 {
        return Type::OnePair;
    }

    Type::HighCard
}

impl TryFrom<char> for Card {
    type Error = anyhow::Error;

    fn try_from(value: char) -> std::prelude::v1::Result<Self, Self::Error> {
        if let Some(x) = value.to_digit(10) {
            return Ok(Card::Number(x as u64));
        }

        match value {
            'T' => Ok(Card::T),
            'J' => Ok(Card::J),
            'Q' => Ok(Card::Q),
            'K' => Ok(Card::K),
            'A' => Ok(Card::A),
            _ => Err(anyhow!("Invalid card: '{value}'")),
        }
    }
}

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

impl Ord for Hand<Card> {
    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
        let self_type = get_type(self.cards);
        let other_type = get_type(other.cards);

        match self_type.cmp(&other_type) {
            std::cmp::Ordering::Equal => self.cards.cmp(&other.cards),
            x => x,
        }
    }
}

impl PartialEq for Hand<Card> {
    fn eq(&self, other: &Self) -> bool {
        let mut my_cards = self.cards;
        let mut your_cards = other.cards;

        my_cards.sort();
        your_cards.sort();

        my_cards == your_cards
    }
}

impl Eq for Hand<Card> {}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn ord() {
        assert!(Card::Number(5) < Card::Number(7));
        assert!(Card::Number(5) < Card::K);
        assert!(Card::Number(6) > Card::Number(3));
        assert!(Card::A > Card::T);
        assert!(Card::J > Card::Number(3));
    }
}
}

Part Two

Part two consists of making some adaptations related to the Joker. I created a lot of tests for debugging cases that were not taken into consideration for the given test cases.

#![allow(unused)]
fn main() {
use anyhow::anyhow;
use itertools::Itertools;

use crate::hand::{Hand, Type};

#[derive(PartialEq, PartialOrd, Eq, Ord, Clone, Copy, Hash)]
pub(crate) enum CardWithJoker {
    J,
    Number(u64),
    T,
    Q,
    K,
    A,
}

fn get_type_with_joker(cards: [CardWithJoker; 5]) -> Type {
    let jokers = cards
        .iter()
        .filter(|x| matches!(x, CardWithJoker::J))
        .count();

    let non_jokers: Vec<CardWithJoker> = cards
        .iter()
        .copied()
        .filter(|x| !matches!(x, CardWithJoker::J))
        .collect();

    if non_jokers
        .iter()
        .counts()
        .values()
        .any(|v| *v + jokers == 5)
        || jokers == 5
    {
        return Type::FiveOfAKind;
    }

    if non_jokers
        .iter()
        .counts()
        .values()
        .any(|v| *v + jokers == 4)
    {
        return Type::FourOfAKind;
    }

    if let Some((x, y)) = non_jokers.iter().counts().values().collect_tuple() {
        let mut counts = vec![*x, *y, jokers];
        counts.sort();

        if counts == vec![1, 2, 2] || counts == vec![0, 2, 3] {
            return Type::FullHouse;
        }
    }

    if non_jokers
        .iter()
        .counts()
        .values()
        .any(|v| *v + jokers == 3)
    {
        return Type::ThreeOfAKind;
    }

    // Two pair can't happen with a joker, because otherwise it would at least turn
    // into a three of a kind.
    if non_jokers
        .iter()
        .counts()
        .values()
        .filter(|v| **v == 2)
        .count()
        == 2
    {
        return Type::TwoPair;
    }

    if non_jokers
        .iter()
        .counts()
        .values()
        .any(|v| *v + jokers == 2)
    {
        return Type::OnePair;
    }

    Type::HighCard
}

impl TryFrom<char> for CardWithJoker {
    type Error = anyhow::Error;

    fn try_from(value: char) -> std::prelude::v1::Result<Self, Self::Error> {
        if let Some(x) = value.to_digit(10) {
            return Ok(CardWithJoker::Number(x as u64));
        }

        match value {
            'T' => Ok(CardWithJoker::T),
            'J' => Ok(CardWithJoker::J),
            'Q' => Ok(CardWithJoker::Q),
            'K' => Ok(CardWithJoker::K),
            'A' => Ok(CardWithJoker::A),
            _ => Err(anyhow!("Invalid card: '{value}'")),
        }
    }
}

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

impl Ord for Hand<CardWithJoker> {
    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
        let self_type = get_type_with_joker(self.cards);
        let other_type = get_type_with_joker(other.cards);

        match self_type.cmp(&other_type) {
            std::cmp::Ordering::Equal => self.cards.cmp(&other.cards),
            x => x,
        }
    }
}

impl PartialEq for Hand<CardWithJoker> {
    fn eq(&self, other: &Self) -> bool {
        let mut my_cards = self.cards;
        let mut your_cards = other.cards;

        my_cards.sort();
        your_cards.sort();

        my_cards == your_cards
    }
}

impl Eq for Hand<CardWithJoker> {}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn ord() {
        assert!(CardWithJoker::Number(5) < CardWithJoker::Number(7));
        assert!(CardWithJoker::Number(5) < CardWithJoker::K);
        assert!(CardWithJoker::Number(6) > CardWithJoker::Number(3));
        assert!(CardWithJoker::A > CardWithJoker::T);
        assert!(CardWithJoker::J < CardWithJoker::Number(3));
    }

    #[test]
    fn test_matches_with_joker() {
        let cards: [CardWithJoker; 5] = [
            'A'.try_into().unwrap(),
            'J'.try_into().unwrap(),
            'T'.try_into().unwrap(),
            '2'.try_into().unwrap(),
            '7'.try_into().unwrap(),
        ];

        println!("{:?}", get_type_with_joker(cards));
        assert!(matches!(get_type_with_joker(cards), Type::OnePair));

        let cards: [CardWithJoker; 5] = [
            'A'.try_into().unwrap(),
            'J'.try_into().unwrap(),
            'J'.try_into().unwrap(),
            'J'.try_into().unwrap(),
            'A'.try_into().unwrap(),
        ];

        println!("{:?}", get_type_with_joker(cards));
        assert!(matches!(get_type_with_joker(cards), Type::FiveOfAKind));

        let cards: [CardWithJoker; 5] = [
            'A'.try_into().unwrap(),
            'J'.try_into().unwrap(),
            'J'.try_into().unwrap(),
            '2'.try_into().unwrap(),
            '7'.try_into().unwrap(),
        ];

        println!("{:?}", get_type_with_joker(cards));
        assert!(matches!(get_type_with_joker(cards), Type::ThreeOfAKind));

        let cards: [CardWithJoker; 5] = [
            'A'.try_into().unwrap(),
            'J'.try_into().unwrap(),
            '2'.try_into().unwrap(),
            '2'.try_into().unwrap(),
            '7'.try_into().unwrap(),
        ];

        println!("{:?}", get_type_with_joker(cards));
        assert!(matches!(get_type_with_joker(cards), Type::ThreeOfAKind));

        let cards: [CardWithJoker; 5] = [
            'J'.try_into().unwrap(),
            'J'.try_into().unwrap(),
            'T'.try_into().unwrap(),
            'J'.try_into().unwrap(),
            '7'.try_into().unwrap(),
        ];

        println!("{:?}", get_type_with_joker(cards));
        assert!(matches!(get_type_with_joker(cards), Type::FourOfAKind));

        let cards: [CardWithJoker; 5] = [
            '2'.try_into().unwrap(),
            'J'.try_into().unwrap(),
            '2'.try_into().unwrap(),
            '7'.try_into().unwrap(),
            '7'.try_into().unwrap(),
        ];

        println!("{:?}", get_type_with_joker(cards));
        assert!(matches!(get_type_with_joker(cards), Type::FullHouse));

        let cards: [CardWithJoker; 5] = [
            '2'.try_into().unwrap(),
            '1'.try_into().unwrap(),
            '2'.try_into().unwrap(),
            '1'.try_into().unwrap(),
            '7'.try_into().unwrap(),
        ];

        println!("{:?}", get_type_with_joker(cards));
        assert!(matches!(get_type_with_joker(cards), Type::TwoPair));
    }
}
}

Day 8

This day is essentially implementing a specific walk (or walks in part two) over a binary tree. Conveniently, we have labels for the nodes, so we can just store them as a HashMap.

Part two has some problematics aspect to it, but let's get into that later.

Part One

For our parsing, we do

#![allow(unused)]
fn main() {
#[derive(Debug)]
struct Possibilities<'a> {
    left: &'a str,
    right: &'a str,
}

fn parse_line(line: &str) -> Result<(&str, Possibilities)> {
    let (origin, destinations) = line
        .split_once(" = ")
        .ok_or(anyhow!("Syntax error at {line}"))?;

    let (left, right) = destinations
        .trim_end_matches(')')
        .trim_start_matches('(')
        .split_once(", ")
        .ok_or(anyhow!("Syntax error at {line}"))?;

    Ok((origin, Possibilities { left, right }))
}

fn parse_contents(contents: &str) -> Result<(Vec<Direction>, HashMap<&str, Possibilities>)> {
    let (first_line, rest) = contents.split_once("\n\n").ok_or(anyhow!("Syntax error"))?;

    let directions: Vec<Direction> = first_line.chars().flat_map(Direction::try_from).collect();
    let parsed_lines: Vec<(&str, Possibilities)> = rest.lines().flat_map(parse_line).collect();

    let transitions = HashMap::from_iter(parsed_lines);

    Ok((directions, transitions))
}
}

We then define how the algorithm operates, and that's it!

#![allow(unused)]
fn main() {
fn go_one_step<'a>(
    from: &'a str,
    direction: &Direction,
    map: &HashMap<&'a str, Possibilities<'a>>,
) -> &'a str {
    match direction {
        Direction::L => map[from].left,
        Direction::R => map[from].right,
    }
}

fn solve_part_one(contents: &str) -> Result<usize> {
    let (directions, transitions) = parse_contents(contents)?;

    let mut current = "AAA";
    Ok(directions
        .iter()
        .cycle()
        .map(|d| {
            let next = go_one_step(current, d, &transitions);

            if next == "ZZZ" {
                None
            } else {
                current = next;
                Some(current)
            }
        })
        .while_some()
        .count()
        + 1)
}
}

Part Two

Part two operates with multiple walks. We want to see where those walks coordinate to finish at something that ends with Z at the same time.

Since that can take a lot of time, the idea is to get the cycle lengths of each of the walks and get the least common multiple to find the cycle length of the whole ensemble.

Consider the following example as an illustration:

1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6
1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2
1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3

As you can see, the cycles coordinate at the twelfth position.

However, the structure above is not necessarily what we have given the problem's description. Indeed, even the examples given do not reflect this structure.

We could have the following:

1 2 3 4 5 6 3 4 5 6 3 4 5 6 3 4 5 6
1 2 3 4 5 6 7 8 9 7 8 9 7 8 9 7 8 9
1 2 3 4 3 4 3 4 3 4 3 4 3 4 3 4 3 4

The real solution to the problem would involve:

Detecting the cycle length of each walk
Reducing those cycle lengths to coprime factors
Applying the Chinese Remainder Theorem to find the beginning of the joint cycle

This way, we reduce the problem to one of a similar structure as the previous illustration, the only difference being the existence of an initial offset that is found using the Chinese Remainder Theorem.

Note that 2. assumes that the cycle lengths are coprime. This is yet another thing that the problem assumes which might not be true for a generic input. If that is not true, the following situation could happen:

1 2 3 4 1 2 3 4 1 2 3 4 1
_ 1 2 3 4 1 2 3 4 1 2 3 4

The cycles would never coordinate in the scenario above, and the problem wouldn't have a solution.

"Luckily", the input is built in such a way that just taking the LCM of the cycles work out well to define the cycle. My solution to this day assumes that the LCM works too. If you want to have a solution that would apply to all possible inputs, you'd have to consider the points mentioned above, including the possibility of a solution not existing.

Day 9

Straightforward day: just create the diffs until you hit all zeroes, then go back adding things bottom up.

Part two can even be done by simply reversing the input. However, we do it by implementing the lines as VecDeques.

Part One and Two

use std::collections::VecDeque;

use anyhow::Result;

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

enum TimeDirection {
    Future,
    Past,
}

struct History {
    values: VecDeque<i32>,
}

impl History {
    fn get_diffs(&self) -> VecDeque<i32> {
        self.values
            .iter()
            .skip(1)
            .zip(&self.values)
            .map(|(next, current)| next - current)
            .collect()
    }

    fn forecast_base(&self, parents: &[i32]) -> Option<i32> {
        let last_parent = parents.last()?;

        let last_value = self.values.back()?;

        Some(last_parent + last_value)
    }

    fn forecast_base_back(&self, parents: &[i32]) -> Option<i32> {
        let last_parent = parents.first()?;

        let last_value = self.values.front()?;

        Some(last_parent + last_value)
    }

    fn forecast(&self, time_direction: TimeDirection) -> Option<i32> {
        let mut diffs: Vec<History> = vec![History {
            values: self.values.clone(),
        }];

        while !diffs
            .last()
            .expect("Diffs have at least the initial history")
            .values
            .iter()
            .all(|&x| x == 0)
        {
            let last_diffs = diffs.last()?;
            let values = last_diffs.get_diffs();

            diffs.push(History { values })
        }

        match time_direction {
            TimeDirection::Future => diffs.last_mut().map(|x| x.values.push_back(0)),
            TimeDirection::Past => diffs.last_mut().map(|x| x.values.push_front(0)),
        };

        for i in 0..(diffs.len() - 1) {
            let idx = diffs.len() - i - 1;
            let seeing = &diffs[idx].values;

            match time_direction {
                TimeDirection::Future => {
                    let last_from_seeing = *seeing.back()?;
                    let last_from_parents = *diffs[idx - 1].values.back()?;

                    diffs[idx - 1]
                        .values
                        .push_back(last_from_parents + last_from_seeing);
                }
                TimeDirection::Past => {
                    let last_from_seeing = *seeing.front()?;
                    let last_from_parents = *diffs[idx - 1].values.front()?;

                    diffs[idx - 1]
                        .values
                        .push_front(last_from_parents - last_from_seeing);
                }
            }
        }

        match time_direction {
            TimeDirection::Future => diffs[0].values.back().map(|x| *x),
            TimeDirection::Past => diffs[0].values.front().map(|x| *x),
        }
    }
}

fn parse_line(line: &str) -> Result<History> {
    let values = line.split(' ').flat_map(|c| c.parse()).collect();

    Ok(History { values })
}

fn parse_contents(contents: &str) -> Result<Vec<History>> {
    contents.lines().map(parse_line).collect()
}

fn solve_part_one(contents: &str) -> Result<i32> {
    let histories = parse_contents(contents)?;

    Ok(histories
        .iter()
        .flat_map(|history| history.forecast(TimeDirection::Future))
        .sum())
}

fn solve_part_two(contents: &str) -> Result<i32> {
    let histories = parse_contents(contents)?;

    Ok(histories
        .iter()
        .flat_map(|history| history.forecast(TimeDirection::Past))
        .sum())
}

fn main() -> Result<()> {
    println!("{}", solve_part_one(INPUT)?);
    println!("{}", solve_part_two(INPUT)?);

    Ok(())
}

#[cfg(test)]
mod tests {
    use super::*;
    const TEST_INPUT: &str = include_str!("../test_input.txt");

    #[test]
    fn part_one() {
        assert_eq!(solve_part_one(TEST_INPUT).unwrap(), 114)
    }

    #[test]
    fn part_two() {
        assert_eq!(solve_part_two("10  13  16  21  30  45").unwrap(), 5)
    }
}

Day 10

This day is very interesting, and boils down to two things:

Loop finding (Part One)
Flood filling (Part Two)

Part One

We create a graph from the given grid. Pasting the full code here would not be very enlightening, since it is a lot of specific case handling.

It is useful, though, to show the loop-finding algorithm. I did not implement it as a BFS. It is more of a DFS. The code is below.

#![allow(unused)]
fn main() {
pub(crate) fn find_loop(
    graph: &UnGraphMap<(usize, usize), ()>,
    beginning: (usize, usize),
) -> Result<Vec<(usize, usize)>> {
    let mut queue = vec![vec![beginning]];

    while let Some(next) = queue.pop() {
        let last = *next.last().expect("Paths should not be empty");

        if last == beginning && next.len() > 1 {
            return Ok(next);
        }

        let neighbors: Vec<(usize, usize)> = graph
            .neighbors(last)
            .filter(|n| {
                if next.len() < 2 {
                    return true;
                }
                if let Some(x) = next.get(next.len() - 2) {
                    n != x
                } else {
                    true
                }
            })
            .collect();

        for neighbor in neighbors {
            let mut path = next.clone();
            path.push(neighbor);

            queue.push(path);
        }
    }

    Err(anyhow!("ERROR: Loop not found"))
}
}

The solution function is then:

#![allow(unused)]
fn main() {
fn solve_part_one(contents: &str) -> Result<usize> {
    let grid = parse_contents(contents)?;
    let lp = pipe::find_loop(&grid.get_graph(), grid.origin)?;

    Ok((lp.len() - 1) / 2) // Subtract one to remove the origin.
}
}

Part Two

Part two is implemented as a simple flood-filling algorithm. There is a complication though, since we allow fluid to "squeeze" through pipes such as the following

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

To be very explicit, filling this would result in the following grid

O O O O
O | | O
O | | O
F J L 7
| O O |
L - - J

The way that we solved this is by zooming into the grid: every tile got transformed into a 3x3 grid itself.

For instance, "J"s get transformed into

. | .
_ J .
. . .

We then flood fill this new grid and then scale it down again.

The main part of the code is given below

#![allow(unused)]
fn main() {
fn solve_part_two(contents: &str) -> Result<usize> {
    let grid = parse_contents(contents)?;
    let lp = pipe::find_loop(&grid.get_graph(), grid.origin)?;

    let scaled_up = grid::scale_up(&grid.matrix);
    let transformed_matrix = grid::transform_matrix(&scaled_up, &lp);

    let filled = grid::flood_fill(&transformed_matrix);
    let scaled_down = grid::scale_down(&filled);

    Ok(scaled_down
        .iter()
        .filter(|e| matches!(e, grid::Filled::Empty))
        .count())
}
}

Advent of Code