aoc2023

day05.rs

use std::{fs, str::FromStr};

#[derive(Debug, PartialEq, Eq, Copy, Clone)]
struct Range {
    start: i64,
    end: i64,
}

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

impl Ord for Range {
    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
        self.partial_cmp(other).unwrap()
    }
}

#[derive(Debug, PartialEq, Eq, Copy, Clone)]
struct Rule {
    src_rng_start: i64,
    src_rng_end: i64,
    dst_rng_start: i64,
}

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

impl Ord for Rule {
    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
        self.partial_cmp(other).unwrap()
    }
}

impl Rule {
    fn overlap(&self, input: &Range) -> Option<Range> {
        let start = std::cmp::max(input.start, self.src_rng_start);
        let end = std::cmp::min(input.end, self.src_rng_end);
        if start < end {
            Some(Range { start, end })
        } else {
            None
        }
    }

    fn contains(&self, input: i64) -> bool {
        (self.src_rng_start..self.src_rng_end).contains(&input)
    }

    fn apply(&self, input: i64) -> i64 {
        if self.contains(input) {
            self.dst_rng_start + (input - self.src_rng_start)
        } else {
            input
        }
    }
}

/// Assume rules are sorted by `src_rng_end`
#[derive(Debug)]
struct Rules(Vec<Rule>);

impl Rules {
    // Assume: Rules don't overlap.
    fn transform(self) -> Self {
        if self.0.len() == 0 {
            return self;
        }

        let mut vec = vec![Rule {
            src_rng_start: 0,
            src_rng_end: self.0[0].src_rng_start,
            dst_rng_start: 0,
        }];

        for rules in self.0.windows(2) {
            vec.push(rules[0]);
            vec.push({
                let src_rng_start = rules[0].src_rng_end;
                Rule {
                    src_rng_start,
                    src_rng_end: rules[1].src_rng_start,
                    dst_rng_start: src_rng_start,
                }
            });
        }

        if let Some(&rule) = self.0.last() {
            vec.push(rule);
        }

        vec.push({
            let src_rng_start = self.0.last().unwrap().src_rng_end;
            Rule {
                src_rng_start,
                src_rng_end: i64::MAX,
                dst_rng_start: src_rng_start,
            }
        });

        Rules(
            vec.into_iter()
                .filter(|r| r.src_rng_end - r.src_rng_start > 0)
                .collect::<Vec<_>>(),
        )
    }

    fn apply(&self, input: i64) -> i64 {
        if let Some(rule) = self.0.iter().find(|rule| rule.contains(input)) {
            rule.apply(input)
        } else {
            input
        }
    }

    fn process(&self, input: Range) -> Vec<Range> {
        let mut output_ranges = vec![];

        for rule in &self.0 {
            if let Some(Range { start, end }) = rule.overlap(&input) {
                output_ranges.push({
                    let offset = rule.dst_rng_start - rule.src_rng_start;
                    Range {
                        start: start + offset,
                        end: end + offset,
                    }
                });
            }
        }

        output_ranges
    }
}

#[derive(Debug)]
struct ParseRuleError;

impl FromStr for Rule {
    type Err = ParseRuleError;

    fn from_str(s: &str) -> Result<Self, Self::Err> {
        let (dst_rng_starg, s) = s.split_once(' ').ok_or(ParseRuleError)?;
        let dst_rng_start = dst_rng_starg.parse().map_err(|_| ParseRuleError)?;

        let (src_rng_start, s) = s.split_once(' ').ok_or(ParseRuleError)?;
        let src_rng_start = src_rng_start.parse().map_err(|_| ParseRuleError)?;

        let range_len = s.parse::<i64>().map_err(|_| ParseRuleError)?;

        Ok(Rule {
            src_rng_start,
            src_rng_end: src_rng_start + range_len,
            dst_rng_start,
        })
    }
}

