Skip to content

Commit 8bfb2a1

Browse files
codeforkjeffcodeforkjeff
committed
day 21 refactored to compute every possible path
1 parent 24330f3 commit 8bfb2a1

File tree

2 files changed

+125
-50
lines changed

2 files changed

+125
-50
lines changed

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

Lines changed: 125 additions & 50 deletions
Original file line numberDiff line numberDiff line change
@@ -10,6 +10,7 @@
1010
import java.util.LinkedList;
1111
import java.util.List;
1212
import java.util.Map;
13+
import java.util.Set;
1314
import java.util.stream.Collectors;
1415
import java.util.stream.IntStream;
1516
import java.util.stream.Stream;
@@ -48,13 +49,17 @@ public String getAction(Button target) {
4849
}
4950
throw new RuntimeException("buttons aren't adjacent in getAction=" + this + "," + target);
5051
}
52+
53+
public String toString() {
54+
return symbol + "(" + pos.x() + "," + pos.y() + ")";
55+
}
5156
}
5257

5358
public record Move(Button from, Button to) {
5459

5560
}
5661

57-
public record ShortestPaths(Button source, Map<Button, Integer> dist, Map<Button, Button> prev) {
62+
public record ShortestPaths(Button source, Map<Button, Integer> dist, Map<Button, Set<Button>> prev) {
5863

5964
// Dijkstra, yet again.
6065
// this is probably overkill since there's not weighted edges in the graph
@@ -65,7 +70,7 @@ record ButtonWithDist(Button button, int dist) {
6570

6671
}
6772
var dist = new HashMap<Button, Integer>();
68-
var prev = new HashMap<Button, Button>();
73+
var prev = new HashMap<Button, Set<Button>>();
6974
var q = new HashSet<Button>();
7075

7176
for(var button : buttons) {
@@ -88,41 +93,66 @@ record ButtonWithDist(Button button, int dist) {
8893

8994
for(var v : neighborsInQ) {
9095
var alt = dist.get(u) + 1;
91-
if (alt < dist.get(v)) {
96+
if (alt <= dist.get(v)) {
9297
dist.put(v, alt);
93-
prev.put(v, u);
98+
if(!prev.containsKey(v)) {
99+
prev.put(v, new HashSet<>());
100+
}
101+
prev.get(v).add(u);
94102
}
95103
}
96104
}
97105
return new ShortestPaths(source, dist, prev);
98106
}
99107

100-
public List<Button> getPath(Button target) {
101-
var s = new LinkedList<Button>();
102-
var u = target;
103-
if(prev.containsKey(u) || u.equals(source)) {
104-
while(u != null) {
105-
s.addFirst(u);
106-
u = prev.get(u);
108+
/**
109+
* get all the possible paths for navigating from source to target
110+
*/
111+
public List<List<Button>> getPaths(Button target) {
112+
var paths = new ArrayList<List<Button>>();
113+
paths.add(new LinkedList<>(List.of(target)));
114+
var finalPaths = new ArrayList<List<Button>>();
115+
while(!paths.isEmpty()) {
116+
var newPaths = new ArrayList<List<Button>>();
117+
for(var path : paths) {
118+
var u = path.getFirst();
119+
if(prev.containsKey(u)){
120+
var allPrev = prev.get(u);
121+
for(var prevItem : allPrev) {
122+
var newPath = new LinkedList<>(path);
123+
newPath.addFirst(prevItem);
124+
newPaths.add(newPath);
125+
}
126+
127+
} else if (u.equals(source)) {
128+
finalPaths.add(path);
129+
}
107130
}
131+
paths = newPaths;
108132
}
109-
return s;
133+
//System.out.println(source + "->" + target + ", returning " + finalPaths.size() + " finalPaths=" + finalPaths);
134+
return finalPaths;
110135
}
111136

112-
public String getPresses(Button target) {
113-
var path = getPath(target);
114-
var result = IntStream.range(1, path.size()).boxed()
115-
.collect(foldLeft(
116-
StringBuilder::new,
117-
(acc, i) -> {
118-
var button = path.get(i);
119-
var prevButton = path.get(i-1);
120-
var action = prevButton.getAction(button);
121-
acc.append(action);
122-
return acc;
123-
})
124-
);
125-
return result.append("A").toString();
137+
public List<String> getPossiblePressSequences(Button target) {
138+
var paths = getPaths(target);
139+
return paths.stream()
140+
.map(path -> {
141+
return IntStream.range(1, path.size()).boxed()
142+
.collect(foldLeft(
143+
StringBuilder::new,
144+
(acc, i) -> {
145+
var button = path.get(i);
146+
var prevButton = path.get(i - 1);
147+
var action = prevButton.getAction(button);
148+
acc.append(action);
149+
return acc;
150+
})
151+
)
152+
.append("A")
153+
.toString();
154+
})
155+
.toList();
126156
}
127157
}
128158

@@ -131,7 +161,7 @@ public static class Keypad {
131161

132162
private final Map<String, Button> buttonsMap;
133163

134-
private final Map<Move, String> movesToPaths;
164+
private final Map<Move, List<String>> movesToPaths;
135165

136166
public Keypad(List<Button> buttons) {
137167
this.buttons = buttons;
@@ -143,8 +173,8 @@ public Keypad(List<Button> buttons) {
143173
this.movesToPaths = createShortestPaths();
144174
}
145175

146-
private Map<Move, String> createShortestPaths() {
147-
Map<Move, String> result = new HashMap<>();
176+
private Map<Move, List<String>> createShortestPaths() {
177+
Map<Move, List<String>> result = new HashMap<>();
148178

149179
// generate graph of adjacent buttons
150180
var graph = new HashMap<Button, List<Button>>();
@@ -171,7 +201,8 @@ private Map<Move, String> createShortestPaths() {
171201
var shortestPaths = ShortestPaths.create(buttons, graph, button1);
172202
var otherButtons = buttons.stream().filter(b -> !b.equals(button1)).toList();
173203
for (var button2 : otherButtons) {
174-
var presses = shortestPaths.getPresses(button2);
204+
var presses = shortestPaths.getPossiblePressSequences(button2);
205+
//System.out.println("move " + button1 + "->" + button2 + " adding presses=" + presses);
175206
result.put(new Move(button1, button2), presses);
176207
}
177208
}
@@ -182,7 +213,7 @@ public Map<String, Button> getButtonsMap() {
182213
return buttonsMap;
183214
}
184215

185-
public Map<Move, String> getMovesToPaths() {
216+
public Map<Move, List<String>> getMovesToPaths() {
186217
return movesToPaths;
187218
}
188219
}
@@ -197,22 +228,38 @@ public KeypadNavigator(Keypad keypad, String current) {
197228
this.current = this.keypad.getButtonsMap().get(current);
198229
}
199230

200-
public String getPresses(String seq) {
201-
StringBuilder presses = new StringBuilder();
231+
public List<String> getPossiblePressSequences(String seq) {
232+
List<StringBuilder> pressSeqList = new ArrayList<>();
233+
pressSeqList.add(new StringBuilder());
202234
var c = current;
203235
while(!seq.isEmpty()) {
236+
var newPressSeqList = new ArrayList<StringBuilder>();
204237
var symbol = seq.substring(0, 1);
205238
var next = keypad.getButtonsMap().get(symbol);
206239
if(next.equals(c)) {
207-
presses.append("A");
240+
for(var pressSeq : pressSeqList) {
241+
pressSeq.append("A");
242+
newPressSeqList.add(pressSeq);
243+
}
208244
} else {
209245
var move = new Move(c, next);
210-
presses.append(keypad.getMovesToPaths().get(move));
246+
var paths = keypad.getMovesToPaths().get(move);
247+
for(var pressSeq : pressSeqList) {
248+
for(var path : paths) {
249+
var copy = new StringBuilder(pressSeq.toString());
250+
copy.append(path);
251+
//System.out.println("move " + move + ", appended " + path + ", copy is: " + copy);
252+
newPressSeqList.add(copy);
253+
}
254+
}
211255
}
256+
pressSeqList = newPressSeqList;
212257
c = next;
213258
seq = seq.substring(1);
214259
}
215-
return presses.toString();
260+
return pressSeqList.stream()
261+
.map(StringBuilder::toString)
262+
.toList();
216263
}
217264

218265
}
@@ -281,31 +328,59 @@ public String solve(Stream<String> data) {
281328
new DirectionalKeypadNavigator("A")
282329
);
283330

284-
record SeqWithFinalPresses(String seq, String finalPresses) {
285-
286-
}
287-
288-
var total = data
331+
var complexities = data
289332
.map(seq -> {
290-
var presses = seq;
333+
System.out.println("doing " + seq);
334+
// run each sequence through a list of navigators, collecting results
335+
var pressesList = List.of(seq);
291336
for (var navigator : navigators) {
292-
presses = navigator.getPresses(presses);
293-
var aCount = presses.chars().filter(ch -> ((char) ch) == 'A').count();
294-
System.out.println(presses + " num A's=" + aCount);
337+
var newPressesList = new ArrayList<String>();
338+
for (var presses : pressesList) {
339+
var possiblePresses = navigator.getPossiblePressSequences(presses);
340+
for (var p : possiblePresses) {
341+
System.out.println(p);
342+
}
343+
newPressesList.addAll(possiblePresses);
344+
}
345+
346+
// var lengthCounts = newPressesList.stream()
347+
// .collect(Collectors.toMap(
348+
// String::length,
349+
// s -> 1,
350+
// Integer::sum
351+
// ));
352+
// for(var len : lengthCounts.keySet().stream().sorted(Integer::compareTo).toList()) {
353+
// System.out.println("press sequences with len = " + len +
354+
// " occurred " + lengthCounts.get(len) + " times");
355+
// }
356+
357+
// group press sequences by their "signature" (where/which elements repeat)
358+
359+
360+
System.out.println(navigator + " found " + newPressesList.size() + " possible presses");
361+
362+
pressesList = newPressesList;
295363
}
296-
return new SeqWithFinalPresses(seq, presses);
364+
System.out.println("found " + pressesList.size() + " possible presses for last navigator");
365+
// find the shortest path of the LAST navigator only
366+
var shortestPress = pressesList.stream()
367+
.min(Comparator.comparingInt(String::length))
368+
.orElseThrow();
369+
System.out.println("shortest press found is "+ shortestPress.length() + " long");
370+
var result = shortestPress.length() * getNumericPortion(seq);
371+
return result;
297372
})
298-
.map(s -> s.finalPresses.length() * getNumericPortion(s.seq))
299-
.mapToInt(i -> i)
300-
.sum();
373+
.toList();
301374

375+
var total = complexities.stream().mapToInt(i -> i).sum();
302376
return String.valueOf(total);
303377
}
304378

305379
@Override
306380
public String solve() {
307381
Assert.assertEquals("126384", solve(getSampleInput()));
308-
return solve(getInput());
382+
//return solve(getInput());
383+
return "";
309384
}
310385

311386
public static void main(String[] args) {

‎src/main/resources/day21/input

47 Bytes
Binary file not shown.

0 commit comments

Comments
 (0)