Skip to content

Commit b49405a

Browse files
codeforkjeffcodeforkjeff
committed
day 21 part 2
1 parent a9e11f5 commit b49405a

13 files changed

+571
-411
lines changed

‎README.md

Lines changed: 17 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -144,3 +144,20 @@ head against a wall. Which I did for WEEKS for some problems during AoC 2018. Wh
144144
(still later that day)
145145

146146
Hey I figured out day 14!
147+
148+
### 1/3/2025
149+
150+
I returned to day 21 and finished part 2. My initial naive attempt tried to generate the full strings of
151+
keypad presses, which, unsurprisingly, caused out of memory errors. Then I had the idea to represent the
152+
press sequences in a way that used less memory. After adding a shortcut after each robot's loop
153+
iteration, it finishes in about 2 minutes on my laptop.
154+
155+
I suspect this is one of those puzzles where there's a pattern in the growth of the sequences, and you can
156+
calculate the minimum size at n iterations without actually having to loop through them. I'm not that clever,
157+
sadly.
158+
159+
I'm still proud of my solution. It was tricky to model properly, and there were lots of hairy one-to-many
160+
transformations. I think it's pretty readable and easy to understand what's happening.
161+
162+
I'm running out of steam, so when I get around to it, I'm going to cheat for days 17 and 24 and see how someone
163+
else solved them. Implementation is still work and learning!

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

Lines changed: 38 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,38 @@
1+
package com.codefork.aoc2024.day21;
2+
3+
public record Button(String symbol, Position pos) {
4+
5+
public boolean isAdjacent(Button other) {
6+
var xDiff = Math.abs(pos().x() - other.pos().x());
7+
var yDiff = Math.abs(pos().y() - other.pos().y());
8+
return xDiff + yDiff == 1;
9+
}
10+
11+
/**
12+
* returns the action symbol when navigating from this button to (adjacent) target
13+
*/
14+
public String getAction(Button target) {
15+
var xDiff = pos().x() - target.pos().x();
16+
var yDiff = pos().y() - target.pos().y();
17+
if (xDiff > 0) {
18+
return "<";
19+
} else if (xDiff < 0) {
20+
return ">";
21+
}
22+
if (yDiff > 0) {
23+
return "^";
24+
} else if (yDiff < 0) {
25+
return "v";
26+
}
27+
throw new RuntimeException("buttons aren't adjacent in getAction=" + this + "," + target);
28+
}
29+
30+
public String toString() {
31+
return symbol + "(" + pos.x() + "," + pos.y() + ")";
32+
}
33+
34+
@SuppressWarnings("unused")
35+
public char asChar() {
36+
return symbol.charAt(0);
37+
}
38+
}

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

Lines changed: 11 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,11 @@
1+
package com.codefork.aoc2024.day21;
2+
3+
import static com.codefork.aoc2024.day21.Keypad.dirKeypad;
4+
5+
public class DirectionalKeypadNavigator extends KeypadNavigator {
6+
7+
public DirectionalKeypadNavigator() {
8+
super(dirKeypad);
9+
}
10+
11+
}

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

Lines changed: 27 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,27 @@
1+
package com.codefork.aoc2024.day21;
2+
3+
import java.util.List;
4+
5+
public class DoorKeypadNavigator extends KeypadNavigator {
6+
7+
private static final List<Button> doorButtons = List.of(
8+
new Button("7", new Position(0, 0)),
9+
new Button("8", new Position(1, 0)),
10+
new Button("9", new Position(2, 0)),
11+
new Button("4", new Position(0, 1)),
12+
new Button("5", new Position(1, 1)),
13+
new Button("6", new Position(2, 1)),
14+
new Button("1", new Position(0, 2)),
15+
new Button("2", new Position(1, 2)),
16+
new Button("3", new Position(2, 2)),
17+
new Button("0", new Position(1, 3)),
18+
new Button("A", new Position(2, 3))
19+
);
20+
21+
private static final Keypad doorKeypad = new Keypad(doorButtons);
22+
23+
public DoorKeypadNavigator() {
24+
super(doorKeypad);
25+
}
26+
27+
}

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

