Skip to content

Commit 74ca528

Browse files
codeforkjeffcodeforkjeff
committed
day 20
1 parent bf4b866 commit 74ca528

File tree

9 files changed

+329
-8
lines changed

9 files changed

+329
-8
lines changed

‎README.md

Lines changed: 6 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -109,3 +109,9 @@ Considering how hard the problems are getting, I solved days 18 and 19 pretty da
109109
Both of those were the ideal programming puzzles, in my view. Apply the right algorithms for
110110
both parts and you're done. No tricks in the input data, no having to be clever about what
111111
the rules imply and calculating a "shortcut" solution. Just nice efficient coding.
112+
113+
### 12/20/2024
114+
115+
Day 20 was the first puzzle where a recursive method caused a StackOverflowError
116+
when running it on the real input. This is yet another limit of trying to do pure FP in Java:
117+
it doesn't have [tail call optimization](https://en.wikipedia.org/wiki/Tail_call).

‎src/main/java/com/codefork/aoc2024/day20/Cheat.java

Lines changed: 7 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,7 @@
1+
package com.codefork.aoc2024.day20;
2+
3+
public record Cheat(Position start, Position end, int saved) {
4+
public Cheat withSaved(int newSaved) {
5+
return new Cheat(start, end, newSaved);
6+
}
7+
}

‎src/main/java/com/codefork/aoc2024/day20/Part01.java

Lines changed: 30 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,4 +1,33 @@
11
package com.codefork.aoc2024.day20;
22

