path: root/2019/src/bin/day_3.rs

use rpds::vector::Vector;
use std::fmt;
use std::io;
use std::io::prelude::*;
use std::process;
use std::str::FromStr;
use structopt::StructOpt;

#[derive(Debug, StructOpt)]
#[structopt(name = "Day 3: Crossed Wires")]
/// Finds the closest intersection between two wires. By default,
/// 'closest' is defined as closest in terms of Manhattan distance. If
/// --signal-distance is set, distance is defined in terms of the
/// total distance along the wire.
///
/// See https://adventofcode.com/2019/day/3 for details.
struct Opt {
    #[structopt(short = "s", long = "signal-distance")]
    /// returns the closest intersection by signal distance.
    signal_distance: bool,
}

fn main() {
    let stdin = io::stdin();
    let opt = Opt::from_args();

    let mut input = stdin
        .lock()
        .lines()
        .map(|x| exit_on_failed_assertion(x, "Error reading input"))
        .map(|x| exit_on_failed_assertion(x.parse::<Wire>(), "Input was not a valid wire"));

    let (wire1, wire2) = match (input.next(), input.next()) {
        (Some(w1), Some(w2)) => (w1, w2),
        _ => {
            eprintln!("Input must have two wires");
            process::exit(1);
        }
    };

    match wire1.closest_collision(&wire2, opt.signal_distance) {
        Some(c) => println!(
            "{}",
            if opt.signal_distance {
                c.signal_distance
            } else {
                c.manhattan_distance()
            }
        ),
        None => {
            eprintln!("No collisions");
            process::exit(1);
        }
    }
}

fn exit_on_failed_assertion<A, E: std::error::Error>(data: Result<A, E>, message: &str) -> A {
    match data {
        Ok(data) => data,
        Err(e) => {
            eprintln!("{}: {}", message, e);
            process::exit(1);
        }
    }
}

#[derive(Debug, Clone)]
struct Wire {
    segments: Vector<WireSegment>,
}

impl FromStr for Wire {
    type Err = UnknownError;

    fn from_str(s: &str) -> Result<Self, UnknownError> {
        s.split(',')
            .fold(
                Ok(Vector::new()),
                |acc: Result<Vector<WireSegment>, UnknownError>, next_str| {
                    acc.and_then(|previous_segments| {
                        WireSegment::from_str(
                            previous_segments.last().map(|l| l.end()).unwrap_or((0, 0)),
                            previous_segments
                                .last()
                                .map(|l| l.end_signal_distance())
                                .unwrap_or(0),
                            next_str,
                        )
                        .map(|seg| previous_segments.push_back(seg))
                    })
                },
            )
            .map(|segments| Wire { segments })
    }
}

impl Wire {
    fn closest_collision(&self, other: &Wire, use_signal_distance: bool) -> Option<Collision> {
        self.collisions(other).min_by_key(|c| {
            if use_signal_distance {
                c.signal_distance
            } else {
                c.manhattan_distance()
            }
        })
    }

    fn collisions<'a>(&'a self, other: &'a Wire) -> impl Iterator<Item = Collision> + 'a {
        self.segments
            .iter()
            .flat_map(move |seg1| other.segments.iter().map(move |seg2| (seg1, seg2)))
            .flat_map(|(seg1, seg2)| seg1.collisions(seg2))
            .filter(|c| !(c.x == 0 && c.y == 0))
    }
}

#[derive(Debug, Clone)]
struct WireSegment {
    start: (i32, i32),
    start_signal_distance: i32,
    direction: Direction,
    length: i32,
}

impl WireSegment {
    fn from_str(
        start: (i32, i32),
        start_signal_distance: i32,
        s: &str,
    ) -> Result<Self, UnknownError> {
        s.parse::<Direction>().and_then(|direction| {
            WireSegment::length_from_str(s).map(|length| WireSegment {
                start,
                start_signal_distance,
                direction,
                length,
            })
        })
    }

    fn length_from_str(s: &str) -> Result<i32, UnknownError> {
        s.chars()
            .skip(1)
            .collect::<String>()
            .parse()
            .map_err(|_| UnknownError)
    }

    fn end(&self) -> (i32, i32) {
        (
            self.start.0 + self.direction.as_vec().0 * self.length,
            self.start.1 + self.direction.as_vec().1 * self.length,
        )
    }

