183 lines
5.1 KiB
Rust
183 lines
5.1 KiB
Rust
use std::io::BufRead;
|
|
use std::str::FromStr;
|
|
use std::num::ParseIntError;
|
|
use std::fmt::{self, Display};
|
|
use std::collections::{HashSet, HashMap};
|
|
|
|
use Segment::*;
|
|
|
|
#[derive(Debug, PartialEq)]
|
|
enum Segment {
|
|
Up(i32),
|
|
Down(i32),
|
|
Right(i32),
|
|
Left(i32),
|
|
}
|
|
|
|
enum SegmentError {
|
|
UnknownDirection(char),
|
|
ParseIntError(ParseIntError)
|
|
}
|
|
|
|
impl Display for SegmentError {
|
|
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
|
|
match *self {
|
|
SegmentError::UnknownDirection(direction) => write!(f, "Unknown direction `{}`", direction),
|
|
SegmentError::ParseIntError(ref e) => e.fmt(f),
|
|
}
|
|
}
|
|
}
|
|
|
|
impl FromStr for Segment {
|
|
type Err = SegmentError;
|
|
|
|
fn from_str(s: &str) -> Result<Self, Self::Err> {
|
|
let direction = s.chars().next().unwrap();
|
|
let length = s[1..].parse().map_err(|e| SegmentError::ParseIntError(e))?;
|
|
|
|
let segment = match direction {
|
|
'U' => Up(length),
|
|
'D' => Down(length),
|
|
'R' => Right(length),
|
|
'L' => Left(length),
|
|
direction => {
|
|
return Err(SegmentError::UnknownDirection(direction));
|
|
}
|
|
};
|
|
Ok(segment)
|
|
}
|
|
}
|
|
|
|
impl Segment {
|
|
#[inline]
|
|
fn direction(&self) -> (i32, i32) {
|
|
match self {
|
|
Up(_) => (0, 1),
|
|
Down(_) => (0, -1),
|
|
Right(_) => (1, 0),
|
|
Left(_) => (-1, 0),
|
|
}
|
|
}
|
|
|
|
#[inline]
|
|
fn length(&self) -> i32 {
|
|
match self {
|
|
Up(l) | Down(l) | Right(l) | Left(l) => *l
|
|
}
|
|
}
|
|
}
|
|
|
|
fn parse_input<F: BufRead> (input: &mut F) -> Vec<Segment> {
|
|
let mut buf = String::new();
|
|
let _num_bytes = input.read_line(&mut buf).expect("Unable to read a line of input file");
|
|
buf.trim().split(",").filter_map(|segment| segment.parse().ok()).collect()
|
|
}
|
|
|
|
pub fn part1<F: BufRead> (mut input: F) {
|
|
let path1 = parse_input(&mut input);
|
|
let path2 = parse_input(&mut input);
|
|
let res = compute_closest_intersection(path1, path2);
|
|
println!("{}", res);
|
|
}
|
|
|
|
fn compute_closest_intersection(path1: Vec<Segment>, path2: Vec<Segment>) -> i32 {
|
|
let steps1 = build_full_path(path1, 0, (0, 0), HashMap::new(), 1);
|
|
let steps2 = build_full_path(path2, 0, (0, 0), HashMap::new(), 1);
|
|
|
|
let seen1: HashSet<_> = steps1.keys().collect();
|
|
let seen2: HashSet<_> = steps2.keys().collect();
|
|
|
|
seen1.intersection(&seen2).map(|(x, y)| x.abs() + y.abs()).min().unwrap()
|
|
}
|
|
|
|
pub fn part2<F: BufRead> (mut input: F) {
|
|
let path1 = parse_input(&mut input);
|
|
let path2 = parse_input(&mut input);
|
|
let res = compute_first_intersection(path1, path2);
|
|
println!("{}", res);
|
|
}
|
|
|
|
fn compute_first_intersection(path1: Vec<Segment>, path2: Vec<Segment>) -> i32 {
|
|
let steps1 = build_full_path(path1, 0, (0, 0), HashMap::new(), 1);
|
|
let steps2 = build_full_path(path2, 0, (0, 0), HashMap::new(), 1);
|
|
|
|
let seen1: HashSet<_> = steps1.keys().collect();
|
|
let seen2: HashSet<_> = steps2.keys().collect();
|
|
|
|
seen1.intersection(&seen2).map(|coord| steps1[coord] + steps2[coord]).min().unwrap()
|
|
}
|
|
|
|
fn build_full_path(
|
|
path: Vec<Segment>,
|
|
index: usize,
|
|
(x0, y0): (i32, i32),
|
|
mut steps: HashMap<(i32, i32), i32>,
|
|
current_step: i32
|
|
) -> HashMap<(i32, i32), i32> {
|
|
if index == path.len() {
|
|
steps
|
|
} else {
|
|
let segment = &path[index];
|
|
let (dx, dy) = segment.direction();
|
|
let length = segment.length();
|
|
let mut current_step = current_step;
|
|
|
|
for i in 1..(length + 1) {
|
|
steps.entry((x0 + i * dx, y0 + i * dy)).or_insert(current_step);
|
|
current_step += 1;
|
|
}
|
|
|
|
build_full_path(path, index + 1, (x0 + length * dx, y0 + length * dy), steps, current_step)
|
|
}
|
|
}
|
|
|
|
#[cfg(test)]
|
|
mod test {
|
|
use super::*;
|
|
|
|
#[test]
|
|
fn test_input_parsing() {
|
|
let mut input = "U7,R6,D4,L4\n".as_bytes();
|
|
let expected = vec![Up(7), Right(6), Down(4), Left(4)];
|
|
|
|
let res = parse_input(&mut input);
|
|
assert_eq!(res, expected);
|
|
}
|
|
|
|
#[test]
|
|
fn test_compute_closest_intersection() {
|
|
let mut input = r#"R8,U5,L5,D3
|
|
U7,R6,D4,L4
|
|
R75,D30,R83,U83,L12,D49,R71,U7,L72
|
|
U62,R66,U55,R34,D71,R55,D58,R83
|
|
R98,U47,R26,D63,R33,U87,L62,D20,R33,U53,R51
|
|
U98,R91,D20,R16,D67,R40,U7,R15,U6,R7
|
|
"#.as_bytes();
|
|
let test_results = [6, 159, 135];
|
|
for expected in &test_results {
|
|
let path1 = parse_input(&mut input);
|
|
let path2 = parse_input(&mut input);
|
|
let res = compute_closest_intersection(path1, path2);
|
|
assert_eq!(res, *expected)
|
|
}
|
|
}
|
|
|
|
#[test]
|
|
fn test_compute_first_intersection() {
|
|
let mut input = r#"R8,U5,L5,D3
|
|
U7,R6,D4,L4
|
|
R75,D30,R83,U83,L12,D49,R71,U7,L72
|
|
U62,R66,U55,R34,D71,R55,D58,R83
|
|
R98,U47,R26,D63,R33,U87,L62,D20,R33,U53,R51
|
|
U98,R91,D20,R16,D67,R40,U7,R15,U6,R7
|
|
"#.as_bytes();
|
|
let test_results = [30, 610, 410];
|
|
for expected in &test_results {
|
|
let path1 = parse_input(&mut input);
|
|
let path2 = parse_input(&mut input);
|
|
let res = compute_first_intersection(path1, path2);
|
|
assert_eq!(res, *expected)
|
|
}
|
|
}
|
|
}
|