Skip to content

Commit edcce40

Browse files
codeforkjeffcodeforkjeff
committed
day 17 part 2
1 parent 65fc7f1 commit edcce40

File tree

4 files changed

+89
-80
lines changed

4 files changed

+89
-80
lines changed

‎README.md

Lines changed: 18 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -195,3 +195,21 @@ I suppose slogging through it was worth the insight into how mathematical additi
195195

196196
Anyway, day 17 part 2 is the last remaining puzzle for me. Like day 24, it involves implementing a computer. Ugh,
197197
I dislike these types of problems so much.
198+
199+
### 1/16/2025
200+
201+
I owe the solution to day 17 part 2 entirely to my friend [Rob](https://github.com/robabrazado/adventofcode2024/)
202+
and discussions I found on reddit.
203+
204+
It may be that there's only one viable approach to this problem, as every single solution I looked at
205+
did it pretty much the same way, by analyzing what the program in the puzzle input actually did. I'm fairly sure
206+
there's no "generic" solution, since not every program is a quine.
207+
208+
I wrote up my own understanding of the solution in comments in the code.
209+
210+
This was my least favorite puzzle by far. Finishing days 24 and 17 last is pretty good evidence I suck at looking
211+
for patterns in machine instructions and logic gates.
212+
213+
But now I'm FINISHED! It's a great feeling, especially after not being able to complete AoC 2018.
214+
215+
I'll write up a post-mortem in a few days.

‎src/main/java/com/codefork/aoc2024/day17/Computer.java

Lines changed: 21 additions & 29 deletions
Original file line numberDiff line numberDiff line change
@@ -5,7 +5,6 @@
55
import java.util.Collections;
66
import java.util.List;
77
import java.util.Map;
8-
import java.util.Optional;
98
import java.util.regex.Pattern;
109
import java.util.stream.Collectors;
1110
import java.util.stream.Stream;
@@ -93,40 +92,33 @@ public Computer run() {
9392
var instruction = opcodesToInstructions.get(opcode);
9493
var operand = instruction.parseOperand(rawOperand);
9594
state = instruction.apply(operand, state);
95+
// System.out.printf("%s raw_op=%s A=%s B=%s C=%s ip=%s out=%s%n",
96+
// instruction.name(),
97+
// rawOperand,
98+
// Long.toBinaryString(state.a),
99+
// Long.toBinaryString(state.b),
100+
// Long.toBinaryString(state.c),
101+
// state.ip,
102+
// state.output);
96103
}
97104
return state;
98105
}
99106

