Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly
Appearance settings

Commit 128d421

Browse filesBrowse files
l0sl0s
committed
Day 15
1 parent 4aa6730 commit 128d421
Copy full SHA for 128d421

File tree

2 files changed

+219
-0
lines changed
Filter options

2 files changed

+219
-0
lines changed

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

Copy file name to clipboard
+205Lines changed: 205 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,205 @@
1+
package com.macasaet;
2+
3+
import org.junit.jupiter.api.Assertions;
4+
import org.junit.jupiter.api.Test;
5+
6+
import java.util.Arrays;
7+
import java.util.Collections;
8+
import java.util.HashMap;
9+
import java.util.List;
10+
import java.util.Map;
11+
import java.util.function.IntPredicate;
12+
import java.util.stream.StreamSupport;
13+
14+
/**
15+
* --- Day 15: Beacon Exclusion Zone ---
16+
* <a href="https://adventofcode.com/2022/day/15">https://adventofcode.com/2022/day/15</a>
17+
*/
18+
public class Day15 {
19+
20+
record Coordinate(int x, int y) {
21+
static Coordinate parse(final String string) {
22+
final var components = string.split(", ");
23+
return new Coordinate(Integer.parseInt(components[1].replaceAll("^y=", "")),
24+
Integer.parseInt(components[0].replaceAll("^x=", "")));
25+
}
26+
27+
Map<Integer, Item> getRow(final Map<Integer, Map<Integer, Item>> grid) {
28+
return grid.computeIfAbsent(x(), ignored -> new HashMap<>());
29+
}
30+
31+
int distanceTo(final Coordinate other) {
32+
return Math.abs(x() - other.x()) + Math.abs(y() - other.y());
33+
}
34+
}
35+
36+
public record Sensor(Coordinate location, Coordinate beaconLocation) {
37+
public static Sensor parse(final String line) {
38+
final var location = Coordinate.parse(line.replaceAll("^Sensor at ", "").replaceAll(": closest beacon is at .*$", ""));
39+
final var beaconLocation = Coordinate.parse(line.replaceAll("^.*: closest beacon is at ", ""));
40+
return new Sensor(location, beaconLocation);
41+
}
42+
43+
void setSensor(final Map<Integer, Map<Integer, Item>> grid, IntPredicate includeRow, IntPredicate includeColumn) {
44+
if(includeRow.test(location().x()) && includeColumn.test(location().y())) {
45+
location().getRow(grid).put(location().y(), Item.SENSOR);
46+
}
47+
}
48+
49+
void setBeacon(final Map<Integer, Map<Integer, Item>> grid, IntPredicate includeRow, IntPredicate includeColumn) {
50+
if(includeRow.test(beaconLocation().x()) && includeColumn.test(beaconLocation().y())) {
51+
beaconLocation().getRow(grid).put(beaconLocation().y(), Item.BEACON);
52+
}
53+
}
54+
55+
void setCoverageArea(final Map<Integer, Map<Integer, Item>> grid, IntPredicate includeRow, IntPredicate includeColumn) {
56+
final var distance = distanceToBeacon();
57+
final var x = location().x();
58+
final var y = location().y();
59+
60+
for(int i = 0; i <= distance; i++ ) {
61+
if(!includeRow.test(x + i) && !includeRow.test(x - i)) {
62+
continue;
63+
}
64+
final var lowerRow = includeRow.test(x + i)
65+
? grid.computeIfAbsent(x + i, ignored -> new HashMap<>())
66+
: new HashMap<Integer, Item>();
67+
final var upperRow = includeRow.test(x - i)
68+
? grid.computeIfAbsent(x - i, ignored -> new HashMap<>())
69+
: new HashMap<Integer, Item>();
70+
for(int j = 0; j <= distance - i; j++ ) {
71+
if(includeColumn.test(y + j)) {
72+
// SE
73+
lowerRow.putIfAbsent(y + j, Item.COVERED);
74+
// NE
75+
upperRow.putIfAbsent(y + j, Item.COVERED);
76+
}
77+
if(includeColumn.test(y - j)) {
78+
// SW
79+
lowerRow.putIfAbsent(y - j, Item.COVERED);
80+
81+
// NW
82+
upperRow.putIfAbsent(y - j, Item.COVERED);
83+
}
84+
}
85+
}
86+
}
87+
88+
int distanceToBeacon() {
89+
return location().distanceTo(beaconLocation());
90+
}
91+
}
92+
93+
enum Item {
94+
SENSOR,
95+
BEACON,
96+
COVERED
97+
}
98+
public record CaveMap(Map<Integer, Map<Integer, Item>> grid, int minX, int maxX, int minY, int maxY) {
99+
public int countCoveredCellsInRow(final int x) {
100+
final var row = grid().getOrDefault(x, Collections.emptyMap());
101+
int result = 0;
102+
for(int j = minY(); j <= maxY(); j++) {
103+
final var cell = row.get(j);
104+
if(cell != null && cell != Item.BEACON) {
105+
result++;
106+
}
107+
}
108+
return result;
109+
}
110+
111+
public static CaveMap fromSensors(final Iterable<? extends Sensor> sensors, IntPredicate includeRow, IntPredicate includeColumn) {
112+
int minX = Integer.MAX_VALUE;
113+
int maxX = Integer.MIN_VALUE;
114+
int minY = Integer.MAX_VALUE;
115+
int maxY = Integer.MIN_VALUE;
116+
final var grid = new HashMap<Integer, Map<Integer, Item>>();
117+
for(final var sensor : sensors) {
118+
minX = Math.min(minX, sensor.location().x() - sensor.distanceToBeacon());
119+
maxX = Math.max(maxX, sensor.location().x() + sensor.distanceToBeacon());
120+
minY = Math.min(minY, sensor.location().y() - sensor.distanceToBeacon());
121+
maxY = Math.max(maxY, sensor.location().y() + sensor.distanceToBeacon());
122+
123+
sensor.setCoverageArea(grid, includeRow, includeColumn);
124+
sensor.setBeacon(grid, includeRow, includeColumn);
125+
sensor.setSensor(grid, includeRow, includeColumn);
126+
}
127+
128+
return new CaveMap(grid, minX, maxX, minY, maxY);
129+
}
130+
131+
public String toString() {
132+
final var builder = new StringBuilder();
133+
for(int i = minX(); i <= maxX(); i++) {
134+
builder.append(i).append('\t');
135+
final var row = grid().getOrDefault(i, Collections.emptyMap());
136+
for(int j = minY(); j <= maxY(); j++) {
137+
final var item = row.get(j);
138+
final var marker = item == null
139+
? '.'
140+
: item == Item.BEACON
141+
? 'B'
142+
: item == Item.SENSOR
143+
? 'S'
144+
: '#';
145+
builder.append(marker);
146+
}
147+
builder.append('\n');
148+
}
149+
return builder.toString();
150+
}
151+
}
152+
153+
protected CaveMap getInput(final IntPredicate includeRow, IntPredicate includeColumn) {
154+
final var sensors = getSensors();
155+
return CaveMap.fromSensors(sensors, includeRow, includeColumn);
156+
}
157+
158+
protected static List<Sensor> getSensors() {
159+
return StreamSupport.stream(new LineSpliterator("day-15.txt"), false)
160+
.map(Sensor::parse)
161+
.toList();
162+
}
163+
164+
@Test
165+
public final void part1() {
166+
final int rowOfInterest = 2_000_000;
167+
final var map = getInput(row -> row == rowOfInterest, _column -> true);
168+
final var result = map.countCoveredCellsInRow(rowOfInterest);
169+
170+
System.out.println("Part 1: " + result);
171+
}
172+
173+
@Test
174+
public final void part2() {
175+
final int max = 4_000_000;
176+
final var sensors = getSensors();
177+
for(final var sensor : sensors) {
178+
final var x = sensor.location().x();
179+
final var y = sensor.location().y();
180+
final var reach = sensor.distanceToBeacon();
181+
// Find all the points just outside this sensor's reach
182+
for(int horizontalOffset = 0; horizontalOffset <= reach + 1; horizontalOffset++) {
183+
final var verticalOffset = reach + 1 - horizontalOffset;
184+
Assertions.assertEquals(horizontalOffset + verticalOffset, reach + 1);
185+
for(final var candidate : Arrays.asList(new Coordinate(x + verticalOffset, y + horizontalOffset), // SE
186+
new Coordinate(x + verticalOffset, y - horizontalOffset), // SW
187+
new Coordinate(x - verticalOffset, y + horizontalOffset), // NE
188+
new Coordinate(x - verticalOffset, y - horizontalOffset))) { // NW
189+
if(candidate.x() < 0 || candidate.y() < 0 || candidate.x() > max || candidate.y() > max) {
190+
continue;
191+
}
192+
Assertions.assertTrue(candidate.distanceTo(sensor.location()) > sensor.distanceToBeacon());
193+
// Check if the point is also outside the reach of every other sensor
194+
if(sensors.stream().allMatch(other -> candidate.distanceTo(other.location()) > other.distanceToBeacon())) {
195+
final long result = (long)candidate.y() * 4_000_000l + (long)candidate.x();
196+
System.out.println("Part 2: " + result);
197+
return;
198+
}
199+
}
200+
}
201+
}
202+
throw new IllegalStateException("No uncovered point found");
203+
}
204+
205+
}

