Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commitedcce40

Browse files
committed
day 17 part 2
1 parent65fc7f1 commitedcce40

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
importjava.util.Collections;
66
importjava.util.List;
77
importjava.util.Map;
8-
importjava.util.Optional;
98
importjava.util.regex.Pattern;
109
importjava.util.stream.Collectors;
1110
importjava.util.stream.Stream;
@@ -93,40 +92,33 @@ public Computer run() {
9392
varinstruction =opcodesToInstructions.get(opcode);
9493
varoperand =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
returnstate;
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-
publicOptional<Computer>runUntilMatch() {
105-
varstate =this;
106-
varmismatch =false;
107-
while(state.ip() <=state.program.size() -2 && !mismatch) {
108-
varopcode =state.program().get(state.ip());
109-
varrawOperand =state.program().get(state.ip()+1);
107+
publicvoidprintProgram() {
108+
for(vari =0;i <program.size();i +=2) {
109+
varopcode =program().get(i);
110+
varrawOperand =program().get(i+1);
110111
varinstruction =opcodesToInstructions.get(opcode);
111-
varoperand =instruction.parseOperand(rawOperand);
112-
state =instruction.apply(operand,state);
113-
//System.out.println(state);
114-
115-
if(instruction.equals(Instruction.out)) {
116-
varsizeLimit =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(vari =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-
returnOptional.of(state);
127-
}
112+
System.out.println(instruction.name() +" " +rawOperand);
128113
}
129-
returnOptional.empty();
114+
}
115+
116+
publicvoiddump() {
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
publicComputerapply(Operandoperand,Computercomputer) {
130130
varoperandEvaluated =operand.eval(computer);
131-
varresult =computer.a() / (int)Math.pow(2,operandEvaluated);
131+
varresult =computer.a() / (long)Math.pow(2,operandEvaluated);
132132
returncomputer.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
importcom.codefork.aoc2024.Problem;
44
importcom.codefork.aoc2024.util.Assert;
55

6+
importjava.util.ArrayList;
7+
importjava.util.List;
68
importjava.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
publicclassPart02extendsProblem {
932

1033
publicStringsolve(Stream<String>data) {
11-
varcomputer =Computer.parse(data).withA(35184372088831L);
12-
while(true) {
13-
varresult =computer.run();//UntilMatch();
14-
// if(result.isPresent()) {
15-
// return result.get().getOutputAsString();
16-
// }
17-
if(result.program().equals(result.output())) {
18-
returnString.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+
varinitialComputer =Computer.parse(data);
35+
varprogramSize =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+
vari =programSize -1;
38+
List<Integer>expectedOutput =newArrayList<>();
39+
List<Long>candidates =newArrayList<>();
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-
publicvoidsearch(Computercomputer) {
48-
varlower =0L;
49-
varupper =Long.MAX_VALUE;
50-
longmid =0L;
51-
varfound =false;
45+
List<Long>newCandidates =newArrayList<>();
5246

53-
while (!found) {
54-
mid = (lower +upper) /2;
55-
varresult =computer.withA(mid).run();
56-
System.out.println(computer.a() +" = " +result);
57-
if(result.output().size() <result.program().size()) {
58-
upper =mid;
59-
}elseif(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(varcandidate :candidates) {
50+
for(varthreeBits =0;threeBits <8;threeBits++) {
51+
vartestA = (candidate <<3) +threeBits;
52+
vartestComputer =initialComputer.withA(testA);
53+
varfinalState =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+
varlowest =candidates.stream().mapToLong(n ->n).min().orElseThrow();
65+
returnString.valueOf(lowest);
6666
}
6767

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

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp