aoc 2023 solutions

day10.rs

#[allow(dead_code)]
use std::path::PathBuf;

use itertools::iproduct;
use nom::*;
use nom::{branch::*, character::complete::*, combinator::*, multi::*};
use nom_locate::LocatedSpan;

use crate::download::CachedDownloader;
use crate::parsers::Span;

#[tracing::instrument]
pub fn execute(part: crate::Part) -> anyhow::Result<Box<dyn std::fmt::Display>> {
    let dl = CachedDownloader::new(PathBuf::from("./aoc-session.cookie"))?;
    tracing::trace!("get-input-body");
    let body = dl.get_input("https://adventofcode.com/2023/day/10/input")?;

    process(body.as_str(), part)
}

fn tile(input: Span) -> IResult<Span, (Tile, Option<Position>)> {
    let (s, c) = alt((
        char('|'),
        char('-'),
        char('L'),
        char('J'),
        char('7'),
        char('F'),
        char('.'),
        char('S'),
    ))(input)?;

    let t = match c {
        '|' => (Tile::VerticalPipe, None),
        '-' => (Tile::HorizontalPipe, None),
        'L' => (Tile::NEBend, None),
        'J' => (Tile::NWBend, None),
        '7' => (Tile::SWBend, None),
        'F' => (Tile::SEBend, None),
        '.' => (Tile::Ground, None),
        'S' => {
            let x = input.get_column() - 1;
            let y = input.location_line() as usize - 1;
            (Tile::AnimalStartPosition, Some(Position { x: x, y: y }))
        }
        _ => unreachable!(),
    };

    Ok((s, t))
}

fn row(s: Span) -> IResult<Span, (Vec<Tile>, Option<Position>)> {
    let (s, (ts, _)) = many_till(tile, newline)(s)?;
    let position = ts.iter().find_map(|(_, p)| p.as_ref().cloned());
    let ts = ts.into_iter().map(|(tile, _)| tile).collect();
    Ok((s, (ts, position)))
}

fn parse_input(s: Span) -> IResult<Span, Input> {
    let (s, (tiles, _)) = many_till(row, eof)(s)?;
    let animal_starting_position = tiles.iter().find_map(|(_, p)| p.as_ref().cloned()).unwrap();
    let tiles = tiles.into_iter().map(|(tile, _)| tile).collect();
    let i = Input {
        grid: Grid { tiles },
        animal_starting_position,
    };
    Ok((s, i))
}

#[derive(Clone, Debug, Default, Eq, PartialEq)]
struct Position {
    x: usize,
    y: usize,
}

impl Position {
    fn get_surrounding(&self) -> Vec<Position> {
        let xs = if self.x > 0 {
            self.x - 1..self.x + 2
        } else {
            self.x..self.x + 2
        };
        let ys = if self.y > 0 {
            self.y - 1..self.y + 2
        } else {
            self.y..self.y + 2
        };
        //println!("x range: {xs:?}");
        //println!("y range: {ys:?}");
        iproduct!(xs, ys)
            .filter_map(|(x, y)| {
                if (x, y) == (self.x, self.y) {
                    //println!("rejecting ({x}, {y})");
                    None
                } else {
                    //println!("including ({x}, {y})");
                    Some(Position { x, y })
                }
            })
            .collect()
    }

    #[inline]
    fn inc(&self, incx: isize, incy: isize) -> Option<Position> {
        let x = if incx < 0 {
            if self.x == 0 {
                return None;
            }
            self.x - incx.abs() as usize
        } else {
            self.x + incx.abs() as usize
        };
        let y = if incy < 0 {
            if self.y == 0 {
                return None;
            }
            self.y - incy.abs() as usize
        } else {
            self.y + incy.abs() as usize
        };
        Some(Position { x, y })
    }

    fn update(&mut self, from: &Self) {
        self.x = from.x;
        self.y = from.y;
    }
}

#[derive(Debug)]
enum Tile {
    VerticalPipe,
    HorizontalPipe,
    NEBend,
    SEBend,
    NWBend,
    SWBend,
    Ground,
    AnimalStartPosition,
}

impl std::fmt::Display for Tile {
    fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
        match self {
            Self::VerticalPipe => write!(f, "║"),
            Self::HorizontalPipe => write!(f, "═"),
            Self::NEBend => write!(f, "╚"),
            Self::SEBend => write!(f, "╔"),
            Self::NWBend => write!(f, "╝"),
            Self::SWBend => write!(f, "╗"),
            Self::Ground => write!(f, " "),
            Self::AnimalStartPosition => write!(f, "S"),
        }
    }
}

struct Grid {
    tiles: Vec<Vec<Tile>>,
}

