Skip to content

Commit 5acbf0e

Browse files
SimonBaarsSimonBaars
committed
optimize solutions
1 parent f6dce16 commit 5acbf0e

File tree

2 files changed

+125
-85
lines changed

2 files changed

+125
-85
lines changed

‎src/main/java/com/sbaars/adventofcode/year16/days/Day11.java

Lines changed: 103 additions & 62 deletions
Original file line numberDiff line numberDiff line change
@@ -5,6 +5,8 @@
55
import java.util.regex.Matcher;
66
import java.util.regex.Pattern;
77
import java.util.stream.Collectors;
8+
import java.util.stream.IntStream;
9+
import java.util.stream.Stream;
810

911
public class Day11 extends Day2016 {
1012
private static final Pattern ITEM_PATTERN = Pattern.compile("(\\w+)(?:-compatible)? (microchip|generator)");
@@ -17,76 +19,82 @@ public static void main(String[] args) {
1719
new Day11().printParts();
1820
}
1921

20-
private record State(int elevator, List<Set<String>> floors) {
22+
private record ElementPosition(int generatorFloor, int microchipFloor) implements Comparable<ElementPosition> {
23+
@Override
24+
public int compareTo(ElementPosition o) {
25+
int cmp = Integer.compare(generatorFloor, o.generatorFloor);
26+
if (cmp != 0) return cmp;
27+
return Integer.compare(microchipFloor, o.microchipFloor);
28+
}
29+
}
30+
31+
private record State(int elevatorFloor, List<ElementPosition> elements) {
32+
public State {
33+
elements = new ArrayList<>(elements);
34+
Collections.sort(elements);
35+
}
36+
2137
public boolean isValid() {
22-
for (Set<String> floor : floors) {
23-
Set<String> generators = floor.stream()
24-
.filter(s -> s.endsWith("G"))
25-
.collect(Collectors.toSet());
26-
Set<String> microchips = floor.stream()
27-
.filter(s -> s.endsWith("M"))
28-
.collect(Collectors.toSet());
29-
30-
if (!generators.isEmpty()) {
31-
for (String chip : microchips) {
32-
String gen = chip.substring(0, chip.length() - 1) + "G";
33-
if (!generators.contains(gen)) {
34-
return false;
35-
}
38+
for (ElementPosition elem : elements) {
39+
if (elem.microchipFloor != elem.generatorFloor) {
40+
final int floor = elem.microchipFloor;
41+
boolean hasGenerator = elements.stream()
42+
.anyMatch(e -> e.generatorFloor == floor);
43+
if (hasGenerator) {
44+
return false;
3645
}
3746
}
3847
}
3948
return true;
4049
}
4150

4251
public boolean isComplete() {
43-
return floors.get(0).isEmpty() &&
44-
floors.get(1).isEmpty() &&
45-
floors.get(2).isEmpty();
52+
return elements.stream()
53+
.allMatch(e -> e.generatorFloor == 3 && e.microchipFloor == 3);
4654
}
4755

4856
public List<State> nextStates() {
4957
List<State> states = new ArrayList<>();
50-
Set<String> currentFloor = floors.get(elevator);
51-
52-
// Try moving one or two items
53-
List<List<String>> itemCombos = new ArrayList<>();
54-
currentFloor.forEach(item -> itemCombos.add(List.of(item)));
55-
for (String item1 : currentFloor) {
56-
for (String item2 : currentFloor) {
57-
if (item1.compareTo(item2) < 0) {
58-
itemCombos.add(List.of(item1, item2));
59-
}
58+
List<MoveItem> movable = new ArrayList<>();
59+
60+
for (int i = 0; i < elements.size(); i++) {
61+
ElementPosition elem = elements.get(i);
62+
if (elem.generatorFloor == elevatorFloor) {
63+
movable.add(new MoveItem(i, true));
64+
}
65+
if (elem.microchipFloor == elevatorFloor) {
66+
movable.add(new MoveItem(i, false));
6067
}
6168
}
6269

63-
// Try moving up or down
64-
for (int newElevator : List.of(elevator - 1, elevator + 1)) {
65-
if (newElevator >= 0 && newElevator < floors.size()) {
66-
for (List<String> items : itemCombos) {
67-
List<Set<String>> newFloors = new ArrayList<>();
68-
for (int i = 0; i < floors.size(); i++) {
69-
newFloors.add(new HashSet<>(floors.get(i)));
70+
for (int dir : new int[]{-1, 1}) {
71+
int newFloor = elevatorFloor + dir;
72+
if (newFloor < 0 || newFloor >= 4) continue;
73+
74+
for (int count = 1; count <= Math.min(2, movable.size()); count++) {
75+
Combinations.combinations(movable, count).forEach(combo -> {
76+
List<ElementPosition> newElements = new ArrayList<>(elements);
77+
for (MoveItem item : combo) {
78+
ElementPosition e = newElements.get(item.elementIndex);
79+
if (item.isGenerator) {
80+
newElements.set(item.elementIndex, new ElementPosition(newFloor, e.microchipFloor));
81+
} else {
82+
newElements.set(item.elementIndex, new ElementPosition(e.generatorFloor, newFloor));
83+
}
7084
}
71-
72-
// Move items
73-
items.forEach(item -> {
74-
newFloors.get(elevator).remove(item);
75-
newFloors.get(newElevator).add(item);
76-
});
77-
78-
State newState = new State(newElevator, newFloors);
85+
State newState = new State(newFloor, newElements);
7986
if (newState.isValid()) {
8087
states.add(newState);
8188
}
82-
}
89+
});
8390
}
8491
}
85-
8692
return states;
8793
}
8894
}
8995

96+
private record MoveItem(int elementIndex, boolean isGenerator) {}
97+
9098
private int findMinSteps(State initial) {
9199
Queue<State> queue = new ArrayDeque<>();
92100
Map<State, Integer> visited = new HashMap<>();
@@ -103,38 +111,52 @@ private int findMinSteps(State initial) {
103111

104112
for (State next : current.nextStates()) {
105113
if (!visited.containsKey(next)) {
106-
queue.add(next);
107114
visited.put(next, steps + 1);
115+
queue.add(next);
108116
}
109117
}
110118
}
111-
112119
return -1;
113120
}
114121

115-
private State parseInput(boolean includePart2Items) {
116-
List<Set<String>> floors = new ArrayList<>();
117-
for (int i = 0; i < 4; i++) {
118-
floors.add(new HashSet<>());
119-
}
120-
122+
private State parseInput(boolean includePart2) {
123+
Map<String, Integer> generatorFloors = new HashMap<>();
124+
Map<String, Integer> microchipFloors = new HashMap<>();
125+
121126
int floor = 0;
122127
for (String line : dayStream().toList()) {
123-
Matcher matcher = ITEM_PATTERN.matcher(line);
124-
while (matcher.find()) {
125-
String element = matcher.group(1);
126-
String type = matcher.group(2);
127-
floors.get(floor).add(element.substring(0, 2).toUpperCase() +
128-
(type.equals("generator") ? "G" : "M"));
128+
Matcher m = ITEM_PATTERN.matcher(line);
129+
while (m.find()) {
130+
String element = m.group(1).substring(0, 2).toUpperCase();
131+
String type = m.group(2);
132+
if (type.equals("generator")) {
133+
generatorFloors.put(element, floor);
134+
} else {
135+
microchipFloors.put(element, floor);
136+
}
129137
}
130138
floor++;
131139
}
132140

133-
if (includePart2Items) {
134-
floors.get(0).addAll(Set.of("ELG", "ELM", "DIG", "DIM"));
141+
if (includePart2) {
142+
generatorFloors.put("EL", 0);
143+
microchipFloors.put("EL", 0);
144+
generatorFloors.put("DI", 0);
145+
microchipFloors.put("DI", 0);
135146
}
136147

137-
return new State(0, floors);
148+
Set<String> allElements = new HashSet<>();
149+
allElements.addAll(generatorFloors.keySet());
150+
allElements.addAll(microchipFloors.keySet());
151+
152+
List<ElementPosition> elements = allElements.stream()
153+
.map(e -> new ElementPosition(
154+
generatorFloors.getOrDefault(e, -1),
155+
microchipFloors.getOrDefault(e, -1)
156+
))
157+
.toList();
158+
159+
return new State(0, elements);
138160
}
139161

140162
@Override
@@ -147,3 +169,22 @@ public Object part2() {
147169
return findMinSteps(parseInput(true));
148170
}
149171
}
172+
173+
class Combinations {
174+
static <T> Stream<List<T>> combinations(List<T> items, int k) {
175+
if (k == 0) {
176+
return Stream.of(Collections.emptyList());
177+
} else {
178+
return IntStream.range(0, items.size()).boxed()
179+
.flatMap(i -> combinations(items.subList(i+1, items.size()), k-1)
180+
.map(t -> prepend(items.get(i), t)));
181+
}
182+
}
183+
184+
private static <T> List<T> prepend(T head, List<T> tail) {
185+
List<T> result = new ArrayList<>();
186+
result.add(head);
187+
result.addAll(tail);
188+
return result;
189+
}
190+
}

‎src/main/java/com/sbaars/adventofcode/year16/days/Day5.java

Lines changed: 22 additions & 23 deletions
Original file line numberDiff line numberDiff line change
@@ -22,14 +22,18 @@ public Object part1() {
2222
String doorId = day().trim();
2323
StringBuilder password = new StringBuilder();
2424
int index = 0;
25+
2526
try {
2627
MessageDigest md = MessageDigest.getInstance("MD5");
2728
while (password.length() < 8) {
28-
String input = doorId + index;
29-
byte[] digest = md.digest(input.getBytes(StandardCharsets.UTF_8));
30-
String hash = bytesToHex(digest);
31-
if (hash.startsWith("00000")) {
32-
password.append(hash.charAt(5));
29+
byte[] digest = md.digest((doorId + index).getBytes(StandardCharsets.UTF_8));
30+
31+
// Check if first 20 bits (5 hex zeroes) are zero
32+
// digest[0] == 0 && digest[1] == 0 && (digest[2] & 0xF0) == 0
33+
if (digest[0] == 0 && digest[1] == 0 && (digest[2] & 0xF0) == 0) {
34+
// The 6th hex character is the low nibble of digest[2]
35+
int nib5 = digest[2] & 0x0F;
36+
password.append(toHexChar(nib5));
3337
}
3438
index++;
3539
}
@@ -46,21 +50,20 @@ public Object part2() {
4650
Arrays.fill(password, '_');
4751
int filled = 0;
4852
int index = 0;
53+
4954
try {
5055
MessageDigest md = MessageDigest.getInstance("MD5");
5156
while (filled < 8) {
52-
String input = doorId + index;
53-
byte[] digest = md.digest(input.getBytes(StandardCharsets.UTF_8));
54-
String hash = bytesToHex(digest);
55-
if (hash.startsWith("00000") && hash.length() >= 7) {
56-
char posChar = hash.charAt(5);
57-
if (posChar >= '0' && posChar <= '7') {
58-
int pos = posChar - '0';
59-
if (password[pos] == '_') {
60-
char c = hash.charAt(6);
61-
password[pos] = c;
62-
filled++;
63-
}
57+
byte[] digest = md.digest((doorId + index).getBytes(StandardCharsets.UTF_8));
58+
// Same check as above
59+
if (digest[0] == 0 && digest[1] == 0 && (digest[2] & 0xF0) == 0) {
60+
// 6th hex character is nib5 (low nibble of digest[2]), 7th is nib6 (high nibble of digest[3])
61+
int nib5 = digest[2] & 0x0F; // position
62+
int nib6 = (digest[3] & 0xF0) >>> 4; // actual character
63+
64+
if (nib5 < 8 && password[nib5] == '_') {
65+
password[nib5] = toHexChar(nib6);
66+
filled++;
6467
}
6568
}
6669
index++;
@@ -71,11 +74,7 @@ public Object part2() {
7174
return new String(password);
7275
}
7376

74-
private static String bytesToHex(byte[] bytes) {
75-
StringBuilder sb = new StringBuilder();
76-
for (byte b : bytes) {
77-
sb.append(String.format("%02x", b));
78-
}
79-
return sb.toString();
77+
private static char toHexChar(int nibble) {
78+
return (char) (nibble < 10 ? ('0' + nibble) : ('a' + (nibble - 10)));
8079
}
8180
}

0 commit comments

Comments
 (0)