|
1 | 1 | package com.codefork.aoc2024.day17; |
2 | 2 |
|
3 | 3 | import com.codefork.aoc2024.Problem; |
4 | | -import com.codefork.aoc2024.util.Assert; |
5 | 4 |
|
6 | 5 | import java.util.ArrayList; |
7 | 6 | import java.util.List; |
| 7 | +import java.util.stream.IntStream; |
8 | 8 | import java.util.stream.Stream; |
9 | 9 |
|
10 | 10 | /** |
|
30 | 30 | */ |
31 | 31 | public class Part02 extends Problem { |
32 | 32 |
|
| 33 | + public long findLowestAForQuine(Computer computer, int i, List<Long> candidates) { |
| 34 | + if(i >= 0) { |
| 35 | + var expectedOutput = computer.program().subList(i, computer.program().size()); |
| 36 | + var newCandidates = candidates.stream() |
| 37 | + .flatMap(candidate -> |
| 38 | + IntStream.range(0, 8).boxed().flatMap(threeBits -> { |
| 39 | + var testA = (candidate << 3) + threeBits; |
| 40 | + var testComputer = computer.withA(testA).run(); |
| 41 | + return testComputer.output().equals(expectedOutput) ? Stream.of(testA) : Stream.empty(); |
| 42 | + })) |
| 43 | + .toList(); |
| 44 | + return findLowestAForQuine(computer, i-1, newCandidates); |
| 45 | + } else { |
| 46 | + return candidates.stream().mapToLong(n -> n).min().orElseThrow(); |
| 47 | + } |
| 48 | + } |
| 49 | + |
33 | 50 | public String solve(Stream<String> data) { |
34 | 51 | var initialComputer = Computer.parse(data); |
35 | | - var programSize = initialComputer.program().size(); |
36 | | - |
37 | | - var i = programSize - 1; |
38 | | - List<Integer> expectedOutput = new ArrayList<>(); |
39 | | - List<Long> candidates = new ArrayList<>(); |
40 | | - candidates.add(0L); |
41 | 52 |
|
42 | | - while (i >= 0) { |
43 | | - expectedOutput.addFirst(initialComputer.program().get(i)); |
| 53 | + vari = initialComputer.program().size() - 1; |
| 54 | + List<Long> candidates = List.of(0L); |
44 | 55 |
|
45 | | - List<Long> newCandidates = new ArrayList<>(); |
46 | | - |
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 | | - } |
58 | | - } |
59 | | - candidates = newCandidates; |
60 | | - //System.out.println("candidates=" + candidates); |
61 | | - i--; |
62 | | - } |
| 56 | + var lowestA = findLowestAForQuine(initialComputer, i, candidates); |
63 | 57 |
|
64 | | - var lowest = candidates.stream().mapToLong(n -> n).min().orElseThrow(); |
65 | | - return String.valueOf(lowest); |
| 58 | + return String.valueOf(lowestA); |
66 | 59 | } |
67 | 60 |
|
68 | 61 | @Override |
|
0 commit comments