fn main() {
    let input = fs::read_to_string("./input.txt").unwrap();

    let (hdr, maps) = input.split_once("\n\n").unwrap();

    // Part 1
    let mut seeds = hdr
        .split(' ')
        .filter_map(|s| s.parse::<i64>().ok())
        .collect::<Vec<_>>();

    let ranges = hdr.split(' ').skip(1).collect::<Vec<_>>();
    let mut ranges = ranges
        .chunks(2)
        .filter_map(|chunk| {
            if let Ok(start) = chunk[0].parse() {
                if let Ok(len) = chunk[1].parse::<i64>() {
                    Some(Range {
                        start,
                        end: start + len,
                    })
                } else {
                    None
                }
            } else {
                None
            }
        })
        .collect::<Vec<_>>();

    for map in maps.split("\n\n") {
        let mut rules = Rules(
            map.split('\n')
                .filter_map(|s| Rule::from_str(s).ok())
                .collect::<Vec<_>>(),
        );
        rules.0.sort();
        rules = rules.transform();

        // Part 1
        for seed in &mut seeds {
            *seed = rules.apply(*seed);
        }

        // Part 2
        ranges = ranges
            .iter()
            .flat_map(|&rng| rules.process(rng))
            .collect::<Vec<_>>();
    }

    println!("{:?}", seeds.iter().min());

    ranges.sort();
    println!("{:?}", ranges.first().unwrap());
}

day10.rs

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

#[derive(Debug)]
struct Tile(Pipe);

#[derive(Debug)]
struct Maze {
    tiles: Vec<Vec<Tile>>,
    r#loop: HashSet<(i64, i64)>
}

#[derive(Debug, PartialEq, Eq, Clone, Copy)]
enum Pipe {
    Vertical,
    Horizontal,
    NorthEast,
    NorthWest,
    SouthWest,
    SouthEast,
    Ground,
    Start,
}

const SOUTH: (i64, i64) = (1, 0);
const NORTH: (i64, i64) = (-1, 0);
const EAST: (i64, i64) = (0, 1);
const WEST: (i64, i64) = (0, -1);

impl Maze {
    fn connected(&self, t1: (i64, i64), t2: (i64, i64)) -> Option<bool> {
        let dir = (t2.0 - t1.0, t2.1 - t1.1);

        let p1 = self.tiles.get(t1.0 as usize)?.get(t1.1 as usize)?;
        let p2 = self.tiles.get(t2.0 as usize)?.get(t2.1 as usize)?;

        let connected = match dir {
            // p1 | F 7
            // p2 | J L
            SOUTH => {
                match &(p1.0, p2.0) {
                    (Pipe::Vertical, _) | (Pipe::SouthEast, _) | (Pipe::SouthWest, _) | (Pipe::Start, _) => {
                        p2.0 == Pipe::Vertical || p2.0 == Pipe::NorthEast || p2.0 == Pipe::NorthWest
                    },
                    _ => false,
                }
            },
            // p2 | F 7
            // p1 | J L
            NORTH => {
                match &(p1.0, p2.0) {
                    (Pipe::Vertical, _) | (Pipe::NorthEast, _) | (Pipe::NorthWest, _) | (Pipe::Start, _) => {
                        p2.0 == Pipe::Vertical || p2.0 == Pipe::SouthEast || p2.0 == Pipe::SouthWest
                    },
                    _ => false,
                }
            },
            // p1 p2
            EAST => {
                match &(p1.0, p2.0) {
                    (Pipe::Horizontal, _) | (Pipe::SouthEast, _) | (Pipe::NorthEast, _) | (Pipe::Start, _)=> {
                        p2.0 == Pipe::Horizontal || p2.0 == Pipe::NorthWest || p2.0 == Pipe::SouthWest
                    },
                    _ => false,
                }
            },
            // p2 p1
            WEST => {
                match &(p1.0, p2.0) {
                    (Pipe::Horizontal , _) | (Pipe::NorthWest, _) | (Pipe::SouthWest, _) | (Pipe::Start, _) => {
                        p2.0 == Pipe::Horizontal || p2.0 == Pipe::NorthEast || p2.0 == Pipe::SouthEast
                    },
                    _ => false,
                }
            },
            _ => false,
        };

        Some(connected)
    }

    fn neighbors(&self, p: (i64, i64)) -> Vec<(i64, i64)> {
        let neighbors = vec![
            (p.0 + SOUTH.0, p.1 + SOUTH.1),
            (p.0 + NORTH.0, p.1 + NORTH.1),
            (p.0 + EAST.0, p.1 + EAST.1),
            (p.0 + WEST.0, p.1 + WEST.1),
        ];

        let x: Vec<(i64, i64)> = neighbors.into_iter()
            .filter(|&q| self.connected(p, q) == Some(true))
            .collect();

        if x.len() == 0 { println!("WHAT?"); }

        x
    }