impl Grid {
    fn get_connected(&self, current: &Position) -> (Option<Position>, Option<Position>) {
        let tile = self.tiles.get(current.y).unwrap().get(current.x).unwrap();
        let (next, previous) = match tile {
            Tile::VerticalPipe => (current.inc(0, -1), current.inc(0, 1)),
            Tile::HorizontalPipe => (current.inc(-1, 0), current.inc(1, 0)),
            Tile::NEBend => (current.inc(0, -1), current.inc(1, 0)),
            Tile::SEBend => (current.inc(0, 1), current.inc(1, 0)),
            Tile::NWBend => (current.inc(0, -1), current.inc(-1, 0)),
            Tile::SWBend => (current.inc(0, 1), current.inc(-1, 0)),
            Tile::Ground => return (None, None),
            Tile::AnimalStartPosition => {
                println!("looking for connected segements of {current:?}");
                let surrounding = current.get_surrounding();
                //println!("looking in {surrounding:?}");
                let mut surrounding = surrounding.into_iter();
                //println!("looking for next");
                let next = surrounding.find(|p| {
                    //println!("checking {p:?}");
                    match self.get_connected(p) {
                        (Some(cn), Some(_)) if *current == cn => true,
                        (Some(cn), None) if *current == cn => false,
                        (Some(_), Some(cp)) if *current == cp => true,
                        (None, Some(cp)) if *current == cp => false,
                        (_, _) => false,
                    }
                });
                //println!("found next: {next:?}");
                //println!("looking for previous");
                let previous = surrounding.find(|p| {
                    //println!("checking {p:?}");
                    match self.get_connected(p) {
                        (Some(cn), Some(_)) if *current == cn => true,
                        (Some(cn), None) if *current == cn => false,
                        (Some(_), Some(cp)) if *current == cp => true,
                        (None, Some(cp)) if *current == cp => false,
                        (_, _) => false,
                    }
                });
                //println!("found previous: {previous:?}");
                (next, previous)
            }
        };
        (next, previous)
    }

    fn pipe_iters(&self, start: Position) -> (PipeIter, PipeIter) {
        match self.get_connected(&start) {
            (Some(p), Some(n)) => (
                PipeIter {
                    grid: &self,
                    previous: start.clone(),
                    start: start.clone(),
                    current: p,
                },
                PipeIter {
                    grid: &self,
                    previous: start.clone(),
                    start: start.clone(),
                    current: n,
                },
            ),
            (_, _) => unreachable!(),
        }
    }
}

struct PipeIter<'a> {
    grid: &'a Grid,
    start: Position,
    previous: Position,
    current: Position,
}

impl<'a> std::fmt::Debug for PipeIter<'a> {
    fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
        write!(f, "{:?}\n", self.grid)?;
        write!(f, "   start: {:?}\n", self.start)?;
        write!(f, "previous: {:?}\n", self.previous)?;
        write!(f, " current: {:?}\n", self.current)
    }
}

impl<'a> Iterator for PipeIter<'a> {
    type Item = Position;

    fn next(&mut self) -> Option<Self::Item> {
        //println!("next:\n{self:?}");
        if self.current == self.start {
            println!("current == start, terminating PipeIter");
            return None;
        }
        let retval = self.current.clone();

        let (a, b) = self.grid.get_connected(&self.current);

        match (a, b) {
            (Some(a), Some(b)) if a == self.previous => {
                //println!("setting new current: {b:?}");
                self.previous.update(&self.current);
                self.current = b;
            }
            (Some(a), Some(b)) if b == self.previous => {
                //println!("setting new current: {a:?}");
                self.previous.update(&self.current);
                self.current = a;
            }
            (_, _) => {
                //println!("found {a:?} and {b:?}");
                unreachable!()
            }
        }

        //println!("returning {retval:?}");
        Some(retval)
    }
}

impl std::fmt::Debug for Grid {
    fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
        for row in &self.tiles {
            for column in row {
                write!(f, "{}", column)?;
            }
            write!(f, "\n")?;
        }
        Ok(())
    }
}

#[derive(Debug)]
struct Input {
    grid: Grid,
    animal_starting_position: Position,
}

fn process<'a>(body: &str, part: crate::Part) -> anyhow::Result<Box<dyn std::fmt::Display>> {
    tracing::trace!("parse-input-body");
    let span = LocatedSpan::new(body);
    let (_, input) = parse_input(span).map_err(|e| anyhow::Error::msg(format!("{e}")))?;

    tracing::trace!("process-input-body");
    let output = match part {
        crate::Part::One => {
            tracing::trace!("process-input-body");
            process_part1(input)
        }
        crate::Part::Two => {
            tracing::trace!("process-input-body");
            process_part2(input)
        }
    };

    Ok(Box::new(output))
}

fn process_part1(input: Input) -> u64 {
    //println!("{:?}", input.grid);
    //println!("start position: {:?}", input.animal_starting_position);
    let (backward, forward) = input.grid.pipe_iters(input.animal_starting_position);
    backward
        .zip(forward)
        .enumerate()
        .find(|(_, (b, f))| {
            //println!("checking {b:?} == {f:?}");
            b == f
        })
        .map(|(i, _)| i as u64 + 1u64)
        .expect("something bad happened")
}

fn process_part2(input: Input) -> u64 {
    0
}

#[cfg(test)]
mod test {
    use crate::read_to_string;

    use super::*;

    use rstest::rstest;

    #[rstest]
    #[case::actual_input("input_cache/httpsadventofcode.com2023day10input", "6690")]
    #[case::example_input("examples/day10part1_ex1", "4")]
    #[case::example_input("examples/day10part1_ex2", "4")]
    #[case::example_input("examples/day10part1_ex3", "8")]
    #[case::example_input("examples/day10part1_ex4", "8")]
    fn part1(#[case] path: PathBuf, #[case] expected: String) -> anyhow::Result<()> {
        let body = read_to_string(&path)?;
        let displayable = process(body.as_str(), crate::Part::One)?;
        assert_eq!(expected, format!("{displayable}"));

        Ok(())
    }

    // #[rstest]
    // //#[case::actual_input("input_cache/httpsadventofcode.com2023day10input", "")]
    // #[case::example_input("examples/day10part1", "")]
    // fn part2(#[case] path: PathBuf, #[case] expected: String) -> anyhow::Result<()> {
    //     let body = read_to_string(&path)?;
    //     let displayable = process(body.as_str(), crate::Part::Two)?;
    //     assert_eq!(expected, format!("{displayable}"));

    //     Ok(())
    // }
}