3-
public class Part01 {
3+
import com.codefork.aoc2024.Problem;
4+
5+
import java.util.stream.Stream;
6+
7+
public class Part01 extends Problem {
8+
9+
public String solve(Stream<String> data, boolean printSummary) {
10+
var racetrack = Racetrack.create(data);
11+
12+
var cheats = racetrack.findCheats(2);
13+
if(printSummary) {
14+
Racetrack.printCheatsSummary(cheats);
15+
}
16+
17+
var count = cheats.stream()
18+
.filter(cheat -> cheat.saved() >= 100)
19+
.count();
20+
21+
return String.valueOf(count);
22+
}
23+
24+
@Override
25+
public String solve() {
26+
//return solve(getSampleInput(), true);
27+
return solve(getInput(), false);
28+
}
29+
30+
public static void main(String[] args) {
31+
new Part01().run();
32+
}
433
}

‎src/main/java/com/codefork/aoc2024/day20/Part02.java

Lines changed: 47 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,47 @@
1+
package com.codefork.aoc2024.day20;
2+
3+
import com.codefork.aoc2024.Problem;
4+
5+
import java.util.stream.Collectors;
6+
import java.util.stream.IntStream;
7+
import java.util.stream.Stream;
8+
9+
public class Part02 extends Problem {
10+
11+
public String solve(Stream<String> data, boolean printSummary) {
12+
var racetrack = Racetrack.create(data);
13+
14+
// not sure how to optimize this. there is probably some short-circuiting
15+
// that's possible, but I can't see how
16+
17+
var allCheats = IntStream.range(2, 21).boxed()
18+
.flatMap(n -> {
19+
var start = System.currentTimeMillis();
20+
var cheats = racetrack.findCheats(n);
21+
// System.out.println("n=" + n + " took " + (System.currentTimeMillis() - start) +
22+
// "ms to find " + cheats.size() + " cheats");
23+
return cheats.stream();
24+
})
25+
.collect(Collectors.toSet());
26+
if (printSummary) {
27+
Racetrack.printCheatsSummary(allCheats);
28+
}
29+
30+
var count = allCheats.stream()
31+
.filter(cheat -> cheat.saved() >= 100)
32+
.count();
33+
34+
return String.valueOf(count);
35+
}
36+
37+
@Override
38+
public String solve() {
39+
//return solve(getSampleInput(), true);
40+
System.out.println("TODO: This takes ~25s to run, needs to be optimized");
41+
return solve(getInput(), false);
42+
}
43+
44+
public static void main(String[] args) {
45+
new Part02().run();
46+
}
47+
}

‎src/main/java/com/codefork/aoc2024/day20/Position.java

Lines changed: 23 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,23 @@
1+
package com.codefork.aoc2024.day20;
2+
3+
public record Position(int x, int y) {
4+
5+
public static final Position UNSET = new Position(-1, -1);
6+
7+
public Position decX() {
8+
return new Position(x - 1, y);
9+
}
10+
11+
public Position incX() {
12+
return new Position(x + 1, y);
13+
}
14+
15+
public Position decY() {
16+
return new Position(x, y - 1);
17+
}
18+
19+
public Position incY() {
20+
return new Position(x, y + 1);
21+
}
22+
23+
}

‎src/main/java/com/codefork/aoc2024/day20/Racetrack.java

Lines changed: 193 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,193 @@
1+
package com.codefork.aoc2024.day20;
2+
3+
import com.codefork.aoc2024.util.Assert;
4+
import com.codefork.aoc2024.util.Grid;
5+
import com.codefork.aoc2024.util.WithIndex;
6+
7+
import java.util.ArrayList;
8+
import java.util.Comparator;
9+
import java.util.HashSet;
10+
import java.util.List;
11+
import java.util.Map;
12+
import java.util.Set;
13+
import java.util.stream.Collectors;
14+
import java.util.stream.IntStream;
15+
import java.util.stream.Stream;
16+
17+
public record Racetrack(int height, int width,
18+
Position start, Position end,
19+
Set<Position> track, Set<Position> walls,
20+
List<Position> course) {
21+
22+
public static Racetrack create(Stream<String> data) {
23+
var racetrack = Grid.parse(
24+
data,
25+
() -> new Racetrack(-1, -1, Position.UNSET, Position.UNSET, new HashSet<>(), new HashSet<>(), new ArrayList<>()),
26+
(acc, x, y, ch) -> {
27+
var pos = new Position(x, y);
28+
var newAcc = acc.withHeight(y + 1).withWidth(x + 1);
29+
// just mutate track and walls here :(
30+
if (".".equals(ch)) {
31+
newAcc.track().add(pos);
32+
return newAcc;
33+
} else if ("#".equals(ch)) {
34+
newAcc.walls().add(pos);
35+
return newAcc;
36+
} else if ("S".equals(ch)) {
37+
newAcc.track().add(pos);
38+
return newAcc.withStart(pos);
39+
} else if ("E".equals(ch)) {
40+
newAcc.track().add(pos);
41+
return newAcc.withEnd(pos);
42+
}
43+
throw new RuntimeException("unhandled character: " + ch);
44+
});
45+
return racetrack.withCourse(racetrack.walk());
46+
}
47+
48+
public Racetrack withStart(Position newStart) {
49+
return new Racetrack(height, width, newStart, end, track, walls, course);
50+
}
51+
52+
public Racetrack withEnd(Position newEnd) {
53+
return new Racetrack(height, width, start, newEnd, track, walls, course);
54+
}
55+
56+
public Racetrack withHeight(int newHeight) {
57+
return new Racetrack(newHeight, width, start, end, track, walls, course);
58+
}
59+
60+
public Racetrack withWidth(int newWidth) {
61+
return new Racetrack(height, newWidth, start, end, track, walls, course);
62+
}
63+
64+
public Racetrack withCourse(List<Position> newCourse) {
65+
return new Racetrack(height, width, start, end, track, walls, newCourse);
66+
}
67+
68+
public Set<Position> getTrackNeighbors(Position pos) {
69+
return Stream.of(pos.decX(), pos.incX(), pos.decY(), pos.incY())
70+
.filter(p -> track().contains(p))
71+
.collect(Collectors.toSet());
72+
}
73+
74+
/**
75+
* find all the positions at distance d from pos.
76+
* some of these may be invalid positions (i.e. negative coordinates);
77+
* we filter those out at a separate step
78+
**/
79+
public Set<Position> getPositionsFromDist(Position pos, int d) {
80+
// this is a diamond shape
81+
return IntStream.range(pos.x() - d, pos.x() + d + 1)
82+
.boxed()
83+
.flatMap(x -> {
84+
var xDist = pos.x() > x ? pos.x() - x : x - pos.x();
85+
var yDist = d - xDist;
86+
if(yDist > 0) {
87+
return Stream.of(
88+
new Position(x, pos.y() + yDist),
89+
new Position(x, pos.y() - yDist)
90+
);
91+
} else {
92+
return Stream.of(new Position(x, pos.y()));
93+
}
94+
})
95+
.collect(Collectors.toSet());
96+
}
97+
98+
/**
99+
* Walk the racetrack, building a path. includes start and end.
100+
* This recursive version causes a stack overflow.
101+
*/
102+
@SuppressWarnings("unused")
103+
public List<Position> walkRecursive(Position current, List<Position> acc) {
104+
var last = !acc.isEmpty() ? acc.getLast() : null;
105+
acc.add(current);
106+
if (current.equals(end)) {
107+
return acc;
108+
}
109+
var neighbors = getTrackNeighbors(current).stream()
110+
.filter(neighbor -> !neighbor.equals(last))
111+
.toList();
112+
Assert.assertEquals(1, neighbors.size());
113+
return walkRecursive(neighbors.getFirst(), acc);
114+
}
115+
116+
public List<Position> walkIterative(Position current, List<Position> acc) {
117+
var keepGoing = true;
118+
while (keepGoing) {
119+
var last = !acc.isEmpty() ? acc.getLast() : null;
120+
acc.add(current);
121+
if (!current.equals(end)) {
122+
var neighbors = getTrackNeighbors(current).stream()
123+
.filter(neighbor -> !neighbor.equals(last))
124+
.toList();
125+
Assert.assertEquals(1, neighbors.size());
126+
current = neighbors.getFirst();
127+
} else {
128+
keepGoing = false;
129+
}
130+
}
131+
return acc;
132+
}
133+
134+
public List<Position> walk() {
135+
return walkIterative(start, new ArrayList<>());
136+
}
137+
138+
/**
139+
* find all the cheats if you're allowed exactly picoseconds to walk through walls
140+
*/
141+
public Set<Cheat> findCheats(int picoseconds) {
142+
var regularCourseTime = course.size() - 1;
143+
//System.out.println("regularCourseTime=" + regularCourseTime);
144+
return course.stream()
145+
.map(WithIndex.indexed())
146+
.flatMap(posWithIndex -> {
147+
var i = posWithIndex.index();
148+
var pos = posWithIndex.value();
149+
150+
// find all the positions that actually intersect with
151+
// the portion of the course still ahead of us
152+
var courseAhead = new HashSet<>(course.subList(i + 1, course.size()));
153+
154+
var possibleTrackPositions = getPositionsFromDist(pos, picoseconds);
155+
return possibleTrackPositions.stream()
156+
.filter(courseAhead::contains)
157+
.map(p -> new Cheat(pos, p, -1));
158+
})
159+
.map(cheat -> {
160+
// populate "saved"
161+
var cheatStartIndex = course.indexOf(cheat.start());
162+
var cheatEndIndex = course.indexOf(cheat.end());
163+
164+
// we don't need to generate the actual shortened course, just its length
165+
var shortenedCourseLength = cheatStartIndex + 1
166+
+ picoseconds - 1
167+
+ (course.size() - cheatEndIndex);
168+
169+
var saved = regularCourseTime - (shortenedCourseLength - 1);
170+
171+
return cheat.withSaved(saved);
172+
})
173+
.collect(Collectors.toSet());
174+
}
175+
176+
/**
177+
* prints out a summary in the format shown in the puzzle instructions.
178+
* helpful for verifying/debugging
179+
*/
180+
public static void printCheatsSummary(Set<Cheat> cheats) {
181+
var grouped = cheats.stream().collect(Collectors.groupingBy(Cheat::saved));
182+
183+
var sortedEntries = grouped.entrySet().stream()
184+
.sorted(Comparator.comparingInt(Map.Entry::getKey))
185+
.toList();
186+
187+
for (var entry : sortedEntries) {
188+
var count = entry.getValue().size();
189+
var saved = entry.getKey();
190+
System.out.println("there are " + count + " cheats that save " + saved + " picoseconds");
191+
}
192+
}
193+
}

‎src/main/java/com/codefork/aoc2024/util/Grid.java

Lines changed: 23 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -1,35 +1,51 @@
11
package com.codefork.aoc2024.util;
22

3-
import com.codefork.aoc2024.day20.Part01;
4-
5-
import java.util.HashSet;
6-
import java.util.function.BiFunction;
73
import java.util.function.Supplier;
84
import java.util.stream.Stream;
95

106
import static com.codefork.aoc2024.util.FoldLeft.foldLeft;
117

8+
/**
9+
* Class of functions to help with grid input
10+
*/
1211
public class Grid {
1312

13+
public interface Reducer<T> {
14+
T apply(T t, int x, int y, String u);
15+
}
16+
17+
/**
18+
* Parse a grid of string data.
19+
* @param data stream to consume
20+
* @param accInitializer lambda that provides the accumulator
21+
* @param reducer lambda that returns the same type as accumulator, with x, y, and ch values to process
22+
* @return the final accumulated object
23+
* @param <T>
24+
*/
1425
public static <T> T parse(
1526
Stream<String> data,
1627
Supplier<T> accInitializer,
17-
BiFunction<T, String, T> reducer) {
28+
Reducer<T> reducer) {
1829
return data
1930
.map(WithIndex.indexed())
2031
.filter(lineWithIndex -> !lineWithIndex.value().isEmpty())
2132
.collect(foldLeft(
22-
() -> accInitializer.get(),
33+
accInitializer,
2334
(acc, lineWithIndex) -> {
2435
var y = lineWithIndex.index();
2536
var line = lineWithIndex.value();
2637

2738
return line.chars()
2839
.boxed()
2940
.map(ch -> String.valueOf((char) ch.intValue()))
41+
.map(WithIndex.indexed())
3042
.collect(foldLeft(
3143
() -> acc,
32-
(acc2, ch) -> reducer.apply(acc2, ch)
44+
(acc2, chWithIndex) -> {
45+
var x = chWithIndex.index();
46+
var ch = chWithIndex.value();
47+
return reducer.apply(acc2, x, y, ch);
48+
}
3349
));
3450
})
3551
);

‎src/main/resources/day20/input

19.6 KB
Binary file not shown.

‎src/main/resources/day20/sample

240 Bytes
Binary file not shown.

0 commit comments

Comments
 (0)