100-
/**
101-
* keep running until output matches the program; if it starts to mismatch at any point,
102-
* return an empty optional
103-
*/
104-
public Optional<Computer> runUntilMatch() {
105-
var state = this;
106-
var mismatch = false;
107-
while(state.ip() <= state.program.size() - 2 && !mismatch) {
108-
var opcode = state.program().get(state.ip());
109-
var rawOperand = state.program().get(state.ip()+1);
107+
public void printProgram() {
108+
for(var i = 0; i < program.size(); i += 2) {
109+
var opcode = program().get(i);
110+
var rawOperand =program().get(i+1);
110111
var instruction = opcodesToInstructions.get(opcode);
111-
var operand = instruction.parseOperand(rawOperand);
112-
state = instruction.apply(operand, state);
113-
//System.out.println(state);
114-
115-
if(instruction.equals(Instruction.out)) {
116-
var sizeLimit = Math.min(state.output().size(), state.program().size());
117-
// System.out.println(state.output().size() + " " + state.program().size());
118-
// System.out.println("sizeLimit=" + sizeLimit);
119-
for(var i = 0; i < sizeLimit && !mismatch; i++) {
120-
if(!state.output().get(i).equals(state.program().get(i))) {
121-
mismatch = true;
122-
}
123-
}
124-
}
125-
if(!mismatch && state.output().size() == state.program().size()) {
126-
return Optional.of(state);
127-
}
112+
System.out.println(instruction.name() + " " + rawOperand);
128113
}
129-
return Optional.empty();
114+
}
115+
116+
public void dump() {
117+
System.out.printf("A=%s B=%s C=%s out=%s%n",
118+
Long.toBinaryString(a),
119+
Long.toBinaryString(b),
120+
Long.toBinaryString(c),
121+
output());
130122
}
131123
}
132124

‎src/main/java/com/codefork/aoc2024/day17/Instruction.java

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -128,7 +128,7 @@ public Operand parseOperand(int operand) {
128128
@Override
129129
public Computer apply(Operand operand, Computer computer) {
130130
var operandEvaluated = operand.eval(computer);
131-
var result = computer.a() / (int) Math.pow(2, operandEvaluated);
131+
var result = computer.a() / (long) Math.pow(2, operandEvaluated);
132132
return computer.withB(result).advanceIp();
133133
}
134134
},

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

Lines changed: 49 additions & 50 deletions
Original file line numberDiff line numberDiff line change
@@ -3,71 +3,70 @@
33
import com.codefork.aoc2024.Problem;
44
import com.codefork.aoc2024.util.Assert;
55

6+
import java.util.ArrayList;
7+
import java.util.List;
68
import java.util.stream.Stream;
79

10+
/**
11+
* Adapted from these solutions:
12+
* https://github.com/robabrazado/adventofcode2024/blob/main/src/com/robabrazado/aoc2024/day17/Computer.java
13+
* https://git.sr.ht/~murr/advent-of-code/tree/master/item/2024/17/p2.c
14+
* <p>
15+
* Writing out the program by hand, you can see it's a single giant loop that
16+
* does the following:
17+
* - set register B = last 3 bits of register A
18+
* - update registers B and C with a bunch of operations, using all 3 registers
19+
* - right-shift 3 bits off of register A
20+
* - print the rightmost 3 bits of register B
21+
* - starts again from the beginning if A != 0
22+
* This means we don't have to care about the bunch of operations sandwiched
23+
* in the loop. Since the loop gradually right-shifts register A until it's 0,
24+
* we can work backwards:
25+
* - find the 3 bit values (there will be more than one) that will produce the last
26+
* desired item
27+
* - left shift those values
28+
* - add another 3 bits to those values, to try to produce the last two desired items
29+
* - etc.
30+
*/
831
public class Part02 extends Problem {
932

1033
public String solve(Stream<String> data) {
11-
var computer = Computer.parse(data).withA(35184372088831L);
12-
while(true) {
13-
var result = computer.run(); //UntilMatch();
14-
// if(result.isPresent()) {
15-
// return result.get().getOutputAsString();
16-
// }
17-
if(result.program().equals(result.output())) {
18-
return String.valueOf(computer.a());
19-
}
20-
System.out.println(computer.a() + " = " + result);
21-
computer = computer.clearOutput().withA(computer.a() + 2000000);
22-
// if(computer.a() % 1000000 == 0) {
23-
// System.out.println(computer.a() + " = " + result);
24-
// }
25-
}
34+
var initialComputer = Computer.parse(data);
35+
var programSize = initialComputer.program().size();
2636

27-
// -------------------------------
28-
// output with 16 numbers begins at a=35184372088832,
29-
// 17 numbers begins at 281474976710656.
30-
// brute force would need to scan 246290604621824 numbers.
37+
var i = programSize - 1;
38+
List<Integer> expectedOutput = new ArrayList<>();
39+
List<Long> candidates = new ArrayList<>();
40+
candidates.add(0L);
3141

32-
// var computer = Computer.parse(data).withA(35184372088831L);
33-
//
34-
// //search(computer);
35-
//
36-
// while(true) {
37-
// var result = computer.run();
38-
// System.out.println(computer.a() + " = " + result);
39-
// if(result.output().equals(result.program())) {
40-
// return String.valueOf(computer.a());
41-
// }
42-
// //computer = computer.withA((computer.a() * 2) - 1);
43-
// computer = computer.clearOutput().withA(computer.a() +1);
44-
// }
45-
}
42+
while (i >= 0) {
43+
expectedOutput.addFirst(initialComputer.program().get(i));
4644

47-
public void search(Computer computer) {
48-
var lower = 0L;
49-
var upper = Long.MAX_VALUE;
50-
long mid = 0L;
51-
var found = false;
45+
List<Long> newCandidates = new ArrayList<>();
5246

53-
while (!found) {
54-
mid = (lower + upper) / 2;
55-
var result = computer.withA(mid).run();
56-
System.out.println(computer.a() + " = " + result);
57-
if(result.output().size() < result.program().size()) {
58-
upper = mid;
59-
} else if(result.output().size() > result.program().size()) {
60-
lower = mid;
61-
} else {
62-
System.out.println("finished? " + mid);
63-
found = true;
47+
//System.out.println("looking for next expected output=" + expectedOutput);
48+
49+
for(var candidate : candidates) {
50+
for(var threeBits = 0; threeBits < 8; threeBits++) {
51+
var testA = (candidate << 3) + threeBits;
52+
var testComputer = initialComputer.withA(testA);
53+
var finalState = testComputer.run();
54+
if(finalState.output().equals(expectedOutput)) {
55+
newCandidates.add(testA);
56+
}
57+
}
6458
}
59+
candidates = newCandidates;
60+
//System.out.println("candidates=" + candidates);
61+
i--;
6562
}
63+
64+
var lowest = candidates.stream().mapToLong(n -> n).min().orElseThrow();
65+
return String.valueOf(lowest);
6666
}
6767

6868
@Override
6969
public String solve() {
70-
//Assert.assertEquals("0,3,5,4,3,0", solve(getFileAsStream("sample2")));
7170
return solve(getInput());
7271
}
7372

0 commit comments

Comments
 (0)