    fn end_signal_distance(&self) -> i32 {
        self.start_signal_distance + self.length
    }

    fn collisions(&self, other: &WireSegment) -> Option<Collision> {
        use Direction::*;

        match (self.direction, other.direction) {
            (Left, Left) | (Right, Right) | (Up, Up) | (Down, Down) => None,
            (Left, Right) | (Right, Left) | (Up, Down) | (Down, Up) => None,
            (Left, Up) => collisions(
                self.end(),
                self.end_signal_distance(),
                self.length,
                -1,
                other.start,
                other.start_signal_distance,
                other.length,
                1,
            ),
            (Left, Down) => collisions(
                self.end(),
                self.end_signal_distance(),
                self.length,
                -1,
                other.end(),
                other.end_signal_distance(),
                other.length,
                -1,
            ),
            (Right, Up) => collisions(
                self.start,
                self.start_signal_distance,
                self.length,
                1,
                other.start,
                other.start_signal_distance,
                other.length,
                1,
            ),
            (Right, Down) => collisions(
                self.start,
                self.start_signal_distance,
                self.length,
                1,
                other.end(),
                other.end_signal_distance(),
                other.length,
                -1,
            ),
            (Down, Right) => collisions(
                other.start,
                other.start_signal_distance,
                other.length,
                1,
                self.end(),
                self.end_signal_distance(),
                self.length,
                -1,
            ),
            (Down, Left) => collisions(
                other.end(),
                other.end_signal_distance(),
                other.length,
                -1,
                self.end(),
                self.end_signal_distance(),
                self.length,
                -1,
            ),
            (Up, Right) => collisions(
                other.start,
                other.start_signal_distance,
                other.length,
                1,
                self.start,
                self.start_signal_distance,
                self.length,
                1,
            ),
            (Up, Left) => collisions(
                other.end(),
                other.end_signal_distance(),
                other.length,
                -1,
                self.start,
                self.start_signal_distance,
                self.length,
                1,
            ),
        }
    }
}

fn collisions(
    horizontal_start: (i32, i32),
    horizontal_start_signal_distance: i32,
    horizontal_length: i32,
    horizontal_signal_distance_multiplier: i32,
    vertical_start: (i32, i32),
    vertical_start_signal_distance: i32,
    vertical_length: i32,
    vertical_signal_distance_multiplier: i32,
) -> Option<Collision> {
    if horizontal_start.1 >= vertical_start.1
        && horizontal_start.1 <= vertical_start.1 + vertical_length
        && vertical_start.0 >= horizontal_start.0
        && vertical_start.0 <= horizontal_start.0 + horizontal_length
    {
        Some(Collision {
            x: vertical_start.0,
            y: horizontal_start.1,
            signal_distance: horizontal_start_signal_distance
                + (vertical_start.0 - horizontal_start.0) * horizontal_signal_distance_multiplier
                + vertical_start_signal_distance
                + (horizontal_start.1 - vertical_start.1) * vertical_signal_distance_multiplier,
        })
    } else {
        None
    }
}

#[derive(Debug, Clone, Copy)]
enum Direction {
    Up,
    Down,
    Left,
    Right,
}

impl FromStr for Direction {
    type Err = UnknownError;

    fn from_str(s: &str) -> Result<Self, UnknownError> {
        use Direction::*;
        match s.chars().next() {
            Some('L') => Ok(Left),
            Some('R') => Ok(Right),
            Some('U') => Ok(Up),
            Some('D') => Ok(Down),
            Some(_) => Err(UnknownError),
            None => Err(UnknownError),
        }
    }
}
impl Direction {
    fn as_vec(&self) -> (i32, i32) {
        use Direction::*;
        match self {
            Up => (0, 1),
            Down => (0, -1),
            Left => (-1, 0),
            Right => (1, 0),
        }
    }
}

struct Collision {
    x: i32,
    y: i32,
    signal_distance: i32,
}

impl Collision {
    fn manhattan_distance(&self) -> i32 {
        self.x.abs() + self.y.abs()
    }
}

#[derive(Debug, PartialEq)]
struct UnknownError;

impl fmt::Display for UnknownError {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        write!(f, "Unknown error")
    }
}
impl std::error::Error for UnknownError {}