Movatterモバイル変換

[0]ホーム
URL:

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

 Sign up
Appearance settings

Commit8bfb2a1

Browse files
committed
day 21 refactored to compute every possible path
1 parent24330f3 commit8bfb2a1

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
importjava.util.LinkedList;
1111
importjava.util.List;
1212
importjava.util.Map;
13+
importjava.util.Set;
1314
importjava.util.stream.Collectors;
1415
importjava.util.stream.IntStream;
1516
importjava.util.stream.Stream;
@@ -48,13 +49,17 @@ public String getAction(Button target) {
4849
}
4950
thrownewRuntimeException("buttons aren't adjacent in getAction=" +this +"," +target);
5051
}
52+
53+
publicStringtoString() {
54+
returnsymbol +"(" +pos.x() +"," +pos.y() +")";
55+
}
5156
}
5257

5358
publicrecordMove(Buttonfrom,Buttonto) {
5459

5560
}
5661

57-
publicrecordShortestPaths(Buttonsource,Map<Button,Integer>dist,Map<Button,Button>prev) {
62+
publicrecordShortestPaths(Buttonsource,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
vardist =newHashMap<Button,Integer>();
68-
varprev =newHashMap<Button,Button>();
73+
varprev =newHashMap<Button,Set<Button>>();
6974
varq =newHashSet<Button>();
7075

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

8994
for(varv :neighborsInQ) {
9095
varalt =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,newHashSet<>());
100+
}
101+
prev.get(v).add(u);
94102
}
95103
}
96104
}
97105
returnnewShortestPaths(source,dist,prev);
98106
}
99107

100-
publicList<Button>getPath(Buttontarget) {
101-
vars =newLinkedList<Button>();
102-
varu =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+
publicList<List<Button>>getPaths(Buttontarget) {
112+
varpaths =newArrayList<List<Button>>();
113+
paths.add(newLinkedList<>(List.of(target)));
114+
varfinalPaths =newArrayList<List<Button>>();
115+
while(!paths.isEmpty()) {
116+
varnewPaths =newArrayList<List<Button>>();
117+
for(varpath :paths) {
118+
varu =path.getFirst();
119+
if(prev.containsKey(u)){
120+
varallPrev =prev.get(u);
121+
for(varprevItem :allPrev) {
122+
varnewPath =newLinkedList<>(path);
123+
newPath.addFirst(prevItem);
124+
newPaths.add(newPath);
125+
}
126+
127+
}elseif (u.equals(source)) {
128+
finalPaths.add(path);
129+
}
107130
}
131+
paths =newPaths;
108132
}
109-
returns;
133+
//System.out.println(source + "->" + target + ", returning " + finalPaths.size() + " finalPaths=" + finalPaths);
134+
returnfinalPaths;
110135
}
111136

112-
publicStringgetPresses(Buttontarget) {
113-
varpath =getPath(target);
114-
varresult =IntStream.range(1,path.size()).boxed()
115-
.collect(foldLeft(
116-
StringBuilder::new,
117-
(acc,i) -> {
118-
varbutton =path.get(i);
119-
varprevButton =path.get(i-1);
120-
varaction =prevButton.getAction(button);
121-
acc.append(action);
122-
returnacc;
123-
})
124-
);
125-
returnresult.append("A").toString();
137+
publicList<String>getPossiblePressSequences(Buttontarget) {
138+
varpaths =getPaths(target);
139+
returnpaths.stream()
140+
.map(path -> {
141+
returnIntStream.range(1,path.size()).boxed()
142+
.collect(foldLeft(
143+
StringBuilder::new,
144+
(acc,i) -> {
145+
varbutton =path.get(i);
146+
varprevButton =path.get(i -1);
147+
varaction =prevButton.getAction(button);
148+
acc.append(action);
149+
returnacc;
150+
})
151+
)
152+
.append("A")
153+
.toString();
154+
})
155+
.toList();
126156
}
127157
}
128158

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

132162
privatefinalMap<String,Button>buttonsMap;
133163

134-
privatefinalMap<Move,String>movesToPaths;
164+
privatefinalMap<Move,List<String>>movesToPaths;
135165

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

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

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

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

200-
publicStringgetPresses(Stringseq) {
201-
StringBuilderpresses =newStringBuilder();
231+
publicList<String>getPossiblePressSequences(Stringseq) {
232+
List<StringBuilder>pressSeqList =newArrayList<>();
233+
pressSeqList.add(newStringBuilder());
202234
varc =current;
203235
while(!seq.isEmpty()) {
236+
varnewPressSeqList =newArrayList<StringBuilder>();
204237
varsymbol =seq.substring(0,1);
205238
varnext =keypad.getButtonsMap().get(symbol);
206239
if(next.equals(c)) {
207-
presses.append("A");
240+
for(varpressSeq :pressSeqList) {
241+
pressSeq.append("A");
242+
newPressSeqList.add(pressSeq);
243+
}
208244
}else {
209245
varmove =newMove(c,next);
210-
presses.append(keypad.getMovesToPaths().get(move));
246+
varpaths =keypad.getMovesToPaths().get(move);
247+
for(varpressSeq :pressSeqList) {
248+
for(varpath :paths) {
249+
varcopy =newStringBuilder(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-
returnpresses.toString();
260+
returnpressSeqList.stream()
261+
.map(StringBuilder::toString)
262+
.toList();
216263
}
217264

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

284-
recordSeqWithFinalPresses(Stringseq,StringfinalPresses) {
285-
286-
}
287-
288-
vartotal =data
331+
varcomplexities =data
289332
.map(seq -> {
290-
varpresses =seq;
333+
System.out.println("doing " +seq);
334+
// run each sequence through a list of navigators, collecting results
335+
varpressesList =List.of(seq);
291336
for (varnavigator :navigators) {
292-
presses =navigator.getPresses(presses);
293-
varaCount =presses.chars().filter(ch -> ((char)ch) =='A').count();
294-
System.out.println(presses +" num A's=" +aCount);
337+
varnewPressesList =newArrayList<String>();
338+
for (varpresses :pressesList) {
339+
varpossiblePresses =navigator.getPossiblePressSequences(presses);
340+
for (varp :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-
returnnewSeqWithFinalPresses(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+
varshortestPress =pressesList.stream()
367+
.min(Comparator.comparingInt(String::length))
368+
.orElseThrow();
369+
System.out.println("shortest press found is "+shortestPress.length() +" long");
370+
varresult =shortestPress.length() *getNumericPortion(seq);
371+
returnresult;
297372
})
298-
.map(s ->s.finalPresses.length() *getNumericPortion(s.seq))
299-
.mapToInt(i ->i)
300-
.sum();
373+
.toList();
301374

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

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

311386
publicstaticvoidmain(String[]args) {

‎src/main/resources/day21/input‎

47 Bytes
Binary file not shown.

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp