Skip to content

Commit de95d6b

Browse files
codeforkjeffcodeforkjeff
committed
exploratory code for day 24 part 2 (not finished)
1 parent 8e9c1da commit de95d6b

File tree

2 files changed

+138
-0
lines changed

2 files changed

+138
-0
lines changed

‎src/main/java/com/codefork/aoc2024/day24/Device.java

Lines changed: 64 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1,7 +1,12 @@
11
package com.codefork.aoc2024.day24;
22

3+
import java.sql.Array;
4+
import java.util.ArrayList;
35
import java.util.HashMap;
6+
import java.util.HashSet;
7+
import java.util.List;
48
import java.util.Map;
9+
import java.util.Set;
510
import java.util.regex.Pattern;
611
import java.util.stream.Stream;
712

@@ -93,4 +98,63 @@ public static Device parse(Stream<String> data) {
9398
public int getWire(String wireName) {
9499
return namesToWires.get(wireName).value(this);
95100
}
101+
102+
public boolean hasWire(String wireName) {
103+
return namesToWires().containsKey(wireName);
104+
}
105+
106+
public Device swap(String name1, String name2) {
107+
var newNamesToWires = new HashMap<>(namesToWires());
108+
var wire1 = newNamesToWires.get(name1);
109+
var wire2 = newNamesToWires.get(name2);
110+
newNamesToWires.put(name1, wire2);
111+
newNamesToWires.put(name2, wire1);
112+
return new Device(newNamesToWires);
113+
}
114+
115+
/** get only the gate dependencies (not the x and y wire values) */
116+
public Set<String> getGateDependencies(String name) {
117+
var toVisit = new ArrayList<String>();
118+
var visited = new HashSet<String>();
119+
toVisit.add(name);
120+
var dependencies = new HashSet<String>();
121+
while(!toVisit.isEmpty()) {
122+
var wireName = toVisit.getFirst();
123+
if(visited.contains(wireName)) {
124+
toVisit.removeFirst();
125+
continue;
126+
}
127+
if(wireName.startsWith("x") || wireName.startsWith("y")) {
128+
toVisit.removeFirst();
129+
visited.add(wireName);
130+
continue;
131+
}
132+
dependencies.add(wireName);
133+
var wire = namesToWires().get(wireName);
134+
switch (wire) {
135+
case Or w -> {
136+
toVisit.add(w.op1.name());
137+
toVisit.add(w.op2.name());
138+
}
139+
case And w -> {
140+
toVisit.add(w.op1.name());
141+
toVisit.add(w.op2.name());
142+
}
143+
case Xor w -> {
144+
toVisit.add(w.op1.name());
145+
toVisit.add(w.op2.name());
146+
}
147+
case NamedValue v -> {
148+
// do nothing
149+
}
150+
case LiteralValue v -> {
151+
// do nothing
152+
}
153+
}
154+
toVisit.removeFirst();
155+
visited.add(wireName);
156+
}
157+
return dependencies;
158+
}
159+
96160
}

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

Lines changed: 74 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,74 @@
1+
package com.codefork.aoc2024.day24;
2+
3+
import com.codefork.aoc2024.Problem;
4+
import com.codefork.aoc2024.util.Assert;
5+
6+
import java.util.ArrayList;
7+
import java.util.HashSet;
8+
import java.util.List;
9+
import java.util.stream.Collectors;
10+
import java.util.stream.Stream;
11+
12+
import static com.codefork.aoc2024.util.FoldLeft.foldLeft;
13+
14+
public class Part02 extends Problem {
15+
16+
public String solve(Stream<String> data) {
17+
var device = Device.parse(data);
18+
19+
// this is just a bunch of exploratory code at the moment
20+
21+
var xyz = List.of("x", "y", "z");
22+
// group xyz wires by two-digit numeric suffix
23+
var byPos = device.namesToWires().keySet().stream()
24+
.filter(name -> xyz.contains(name.substring(0, 1)))
25+
.collect(Collectors.groupingBy((name) -> name.substring(1, 3)));
26+
27+
var positions = byPos.keySet().stream().sorted().toList();
28+
29+
var badZ = new ArrayList<String>();
30+
31+
// look through each bit position, calculate what it should be, and flag it if it's not what we expect
32+
var carry = 0;
33+
for(var pos : positions) {
34+
var z = device.getWire("z" + pos);
35+
if(device.hasWire("x" + pos)) {
36+
var x = device.getWire("x" + pos);
37+
var y = device.getWire("y" + pos);
38+
var posSum = x ^ y;
39+
var expected = posSum ^ carry; // if x and y differ, you get the carry
40+
var flag = (z != expected) ? "FLAGGED" : "";
41+
if (z != expected) {
42+
badZ.add("z" + pos);
43+
}
44+
System.out.printf("%s carry=%s x=%s y=%s z=%s expected=%s %s%n", pos, carry, x, y, z, expected, flag);
45+
carry = (expected == 0 & carry == 1) || ((x & y) == 1) ? 1 : 0;
46+
} else {
47+
System.out.printf("%s z=%s%n", pos, z);
48+
}
49+
}
50+
51+
// badZ and its dependencies = swap candidates
52+
var candidates = new HashSet<String>();
53+
for(var zName : badZ) {
54+
var deps = device.getGateDependencies(zName);
55+
System.out.println(zName + " dependencies = " + deps);
56+
candidates.addAll(deps);
57+
}
58+
// this reduces the candidate pool, but only by about 50. doesn't seem like the optimal way to do this.
59+
System.out.println("total candidates=" + candidates.size());
60+
61+
// figure out how to test every combination of 4 pair swaps in that set of candidates?
62+
return "UNFINISHED";
63+
}
64+
65+
@Override
66+
public String solve() {
67+
return solve(getInput());
68+
}
69+
70+
public static void main(String[] args) {
71+
new Part02().run();
72+
}
73+
74+
}

0 commit comments

Comments
 (0)