‎src/test/resources/sample/day-15.txt

Copy file name to clipboard
+14Lines changed: 14 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,14 @@
1+
Sensor at x=2, y=18: closest beacon is at x=-2, y=15
2+
Sensor at x=9, y=16: closest beacon is at x=10, y=16
3+
Sensor at x=13, y=2: closest beacon is at x=15, y=3
4+
Sensor at x=12, y=14: closest beacon is at x=10, y=16
5+
Sensor at x=10, y=20: closest beacon is at x=10, y=16
6+
Sensor at x=14, y=17: closest beacon is at x=10, y=16
7+
Sensor at x=8, y=7: closest beacon is at x=2, y=10
8+
Sensor at x=2, y=0: closest beacon is at x=2, y=10
9+
Sensor at x=0, y=11: closest beacon is at x=2, y=10
10+
Sensor at x=20, y=14: closest beacon is at x=25, y=17
11+
Sensor at x=17, y=20: closest beacon is at x=21, y=22
12+
Sensor at x=16, y=7: closest beacon is at x=15, y=3
13+
Sensor at x=14, y=3: closest beacon is at x=15, y=3
14+
Sensor at x=20, y=1: closest beacon is at x=15, y=3

0 commit comments

Comments
0 (0)
Morty Proxy This is a proxified and sanitized view of the page, visit original site.