main.rs (7647B)
1 use std::collections::{HashSet, VecDeque};
2
3 #[derive(Debug, Clone, Copy, PartialEq, Eq)]
4 enum Axis {
5 X,
6 Y,
7 Z,
8 }
9
10 #[derive(Debug, Clone, Copy, PartialEq, Eq)]
11 struct Mapping {
12 axis: [Axis; 3],
13 flip: [bool; 3],
14 }
15
16 #[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
17 struct Pos([i32; 3]);
18
19 impl Pos {
20 fn new(s: &str) -> Pos {
21 let coord = s
22 .split(",")
23 .map(|c| c.parse::<i32>().unwrap())
24 .collect::<Vec<_>>();
25 Pos([coord[0], coord[1], coord[2]])
26 }
27
28 fn remap(&self, mapping: Mapping) -> Self {
29 let mut coord = [0; 3];
30 for i in 0..3 {
31 match mapping.axis[i] {
32 Axis::X => {
33 coord[i] = self.0[0] * (if mapping.flip[i] { -1 } else { 1 });
34 }
35 Axis::Y => {
36 coord[i] = self.0[1] * (if mapping.flip[i] { -1 } else { 1 });
37 }
38 Axis::Z => {
39 coord[i] = self.0[2] * (if mapping.flip[i] { -1 } else { 1 });
40 }
41 }
42 }
43 Pos(coord)
44 }
45
46 fn project(&self, mapping: Mapping, src: Pos, dest: Pos) -> Self {
47 // remaps self, then applies projection same as from mapped(src) -> dest
48 let mapped_src = src.remap(mapping);
49 let mapped_self = self.remap(mapping);
50 Pos([
51 mapped_self.0[0] + (dest.0[0] - mapped_src.0[0]),
52 mapped_self.0[1] + (dest.0[1] - mapped_src.0[1]),
53 mapped_self.0[2] + (dest.0[2] - mapped_src.0[2]),
54 ])
55 }
56
57 fn dist(&self, other: &Pos) -> (i32, i32) {
58 (
59 (self.0[0] - other.0[0]).abs()
60 + (self.0[1] - other.0[1]).abs()
61 + (self.0[2] - other.0[2]).abs(),
62 (self.0[0] - other.0[0]).pow(2)
63 + (self.0[1] - other.0[1]).pow(2)
64 + (self.0[2] - other.0[2]).pow(2),
65 )
66 }
67 }
68
69 fn main() {
70 let scanner_data = {
71 let mut tmp = Vec::<Vec<Pos>>::new();
72 let mut curr_scanner = Vec::<Pos>::new();
73 for l in std::fs::read_to_string("input.txt")
74 .unwrap()
75 .trim()
76 .split('\n')
77 {
78 if l == "" {
79 tmp.push(curr_scanner);
80 curr_scanner = Vec::new();
81 } else if !l.starts_with("--") {
82 curr_scanner.push(Pos::new(l));
83 }
84 }
85 tmp.push(curr_scanner);
86 tmp
87 };
88 // 425
89 let (count, scanner_coord) = part_1(&scanner_data);
90 println!("Part 1: {}", count);
91 // 13354
92 println!("Part 2: {}", part_2(&scanner_coord));
93 }
94
95 fn part_1(scanner_data: &Vec<Vec<Pos>>) -> (usize, Vec<Pos>) {
96 let all_mapping = {
97 let mut tmp = Vec::<Mapping>::new();
98 let basic = vec![
99 Mapping {
100 axis: [Axis::X, Axis::Y, Axis::Z],
101 flip: [false, false, false],
102 },
103 Mapping {
104 axis: [Axis::X, Axis::Y, Axis::Z],
105 flip: [true, false, true],
106 },
107 Mapping {
108 axis: [Axis::Y, Axis::X, Axis::Z],
109 flip: [false, true, false],
110 },
111 Mapping {
112 axis: [Axis::Y, Axis::X, Axis::Z],
113 flip: [true, false, false],
114 },
115 Mapping {
116 axis: [Axis::Z, Axis::Y, Axis::X],
117 flip: [false, false, true],
118 },
119 Mapping {
120 axis: [Axis::Z, Axis::Y, Axis::X],
121 flip: [true, false, false],
122 },
123 ];
124 for m in basic {
125 // generate all 4 rotations
126 tmp.push(m);
127 tmp.push(Mapping {
128 axis: [m.axis[0], m.axis[2], m.axis[1]],
129 flip: [m.flip[0], m.flip[2], !m.flip[1]],
130 });
131 tmp.push(Mapping {
132 axis: [m.axis[0], m.axis[1], m.axis[2]],
133 flip: [m.flip[0], !m.flip[1], !m.flip[2]],
134 });
135 tmp.push(Mapping {
136 axis: [m.axis[0], m.axis[2], m.axis[1]],
137 flip: [m.flip[0], !m.flip[2], m.flip[1]],
138 });
139 }
140 tmp
141 };
142
143 let mut scanner_coord = vec![None; scanner_data.len()];
144 scanner_coord[0] = Some(Pos([0, 0, 0]));
145 let mut all_beacons = HashSet::<Pos>::new();
146 for x in scanner_data[0].iter() {
147 all_beacons.insert(*x);
148 }
149 // remapped and transferred to scanner 0 format
150 let mut corrected_scanner_data = vec![None; scanner_data.len()];
151 corrected_scanner_data[0] = Some(scanner_data[0].clone());
152 let mut match_queue = VecDeque::new();
153 match_queue.push_back(0);
154 while let Some(to_match) = match_queue.pop_front() {
155 let ref_data = corrected_scanner_data[to_match].clone().unwrap();
156 for matched in 0..scanner_data.len() {
157 if corrected_scanner_data[matched].is_none() {
158 // see if we have more than 12 matching points
159 let mut matching_pairs = Vec::new();
160 for a in 0..ref_data.len() {
161 for b in 0..scanner_data[matched].len() {
162 let dist_a = ref_data
163 .iter()
164 .map(|x| ref_data[a].dist(x))
165 .collect::<HashSet<_>>();
166 let dist_b = scanner_data[matched]
167 .iter()
168 .map(|x| scanner_data[matched][b].dist(x))
169 .collect::<HashSet<_>>();
170 // measuring 12 points ensures unique identification (self + 11 others)
171 if dist_a.intersection(&dist_b).count() >= 12 {
172 matching_pairs.push((a, b));
173 }
174 }
175 }
176 // find right mapping by matching calculated scanner position
177 for mapping in all_mapping.iter() {
178 let possible_scanner_pos = matching_pairs
179 .iter()
180 .map(|&(a, b)| {
181 let a = ref_data[a];
182 let b = scanner_data[matched][b].remap(*mapping);
183 Pos([a.0[0] - b.0[0], a.0[1] - b.0[1], a.0[2] - b.0[2]])
184 })
185 .collect::<HashSet<_>>();
186 if possible_scanner_pos.len() == 1 {
187 scanner_coord[matched] = Some(*possible_scanner_pos.iter().next().unwrap());
188 match_queue.push_back(matched);
189 let mut corrected_data = Vec::new();
190 for x in scanner_data[matched].iter() {
191 let x = x.project(
192 *mapping,
193 scanner_coord[0].unwrap(),
194 scanner_coord[matched].unwrap(),
195 );
196 all_beacons.insert(x);
197 corrected_data.push(x);
198 }
199 corrected_scanner_data[matched] = Some(corrected_data);
200 break;
201 }
202 }
203 }
204 }
205 }
206 (
207 all_beacons.len(),
208 scanner_coord.into_iter().map(|x| x.unwrap()).collect(),
209 )
210 }
211
212 fn part_2(scanner_coord: &Vec<Pos>) -> i32 {
213 let mut max_mdist = 0;
214 for a in scanner_coord.iter() {
215 for b in scanner_coord.iter() {
216 max_mdist = max_mdist.max(a.dist(b).0);
217 }
218 }
219 max_mdist
220 }