Skip to content

Commit b89a743

Browse files
pareroniapareronia
committed
AoC 2022 Day 15 - java - faster
1 parent cccc46c commit b89a743

File tree

4 files changed

+171
-177
lines changed

4 files changed

+171
-177
lines changed

‎src/main/java/AoC2022_15.java‎

Lines changed: 78 additions & 110 deletions
Original file line numberDiff line numberDiff line change
@@ -1,104 +1,117 @@
1-
import java.util.ArrayDeque;
21
import java.util.ArrayList;
3-
import java.util.Collections;
4-
import java.util.Deque;
52
import java.util.HashMap;
63
import java.util.HashSet;
74
import java.util.List;
85
import java.util.Map;
6+
import java.util.Map.Entry;
97
import java.util.Set;
108

9+
import com.github.pareronia.aoc.IterTools;
1110
import com.github.pareronia.aoc.RangeInclusive;
11+
import com.github.pareronia.aoc.StringOps;
1212
import com.github.pareronia.aoc.Utils;
1313
import com.github.pareronia.aoc.geometry.Position;
14-
import com.github.pareronia.aocd.Aocd;
15-
import com.github.pareronia.aocd.Puzzle;
14+
import com.github.pareronia.aoc.solution.SolutionBase;
1615

17-
public class AoC2022_15 extends AoCBase {
16+
public class AoC2022_15 extends SolutionBase<AoC2022_15.Input, Integer, Long> {
1817

19-
private final Set<Sensor> sensors;
20-
private final Map<Integer, Set<Integer>> beacons;
21-
22-
private AoC2022_15(final List<String> input, final boolean debug) {
18+
private AoC2022_15(final boolean debug) {
2319
super(debug);
24-
this.sensors = new HashSet<>();
25-
this.beacons = new HashMap<>();
26-
for (final String line : input) {
27-
final int[] nums = Utils.integerNumbers(line);
28-
final var sensor = new Sensor(nums[0], nums[1], nums[2], nums[3]);
29-
this.sensors.add(sensor);
30-
this.beacons.computeIfAbsent(nums[3], k -> new HashSet<>()).add(nums[2]);
31-
}
32-
log(this.sensors);
33-
log(this.beacons);
3420
}
3521

36-
public static final AoC2022_15 create(final List<String> input) {
37-
return new AoC2022_15(input, false);
22+
public static final AoC2022_15 create() {
23+
return new AoC2022_15(false);
3824
}
3925

40-
public static final AoC2022_15 createDebug(final List<String> input) {
41-
return new AoC2022_15(input, true);
26+
public static final AoC2022_15 createDebug() {
27+
return new AoC2022_15(true);
4228
}
4329

44-
private Deque<RangeInclusive<Integer>> getRanges(final int y) {
45-
final var ranges = new HashSet<RangeInclusive<Integer>>();
46-
for (final var sensor : this.sensors) {
47-
if (Math.abs(sensor.y - y) > sensor.distanceToBeacon) {
30+
@Override
31+
protected Input parseInput(final List<String> inputs) {
32+
final Map<Position, Integer> sensors = new HashMap<>();
33+
final Set<Position> beacons = new HashSet<>();
34+
for (final String line : inputs) {
35+
final int[] nums = Utils.integerNumbers(line);
36+
final Position s = Position.of(nums[0], nums[1]);
37+
final Position b = Position.of(nums[2], nums[3]);
38+
sensors.put(s, s.manhattanDistance(b));
39+
beacons.add(b);
40+
}
41+
return new Input(sensors, beacons);
42+
}
43+
44+
private int solve1(final Input input, final int y) {
45+
final var ranges = new ArrayList<RangeInclusive<Integer>>();
46+
for (final Entry<Position, Integer> entry : input.sensors.entrySet()) {
47+
final Position s = entry.getKey();
48+
final int md = entry.getValue();
49+
final int dy = Math.abs(s.getY() - y);
50+
if (dy > md) {
4851
continue;
4952
}
50-
ranges.add(sensor.xRangeAt(y));
53+
ranges.add(RangeInclusive.between(
54+
s.getX() - md + dy, s.getX() + md - dy));
5155
}
52-
return RangeMerger.mergeRanges(ranges);
53-
}
54-
55-
private int solve1(final int y) {
56-
final Set<Integer> beaconsXs = this.beacons.get(y);
57-
return (int) getRanges(y).stream()
58-
.mapToLong(r -> r.getMaximum() - r.getMinimum() + 1
59-
- beaconsXs.stream().filter(r::contains).count())
56+
return (int) RangeInclusive.mergeRanges(ranges).stream()
57+
.mapToLong(r ->
58+
r.getMaximum() - r.getMinimum() + 1
59+
- input.beacons.stream()
60+
.filter(b -> b.getY() == y && r.contains(b.getX()))
61+
.count())
6062
.sum();
6163
}
6264

63-
private long solve2(final int max) {
64-
for (int y = max; y >= 0; y--) {
65-
final var ranges = getRanges(y);
66-
for (int x = 0; x <= max; x++) {
67-
for (final var merged : ranges) {
68-
if (merged.isAfter(x)) {
69-
log(Position.of(x, y));
70-
return x * 4_000_000L + y;
71-
}
72-
x = merged.getMaximum() + 1;
73-
}
74-
}
65+
private long solve2(final Map<Position, Integer> sensors, final int max) {
66+
final Set<Integer> acoeffs = new HashSet<>();
67+
final Set<Integer> bcoeffs = new HashSet<>();
68+
for (final Entry<Position, Integer> entry : sensors.entrySet()) {
69+
final Position s = entry.getKey();
70+
final int md = entry.getValue();
71+
acoeffs.add(s.getY() - s.getX() + md + 1);
72+
acoeffs.add(s.getY() - s.getX() - md - 1);
73+
bcoeffs.add(s.getX() + s.getY() + md + 1);
74+
bcoeffs.add(s.getX() + s.getY() - md - 1);
7575
}
76-
throw new IllegalStateException("Unsolvable");
76+
return IterTools.product(acoeffs, bcoeffs).stream()
77+
.filter(ab -> ab.first() < ab.second())
78+
.filter(ab -> (ab.second() - ab.first()) % 2 == 0)
79+
.map(ab -> Position.of(
80+
(ab.second() - ab.first()) / 2,
81+
(ab.first() + ab.second()) / 2))
82+
.filter(p -> 0 < p.getX() && p.getX() < max)
83+
.filter(p -> 0 < p.getY() && p.getY() < max)
84+
.filter(p -> sensors.keySet().stream().allMatch(
85+
s -> p.manhattanDistance(s) > sensors.get(s)))
86+
.mapToLong(p -> 4_000_000L * p.getX() + p.getY())
87+
.findFirst().orElseThrow();
7788
}
7889

7990
@Override
80-
public Integer solvePart1() {
81-
return solve1(2_000_000);
91+
public Integer solvePart1(final Input input) {
92+
return solve1(input, 2_000_000);
8293
}
8394

8495
@Override
85-
public Long solvePart2() {
86-
return solve2(4_000_000);
96+
public Long solvePart2(final Input input) {
97+
return solve2(input.sensors, 4_000_000);
98+
}
99+
100+
record Input(Map<Position, Integer> sensors, Set<Position> beacons) {}
101+
102+
@Override
103+
public void samples() {
104+
final AoC2022_15 test = AoC2022_15.createDebug();
105+
final Input input = test.parseInput(StringOps.splitLines(TEST));
106+
assert test.solve1(input, 10) == 26;
107+
assert test.solve2(input.sensors, 20) == 56_000_011L;
87108
}
88109

89110
public static void main(final String[] args) throws Exception {
90-
assert AoC2022_15.createDebug(TEST).solve1(10) == 26;
91-
assert AoC2022_15.createDebug(TEST).solve2(20) == 56_000_011L;
92-
93-
final Puzzle puzzle = Aocd.puzzle(2022, 15);
94-
final List<String> inputData = puzzle.getInputData();
95-
puzzle.check(
96-
() -> lap("Part 1", AoC2022_15.create(inputData)::solvePart1),
97-
() -> lap("Part 2", AoC2022_15.create(inputData)::solvePart2)
98-
);
111+
AoC2022_15.create().run();
99112
}
100113

101-
private static final List<String> TEST = splitLines("""
114+
private static final String TEST = """
102115
Sensor at x=2, y=18: closest beacon is at x=-2, y=15
103116
Sensor at x=9, y=16: closest beacon is at x=10, y=16
104117
Sensor at x=13, y=2: closest beacon is at x=15, y=3
@@ -113,50 +126,5 @@ public static void main(final String[] args) throws Exception {
113126
Sensor at x=16, y=7: closest beacon is at x=15, y=3
114127
Sensor at x=14, y=3: closest beacon is at x=15, y=3
115128
Sensor at x=20, y=1: closest beacon is at x=15, y=3
116-
""");
117-
118-
private static final record Sensor(int x, int y, int distanceToBeacon) {
119-
public Sensor(final int x, final int y, final int beaconX, final int beaconY) {
120-
this(x, y, Math.abs(beaconX - x) + Math.abs(beaconY - y));
121-
}
122-
123-
public RangeInclusive<Integer> xRangeAt(final int y) {
124-
final int dy = Math.abs(this.y - y);
125-
assert dy <= distanceToBeacon;
126-
return RangeInclusive.between(
127-
x - distanceToBeacon + dy,
128-
x + distanceToBeacon - dy);
129-
}
130-
}
131-
132-
static final class RangeMerger {
133-
134-
public static Deque<RangeInclusive<Integer>> mergeRanges(final Set<RangeInclusive<Integer>> ranges) {
135-
final var m = new ArrayDeque<RangeInclusive<Integer>>();
136-
final var sorted = new ArrayList<>(ranges);
137-
Collections.sort(sorted, (r1, r2) -> {
138-
final int first = Integer.compare(r1.getMinimum(), r2.getMinimum());
139-
if (first == 0) {
140-
return Integer.compare(r1.getMaximum(), r2.getMaximum());
141-
}
142-
return first;
143-
});
144-
for (final var range : sorted) {
145-
if (m.isEmpty()) {
146-
m.addLast(range);
147-
continue;
148-
}
149-
final var last = m.peekLast();
150-
if (range.isOverlappedBy(last)) {
151-
m.removeLast();
152-
m.add(RangeInclusive.between(
153-
last.getMinimum(),
154-
Math.max(last.getMaximum(), range.getMaximum())));
155-
} else {
156-
m.addLast(range);
157-
}
158-
}
159-
return m;
160-
}
161-
}
129+
""";
162130
}

‎src/main/java/com/github/pareronia/aoc/RangeInclusive.java‎

Lines changed: 35 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1,6 +1,11 @@
11
package com.github.pareronia.aoc;
22

3+
import java.util.ArrayDeque;
4+
import java.util.ArrayList;
5+
import java.util.Collection;
6+
import java.util.Collections;
37
import java.util.Comparator;
8+
import java.util.List;
49
import java.util.Objects;
510

611
public final class RangeInclusive<T> {
@@ -40,6 +45,36 @@ public static <T> RangeInclusive<T> between(final T fromInclusive, final T toInc
4045
return new RangeInclusive<>(fromInclusive, toInclusive);
4146
}
4247

48+
public static List<RangeInclusive<Integer>> mergeRanges(
49+
final Collection<RangeInclusive<Integer>> ranges
50+
) {
51+
final var merged = new ArrayDeque<RangeInclusive<Integer>>();
52+
final var sorted = new ArrayList<>(ranges);
53+
Collections.sort(sorted, (r1, r2) -> {
54+
final int first = Integer.compare(r1.getMinimum(), r2.getMinimum());
55+
if (first == 0) {
56+
return Integer.compare(r1.getMaximum(), r2.getMaximum());
57+
}
58+
return first;
59+
});
60+
for (final var range : sorted) {
61+
if (merged.isEmpty()) {
62+
merged.addLast(range);
63+
continue;
64+
}
65+
final var last = merged.peekLast();
66+
if (range.isOverlappedBy(last)) {
67+
merged.removeLast();
68+
merged.add(RangeInclusive.between(
69+
last.getMinimum(),
70+
Math.max(last.getMaximum(), range.getMaximum())));
71+
} else {
72+
merged.addLast(range);
73+
}
74+
}
75+
return merged.stream().toList();
76+
}
77+
4378
public T getMinimum() {
4479
return minimum;
4580
}

‎src/test/java/AoC2022_15TestCase.java‎

Lines changed: 0 additions & 66 deletions
This file was deleted.

0 commit comments

Comments
 (0)