From 9892e3ebde304726903a1e5c358d05c2e343ea5e Mon Sep 17 00:00:00 2001 From: Justin Wernick Date: Tue, 19 Apr 2022 20:26:36 +0200 Subject: Refile for merging repos --- 2019/src/bin/day_3.rs | 333 ++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 333 insertions(+) create mode 100644 2019/src/bin/day_3.rs (limited to '2019/src/bin/day_3.rs') diff --git a/2019/src/bin/day_3.rs b/2019/src/bin/day_3.rs new file mode 100644 index 0000000..f4163bd --- /dev/null +++ b/2019/src/bin/day_3.rs @@ -0,0 +1,333 @@ +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::(), "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(data: Result, message: &str) -> A { + match data { + Ok(data) => data, + Err(e) => { + eprintln!("{}: {}", message, e); + process::exit(1); + } + } +} + +#[derive(Debug, Clone)] +struct Wire { + segments: Vector, +} + +impl FromStr for Wire { + type Err = UnknownError; + + fn from_str(s: &str) -> Result { + s.split(',') + .fold( + Ok(Vector::new()), + |acc: Result, 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 { + 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 + '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 { + s.parse::().and_then(|direction| { + WireSegment::length_from_str(s).map(|length| WireSegment { + start, + start_signal_distance, + direction, + length, + }) + }) + } + + fn length_from_str(s: &str) -> Result { + s.chars() + .skip(1) + .collect::() + .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 { + 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 { + 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 { + 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 {} -- cgit v1.2.3