8000 Add non-Z3 reverse engineered solution to 2024 day 17 part 2 · sim642/adventofcode@fb0737a · GitHub
[go: up one dir, main page]
Skip to content

Commit fb0737a

Browse files
sim642sim642
committed
Add non-Z3 reverse engineered solution to 2024 day 17 part 2
1 parent 9bda4ef commit fb0737a

File tree

2 files changed

+29
-0
lines changed

2 files changed

+29
-0
lines changed

‎src/main/scala/eu/sim642/adventofcode2024/Day17.scala

Lines changed: 26 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -2,6 +2,7 @@ package eu.sim642.adventofcode2024
22

33
import com.microsoft.z3.{BitVecExpr, BoolExpr, Context, Status}
44

5+
import scala.annotation.tailrec
56
import scala.jdk.CollectionConverters.*
67

78
object Day17 {
@@ -211,6 +212,31 @@ object Day17 {
211212
}
212213
}
213214

215+
object ReverseEngineeredPart2Solution extends Part2Solution {
216+
override def findQuineA(input: Input): Long = {
217+
val iterProgram :+ 3 :+ 0 = input.program
218+
219+
@tailrec
220+
def helper(as: Set[Long], expectedOutputsRev: List[Int]): Set[Long] = expectedOutputsRev match {
221+
case Nil => as
222+
case expectedOutput :: newExpectedOutputsRev =>
223+
val newAs =
224+
for {
225+
a <- as
226+
aStep <- 0 to 7
227+
newA = (a << 3) | aStep
228+
out = runOutput0(Input(Registers((newA & 0b1111111111).toInt, 0, 0), iterProgram))
229+
if out == Seq(expectedOutput)
230+
} yield newA
231+
helper(newAs, newExpectedOutputsRev)
232+
}
233+
234+
val as = helper(Set(0), input.program.reverse.toList)
235+
//as.foreach(println)
236+
as.min
237+
}
238+
}
239+
214240
def parseInput(input: String): Input = input match {
215241
case s"Register A: $a\nRegister B: $b\nRegister C: $c\n\nProgram: $programStr" =>
216242
val registers = Registers(a.toInt, b.toInt, c.toInt)

‎src/test/scala/eu/sim642/adventofcode2024/Day17Test.scala

Lines changed: 3 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -10,6 +10,7 @@ class Day17Test extends Suites(
1010
new NaivePart2SolutionTest,
1111
new ReverseEngineeredZ3Part2SolutionTest,
1212
new GenericZ3Part2SolutionTest,
13+
new ReverseEngineeredPart2SolutionTest,
1314
)
1415

1516
object Day17Test {
@@ -73,4 +74,6 @@ object Day17Test {
7374
class ReverseEngineeredZ3Part2SolutionTest extends Part2SolutionInputTest(ReverseEngineeredZ3Part2Solution)
7475

7576
class GenericZ3Part2SolutionTest extends Part2SolutionExampleTest(GenericZ3Part2Solution) with Part2SolutionInputTest(GenericZ3Part2Solution)
77+
78+
class ReverseEngineeredPart2SolutionTest extends Part2SolutionInputTest(ReverseEngineeredPart2Solution)
7679
}

0 commit comments

Comments
 (0)
0