Skip to content

Commit 24330f3

Browse files
codeforkjeffcodeforkjeff
committed
day 21
1 parent 74ca528 commit 24330f3

File tree

2 files changed

+314
-0
lines changed

2 files changed

+314
-0
lines changed

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

Lines changed: 314 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,314 @@
1+
package com.codefork.aoc2024.day21;
2+
3+
import com.codefork.aoc2024.Problem;
4+
import com.codefork.aoc2024.util.Assert;
5+
6+
import java.util.ArrayList;
7+
import java.util.Comparator;
8+
import java.util.HashMap;
9+
import java.util.HashSet;
10+
import java.util.LinkedList;
11+
import java.util.List;
12+
import java.util.Map;
13+
import java.util.stream.Collectors;
14+
import java.util.stream.IntStream;
15+
import java.util.stream.Stream;
16+
17+
import static com.codefork.aoc2024.util.FoldLeft.foldLeft;
18+
19+
public class Part01 extends Problem {
20+
21+
public record Position(int x, int y) {
22+
23+
}
24+
25+
public record Button(String symbol, Position pos) {
26+
27+
public boolean isAdjacent(Button other) {
28+
var xDiff = Math.abs(pos().x() - other.pos().x());
29+
var yDiff = Math.abs(pos().y() - other.pos().y());
30+
return xDiff + yDiff == 1;
31+
}
32+
33+
/**
34+
* returns the action symbol when navigating from this button to (adjacent) target
35+
*/
36+
public String getAction(Button target) {
37+
var xDiff = pos().x() - target.pos().x();
38+
var yDiff = pos().y() - target.pos().y();
39+
if(xDiff > 0) {
40+
return "<";
41+
} else if(xDiff < 0) {
42+
return ">";
43+
}
44+
if(yDiff > 0) {
45+
return "^";
46+
} else if (yDiff < 0) {
47+
return "v";
48+
}
49+
throw new RuntimeException("buttons aren't adjacent in getAction=" + this + "," + target);
50+
}
51+
}
52+
53+
public record Move(Button from, Button to) {
54+
55+
}
56+
57+
public record ShortestPaths(Button source, Map<Button, Integer> dist, Map<Button, Button> prev) {
58+
59+
// Dijkstra, yet again.
60+
// this is probably overkill since there's not weighted edges in the graph
61+
// but I've already implemented it twice so far for AoC, so it's the easiest way
62+
// for me to create shortest paths at this point
63+
private static ShortestPaths create(List<Button> buttons, Map<Button, List<Button>> graph, Button source) {
64+
record ButtonWithDist(Button button, int dist) {
65+
66+
}
67+
var dist = new HashMap<Button, Integer>();
68+
var prev = new HashMap<Button, Button>();
69+
var q = new HashSet<Button>();
70+
71+
for(var button : buttons) {
72+
dist.put(button, Integer.MAX_VALUE);
73+
q.add(button);
74+
}
75+
dist.put(source, 0);
76+
77+
while(!q.isEmpty()) {
78+
var u = q.stream()
79+
.map(button -> new ButtonWithDist(button, dist.get(button)))
80+
.min(Comparator.comparingInt(ButtonWithDist::dist))
81+
.orElseThrow()
82+
.button();
83+
q.remove(u);
84+
85+
var neighborsInQ = graph.get(u).stream()
86+
.filter(q::contains)
87+
.toList();
88+
89+
for(var v : neighborsInQ) {
90+
var alt = dist.get(u) + 1;
91+
if (alt < dist.get(v)) {
92+
dist.put(v, alt);
93+
prev.put(v, u);
94+
}
95+
}
96+
}
97+
return new ShortestPaths(source, dist, prev);
98+
}
99+
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);
107+
}
108+
}
109+
return s;
110+
}
111+
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();
126+
}
127+
}
128+
129+
public static class Keypad {
130+
private final List<Button> buttons;
131+
132+
private final Map<String, Button> buttonsMap;
133+
134+
private final Map<Move, String> movesToPaths;
135+
136+
public Keypad(List<Button> buttons) {
137+
this.buttons = buttons;
138+
this.buttonsMap = buttons.stream()
139+
.collect(Collectors.toMap(
140+
Button::symbol,
141+
b -> b));
142+
143+
this.movesToPaths = createShortestPaths();
144+
}
145+
146+
private Map<Move, String> createShortestPaths() {
147+
Map<Move, String> result = new HashMap<>();
148+
149+
// generate graph of adjacent buttons
150+
var graph = new HashMap<Button, List<Button>>();
151+
for(var i=0; i < buttons.size(); i++) {
152+
var button1 = buttons.get(i);
153+
for(var j=i; j < buttons.size(); j++) {
154+
var button2 = buttons.get(j);
155+
if(button1.isAdjacent(button2)) {
156+
if(!graph.containsKey(button1)) {
157+
graph.put(button1, new ArrayList<>());
158+
}
159+
graph.get(button1).add(button2);
160+
if(!graph.containsKey(button2)) {
161+
graph.put(button2, new ArrayList<>());
162+
}
163+
graph.get(button2).add(button1);
164+
}
165+
}
166+
}
167+
168+
// generate shortest paths for every button to every other button
169+
for(var i=0; i < buttons.size(); i++) {
170+
var button1 = buttons.get(i);
171+
var shortestPaths = ShortestPaths.create(buttons, graph, button1);
172+
var otherButtons = buttons.stream().filter(b -> !b.equals(button1)).toList();
173+
for (var button2 : otherButtons) {
174+
var presses = shortestPaths.getPresses(button2);
175+
result.put(new Move(button1, button2), presses);
176+
}
177+
}
178+
return result;
179+
}
180+
181+
public Map<String, Button> getButtonsMap() {
182+
return buttonsMap;
183+
}
184+
185+
public Map<Move, String> getMovesToPaths() {
186+
return movesToPaths;
187+
}
188+
}
189+
190+
public static class KeypadNavigator {
191+
192+
private final Keypad keypad;
193+
private final Button current;
194+
195+
public KeypadNavigator(Keypad keypad, String current) {
196+
this.keypad = keypad;
197+
this.current = this.keypad.getButtonsMap().get(current);
198+
}
199+
200+
public String getPresses(String seq) {
201+
StringBuilder presses = new StringBuilder();
202+
var c = current;
203+
while(!seq.isEmpty()) {
204+
var symbol = seq.substring(0, 1);
205+
var next = keypad.getButtonsMap().get(symbol);
206+
if(next.equals(c)) {
207+
presses.append("A");
208+
} else {
209+
var move = new Move(c, next);
210+
presses.append(keypad.getMovesToPaths().get(move));
211+
}
212+
c = next;
213+
seq = seq.substring(1);
214+
}
215+
return presses.toString();
216+
}
217+
218+
}
219+
220+
public static class DoorKeypadNavigator extends KeypadNavigator {
221+
222+
private static final List<Button> doorButtons = List.of(
223+
new Button("7", new Position(0, 0)),
224+
new Button("8", new Position(1, 0)),
225+
new Button("9", new Position(2, 0)),
226+
new Button("4", new Position(0, 1)),
227+
new Button("5", new Position(1, 1)),
228+
new Button("6", new Position(2, 1)),
229+
new Button("1", new Position(0, 2)),
230+
new Button("2", new Position(1, 2)),
231+
new Button("3", new Position(2, 2)),
232+
new Button("0", new Position(1, 3)),
233+
new Button("A", new Position(2, 3))
234+
);
235+
236+
private static final Keypad doorKeypad = new Keypad(doorButtons);
237+
238+
public DoorKeypadNavigator(String startSymbol) {
239+
super(doorKeypad, startSymbol);
240+
}
241+
242+
}
243+
244+
public static class DirectionalKeypadNavigator extends KeypadNavigator {
245+
246+
private static final List<Button> robotButtons = List.of(
247+
new Button("^", new Position(1, 0)),
248+
new Button("A", new Position(2, 0)),
249+
new Button("<", new Position(0, 1)),
250+
new Button("v", new Position(1, 1)),
251+
new Button(">", new Position(2, 1))
252+
);
253+
254+
private static final Keypad robotKeypad = new Keypad(robotButtons);
255+
256+
public DirectionalKeypadNavigator(String startSymbol) {
257+
super(robotKeypad, startSymbol);
258+
}
259+
260+
}
261+
262+
public int getNumericPortion(String str) {
263+
return Integer.parseInt(str.chars()
264+
.boxed()
265+
.map(ch -> String.valueOf((char) ch.intValue()))
266+
.filter(s -> {
267+
try {
268+
Integer.parseInt(s);
269+
} catch(NumberFormatException e) {
270+
return false;
271+
}
272+
return true;
273+
})
274+
.collect(Collectors.joining()));
275+
}
276+
277+
public String solve(Stream<String> data) {
278+
var navigators = List.of(
279+
new DoorKeypadNavigator("A"),
280+
new DirectionalKeypadNavigator("A"),
281+
new DirectionalKeypadNavigator("A")
282+
);
283+
284+
record SeqWithFinalPresses(String seq, String finalPresses) {
285+
286+
}
287+
288+
var total = data
289+
.map(seq -> {
290+
var presses = seq;
291+
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);
295+
}
296+
return new SeqWithFinalPresses(seq, presses);
297+
})
298+
.map(s -> s.finalPresses.length() * getNumericPortion(s.seq))
299+
.mapToInt(i -> i)
300+
.sum();
301+
302+
return String.valueOf(total);
303+
}
304+
305+
@Override
306+
public String solve() {
307+
Assert.assertEquals("126384", solve(getSampleInput()));
308+
return solve(getInput());
309+
}
310+
311+
public static void main(String[] args) {
312+
new Part01().run();
313+
}
314+
}

‎src/main/resources/day21/sample

47 Bytes
Binary file not shown.

0 commit comments

Comments
 (0)