Lines changed: 97 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,97 @@
1+
package com.codefork.aoc2024.day21;
2+
3+
import java.util.ArrayList;
4+
import java.util.HashMap;
5+
import java.util.List;
6+
import java.util.Map;
7+
import java.util.stream.Collectors;
8+
9+
public class Keypad {
10+
11+
// directional keypad buttons
12+
private static final List<Button> dirKeypadButtons = List.of(
13+
new Button("^", new Position(1, 0)),
14+
new Button("A", new Position(2, 0)),
15+
new Button("<", new Position(0, 1)),
16+
new Button("v", new Position(1, 1)),
17+
new Button(">", new Position(2, 1))
18+
);
19+
20+
// directional keypad: this is used by both navigator
21+
public static final Keypad dirKeypad = new Keypad(dirKeypadButtons);
22+
23+
private final List<Button> buttons;
24+
25+
private final Map<String, Button> buttonsMap;
26+
27+
// map of moves to every possible path for making that move
28+
private final Map<Move, List<String>> movesToPaths;
29+
30+
public Keypad(List<Button> buttons) {
31+
this.buttons = buttons;
32+
this.buttonsMap = buttons.stream()
33+
.collect(Collectors.toMap(
34+
Button::symbol,
35+
b -> b));
36+
37+
this.movesToPaths = createShortestPaths();
38+
}
39+
40+
private Map<Move, List<String>> createShortestPaths() {
41+
Map<Move, List<String>> result = new HashMap<>();
42+
43+
// generate graph of adjacent buttons
44+
var graph = new HashMap<Button, List<Button>>();
45+
for (var i = 0; i < buttons.size(); i++) {
46+
var button1 = buttons.get(i);
47+
for (var j = i; j < buttons.size(); j++) {
48+
var button2 = buttons.get(j);
49+
if (button1.isAdjacent(button2)) {
50+
if (!graph.containsKey(button1)) {
51+
graph.put(button1, new ArrayList<>());
52+
}
53+
graph.get(button1).add(button2);
54+
if (!graph.containsKey(button2)) {
55+
graph.put(button2, new ArrayList<>());
56+
}
57+
graph.get(button2).add(button1);
58+
}
59+
}
60+
}
61+
62+
// generate shortest paths for every button to every other button
63+
for (var i = 0; i < buttons.size(); i++) {
64+
var button1 = buttons.get(i);
65+
var shortestPaths = ShortestPaths.create(buttons, graph, button1);
66+
var otherButtons = buttons.stream().filter(b -> !b.equals(button1)).toList();
67+
for (var button2 : otherButtons) {
68+
var presses = shortestPaths.getPossiblePressSequences(button2);
69+
//System.out.println("move " + button1 + "->" + button2 + " adding presses=" + presses);
70+
result.put(new Move(button1, button2), presses);
71+
}
72+
}
73+
74+
// path from a button to itself it just "A"
75+
for (Button button : buttons) {
76+
result.put(new Move(button, button), List.of("A"));
77+
}
78+
79+
return result;
80+
}
81+
82+
public Map<String, Button> getButtonsMap() {
83+
return buttonsMap;
84+
}
85+
86+
public Button getButton(String symbol) {
87+
return buttonsMap.get(symbol);
88+
}
89+
90+
public Button getButton(char symbol) {
91+
return buttonsMap.get(String.valueOf(symbol));
92+
}
93+
94+
public Map<Move, List<String>> getMovesToPaths() {
95+
return movesToPaths;
96+
}
97+
}

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

