8000 Days 15 and 17 · l0s/advent-of-code-java@ca0db89 · GitHub
[go: up one dir, main page]
Skip to content

Commit ca0db89

Browse files
l0sl0s
committed
Days 15 and 17
1 parent 02eba5b commit ca0db89

File tree

4 files changed

+377
-0
lines changed

4 files changed

+377
-0
lines changed

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

Lines changed: 228 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,228 @@
1+
package com.macasaet;
2+
3+
import java.util.*;
4+
import java.util.stream.Collectors;
5+
import java.util.stream.Stream;
6+
import java.util.stream.StreamSupport;
7+
8+
import org.junit.jupiter.api.Test;
9+
10+
/**
11+
* --- Day 15: Chiton ---
12+
*/
13+
public class Day15 {
14+
15+
protected Stream<String> getInput() {
16+
return StreamSupport
17+
.stream(new LineSpliterator("day-15.txt"),
18+
false);
19+
}
20+
21+
protected int[][] getGrid() {
22+
final var list = getInput().collect(Collectors.toList());
23+
final int[][] grid = new int[list.size()][];
24+
for (int i = 0; i < grid.length; i++) {
25+
final var chars = list.get(i).toCharArray();
26+
final var row = new int[chars.length];
27+
for (int j = chars.length; --j >= 0; row[j] = chars[j] - '0') ;
28+
grid[i] = row;
29+
}
30+
return grid;
31+
}
32+
33+
public record Point(int x, int y) {
34+
35+
public int risk(int[][] risks) {
36+
return risks[x][y];
37+
}
38+
39+
}
40+
41+
public record Cavern(int[][] grid) {
42+
43+
public Set<Point> predecessors(final Point source) {
44+
final var result = new HashSet<Point>();
45+
if (source.x() > 0) {
46+
result.add(new Point(source.x() - 1, source.y()));
47+
}
48+
if (source.y() > 0) {
49+
result.add(new Point(source.x(), source.y() - 1));
50+
}
51+
return Collections.unmodifiableSet(result);
52+
}
53+
54+
public Set<Point> successors(final Point source) {
55+
final var result = new HashSet<Point>();
56+
if (source.x() < grid().length - 1) {
57+
result.add(new Point(source.x() + 1, source.y()));
58+
}
59+
if (source.y() < grid()[source.x()].length - 1) {
60+
result.add(new Point< 10000 /span>(source.x(), source.y() + 1));
61+
}
62+
return Collections.unmodifiableSet(result);
63+
}
64+
65+
public Cavern explode() {
66+
final int[][] largeGrid = new int[grid.length * 5][];
67+
for (int i = largeGrid.length; --i >= 0; ) {
68+
largeGrid[i] = new int[grid.length * 5];
69+
}
70+
for (int i = grid.length; --i >= 0; ) {
71+
for (int j = grid.length; --j >= 0; ) {
72+
largeGrid[i][j] = grid[i][j];
73+
}
74+
}
75+
for (int tileRow = 0; tileRow < 5; tileRow++) {
76+
for (int tileColumn = 0; tileColumn < 5; tileColumn++) {
77+
if (tileRow > 0) {
78+
for (int i = grid.length; --i >= 0; ) {
79+
for (int j = grid.length; --j >= 0; ) {
80+
// copy from row above
81+
int value = largeGrid[(tileRow - 1) * grid.length + i][tileColumn * grid.length + j] + 1;
82+
if (value == 10) {
83+
value = 1;
84+
}
85+
largeGrid[tileRow * grid.length + i][tileColumn * grid.length + j] = value;
86+
}
87+
}
88+
} else if (tileColumn > 0) {
89+
for (int i = grid.length; --i >= 0; ) {
90+
for (int j = grid.length; --j >= 0; ) {
91+
// copy from column to the left
92+
int value = largeGrid[tileRow * grid.length + i][(tileColumn - 1) * grid.length + j] + 1;
93+
if (value == 10) {
94+
value = 1;
95+
}
96+
largeGrid[tileRow * grid.length + i][tileColumn * grid.length + j] = value;
97+
}
98+
}
99+
}
100+
}
101+
}
102+
return new Cavern(largeGrid);
103+
}
104+
105+
public long[][] calculateCumulativeRisk() {
106+
final var cumulative = new long[grid().length][];
107+
for (int i = cumulative.length; --i >= 0; cumulative[i] = new long[grid()[i].length]) ;
108+
final var visited = new HashSet<Point>();
109+
final var queue = new LinkedList<Point>();
110+
final var destination = new Point(grid().length - 1, grid()[grid().length - 1].length - 1);
111+
queue.add(destination);
112+
visited.add(destination);
113+
114+
while (!queue.isEmpty()) {
115+
final var node = queue.remove();
116+
final var successors = successors(node);
117+
if (successors.isEmpty()) {
118+
// destination
119+
cumulative[node.x][node.y] = node.risk(grid());
120+
} else {
121+
var minSuccessorRisk = Long.MAX_VALUE;
122+
for (final var successor : successors) {
123+
if (!visited.contains(successor)) {
124+
throw new IllegalStateException("Successor has not been visited");
125+
}
126+
minSuccessorRisk = Math.min(minSuccessorRisk, cumulative[successor.x][successor.y]);
127+
}
128+
cumulative[node.x][node.y] = node.risk(grid()) + minSuccessorRisk;
129+
}
130+
131+
for (final var predecessor : predecessors(node)) {
132+
if (!visited.contains(predecessor)) {
133+
queue.add(predecessor);
134+
visited.add(predecessor);
135+
}
136+
}
137+
}
138+
return cumulative;
139+
}
140+
141+
/**
142+
* @return the risk level associated with the path through the cavern that avoids the most chitons
143+
*/
144+
public int lowestRiskThroughTheCavern() {
145+
// the lowest known risk from origin to a given node
146+
final var lowestRiskToNode = new HashMap<Point, Integer>();
147+
// the estimated risk from origin to destination if it goes through a given node
148+
final var estimatedRiskThroughNode = new HashMap<Point, Integer>();
149+
final var openSet = new PriorityQueue<Point>(Comparator.comparing(estimatedRiskThroughNode::get));
150+
151+
for (int i = grid().length; --i >= 0; ) {
152+
final var row = grid()[i];
153+
for (int j = row.length; --j >= 0; ) {
154+
final var point = new Point(i, j);
155+
if (i == 0 && j == 0) {
156+
lowestRiskToNode.put(point, 0);
157+
estimatedRiskThroughNode.put(point, manhattanDistance(point));
158+
openSet.add(point);
159+
} else {
160+
lowestRiskToNode.put(point, Integer.MAX_VALUE);
161+
estimatedRiskThroughNode.put(point, Integer.MAX_VALUE);
162+
}
163+
}
164+
}
165+
166+
while(!openSet.isEmpty()) {
167+
final var < 10000 span class=pl-s1>current = openSet.poll();
168+
if(current.x() == grid().length - 1 && current.y() == grid()[grid().length - 1].length - 1) {
169+
return lowestRiskToNode.get(current);
170+
}
171+
final var lowestRiskToCurrent = lowestRiskToNode.get(current);
172+
for(final var neighbour : neighbours(current)) {
173+
final var tentativeRisk = lowestRiskToCurrent + neighbour.risk(grid());
174+
if(tentativeRisk < lowestRiskToNode.get(neighbour)) {
175+
lowestRiskToNode.put(neighbour, tentativeRisk);
176+
estimatedRiskThroughNode.put(neighbour, tentativeRisk + manhattanDistance(neighbour));
177+
if(!openSet.contains(neighbour)) {
178+
openSet.add(neighbour);
179+
}
180+
}
181+
}
182+
}
183+
throw new IllegalStateException("No path out of the cavern!");
184+
}
185+
186+
/**
187+
* @param point
188+
* @return
189+
*/
190+
protected int manhattanDistance(Point point) {
191+
return Math.abs(point.x() - (grid().length - 1))
192+
+ Math.abs(point.y() - (grid()[grid().length - 1].length - 1));
193+
}
194+
195+
public Set<Point> neighbours(final Point point) {
196+
final var result = new HashSet<Point>();
197+
if (point.x() > 0) {
198+
result.add(new Point(point.x() - 1, point.y()));
199+
}
200+
if (point.x() < grid().length - 1) {
201+
result.add(new Point(point.x() + 1, point.y()));
202+
}
203+
if (point.y() > 0) {
204+
result.add(new Point(point.x(), point.y() - 1));
205+
}
206+
if (point.y() < grid()[point.x()].length - 1) {
207+
result.add(new Point(point.x(), point.y() + 1));
208+
}
209+
return Collections.unmodifiableSet(result);
210+
}
211+
212+
}
213+
214+
@Test
215+
public final void part1() {
216+
final var grid = getGrid();
217+
final var cavern = new Cavern(grid);
218+
System.out.println("Part 1: " + cavern.lowestRiskThroughTheCavern());
219+
}
220+
221+
@Test
222+
public final void part2() {
223+
final var grid = getGrid();
224+
final var cavern = new Cavern(grid).explode();
225+
System.out.println("Part 2: " + cavern.lowestRiskThroughTheCavern());
226+
}
227+
228+
}

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

