summaryrefslogtreecommitdiff
path: root/2019/src/bin/day_3.rs
diff options
context:
space:
mode:
Diffstat (limited to '2019/src/bin/day_3.rs')
-rw-r--r--2019/src/bin/day_3.rs333
1 files changed, 333 insertions, 0 deletions
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::<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 {}