-
Notifications
You must be signed in to change notification settings - Fork 0
/
Day15.java
146 lines (127 loc) · 5.21 KB
/
Day15.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
import org.junit.jupiter.api.Test;
import java.io.BufferedReader;
import java.io.FileReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import static org.junit.jupiter.api.Assertions.assertEquals;
public class Day15 {
@Test
public void day15() throws Exception {
// parse the input; collect list of sensors
assertEquals(26, sweep(parseFile("day15.txt"), 10));
assertEquals(5299855, sweep(parseFile("day15-actual.txt"), 2000000));
}
@Test
public void day15part2() throws Exception {
assertEquals(56000011, bruteForcePart2(parseFile("day15.txt"), 20));
assertEquals(56000011, overlapsPart2(parseFile("day15.txt"), 20));
assertEquals(13615843289729L, overlapsPart2(parseFile("day15-actual.txt"), 4000000));
}
private long overlapsPart2(List<Sensor> sensors, long max) {
long sum = 0;
for (long y = 0; y <= max; y++) {
// For this row, evaluate each sensor's horizontal range at this row
List<long[]> ranges = new ArrayList<>();
for (Sensor sensor: sensors) {
long deltaY = Math.abs(y - sensor.y);
long xRearch = sensor.range - deltaY; // How much of this sensor's range is available to reach along the x axis
long right = sensor.x + xRearch;
if (xRearch >= 0 && right >= 0) {
ranges.add(new long[]{sensor.x - xRearch, right});
}
}
// Sort by left most first
Collections.sort(ranges, Comparator.comparingLong(o -> o[0]));
// Merge all the ranges into the best continuous extension from the left most range we can find.
long left = ranges.get(0)[0];
long right = ranges.get(0)[1];
for (long[] range: ranges) {
if (range[0] <= right + 1) {
if (range[1] > right) {
right = range[1];
}
}
}
boolean isCompletelyCovered = left <= 0 && right >= max;
if (!isCompletelyCovered) {
return ((right + 1) * 4000000) + y;
}
}
throw new RuntimeException();
}
private long bruteForcePart2(List<Sensor> sensors, long max) {
for (long y = 0; y <= max; y++) {
for (long x = 0; x <= max; x++) {
boolean inRange = false;
for (Sensor sensor : sensors) {
long deltaX = Math.abs(x - sensor.x);
long deltaY = Math.abs(y - sensor.y);
long delta = deltaY + deltaX;
if (delta <= sensor.range) {
inRange = true;
}
}
if (!inRange) {
long freq = (x * 4000000) + y;
return freq;
}
}
}
throw new RuntimeException();
}
private long sweep(List<Sensor> sensors, long y) {
// Find the x range
long left = sensors.stream().map(s -> {return s.x - s.range;}).min(Long::compare).get();
long right = sensors.stream().map(s -> {return s.x + s.range;}).max(Long::compare).get();
long sum = 0;
for (long x = left; x <= right; x++) {
boolean inRange = isInRange(sensors, y, x);
if (inRange) {
sum++;
}
}
return sum;
}
private boolean isInRange(List<Sensor> sensors, long y, long x) {
// Are any sensors in range?
boolean inRange = false;
for (Sensor sensor: sensors) {
long delta = Math.abs(y - sensor.y) + Math.abs(x - sensor.x);
boolean isClosestBeaconToThisSensor = x == sensor.closedBeaconX && y == sensor.getClosedBeaconY;
if (delta <= sensor.range && !isClosestBeaconToThisSensor) {
inRange = true;
break;
}
}
return inRange;
}
private List<Sensor> parseFile(String filename) throws Exception {
List<Sensor> sensors = new ArrayList<>();
BufferedReader reader = new BufferedReader(new FileReader(filename));
while(reader.ready()) {
String numbers = reader.readLine().replaceAll("[a-z|A-z|=|,|:]", "").replaceAll("\\s+", " ").trim();
String[] split = numbers.split(" ");
long x = Long.parseLong(split[0]);
long y = Long.parseLong(split[1]);
long cbx = Long.parseLong(split[2]);
long cby = Long.parseLong(split[3]);
sensors.add(new Sensor(x, y, cbx, cby));
}
return sensors;
}
class Sensor {
final long x, y;
final long closedBeaconX, getClosedBeaconY;
final long range;
public Sensor(long x, long y, long closedBeaconX, long getClosedBeaconY) {
this.x = x;
this.y = y;
this.closedBeaconX = closedBeaconX;
this.getClosedBeaconY = getClosedBeaconY;
// Calculate our distance to closest beacon; this is our effective max range
this.range = Math.abs(closedBeaconX - x) + Math.abs(getClosedBeaconY -y);
}
}
}