Lines changed: 138 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,138 @@
1+
package com.macasaet;
2+
3+
import java.util.Optional;
4+
import java.util.stream.Collectors;
5+
import java.util.stream.IntStream;
6+
import java.util.stream.Stream;
7+
import java.util.stream.StreamSupport;
8+
9+
import org.junit.jupiter.api.Test;
10+
11+
/**
12+
* --- Day 17: Trick Shot ---
13+
*/
14+
public class Day17 {
15+
16+
protected Stream<String> getInput() {
17+
return StreamSupport
18+
.stream(new LineSpliterator("day-17.txt"),
19+
false);
20+
}
21+
22+
/**
23+
* The target area in a large ocean trench
24+
*/
25+
public record Target(int minX, int maxX, int minY, int maxY) {
26+
}
27+
28+
/**
29+
* A probe at a given point in time
30+
*/
31+
public record Probe(int xVelocity, int yVelocity, int x, int y) {
32+
33+
/**
34+
* Launch a probe from the origin
35+
*
36+
* @param xVelocity the starting horizontal velocity
37+
* @param yVelocity the starting vertical velocity
38+
* @return the initial state of the probe at the origin
39+
*/
40+
public static Probe launch(final int xVelocity, final int yVelocity) {
41+
return new Probe(xVelocity, yVelocity, 0, 0);
42+
}
43+
44+
public Optional<Probe> step() {
45+
if(x > 0 && x + xVelocity < 0) {
46+
return Optional.empty();
47+
}
48+
if(y < 0 && y + yVelocity > 0) {
49+
return Optional.empty();
50+
}
51+
final int newX = x + xVelocity;
52+
final int newY = y + yVelocity;
53+
final int newXVelocity = xVelocity > 0
54+
? xVelocity - 1
55+
: xVelocity < 0
56+
? xVelocity + 1
57+
: xVelocity;
58+
return Optional.of(new Probe(newXVelocity,
59+
yVelocity - 1,
60+
newX,
61+
newY));
62+
}
63+
64+
public Optional<Integer> peak(final Target target) {
65+
var peak = Integer.MIN_VALUE;
66+
var p = Optional.of(this);
67+
while (p.isPresent()) {
68+
final var probe = p.get();
69+
peak = Math.max(peak, probe.y());
70+
if (probe.x() < target.minX() && probe.y() < target.minY()) {
71+
// short
72+
return Optional.empty();
73+
} else if (probe.x() > target.maxX()) {
74+
// long
75+
return Optional.empty();
76+
} else if (probe.x() >= target.minX() && probe.x() <= target.maxX()
77+
&& probe.y() >= target.minY() && probe.y() <= target.maxY()) {
78+
return Optional.of(peak);
79+
}
80+
p = probe.step();
81+
}
82+
return Optional.empty();
83+
}
84+
85+
}
86+
87+
@Test
88+
public final void part1() {
89+
final var line = getInput().collect(Collectors.toList()).get(0);
90+
final var bounds = line.replaceFirst("target area: ", "").split(", ");
91+
final var xBounds = bounds[0].replaceFirst("x=", "").split("\\.\\.");
92+
final var yBounds = bounds[1].replaceFirst("y=", "").split("\\.\\.");
93+
final int minX = Integer.parseInt(xBounds[0]);
94+
final int maxX = Integer.parseInt(xBounds[1]);
95+
final int minY = Integer.parseInt(yBounds[0]);
96+
final int maxY = Integer.parseInt(yBounds[1]);
97+
final var target = new Target(minX, maxX, minY, maxY);
98+
99+
final var max = IntStream.range(0, 50)
100+
.parallel()
101+
.mapToObj(x -> IntStream.range(-50, 50)
102+
.parallel()
103+
.mapToObj(y -> Probe.launch(x, y))
104+
).flatMap(probes -> probes)
105+
.flatMapToInt(probe -> probe.peak(target)
106+
.stream()
107+
.mapToInt(peak -> peak))
108+
.max();
109+
110+
111+
System.out.println("Part 1: " + max.getAsInt());
112+
}
113+
114+
@Test
115+
public final void part2() {
116+
final var line = getInput().collect(Collectors.toList()).get(0);
117+
final var bounds = line.replaceFirst("target area: ", "").split(", ");
118+
final var xBounds = bounds[0].replaceFirst("x=", "").split("\\.\\.");
119+
final var yBounds = bounds[1].replaceFirst("y=", "").split("\\.\\.");
120+
final int minX = Integer.parseInt(xBounds[0]);
121+
final int maxX = Integer.parseInt(xBounds[1]);
122+
final int minY = Integer.parseInt(yBounds[0]);
123+
final int maxY = Integer.parseInt(yBounds[1]);
124+
final var target = new Target(minX, maxX, minY, maxY);
125+
int count = 0;
126+
for (int x = 1; x <= 400; x++) {
127+
for (int y = -400; y <= 400; y++) {
128+
final var probe = Probe.launch(x, y);
129+
if (probe.peak(target).isPresent()) {
130+
count++;
131+
}
132+
}
133+
}
134+
135+
System.out.println("Part 2: " + count);
136+
}
137+
138+
}

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

Lines changed: 10 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,10 @@
1+
1163751742
2+
1381373672
3+
2136511328
4+
3694931569
5+
7463417111
6+
1319128137
7+
1359912421
8+
3125421639
9+
1293138521
10+
2311944581

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

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1 @@
1+
target area: x=20..30, y=-10..-5

0 commit comments

Comments
 (0)
0