Lines changed: 98 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,98 @@
1+
package com.codefork.aoc2024.day21;
2+
3+
import java.util.ArrayList;
4+
import java.util.HashSet;
5+
import java.util.List;
6+
import java.util.Set;
7+
8+
/**
9+
* Base class representing a robot/person who interacts with a keypad.
10+
* Subclasses specify the particular kind of keypad.
11+
*/
12+
public class KeypadNavigator {
13+
14+
private final Keypad keypad;
15+
16+
public KeypadNavigator(Keypad keypad) {
17+
this.keypad = keypad;
18+
}
19+
20+
public Keypad getKeypad() {
21+
return keypad;
22+
}
23+
24+
/**
25+
* Transforms a PressSequence into its next possible iteration(s)
26+
*/
27+
public Set<PressSequence> getPossiblePressSequences(PressSequence seq) {
28+
List<PressSequence> results = new ArrayList<>();
29+
results.add(PressSequence.create());
30+
31+
//System.out.println("getting possible sequences for seq=" + seq);
32+
33+
// examine each move and append the possibilities to results
34+
for (var entry : seq.moves().entrySet()) {
35+
var newResults = new ArrayList<PressSequence>();
36+
var move = entry.getKey();
37+
var moveCount = entry.getValue();
38+
39+
//System.out.println("handling " + move + " (count=" + moveCount + ")");
40+
41+
for (var result : results) {
42+
var possibilities = addMove(result, move, moveCount);
43+
newResults.addAll(possibilities);
44+
}
45+
results = newResults;
46+
}
47+
48+
return new HashSet<>(results);
49+
}
50+
51+
/**
52+
* returns list of new PressSequences that are the possibilities that can result from adding the passed-in move
53+
*
54+
* @param keypad used to get the Button objects for the symbols, and to get the possible paths between buttons.
55+
*/
56+
public List<PressSequence> addMove(PressSequence seq, Move move, long multiplier) {
57+
var results = new ArrayList<PressSequence>();
58+
var paths = getKeypad().getMovesToPaths().get(move);
59+
60+
//System.out.println("from=" + _from + " to=" + _to + " paths=" + paths);
61+
62+
for (var path : paths) {
63+
var copy = seq.copy();
64+
65+
char first = path.charAt(0);
66+
67+
// note that we use dirKeypad here, since movements match up with the directional keypad
68+
69+
// add a transitional move from the last implicit "A"
70+
if (path.length() > 1 && first != 'A') {
71+
var transition = new Move(Keypad.dirKeypad.getButton("A"), Keypad.dirKeypad.getButton(first));
72+
copy.moves().merge(transition, multiplier, Long::sum);
73+
}
74+
75+
var from = first;
76+
for (var i = 1; i < path.length(); i++) {
77+
var to = path.charAt(i);
78+
79+
var moveInPath = new Move(Keypad.dirKeypad.getButton(from), Keypad.dirKeypad.getButton(to));
80+
copy.moves().merge(moveInPath, multiplier, Long::sum);
81+
82+
from = to;
83+
}
84+
85+
// this happens when a button repeats (i.e. moves from a button to itself)
86+
if (path.length() == 1) {
87+
var aButton = Keypad.dirKeypad.getButton("A");
88+
var moveInPath = new Move(aButton, aButton);
89+
copy.moves().merge(moveInPath, multiplier, Long::sum);
90+
}
91+
results.add(copy);
92+
}
93+
//System.out.println("addMove returning=" + results);
94+
95+
return results;
96+
}
97+
98+
}

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

Lines changed: 5 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,5 @@
1+
package com.codefork.aoc2024.day21;
2+
3+
public record Move(Button from, Button to) {
4+
5+
}

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

Lines changed: 5 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -3,8 +3,13 @@
33
import com.codefork.aoc2024.Problem;
44
import com.codefork.aoc2024.util.Assert;
55

6+
import java.util.ArrayList;
7+
import java.util.HashSet;
8+
import java.util.Set;
69
import java.util.stream.Stream;
710

11+
import static com.codefork.aoc2024.day21.ShipLock.getNumericPortion;
12+
813
public class Part01 extends Problem {
914

1015
public String solve(Stream<String> data) {

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

Lines changed: 2 additions & 22 deletions
Original file line numberDiff line numberDiff line change
@@ -1,34 +1,14 @@
11
package com.codefork.aoc2024.day21;
22

33
import com.codefork.aoc2024.Problem;
4-
import com.codefork.aoc2024.util.Assert;
54

6-
import java.util.ArrayList;
7-
import java.util.List;
85
import java.util.stream.Stream;
96

107
public class Part02 extends Problem {
118

129
public String solve(Stream<String> data) {
13-
// return String.valueOf(ShipLock.calculateSumOfComplexities(data, 25));
14-
15-
var navigator = new ShipLock.DirectionalKeypadNavigator("A");
16-
17-
// see what happens to a single move through 25 generations.
18-
// it doesn't even get past 4.
19-
// var pressSeqList = List.of("^");
20-
// for(var i = 0; i < 25; i++) {
21-
// System.out.println("i=" + i);
22-
// var newPressSeqList = new ArrayList<String>();
23-
// for (var pressSeq : pressSeqList) {
24-
// var possible = navigator.getPossiblePressSequences(pressSeq);
25-
// newPressSeqList.addAll(possible);
26-
// }
27-
// System.out.println(newPressSeqList);
28-
// pressSeqList = newPressSeqList;
29-
// }
30-
31-
return "UNFINISHED";
10+
System.out.println("TODO: This takes ~2 minutes to run, needs to be optimized");
11+
return String.valueOf(ShipLock.calculateSumOfComplexities(data, 25));
3212
}
3313

3414
@Override

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

Lines changed: 5 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,5 @@
1+
package com.codefork.aoc2024.day21;
2+
3+
public record Position(int x, int y) {
4+
5+
}

0 commit comments

Comments
 (0)