8000 Day 19 · l0s/advent-of-code-java@4409fc7 · GitHub
[go: up one dir, main page]
Skip to content

Commit 4409fc7

Browse files
l0sl0s
committed
Day 19
1 parent 8f222bb commit 4409fc7

File tree

2 files changed

+531
-0
lines changed

2 files changed

+531
-0
lines changed

‎src/test/java/com/macasaet/Day19.java

Lines changed: 395 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,395 @@
1+
package com.macasaet;
2+
3+
import static org.junit.jupiter.api.Assertions.assertEquals;
4+
import static org.junit.jupiter.api.Assertions.assertTrue;
5+
6+
import java.util.*;
7+
import java.util.stream.Collectors;
8+
import java.util.stream.Stream;
9+
import java.util.stream.StreamSupport;
10+
11+
import org.junit.jupiter.api.Nested;
12+
import org.junit.jupiter.api.Test;
13+
14+
/**
15+
* --- Day 19: Beacon Scanner ---
16+
*/
17+
public class Day19 {
18+
19+
protected Stream<String> getInput() {
20+
return StreamSupport
21+
.stream(new LineSpliterator("day-19.txt"),
22+
false);
23+
}
24+
25+
protected List<Scanner> getScanners() {
26+
final var list = getInput().toList();
27+
final var result = new ArrayList<Scanner>();
28+
var observations = new HashSet<Position>();
29+
int id = -1;
30+
for (final var line : list) {
31+
if (line.startsWith("--- scanner ")) {
32+
id = Integer.parseInt(line
33+
.replaceFirst("^--- scanner ", "")
34+
.replaceFirst(" ---$", ""));
35+
} else if (!line.isBlank()) {
36+
observations.add(Position.parse(line));
37+
} else { // line is blank
38+
result.add(new Scanner(id, Collections.unmodifiableSet(observations)));
39+
observations = new HashSet<>();
40+
id = -1;
41+
}
42+
}
43+
result.add(new Scanner(id, Collections.unmodifiableSet(observations)));
44+
return Collections.unmodifiableList(result);
45+
}
46+
47+
public enum Direction {
48+
POSITIVE_X {
49+
public Position face(Position position) {
50+
return position;
51+
}
52+
},
53+
NEGATIVE_X {
54+
public Position face(Position position) {
55+
return new Position(-position.x(), position.y(), -position.z());
56+
}
57+
},
58+
POSITIVE_Y {
59+
public Position face(Position position) {
60+
return new Position(position.y(), -position.x(), position.z());
61+
}
62+
},
63+
NEGATIVE_Y {
64+
public Position face(Position position) {
65+
return new Position(-position.y(), position.x(), position.z());
66+
}
67+
},
68+
POSITIVE_Z {
69+
public Position face(Position position) {
70+
return new Position(position.z(), position.y(), -position.x());
71+
}
72+
},
73+
NEGATIVE_Z {
74+
public Position face(Position position) {
75+
return new Position(-position.z(), position.y(), position.x());
76+
}
77+
};
78+
79+
public abstract Position face(final Position position);
80+
81+
}
82+
83+
public enum Rotation {
84+
r0 {
85+
public Position rotate(final Position position) {
86+
return position;
87+
}
88+
},
89+
r90 {
90+
public Position rotate(Position position) {
91+
return new Position(position.x(), -position.z(), position.y());
92+
}
93+
},
94+
r180 {
95+
public Position rotate(Position position) {
96+
return new Position(position.x(), -position.y(), -position.z());
97+
}
98+
},
99+
r270 {
100+
public Position rotate(Position position) {
101+
return new Position(position.x(), position.z(), -position.y());
102+
}
103+
};
104+
105+
public abstract Position rotate(final Position position);
106+
}
107+
108+
public record Transformation(Direction direction, Rotation rotation) {
109+
/**
110+
* Look at a position from a specific orientation
111+
*
112+
* @param position a position relative to one point of view
113+
* @return the same position relative to a different point of view
114+
*/
115+
public Position reorient(final Position position) {
116+
return rotation.rotate(direction.face(position));
117+
}
118+
119+
}
120+
121+
public record Position(int x, int y, int z) {
122+
public static Position parse(final String line) {
123+
final var components = line.split(",");
124+
return new Position(Integer.parseInt(components[0]),
125+
Integer.parseInt(components[1]),
126+
Integer.parseInt(components[2]));
127+
}
128+
129+
public Position plus(Position amount) {
130+
return new Position(x() + amount.x(), y() + amount.y(), z() + amount.z());
131+
}
132+
133+
public Position minus(final Position other) {
134+
return new Position(x() - other.x(), y() - other.y(), z() - other.z());
135+
}
136+
}
137+
138+
public interface OverlapResult {
139+
}
140+
141+
public record Overlap(Position distance, Transformation transformation,
142+
Set<Position> overlappingBeacons) implements OverlapResult {
143+
}
144+
145+
public record None() implements OverlapResult {
146+
}
147+
148+
public record Scanner(int id, Set<Position> observations) {
149+
150+
public OverlapResult getOverlappingBeacons(final Scanner other) {
151+
for (final var direction : Direction.values()) {
152+
for (final var rotation : Rotation.values()) {
153+
final var transformation = new Transformation(direction, rotation);
154+
final var distances = observations().stream()
155+
.flatMap(a -> other.observations()
156+
.stream()
157+
.map(transformation::reorient)
158+
.map(a::minus))
159+
.collect(Collectors.toList());
160+
for (final var offset : distances) {
161+
final var intersection = other.observations()
162+
.stream()
163+
.map(transformation::reorient)
164+
.map(observation -> observation.plus(offset))
165+
.filter(observations()::contains)
166+
.collect(Collectors.toUnmodifiableSet());
167+
if (intersection.size() >= 12) {
168+
return new Overlap(offset, transformation, intersection);
169+
}
170+
}
171+
}
172+
}
173+
return new None();
174+
}
175+
176+
}
177+
178+
@Nested
179+
public class ScannerTest {
180+
@Test
181+
public final void testOverlapWithOrigin() {
182+
// given
183+
final var scanner0Observations = """
184+
404,-588,-901
185+
528,-643,409
186+
-838,591,734
187+
390,-675,-793
188+
-537,-823,-458
189+
-485,-357,347
190+
-345,-311,381
191+
-661,-816,-575
192+
-876,649,763
193+
-618,-824,-621
194+
553,345,-567
195+
474,580,667
196+
-447,-329,318
197+
-584,868,-557
198+
544,-627,-890
199+
564,392,-477
200+
455,729,728
201+
-892,524,684
202+
-689,845,-530
203+
423,-701,434
204+
7,-33,-71
205+
630,319,-379
206+
443,580,662
207+
-789,900,-551
208+
459,-707,401
209+
""";
210+
final var scanner1Observations = """
211+
686,422,578
212+
605,423,415
213+
515,917,-361
214+
-336,658,858
215+
95,138,22
216+
-476,619,847
217+
-340,-569,-846
218+
567,-361,727
219+
-460,603,-452
220+
669,-402,600
221+
729,430,532
222+
-500,-761,534
223+
-322,571,750
224+
-466,-666,-811
225+
-429,-592,574
226+
-355,545,-477
227+
703,-491,-529
228+
-328,-685,520
229+
413,935,-424
230+
-391,539,-444
231+
586,-435,557
232+
-364,-763,-893
233+
807,-499,-711
234+
755,-354,-619
235+
553,889,-390
236+
""";
237+
final var scanner0 = new Scanner(0,
238+
Arrays.stream(scanner0Observations.split("\n"))
239+
.map(Position::parse)
240+
.collect(Collectors.toUnmodifiableSet()));
241+
final var scanner1 = new Scanner(0,
242+
Arrays.stream(scanner1Observations.split("\n"))
243+
.map(Position::parse)
244+
.collect(Collectors.toUnmodifiableSet()));
245+
246+
// when
247+
final var result = scanner0.getOverlappingBeacons(scanner1);
248+
249+
// then
250+
assertTrue(result instanceof Overlap);
251+
final var overlap = (Overlap) result;
252+
assertEquals(12, overlap.overlappingBeacons().size());
253+
}
254+
255+
@Test
256+
public final void testOverlapWithNonOrigin() {
257+
// given
258+
final var scanner1Observations = """
259+
686,422,578
260+
605,423,415
261+
515,917,-361
262+
-336,658,858
263+
95,138,22
264+
-476,619,847
265+
-340,-569,-846
266+
567,-361,727
267+
-460,603,-452
268+
669,-402,600
269+
729,430,532
270+
-500,-761,534
271+
-322,571,750
272+
-466,-666,-811
273+
-429,-592,574
274+
-355,545,-477
275+
703,-491,-529
276+
-328,-685,520
277+
413,935,-424
278+
-391,539,-444
279+
586,-435,557
280+
-364,-763,-893
281+
807,-499,-711
282+
755,-354,-619
283+
553,889,-390
284+
""";
285+
final var scanner4Observations = """
286+
727,592,562
287+
-293,-554,779
288+
441,611,-461
289+
-714,465,-776
290+
-743,427,-804
291+
-660,-479,-426
292+
832,-632,460
293+
927,-485,-438
294+
408,393,-506
295+
466,436,-512
296+
110,16,151
297+
-258,-428,682
298+
-393,719,612
299+
-211,-452,876
300+
808,-476,-593
301+
-575,615,604
302+
-485,667,467
303+
-680,325,-822
304+
-627,-443,-432
305+
872,-547,-609
306+
833,512,582
307+
807,604,487
308+
839,-516,451
309+
891,-625,532
310+
-652,-548,-490
311+
30,-46,-14
312+
""";
313+
final var scanner1 = new Scanner(0,
314+
Arrays.stream(scanner1Observations.split("\n"))
315+
.map(Position::parse)
316+
.collect(Collectors.toUnmodifiableSet()));
317+
final var scanner4 = new Scanner(0,
318+
Arrays.stream(scanner4Observations.split("\n"))
319+
.map(Position::parse)
320+
.collect(Collectors.toUnmodifiableSet()));
321+
322+
// when
323+
final var result = scanner1.getOverlappingBeacons(scanner4);
324+
325+
// then
326+
assertTrue(result instanceof Overlap);
327+
final var overlap = (Overlap) result;
328+
assertEquals(12, overlap.overlappingBeacons().size());
329+
}
330+
}
331+
332+
@Test
333+
public final void part1() {
334+
final var scanners = getScanners();
335+
final var knownBeacons = new HashSet<Position>();
336+
final var origin = new Scanner(-1, knownBeacons);
337+
final var remaining = new ArrayList<>(scanners);
338+
while (!remaining.isEmpty()) {
339+
final var other = remaining.remove(0);
340+
if (knownBeacons.isEmpty()) {
341+
knownBeacons.addAll(other.observations());
342+
continue;
343+
}
344+
final var result = origin.getOverlappingBeacons(other);
345+
if (result instanceof final Overlap overlap) {
346+
knownBeacons.addAll(other.observations()
347+
.stream()
348+
.map(overlap.transformation()::reorient)
349+
.map(observation -> observation.plus(overlap.distance()))
350+
.collect(Collectors.toList()));
351+
} else {
352+
remaining.add(other);
353+
}
354+
}
355+
System.out.println("Part 1: " + knownBeacons.size());
356+
}
357+
358+
@Test
359+
public final void part2() {
360+
final var scanners = getScanners();
361+
final var knownBeacons = new HashSet<Position>();
362+
final var origin = new Scanner(-1, knownBeacons);
363+
final var remaining = new ArrayList<>(scanners);
364+
final var distances = new HashSet<Position>();
365+
while (!remaining.isEmpty()) {
366+
final var other = remaining.remove(0);
367+
if (knownBeacons.isEmpty()) {
368+
knownBeacons.addAll(other.observations());
369+
continue;
370+
}
371+
final var result = origin.getOverlappingBeacons(other);
372+
if (result instanceof final Overlap overlap) {
373+
knownBeacons.addAll(other.observations()
374+
.stream()
375+
.map(overlap.transformation()::reorient)
376+
.map(observation -> observation.plus(overlap.distance()))
377+
.collect(Collectors.toList()));
378+
distances.add(overlap.distance());
379+
} else {
380+
remaining.add(other);
381+
}
382+
}
383+
int maxDistance = Integer.MIN_VALUE;
384+
for (final var x : distances) {
385+
for (final var y : distances) {
386+
final int distance = Math.abs(x.x() - y.x())
387+
+ Math.abs(x.y() - y.y())
388+
+ Math.abs(x.z() - y.z());
389+
maxDistance = Math.max(maxDistance, distance);
390+
}
391+
}
392+
System.out.println("Part 2: " + maxDistance);
393+
}
394+
395+
}

0 commit comments

Comments
 (0)
0