    fn update_start_tile(&mut self, s: (i64, i64)) {
        let north = self.connected(s, (s.0 + NORTH.0, s.1 + NORTH.1));
        let south = self.connected(s, (s.0 + SOUTH.0, s.1 + SOUTH.1));
        let east = self.connected(s, (s.0 + EAST.0, s.1 + EAST.1));
        let west = self.connected(s, (s.0 + WEST.0, s.1 + WEST.1));

        self.tiles[s.0 as usize][s.1 as usize] =
            match (north, south, east, west) {
            (Some(true), Some(true), _, _) => Tile(Pipe::Vertical),
            (Some(true), _, Some(true), _) => Tile(Pipe::NorthEast),
            (Some(true), _, _, Some(true)) => Tile(Pipe::NorthWest),
            (_, Some(true), Some(true), _) => Tile(Pipe::SouthEast),
            (_, Some(true), _, Some(true)) => Tile(Pipe::SouthWest),
            (_, _, Some(true), Some(true)) => Tile(Pipe::Horizontal),
            _ => panic!(),
        };
    }

    fn num_tiles_enclosed_by_loop(&self) -> usize {
        self.tiles.iter().enumerate()
            .map(|(rowid, row)| {
                let mut res = 0usize;
                let mut inside = false;
                let mut prev = Pipe::Ground;

                for i in 0..row.len() {
                    if !self.r#loop.contains(&(rowid as i64, i as i64)) {
                        if inside {
                            res += 1;
                        }

                        continue;
                    }

                    let curr = self.tiles[rowid][i].0;
                    match curr {
                        Pipe::Horizontal => { continue; },
                        Pipe::Vertical => { inside ^= true; }
                        _ => {
                            match (prev, curr) {
                                (Pipe::NorthEast, _) | (Pipe::NorthWest, _) => {
                                    match curr {
                                        Pipe::SouthEast | Pipe::SouthWest => {
                                            inside ^= true;
                                        },
                                        _ => { prev = curr; },
                                    }
                                },
                                (Pipe::SouthEast, _) | (Pipe::SouthWest, _) => {
                                    match curr {
                                        Pipe::NorthEast | Pipe::NorthWest => {
                                            inside ^= true;
                                        },
                                        _ => { prev = curr; },
                                    }
                                },
                                _ => { prev = curr; },
                            }
                        },
                    };
                }

                res
            })
            .sum()
    }
}

impl From<char> for Pipe {
    fn from(value: char) -> Self {
        match value {
            '|'  => Pipe::Vertical,
            '-'  => Pipe::Horizontal,
            'L'  => Pipe::NorthEast,
            'J'  => Pipe::NorthWest,
            '7'  => Pipe::SouthWest,
            'F'  => Pipe::SouthEast,
            '.'  => Pipe::Ground,
            'S'  => Pipe::Start,
            _ => panic!(),
        }
    }
}

fn bfs(
    s: (i64, i64),
    maze: &mut Maze,
) -> HashMap<(i64, i64), i64> {
    let mut dist: HashMap<(i64, i64), i64> = HashMap::new();
    let mut queue: VecDeque::<(i64, i64)> = VecDeque::new();

    queue.push_front(s);
    dist.insert(s, 0);
    maze.r#loop.insert(s);

    while !queue.is_empty() {
        if let Some(p) = queue.pop_back() {
            for q in maze.neighbors(p) {
                if !dist.contains_key(&q) {
                    queue.push_front(q);
                    dist.insert(q, dist[&p] + 1);
                    maze.r#loop.insert(q);
                }
            }
        }
    }

    dist
}

fn main() {
    let input = fs::read_to_string("./input.txt").unwrap();

    let mut maze = {
        let tiles = input.split('\n')
            .map(|line|
                line.chars()
                    .map(|c| Tile(c.into()))
                    .collect::<Vec<_>>()
                )
            .collect::<Vec<_>>();

        Maze {
            tiles,
            r#loop: HashSet::new(),
        }
    };

    let s = {
        let mut s = (0i64, 0i64);
        'outer: for i in 0..maze.tiles.len() {
            for j in 0..maze.tiles[0].len() {
                if maze.tiles[i][j].0 == Pipe::Start {
                    s = (i as i64, j as i64);
                    break 'outer;
                }
            }
        }

        s
    };

    maze.update_start_tile(s);

    let dist = bfs(s, &mut maze);

    let farthest = dist.values().max().unwrap_or(&i64::MIN);

    println!("{}", farthest);

    let res = maze.num_tiles_enclosed_by_loop();

    println!("{}", res);
}