day-03.rs (4739B)
1 use std::fs::File;
2 use std::io::prelude::*;
3 use std::io::BufReader;
4
5 fn main() {
6 let input = BufReader::new(File::open("input.txt").unwrap())
7 .lines()
8 .map(|line| {
9 line.unwrap()
10 .trim()
11 .split(",")
12 .map(|x| x.to_string())
13 .collect::<Vec<String>>()
14 })
15 .collect::<Vec<Vec<String>>>();
16
17 println!("Rust:");
18 println!("Part 1: {}", part_1(&input));
19 println!("Part 2: {}", part_2(&input));
20 }
21
22 type Coord = (i32, i32);
23
24 fn build_path(ops: &Vec<String>) -> Vec<Coord> {
25 // Translates path to coordinates.
26 let mut path = ops
27 .iter()
28 .scan((0, 0), |curr, op| {
29 let steps = op[1..].parse::<i32>().unwrap();
30 let next = match &op[0..=0] {
31 "R" => (steps, 0),
32 "L" => (-steps, 0),
33 "U" => (0, steps),
34 "D" => (0, -steps),
35 _ => unreachable!(),
36 };
37 *curr = (curr.0 + next.0, curr.1 + next.1);
38 Some(curr.clone())
39 })
40 .collect::<Vec<Coord>>();
41 // Remove first step at the origin.
42 path.insert(0, (path[0].0.signum(), path[0].1.signum()));
43
44 path
45 }
46
47 fn build_steps(ops: &Vec<String>) -> Vec<i32> {
48 // Translates path to coordinates.
49 let mut steps = ops
50 .iter()
51 .scan(0, |steps, op| {
52 *steps += op[1..].parse::<i32>().unwrap();
53 Some(steps.clone())
54 })
55 .collect::<Vec<i32>>();
56 // We remove first step.
57 steps.insert(0, 1);
58 steps
59 }
60
61 fn get_min_intersection(
62 mut p1a: Coord,
63 mut p1b: Coord,
64 mut p2a: Coord,
65 mut p2b: Coord,
66 ) -> Option<Coord> {
67 // Returns distance of closest intersection if any.
68 // Always rotate p1 to be horizontal for easy processing.
69 let mut rotated = false;
70 if p1a.0 != p1b.0 {
71 p1a = (p1a.1, p1a.0);
72 p1b = (p1b.1, p1b.0);
73 p2a = (p2a.1, p2a.0);
74 p2b = (p2b.1, p2b.0);
75 rotated = true;
76 }
77
78 let res = if p2a.0 == p2b.0 {
79 if p1a.0 == p2a.0 {
80 // Both horizontal, check if intersecting.
81 let cross_start = std::cmp::max(p1a.1, p2a.1);
82 let cross_end = std::cmp::min(p1b.1, p2b.1);
83 if cross_start <= cross_end {
84 if cross_start * cross_end <= 0 {
85 Some((p1a.0, 0))
86 } else {
87 if cross_start.abs() <= cross_end.abs() {
88 Some((p1a.0, cross_start))
89 } else {
90 Some((p1a.0, cross_end))
91 }
92 }
93 } else {
94 None
95 }
96 } else {
97 None
98 }
99 } else {
100 // p2 is vertical, check for intersection.
101 if (p1a.0 - p2a.0) * (p1a.0 - p2b.0) <= 0 && (p2a.1 - p1a.1) * (p2a.1 - p1b.1) <= 0 {
102 Some((p1a.0, p2a.1))
103 } else {
104 None
105 }
106 };
107
108 if rotated {
109 if let Some((x, y)) = res {
110 Some((y, x))
111 } else {
112 None
113 }
114 } else {
115 res
116 }
117 }
118
119 fn part_1(input: &Vec<Vec<String>>) -> i32 {
120 // Build the line segments.
121 let path_1 = build_path(&input[0]);
122 let path_2 = build_path(&input[1]);
123
124 // Check if each line segment intersect.
125 let mut min_dist = i32::max_value();
126 for i in 1..path_1.len() {
127 for j in 1..path_2.len() {
128 if let Some(min_cross) =
129 get_min_intersection(path_1[i - 1], path_1[i], path_2[j - 1], path_2[j])
130 {
131 min_dist = min_dist.min(min_cross.0.abs() + min_cross.1.abs());
132 };
133 }
134 }
135
136 min_dist
137 }
138
139 fn part_2(input: &Vec<Vec<String>>) -> i32 {
140 // Build the line segments.
141 let path_1 = build_path(&input[0]);
142 let path_2 = build_path(&input[1]);
143 // Build the step counts.
144 let steps_1 = build_steps(&input[0]);
145 let steps_2 = build_steps(&input[1]);
146
147 // Check if each line segment intersect.
148 let mut min_steps = i32::max_value();
149 for i in 1..path_1.len() {
150 for j in 1..path_2.len() {
151 if let Some(min_cross) =
152 get_min_intersection(path_1[i - 1], path_1[i], path_2[j - 1], path_2[j])
153 {
154 let step_1 = steps_1[i - 1]
155 + (min_cross.0 - path_1[i - 1].0).abs()
156 + (min_cross.1 - path_1[i - 1].1).abs();
157 let step_2 = steps_2[j - 1]
158 + (min_cross.0 - path_2[j - 1].0).abs()
159 + (min_cross.1 - path_2[j - 1].1).abs();
160 min_steps = min_steps.min(step_1 + step_2);
161 };
162 }
163 }
164
165 min_steps
166 }