Finish day 24

3 files changed, 237 insertions, 12 deletions

diff --git a/README.md b/README.md
index 34bf6fb..311fa77 100644
--- a/README.md
+++ b/README.md
@@ -1,8 +1,8 @@
 # Advent of Code 2021 in Kotlin
 
 ![Kotlin](https://img.shields.io/badge/Kotlin-grey?logo=Kotlin)
-![](https://img.shields.io/badge/⭐%20stars-37-yellow)
-![](https://img.shields.io/badge/📅%20days-19-blue)
+![](https://img.shields.io/badge/⭐%20stars-39-yellow)
+![](https://img.shields.io/badge/📅%20days-20-blue)
 
 Welcome to the Advent of Code[^aoc] Kotlin project created by [tchojnacki][github] using
 the [Advent of Code Kotlin Template][template] delivered by JetBrains. See other solutions [here][awesome].
@@ -34,7 +34,7 @@ the [Advent of Code Kotlin Template][template] delivered by JetBrains. See other
 | Day 21: Dirac Dice              |        |        |
 | Day 22: Reactor Reboot          |        |        |
 | Day 23: Amphipod                |        |        |
-| Day 24: Arithmetic Logic Unit   |        |        |
+| Day 24: Arithmetic Logic Unit   |   🌟   |   🌟   |
 | Day 25: Sea Cucumber            |   🌟   |        |
 
 [^aoc]:
diff --git a/src/Day24.kt b/src/Day24.kt
new file mode 100644
index 0000000..41ea440
--- /dev/null
+++ b/src/Day24.kt
@@ -0,0 +1,234 @@
+object Day24 {
+    @JvmInline
+    private value class Register private constructor(val address: Int) {
+        companion object {
+            val W = Register(0)
+            val X = Register(1)
+            val Y = Register(2)
+            val Z = Register(3)
+
+            fun fromString(string: String) = when (string) {
+                "x" -> X
+                "y" -> Y
+                "z" -> Z
+                "w" -> W
+                else -> throw IllegalArgumentException(string)
+            }
+        }
+    }
+
+    private sealed class Instruction {
+        companion object {
+            fun fromString(string: String) = string.split(" ").let { parts ->
+                val operatorString = parts[0]
+                val target = Register.fromString(parts[1])
+
+                if (operatorString == "inp") {
+                    Input(target)
+                } else {
+                    val opcode = when (operatorString) {
+                        "add" -> Binary.Opcode.ADD
+                        "mul" -> Binary.Opcode.MUL
+                        "div" -> Binary.Opcode.DIV
+                        "mod" -> Binary.Opcode.MOD
+                        "eql" -> Binary.Opcode.EQL
+                        else -> throw IllegalArgumentException(operatorString)
+                    }
+
+                    val source = when (val parsed = parts[2].toLongOrNull()) {
+                        is Long -> Source.Literal(parsed)
+                        else -> Source.Memory(Register.fromString(parts[2]))
+                    }
+
+                    Binary(opcode, target, source)
+                }
+            }
+        }
+
+        data class Input(val register: Register) : Instruction()
+        data class Binary(val opcode: Opcode, val a: Register, val b: Source) : Instruction() {
+            enum class Opcode {
+                ADD, MUL, DIV, MOD, EQL
+            }
+        }
+
+        sealed class Source {
+            data class Memory(val register: Register) : Source()
+            data class Literal(val value: Long) : Source()
+        }
+    }
+
+    private data class ALU(private val memory: LongArray) {
+        @Suppress("unused")
+        val w get() = memory[Register.W.address]
+
+        @Suppress("unused")
+        val x get() = memory[Register.X.address]
+
+        @Suppress("unused")
+        val y get() = memory[Register.Y.address]
+
+        @Suppress("unused")
+        val z get() = memory[Register.Z.address]
+
+        fun toMutable() = MutableALU(memory.clone())
+
+        override fun equals(other: Any?): Boolean {
+            if (this === other) return true
+            if (javaClass != other?.javaClass) return false
+            return memory.contentEquals((other as ALU).memory)
+        }
+
+        override fun hashCode() = memory.contentHashCode()
+    }
+
+    private class MutableALU(private val memory: LongArray) {
+        constructor() : this(LongArray(4) { 0L })
+
+        fun toImmutable() = ALU(memory.clone())
+
+        fun executeBatch(batch: List<Instruction.Binary>) {
+            batch.forEach {
+                memory[it.a.address] = when (it.opcode) {
+                    Instruction.Binary.Opcode.ADD -> fetch(it.a) + fetch(it.b)
+                    Instruction.Binary.Opcode.MUL -> fetch(it.a) * fetch(it.b)
+                    Instruction.Binary.Opcode.DIV -> fetch(it.a) / fetch(it.b)
+                    Instruction.Binary.Opcode.MOD -> fetch(it.a) % fetch(it.b)
+                    Instruction.Binary.Opcode.EQL -> if (fetch(it.a) == fetch(it.b)) 1L else 0L
+                }
+            }
+        }
+
+        fun feedInput(input: Instruction.Input, value: Long) {
+            memory[input.register.address] = value
+        }
+
+        private fun fetch(register: Register) = memory[register.address]
+
+        private fun fetch(source: Instruction.Source) = when (source) {
+            is Instruction.Source.Literal -> source.value
+            is Instruction.Source.Memory -> memory[source.register.address]
+        }
+    }
+
+    private class Program private constructor(private val parts: List<Part>) {
+        companion object {
+            fun compileFrom(inputs: List<String>): Program {
+                val instructionQueue = inputs.map(Instruction::fromString)
+
+                val parts = mutableListOf<Part>()
+
+                val currentStep = mutableListOf<Instruction.Binary>()
+                var currentInput: Instruction.Input? = null
+
+                for (instruction in instructionQueue) {
+                    when (instruction) {
+                        is Instruction.Input -> {
+                            parts.add(Part(currentInput, currentStep.toList()))
+
+                            currentStep.clear()
+                            currentInput = instruction
+                        }
+
+                        is Instruction.Binary -> currentStep.add(instruction)
+                    }
+                }
+
+                parts.add(Part(currentInput, currentStep.toList()))
+
+                return Program(parts)
+            }
+        }
+
+        private data class Part(val input: Instruction.Input?, val instructionBatch: List<Instruction.Binary>)
+
+        private data class Checkpoint(
+            val partNumber: Int,
+            val alu: ALU,
+        )
+
+        fun findInputDigits(
+            digitRange: IntProgression = 0..9,
+            successCondition: (ALU) -> Boolean
+        ): Sequence<Long> {
+            val cache = mutableSetOf<Checkpoint>()
+            val matchingCheckpoints = mutableSetOf<Checkpoint>()
+
+            fun solveRecursively(checkpoint: Checkpoint, accumulator: Long): Sequence<Long> = sequence {
+                if (cache.contains(checkpoint)) return@sequence
+
+                if (checkpoint.partNumber == parts.size) {
+                    if (successCondition(checkpoint.alu)) {
+                        yield(accumulator)
+                        val statesOfCurrent = inputStateSequence(accumulator).toSet()
+                        matchingCheckpoints.addAll(statesOfCurrent)
+                        cache.removeAll(statesOfCurrent)
+                    }
+
+                    return@sequence
+                }
+
+                for (digit in digitRange) {
+                    yieldAll(
+                        solveRecursively(
+                            Checkpoint(
+                                checkpoint.partNumber + 1,
+                                executePart(checkpoint.partNumber, checkpoint.alu, digit.toLong()),
+                            ),
+                            accumulator * 10 + digit,
+                        )
+                    )
+                }
+
+                if (!matchingCheckpoints.contains(checkpoint)) cache.add(checkpoint)
+
+                Runtime.getRuntime().let {
+                    if (it.totalMemory().toDouble() / it.maxMemory() > 0.75) {
+                        cache.clear()
+                        it.gc()
+                    }
+                }
+            }
+
+            return solveRecursively(Checkpoint(1, executePart(0)), 0L)
+        }
+
+        private fun inputStateSequence(input: Long) = sequence {
+            var checkpoint = Checkpoint(1, executePart(0))
+            yield(checkpoint)
+
+            for (digit in input.toString().toCharArray().map { it.toString().toInt() }) {
+                checkpoint = Checkpoint(
+                    checkpoint.partNumber + 1,
+                    executePart(checkpoint.partNumber, checkpoint.alu, digit.toLong())
+                )
+                yield(checkpoint)
+            }
+        }
+
+        private fun executePart(partNumber: Int, alu: ALU? = null, input: Long? = null): ALU {
+            val part = parts[partNumber]
+            val executor = alu?.toMutable() ?: MutableALU()
+
+            if (part.input != null && input != null)
+                executor.feedInput(part.input, input)
+
+            executor.executeBatch(part.instructionBatch)
+
+            return executor.toImmutable()
+        }
+    }
+
+    fun bothParts(input: List<String>) = Program
+        .compileFrom(input)
+        .findInputDigits(digitRange = 9 downTo 1) { it.z == 0L }
+        .let { it.first() to it.last() }
+}
+
+fun main() {
+    val input = readInputAsLines("Day24")
+    val output = Day24.bothParts(input)
+
+    println(output.first)
+    println(output.second)
+}
diff --git a/src/Utils.kt b/src/Utils.kt
index c0f4f61..e245554 100644
--- a/src/Utils.kt
+++ b/src/Utils.kt
@@ -1,6 +1,4 @@
 import java.io.File
-import java.math.BigInteger
-import java.security.MessageDigest
 
 /**
  * Reads lines from the given input txt file.
@@ -52,10 +50,3 @@ fun parseToMap(input: List<String>): Map<Pos2D, Int> =
             Pos2D(x, y) to char.toString().toInt()
         }
     }.toMap()
-
-/**
- * Converts string to md5 hash.
- * @receiver a string
- * @return md5 hash of receiver
- */
-fun String.md5(): String = BigInteger(1, MessageDigest.getInstance("MD5").digest(toByteArray())).toString(16)