diff options
| -rw-r--r-- | Cargo.lock | 25 | ||||
| -rw-r--r-- | Cargo.toml | 3 | ||||
| -rw-r--r-- | inputs/day_3.txt | 2 | ||||
| -rw-r--r-- | src/bin/day_3.rs | 333 |
4 files changed, 362 insertions, 1 deletions
@@ -6,6 +6,7 @@ version = "0.1.0" dependencies = [ "derive_more 0.99.2 (registry+https://github.com/rust-lang/crates.io-index)", "im 14.0.0 (registry+https://github.com/rust-lang/crates.io-index)", + "rpds 0.7.0 (registry+https://github.com/rust-lang/crates.io-index)", "structopt 0.3.5 (registry+https://github.com/rust-lang/crates.io-index)", ] @@ -18,6 +19,14 @@ dependencies = [ ] [[package]] +name = "archery" +version = "0.3.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +dependencies = [ + "static_assertions 0.3.4 (registry+https://github.com/rust-lang/crates.io-index)", +] + +[[package]] name = "atty" version = "0.2.13" source = "registry+https://github.com/rust-lang/crates.io-index" @@ -129,6 +138,14 @@ dependencies = [ ] [[package]] +name = "rpds" +version = "0.7.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +dependencies = [ + "archery 0.3.0 (registry+https://github.com/rust-lang/crates.io-index)", +] + +[[package]] name = "sized-chunks" version = "0.5.0" source = "registry+https://github.com/rust-lang/crates.io-index" @@ -138,6 +155,11 @@ dependencies = [ ] [[package]] +name = "static_assertions" +version = "0.3.4" +source = "registry+https://github.com/rust-lang/crates.io-index" + +[[package]] name = "strsim" version = "0.8.0" source = "registry+https://github.com/rust-lang/crates.io-index" @@ -232,6 +254,7 @@ source = "registry+https://github.com/rust-lang/crates.io-index" [metadata] "checksum ansi_term 0.11.0 (registry+https://github.com/rust-lang/crates.io-index)" = "ee49baf6cb617b853aa8d93bf420db2383fab46d314482ca2803b40d5fde979b" +"checksum archery 0.3.0 (registry+https://github.com/rust-lang/crates.io-index)" = "d308d8fa3f687f7a7588fccc4812ed6914be09518232f00454693a7417273ad2" "checksum atty 0.2.13 (registry+https://github.com/rust-lang/crates.io-index)" = "1803c647a3ec87095e7ae7acfca019e98de5ec9a7d01343f611cf3152ed71a90" "checksum bitflags 1.2.1 (registry+https://github.com/rust-lang/crates.io-index)" = "cf1de2fe8c75bc145a2f577add951f8134889b4795d47466a54a5c846d691693" "checksum bitmaps 2.0.0 (registry+https://github.com/rust-lang/crates.io-index)" = "81e039a80914325b37fde728ef7693c212f0ac913d5599607d7b95a9484aae0b" @@ -245,7 +268,9 @@ source = "registry+https://github.com/rust-lang/crates.io-index" "checksum quote 1.0.2 (registry+https://github.com/rust-lang/crates.io-index)" = "053a8c8bcc71fcce321828dc897a98ab9760bef03a4fc36693c231e5b3216cfe" "checksum rand_core 0.5.1 (registry+https://github.com/rust-lang/crates.io-index)" = "90bde5296fc891b0cef12a6d03ddccc162ce7b2aff54160af9338f8d40df6d19" "checksum rand_xoshiro 0.4.0 (registry+https://github.com/rust-lang/crates.io-index)" = "a9fcdd2e881d02f1d9390ae47ad8e5696a9e4be7b547a1da2afbc61973217004" +"checksum rpds 0.7.0 (registry+https://github.com/rust-lang/crates.io-index)" = "1196a0a2f52d343bd32179834273eaac7d8739f7e3f8b700227d2fa06b9a423b" "checksum sized-chunks 0.5.0 (registry+https://github.com/rust-lang/crates.io-index)" = "62db64dd92b3b54314b1e216c274634ca2b3fe8da8b3873be670cb1ac4dad30f" +"checksum static_assertions 0.3.4 (registry+https://github.com/rust-lang/crates.io-index)" = "7f3eb36b47e512f8f1c9e3d10c2c1965bc992bd9cdb024fa581e2194501c83d3" "checksum strsim 0.8.0 (registry+https://github.com/rust-lang/crates.io-index)" = "8ea5119cdb4c55b55d432abb513a0429384878c15dde60cc77b1c99de1a95a6a" "checksum structopt 0.3.5 (registry+https://github.com/rust-lang/crates.io-index)" = "30b3a3e93f5ad553c38b3301c8a0a0cec829a36783f6a0c467fc4bf553a5f5bf" "checksum structopt-derive 0.3.5 (registry+https://github.com/rust-lang/crates.io-index)" = "ea692d40005b3ceba90a9fe7a78fa8d4b82b0ce627eebbffc329aab850f3410e" @@ -7,4 +7,5 @@ edition = "2018" [dependencies] structopt = "0.3.5" derive_more = "0.99.2" -im = "14.0.0"
\ No newline at end of file +im = "14.0.0" +rpds = "0.7.0"
\ No newline at end of file diff --git a/inputs/day_3.txt b/inputs/day_3.txt new file mode 100644 index 0000000..504e9fe --- /dev/null +++ b/inputs/day_3.txt @@ -0,0 +1,2 @@ +R995,D882,R144,U180,L638,U282,L907,D326,R731,D117,R323,U529,R330,U252,R73,U173,R345,U552,R230,U682,R861,U640,L930,U590,L851,D249,R669,D878,R951,D545,L690,U392,R609,D841,R273,D465,R546,U858,L518,U567,L474,D249,L463,D390,L443,U392,L196,U418,R433,U651,R520,D450,R763,U714,R495,D716,L219,D289,L451,D594,R874,U451,R406,U662,R261,D242,R821,D951,R808,D862,L871,U133,R841,D465,R710,U300,R879,D497,R85,U173,R941,U953,R705,U972,R260,D315,L632,U182,L26,D586,R438,U275,L588,U956,L550,D576,R738,U974,R648,D880,R595,D510,L789,U455,R627,U709,R7,D486,L184,U999,L404,U329,L852,D154,L232,U398,L587,U881,R938,D40,L657,D164,R45,D917,R106,U698,L824,D426,R879,U700,R847,D891,L948,U625,R663,D814,R217,U30,R610,D781,L415,D435,L904,U815,R152,U587,R287,U141,R866,D636,L290,D114,L751,D660,R6,U383,L263,U799,R330,U96,L6,U542,L449,D361,R486,U278,L990,U329,L519,U605,R501,D559,R916,U198,L499,D174,R513,U396,L473,D565,R337,D770,R211,D10,L591,D920,R367,D748,L330,U249,L307,D645,R661,U266,R234,D403,L513,U443,L989,D1,L674,D210,L537,D872,L607,D961,R894,U632,L195,U744,L426,U531,R337,D821,R113,U436,L700,U779,R555,U891,R268,D30,R958,U411,R904,U24,R760,D958,R231,U229,L561,D134,L382,D961,L237,U676,L223,U324,R663,D186,R833,U188,R419,D349,L721,U152,L912,U490,R10,D995,L98,U47,R140,D815,R826,U730,R808,U256,R479,D322,L504,D891,L413,D848,L732,U375,L307,U7,R682,U270,L495,D248,R691,D945,L70,U220,R635,D159,R269,D15,L161,U214,R814,D3,R354,D632,R469,D36,R85,U215,L243,D183,R140,U179,R812,U180,L905,U136,L34,D937,L875 +L999,D22,L292,U843,R390,U678,R688,D492,L489,U488,R305,U951,L636,U725,R402,U84,L676,U171,L874,D201,R64,D743,R372,U519,R221,U986,L393,D793,R72,D184,L553,D137,L187,U487,L757,U880,L535,U887,R481,U236,L382,D195,L388,D90,R125,U414,R512,D382,R972,U935,L172,D1,R957,U593,L151,D158,R396,D42,L30,D178,R947,U977,R67,D406,R744,D64,L677,U23,R792,U864,R259,U315,R314,U17,L37,D658,L642,U135,R624,U601,L417,D949,R203,D122,R76,D493,L569,U274,L330,U933,R815,D30,L630,D43,R86,U926,L661,D491,L541,D96,R868,D565,R664,D935,L336,D152,R63,U110,L782,U14,R172,D945,L732,D870,R404,U767,L907,D558,R748,U591,R461,D153,L635,D457,R241,U478,L237,U218,R393,U468,L182,D745,L388,D360,L222,D642,L151,U560,R437,D326,R852,U525,R717,U929,L470,U621,R421,U408,L540,D176,L69,U753,L200,U251,R742,U628,R534,U542,R85,D71,R283,U905,L418,D755,L593,U335,L114,D684,L576,D645,R652,D49,R86,D991,L838,D309,L73,U847,L418,U675,R991,U463,R314,D618,L433,U173,R869,D115,L18,U233,R541,U516,L570,U340,R264,D442,L259,U276,R433,D348,R524,D353,R336,D883,R580,U157,R79,D27,L134,D161,L748,D278,R322,D581,R654,D156,L930,D293,L156,U311,R807,D618,R408,U719,R366,D632,R307,D565,R478,D620,R988,D821,R365,D581,L946,D138,L943,U69,R620,U208,L407,U188,L122,U353,L751,U565,R849,D874,R668,D794,L140,D474,R289,D773,R344,D220,L55,D385,L394,U208,R305,U736,L896,D376,R331,D855,L466,U516,L741,U124,L825,U467,L525,D911,R76,U220,L610,U102,L261,D891,L585,U397,L152,U753,R822,D252,R106,U145,L7,U524,R343,U352,L357,D399,L446,D140,L723,U46,R687,D409,R884 diff --git a/src/bin/day_3.rs b/src/bin/day_3.rs new file mode 100644 index 0000000..f4163bd --- /dev/null +++ b/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 {} |