Skip to content

Commit 65fc7f1

Browse files
codeforkjeffcodeforkjeff
committed
day 17 part 2: non-working brute force and exploratory code
1 parent 1908672 commit 65fc7f1

File tree

7 files changed

+136
-29
lines changed

7 files changed

+136
-29
lines changed

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

Lines changed: 20 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -1,18 +1,29 @@
11
package com.codefork.aoc2024.day17;
22

33
public final class Combo extends Operand {
4-
public Combo(int value) {
4+
public Combo(long value) {
55
super(value);
66
}
77

88
@Override
9-
public int eval(Computer computer) {
10-
return switch (value) {
11-
case 0, 1, 2, 3 -> value;
12-
case 4 -> computer.a();
13-
case 5 -> computer.b();
14-
case 6 -> computer.c();
15-
default -> throw new RuntimeException("this should never happen");
16-
};
9+
public long eval(Computer computer) {
10+
// return switch (value) {
11+
// case 0L, 1L, 2L, 3L -> value;
12+
// case 4L -> computer.a();
13+
// case 5L -> computer.b();
14+
// case 6L -> computer.c();
15+
// default -> throw new RuntimeException("this should never happen");
16+
// };
17+
if (value == 0L || value == 1L || value == 2L || value == 3L) {
18+
return value;
19+
} else if (value == 4L) {
20+
return computer.a();
21+
} else if (value == 5L) {
22+
return computer.b();
23+
} else if (value == 6L) {
24+
return computer.c();
25+
} else {
26+
throw new RuntimeException("this should never happen");
27+
}
1728
}
1829
}

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

Lines changed: 52 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -1,15 +1,18 @@
11
package com.codefork.aoc2024.day17;
22

3+
import java.util.ArrayList;
34
import java.util.Arrays;
45
import java.util.Collections;
56
import java.util.List;
67
import java.util.Map;
8+
import java.util.Optional;
79
import java.util.regex.Pattern;
10+
import java.util.stream.Collectors;
811
import java.util.stream.Stream;
912

1013
import static com.codefork.aoc2024.util.FoldLeft.foldLeft;
1114

12-
public record Computer(int a, int b, int c, int ip, List<Integer> program, String output) {
15+
public record Computer(long a, long b, long c, int ip, List<Integer> program, List<Integer> output) {
1316

1417
private static final Map<Integer, Instruction> opcodesToInstructions = Instruction.opcodesToInstructions();
1518

@@ -18,7 +21,7 @@ public record Computer(int a, int b, int c, int ip, List<Integer> program, Strin
1821

1922
public static Computer parse(Stream<String> data) {
2023
return data.collect(foldLeft(
21-
() -> new Computer(0, 0, 0, 0, Collections.emptyList(), ""),
24+
() -> new Computer(0, 0, 0, 0, Collections.emptyList(), Collections.emptyList()),
2225
(acc, line) -> {
2326
var lineMatcher = registerPat.matcher(line);
2427
var progMatcher = programPat.matcher(line);
@@ -42,15 +45,15 @@ public static Computer parse(Stream<String> data) {
4245
);
4346
}
4447

45-
public Computer withA(int newA) {
48+
public Computer withA(long newA) {
4649
return new Computer(newA, b, c, ip, program, output);
4750
}
4851

49-
public Computer withB(int newB) {
52+
public Computer withB(long newB) {
5053
return new Computer(a, newB, c, ip, program, output);
5154
}
5255

53-
public Computer withC(int newC) {
56+
public Computer withC(long newC) {
5457
return new Computer(a, b, newC, ip, program, output);
5558
}
5659

@@ -62,16 +65,26 @@ public Computer withProgram(List<Integer> newProgram) {
6265
return new Computer(a, b, c, ip, newProgram, output);
6366
}
6467

68+
public Computer clearOutput() {
69+
return new Computer(a, b, c, ip, program, Collections.emptyList());
70+
}
71+
6572
// advance by 2, for "normal" instructions
6673
public Computer advanceIp() {
6774
return new Computer(a, b, c, ip + 2, program, output);
6875
}
6976

7077
public Computer appendOutput(int item) {
71-
var newOutput = output + (!output.isEmpty() ? "," : "") + item;
78+
//var newOutput = output + (!output.isEmpty() ? "," : "") + item;
79+
var newOutput = new ArrayList<>(output);
80+
newOutput.add(item);
7281
return new Computer(a, b, c, ip, program, newOutput);
7382
}
7483

84+
public String getOutputAsString() {
85+
return output.stream().map(i -> i.toString()).collect(Collectors.joining(","));
86+
}
87+
7588
public Computer run() {
7689
var state = this;
7790
while(state.ip() <= state.program.size() - 2) {
@@ -83,4 +96,37 @@ public Computer run() {
8396
}
8497
return state;
8598
}
99+
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);
110+
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+
}
128+
}
129+
return Optional.empty();
130+
}
86131
}
132+

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

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -74,7 +74,7 @@ public Operand parseOperand(int operand) {
7474
public Computer apply(Operand operand, Computer computer) {
7575
var operandEvaluated = operand.eval(computer);
7676
if(computer.a() != 0) {
77-
return computer.withIp(operandEvaluated);
77+
return computer.withIp((int) operandEvaluated);
7878
}
7979
return computer.advanceIp();
8080
}
@@ -111,7 +111,7 @@ public Operand parseOperand(int operand) {
111111
public Computer apply(Operand operand, Computer computer) {
112112
var operandEvaluated = operand.eval(computer);
113113
var result = operandEvaluated % 8;
114-
return computer.appendOutput(result).advanceIp();
114+
return computer.appendOutput((int) result).advanceIp();
115115
}
116116
},
117117
bdv {

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

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

33
public final class Literal extends Operand {
4-
public Literal(int value) {
4+
public Literal(long value) {
55
super(value);
66
}
77

88
@Override
9-
public int eval(Computer computer) {
9+
public long eval(Computer computer) {
1010
return value;
1111
}
1212
}

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

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

33
public abstract sealed class Operand permits Literal, Combo {
4-
protected final int value;
4+
protected final long value;
55

6-
public Operand(int value) {
6+
public Operand(long value) {
77
this.value = value;
88
}
99

10-
public abstract int eval(Computer computer);
10+
public abstract long eval(Computer computer);
1111
}

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

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -10,7 +10,7 @@ public class Part01 extends Problem {
1010
public String solve(Stream<String> data) {
1111
var computer = Computer.parse(data);
1212
var finalState = computer.run();
13-
return finalState.output();
13+
return finalState.getOutputAsString();
1414
}
1515

1616
@Override

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

Lines changed: 56 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -8,17 +8,67 @@
88
public class Part02 extends Problem {
99

1010
public String solve(Stream<String> data) {
11-
// var computer = Computer.parse(data);
12-
// var finalState = computer.run();
13-
// return finalState.output();
14-
return "";
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+
}
26+
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.
31+
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+
}
46+
47+
public void search(Computer computer) {
48+
var lower = 0L;
49+
var upper = Long.MAX_VALUE;
50+
long mid = 0L;
51+
var found = false;
52+
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;
64+
}
65+
}
1566
}
1667

1768
@Override
1869
public String solve() {
1970
//Assert.assertEquals("0,3,5,4,3,0", solve(getFileAsStream("sample2")));
20-
//return solve(getInput());
21-
return "UNFINISHED";
71+
return solve(getInput());
2272
}
2373

2474
public static void main(String[] args) {

0 commit comments

Comments
 (0)