bit-jkraushaar
Github: bit-jkraushaar,
Twitter: KraushaarJochen
Table of Contents
bit-jkraushaar
Day 00: kotlin
Hello World
This solution is written in Kotlin.
First Star
The solution is quite straight forward.
Just run "kotlinc-jvm -script solution.kts".
#!/usr/bin/env -S kotlinc-jvm -script
import java.io.File
val greeting = File("./input.txt").readText()
println("Hello $greeting")Day 01: kotlin
Day 01
It took me some time to figure out how the second star is computed… However this is my solution in Kotlin.
First Star
The first star is easy: Compute the module fuel by applying the formula to the mass of the module and then sum everything up.
First Star
val modules = File("./input.txt").readLines().map { it.toInt() }
fun calculateFuel(mass: Int) = (mass / 3) - 2
fun calculateModuleOnlyFuel (modules : List<Int>) = modules.map { calculateFuel(it) }.sum()
val moduleOnlyFuel = calculateModuleOnlyFuel(modules)
println("First star: $moduleOnlyFuel")Second Star
What took me so much time was to figure out that first the fuel of the first module has to be calculated, then fuel for the second module and so on. Finally everything has to be summed together. My first approach was to calculate the sum of the module fuel and then add the fuel and fuel for the fuel, and … So the result was too high.
Second Star
fun calculateModuleFuel(module: Int): Int {
val moduleFuel = calculateFuel(module)
if (moduleFuel <= 0) return 0
return moduleFuel + calculateModuleFuel(moduleFuel)
}
fun calculateTotalFuel(modules : List<Int>) = modules.map { calculateModuleFuel(it) }.sum()
val totalFuel = calculateTotalFuel(modules)
println("Second star: $totalFuel")Day 02: kotlin
Day 02
For todays puzzle I decided to build kind of a Turing machine. Therefore I first wrote an function to determine the next operation.
Determine the next operation
typealias OperatorFunction = (Int, List<Int>) -> Pair<Int, MutableList<Int>>
fun determineOperation(position: Int, intcode: List<Int>): OperatorFunction {
val operation = intcode[position]
return when (operation) {
1 -> ::add
2 -> ::multiply
99 -> ::stop
else -> ::error
}
}The function returns the operation to be executed.
Afterwards I had to write the four operations. Disclaimer: I think the add and multiply functions can be written with less duplicated code. I had a long day, so I decided to leave it as is.
Operator functions
fun add(position: Int, intcode: List<Int>): Pair<Int, MutableList<Int>> {
val firstPosition = intcode[position + 1]
val secondPosition = intcode[position + 2]
val outPosition = intcode[position + 3]
val outValue = intcode[firstPosition] + intcode[secondPosition]
val newIntcode = intcode.toMutableList()
newIntcode[outPosition] = outValue
return Pair(position + 4, newIntcode)
}
fun multiply(position: Int, intcode: List<Int>): Pair<Int, MutableList<Int>> {
val firstPosition = intcode[position + 1]
val secondPosition = intcode[position + 2]
val outPosition = intcode[position + 3]
val outValue = intcode[firstPosition] * intcode[secondPosition]
val newIntcode = intcode.toMutableList()
newIntcode[outPosition] = outValue
return Pair(position + 4, newIntcode)
}
fun stop(position: Int, intcode: List<Int>): Pair<Int, MutableList<Int>> {
return Pair(-1, intcode.toMutableList())
}
fun error(position: Int, intcode: List<Int>): Pair<Int, MutableList<Int>> {
println("Unknown op-code ${intcode[position]}")
return Pair(-1, intcode.toMutableList())
}The last part of my solution is a function to actually calculate the result of the intcode program.
intcode program execution
fun runProgram(noun: Int, verb: Int): Int {
var intcode = File("./input.txt").readText().split(",").map { it.toInt() }.toMutableList()
intcode[1] = noun
intcode[2] = verb
var position = 0
while (position != -1) {
val operation = determineOperation(position, intcode)
val result = operation.invoke(position, intcode)
position = result.first
intcode = result.second
}
return intcode[0]
}Here I am reading the contents of the file and use it to initialize the 'memory'. Then, in the loop, I determine my next operation based on the current position ('pointer'). The operation is executed and the memory and position pointer are updated.
First Star
With this setup, the first star can be solved with this command:
First Star
println(runProgram(12, 2))Second Star
The second star is a little bit more complicated. I had to iterate over all possible input values for the noun and verb. Actually this could have been done using coroutines, but again… I am little bit lazy today.
Second Star
for (noun in 0..99) {
for (verb in 0..99) {
val result = runProgram(noun, verb)
if (result == 19690720) {
println("Getting $result for noun $noun and verb $verb -> answer is ${100 * noun + verb}")
exitProcess(0)
}
}
}Day 03: kotlin
Day 03
This was the first day where I had to give up and go to bed. I was annoyed that all tests pass but my solution was wrong. After a refreshing sleep I finally found the solution to my problem. To cut a long story short: I missunderstod one of the requirements.
If a wire visits a position on the grid multiple times, use the steps value from the first time it visits that position when calculating the total value of a specific intersection.
I thought this means that I have to implement a shortest path algorithm. I was wrong (see Second Star).
First I started defining a point on the grid.
I use Kotlins typealias, because I only want a alias for Kotlins Pair data type.
I also provide a extension function to calculate the Manhattan distance of my Point.
Point definition
typealias Point = Pair<Int, Int>
fun Point.manhattanDistance(): Int = this.first.absoluteValue + this.second.absoluteValueNext I define a Line, which actually consists of a staring and an ending point and a direction.
Each command in the input file is converted into a Line.
Furthermore Line has another extension function to expand all points on the line.
Here I also make use of Kotlins destructuring declarations to extract the contents of my line and points.
Line definition
typealias Line = Triple<Point, Point, String>
fun Line.expandPoints(): List<Point> {
val points = mutableListOf<Point>()
val (startingPoint, endingPoint, direction) = this
val (startX, startY) = startingPoint
val (endX, endY) = endingPoint
when (direction) {
"R" -> {
for (x in startX + 1..endX) {
points.add(Point(x, startY))
}
}
"L" -> {
for (x in startX - 1 downTo endX) {
points.add(Point(x, startY))
}
}
"U" -> {
for (y in startY + 1..endY) {
points.add(Point(startX, y))
}
}
"D" -> {
for (y in startY - 1 downTo endY) {
points.add(Point(startX, y))
}
}
else -> throw RuntimeException("Unknown direction: $direction")
}
return points
}Now I need a function to convert the string commands into lines. Again I am using an extension function, but to be honest it is only for the sake of readability.
String command parsing
fun List<String>.toListOfPoints(): List<Point> {
val points = mutableListOf<Point>()
var currentPoint = Point(0, 0)
for (vector in this) {
val line = createLine(currentPoint, vector)
points.addAll(line.expandPoints())
currentPoint = line.second
}
return points
}
fun createLine(startingPoint: Point, vector: String): Line {
val partition = vector.partition { it.isLetter() }
val direction = partition.first
val distance = partition.second.toInt()
val endingPoint = when (direction) {
"R" -> Point(startingPoint.first + distance, startingPoint.second)
"L" -> Point(startingPoint.first - distance, startingPoint.second)
"U" -> Point(startingPoint.first, startingPoint.second + distance)
"D" -> Point(startingPoint.first, startingPoint.second - distance)
else -> throw RuntimeException("Unknown direction: $direction")
}
return Line(startingPoint, endingPoint, direction)
}Finally I need an utility function to calculate the distance of every point on the wire from the starting point.
Distance calculation for second star
fun List<Point>.asDistanceMap(): Map<Point, Int> = this.mapIndexed { index, point -> point to index + 1 }.toMap()(Yeah, another extension function… ;-))
First Star
Now everything is set up to calculate the result of the first star. The calculation is now quite easy:
-
Read wires from file
-
Convert them an ordered list of points
-
Calculate the intersection of both lists (and remove
Point(0, 0)) -
Calculate the Manhattan distance for every point in the intersection
-
Choose the minimum
val wires = File("./input.txt")
.readLines()
.map { it.split(",") }
.map { it.toListOfPoints() }
val intersections = wires[0].intersect(wires[1]) - Point(0, 0)
val lowestManhattanDistance = intersections
.map { it.manhattanDistance() }
.min()
println(lowestManhattanDistance)Second Star
At the end the second star is really easy… if you have not missunderstod the requirements.
-
Calculate the distance of every point from start on the wire
-
Filter the distances by the points in the intersection
-
Fetch the distances on both wires
-
Choose the minimum
val wire1DistanceMap = wires[0].asDistanceMap().filterKeys { intersections.contains(it) }
val wire2DistanceMap = wires[1].asDistanceMap().filterKeys { intersections.contains(it) }
val minimumDistance: Int? = wire1DistanceMap.map { it.value + (wire2DistanceMap[it.key] ?: throw RuntimeException()) }.min()
println(minimumDistance ?: -1)That’s all.
I feel good, because I solved the puzzle. However, I think I need a break now for one or two days.
Day 04: kotlin
Day 04
After a short real life break I continued with the fourth day.
First Star
My idea to solve this problem was to first create a sequence of numbers. Fortunately Kotlin makes it easy to do so by specifying a range of numbers. Afterwards the sequence of numbers is interpreted as char array and filtered.
val input = (245318..765747).asSequence()
val firstResult = input.map { it.toString().toCharArray() }
.filter { it.shouldHaveAtLeastTwoAdjacentSameDigits() }
.filter { it.shouldNeverDecreaseFromLeftToRight() }
.count()
println(firstResult)So all I have to do is write two filter functions.
Again (see day 3) I am using extension functions for readability.
I make use of the very handy windowed function of Kotlin.
It creates me a list of all adjacent digits in the char array.
fun CharArray.shouldHaveAtLeastTwoAdjacentSameDigits() = this.toList().windowed(2).any { it[0] == it[1]}
fun CharArray.shouldNeverDecreaseFromLeftToRight() = this.toList().windowed(2).all { it[0] <= it[1] }Second Star
The algorithm for the second star is essentially the same. But I had to create an improved version of the 'pair of digits' check.
fun CharArray.shouldHaveTwoLonelyAdjacentSameDigits(): Boolean {
val listOfTwoDigits = this.toList().withIndex().zipWithNext()
val listOfPairs = listOfTwoDigits.filter { it.first.value == it.second.value }
val listOfLonelyPairs = listOfPairs.filter {
val leftNeighborDifferent = if (it.first.index > 0) this[it.first.index - 1] != this[it.first.index] else true
val rightNeighborDifferent = if (it.second.index < 5) this[it.second.index + 1] != this[it.second.index] else true
leftNeighborDifferent && rightNeighborDifferent
}
return listOfLonelyPairs.isNotEmpty()
}First I use withIndex to enrich my chars with their index.
Afterwards zipWithNext does the same as windowed, except it returns a list instead of an iterarble.
Then I filter all pairs and afterwards take a look at the left and right neighbor of the pairs.
If any pair is left, the test of the password is passed.
val secondResult = input.map { it.toString().toCharArray() }
.filter { it.shouldHaveTwoLonelyAdjacentSameDigits() }
.filter { it.shouldNeverDecreaseFromLeftToRight() }
.count()
println(secondResult)Day 05: kotlin
Day 05
For this puzzle I decided to rewrite my solution from day 2 and extend it to be something like a virtual CPU. It is also the first time I am using a class in this year Advent of Code.
Setup
Before I start writing my CPU, I need a couple of helper functions and enumerations.
So I created a typealias for instructions and parameters.
The instruction also supports reading the opcode and parameter modes.
To make parsing easier I pad the instruction with leading zeros and handle it as string.
typealias Instruction = Int
fun Instruction.opCode() : Int = this.toString().padStart(5, '0').drop(3).toInt()
fun Instruction.parameterModes() : List<ParameterMode> {
val parameterModeCodes = this.toString().padStart(5, '0').reversed().drop(2).toCharArray()
return parameterModeCodes
.map { code ->
ParameterMode.values().find { mode -> mode.code == code } ?: ParameterMode.ERROR
}
}
typealias Parameter = Pair<Int, ParameterMode>Then, for extendability, I added two enumerations representing the available operations and parameter modes. Please note: The enumeration already contains operations from the second star.
enum class Operation(val code: Int, val numberOfParameters: Int) {
ADD(1, 3),
MULTIPLY(2, 3),
INPUT(3, 1),
OUTPUT(4, 1),
JUMP_IF_TRUE(5, 2),
JUMP_IF_FALSE(6, 2),
LESS_THAN(7, 3),
EQUALS(8, 3),
STOP(99, 0),
ERROR(-1, 0)
}
enum class ParameterMode(val code: Char) {
POSITION('0'),
IMMEDIATE('1'),
ERROR('?')
}The virtual CPU
Next I wrote the virtual CPU. My CPU has a memory and an instruction pointer. The memory is initialized with the program read from the input file. Running the program takes these steps in a loop:
-
Load the instruction from memory
-
Load the operation of the instruction
-
Load the parameters of the instruction
-
Process the operation with the parameters
While loading the parameters I also add the parameter modes.
To encapsulate the parameter modes, I wrote a load() method.
This method loads the parameter value depending on the mode.
The process() method simply delegates to the concrete implementations.
Each operation method loads its parameters values, processes them and updates the memory and instruction pointer.
class CPU(var memory: List<Int>) {
private var instructionPointer = 0
fun run() {
instructionPointer = 0;
while (instructionPointer != -1) {
val instruction: Instruction = memory[instructionPointer]
val operation = loadOperation(instruction.opCode())
val parameters = loadParameters(operation, instruction.parameterModes())
process(operation, parameters)
}
}
private fun loadOperation(opCode: Int) = Operation.values().find { it.code == opCode } ?: Operation.ERROR
private fun loadParameters(operation: Operation, parameterModes: List<ParameterMode>): List<Parameter> {
val parameters = mutableListOf<Parameter>()
for ((index, parameterPointer) in ((instructionPointer + 1)..(instructionPointer + operation.numberOfParameters)).withIndex()) {
parameters.add(Parameter(memory[parameterPointer], parameterModes[index]))
}
return parameters
}
private fun process(operation: Operation, parameters: List<Parameter>) {
println("$operation with $parameters")
when(operation) {
Operation.ADD -> add(parameters)
Operation.MULTIPLY -> multiply(parameters)
Operation.INPUT -> input(parameters)
Operation.OUTPUT -> output(parameters)
Operation.JUMP_IF_TRUE -> jumpIfTrue(parameters)
Operation.JUMP_IF_FALSE -> jumpIfFalse(parameters)
Operation.LESS_THAN -> lessThan(parameters)
Operation.EQUALS -> equals(parameters)
Operation.STOP -> stop()
else -> error()
}
}
private fun add(parameters: List<Parameter>) {
val first = load(parameters[0])
val second = load(parameters[1])
val outPointer = parameters[2].first
val updatedMemory = memory.toMutableList()
updatedMemory[outPointer] = first + second
memory = updatedMemory
instructionPointer += 4
}
private fun multiply(parameters: List<Parameter>) {
val first = load(parameters[0])
val second = load(parameters[1])
val outPointer = parameters[2].first
val updatedMemory = memory.toMutableList()
updatedMemory[outPointer] = first * second
memory = updatedMemory
instructionPointer += 4
}
private fun input(parameters: List<Parameter>) {
print("Input: ")
val input = readLine()?.toInt()
if (input != null) {
val updatedMemory = memory.toMutableList()
updatedMemory[parameters[0].first] = input
memory = updatedMemory
instructionPointer += 2
} else {
throw RuntimeException("Error while reading from stdin")
}
}
private fun output(parameters: List<Parameter>) {
val value = load(parameters[0])
println(value)
instructionPointer += 2
}
private fun jumpIfTrue(parameters: List<Parameter>) {
val first = load(parameters[0])
val second = load(parameters[1])
if (first != 0) {
instructionPointer = second
} else {
instructionPointer += 3
}
}
private fun jumpIfFalse(parameters: List<Parameter>) {
val first = load(parameters[0])
val second = load(parameters[1])
if (first == 0) {
instructionPointer = second
} else {
instructionPointer += 3
}
}
private fun lessThan(parameters: List<Parameter>) {
val first = load(parameters[0])
val second = load(parameters[1])
val outPointer = parameters[2].first
val updatedMemory = memory.toMutableList()
if (first < second) {
updatedMemory[outPointer] = 1
} else {
updatedMemory[outPointer] = 0
}
memory = updatedMemory
instructionPointer += 4
}
private fun equals(parameters: List<Parameter>) {
val first = load(parameters[0])
val second = load(parameters[1])
val outPointer = parameters[2].first
val updatedMemory = memory.toMutableList()
if (first == second) {
updatedMemory[outPointer] = 1
} else {
updatedMemory[outPointer] = 0
}
memory = updatedMemory
instructionPointer += 4
}
private fun stop() {
instructionPointer = -1
}
private fun error() {
throw RuntimeException("Unknown operation")
}
private fun load(parameter: Parameter) =
when (parameter.second) {
ParameterMode.POSITION -> memory[parameter.first]
ParameterMode.IMMEDIATE -> parameter.first
else -> throw RuntimeException("Unknown parameter found")
}
}To start the virtual CPU, the program has to be loaded from the input file.
Then a new CPU is constructed and run() is called.
val program = File("./input.txt").readText().split(",").map { it.toInt() }
CPU(program).run()You can solve the first star by entering 1 and the second star by entering 5. The program will also output the operation and its parameters for debugging purposes.
Day 06: kotlin
Day 06
I am not very proud of my solution. It is kind of messy, but it works.
So I started by defining a helper class which represents a node in a tree. A node has an ID, an optional parent and a list of children. The node also has two functions:
-
pathToRoot()returns all nodes from this node to the root node of the tree -
level()returns the length of the path from this node to the root node
data class Node(val id: String) {
private var parent: Node? = null
val children = mutableSetOf<Node>()
fun addChild(node: Node) {
children.add(node)
node.parent = this
}
fun pathToRoot(): List<Node> {
val path = mutableListOf<Node>()
var tmpNode: Node? = this
while(tmpNode?.parent != null) {
tmpNode = tmpNode.parent
if (tmpNode != null) {
path.add(tmpNode)
}
}
return path
}
fun level(): Int = pathToRoot().size
}Next I wrote a factory method which creates my nodes from the input. The function stores the nodes in a map for fast and easy access. Unfortunately this also means, that my function is not free of side effects.
fun createNodesFrom(orbitDefinition: Pair<String, String>) {
val firstNode = orbitMap.getOrPut(orbitDefinition.first) { Node(orbitDefinition.first) }
val secondNode = orbitMap.getOrPut(orbitDefinition.second) { Node(orbitDefinition.second) }
firstNode.addChild(secondNode)
}
val orbitMap = mutableMapOf<String, Node>()
File("./input.txt").readLines()
.map { orbit -> orbit.split(")", limit = 2) }
.map { ids -> ids[0] to ids[1] }
.forEach { createNodesFrom(it) }First Star
To solve the first star I added a function which is actually a depth-first search of the tree. The function adds the levels of the nodes to get the result.
fun totalLevels(node: Node): Int {
var totalLevels = node.level()
for (child in node.children) {
totalLevels += totalLevels(child)
}
return totalLevels
}
val comNode = orbitMap["COM"]
if (comNode != null) {
println(totalLevels(comNode))
}Second Star
Using the pathToRoot() function solving the second star is easy.
I get the YOU and the SAN node from the map and intersect their paths to root.
Kotlin preservers the ordering of the nodes in the intersection, so the first node of the result ist actually the first common node.
Then I get the index of the common node in the path to root, which is actually the number of steps to get there.
The result is the sum of the steps from YOU to the common node and SAN to the common node.
val youNode = orbitMap["YOU"]
val sanNode = orbitMap["SAN"]
if (youNode != null && sanNode != null) {
val firstCommonNode = youNode.pathToRoot().intersect(sanNode.pathToRoot()).first()
val youToCommon = youNode.pathToRoot().indexOf(firstCommonNode)
val sanToCommon = sanNode.pathToRoot().indexOf(firstCommonNode)
println(youToCommon + sanToCommon)
}Day 07: kotlin
Day 07
Another Intcode computer puzzle. I am reusing a lot of my code from day 5. The only thing I have changed is the possibility to define an input provider and an output consumer. With this change I can automate writing to and reading from the program.
typealias Instruction = Int
fun Instruction.opCode() : Int = this.toString().padStart(5, '0').drop(3).toInt()
fun Instruction.parameterModes() : List<ParameterMode> {
val parameterModeCodes = this.toString().padStart(5, '0').reversed().drop(2).toCharArray()
return parameterModeCodes
.map { code ->
ParameterMode.values().find { mode -> mode.code == code } ?: ParameterMode.ERROR
}
}
typealias Parameter = Pair<Int, ParameterMode>
enum class Operation(val code: Int, val numberOfParameters: Int) {
ADD(1, 3),
MULTIPLY(2, 3),
INPUT(3, 1),
OUTPUT(4, 1),
JUMP_IF_TRUE(5, 2),
JUMP_IF_FALSE(6, 2),
LESS_THAN(7, 3),
EQUALS(8, 3),
STOP(99, 0),
ERROR(-1, 0)
}
enum class ParameterMode(val code: Char) {
POSITION('0'),
IMMEDIATE('1'),
ERROR('?')
}
class CPU(var memory: List<Int>,
val inputProvider: () -> Int? = { readLine()?.toInt() },
val outputConsumer: (Int) -> Unit = { value -> println(value) }
) {
private var instructionPointer = 0
fun run() {
instructionPointer = 0;
while (instructionPointer != -1) {
val instruction: Instruction = memory[instructionPointer]
val operation = loadOperation(instruction.opCode())
val parameters = loadParameters(operation, instruction.parameterModes())
process(operation, parameters)
}
}
private fun loadOperation(opCode: Int) = Operation.values().find { it.code == opCode } ?: Operation.ERROR
private fun loadParameters(operation: Operation, parameterModes: List<ParameterMode>): List<Parameter> {
val parameters = mutableListOf<Parameter>()
for ((index, parameterPointer) in ((instructionPointer + 1)..(instructionPointer + operation.numberOfParameters)).withIndex()) {
parameters.add(Parameter(memory[parameterPointer], parameterModes[index]))
}
return parameters
}
private fun process(operation: Operation, parameters: List<Parameter>) {
//println("$operation with $parameters")
when(operation) {
Operation.ADD -> add(parameters)
Operation.MULTIPLY -> multiply(parameters)
Operation.INPUT -> input(parameters)
Operation.OUTPUT -> output(parameters)
Operation.JUMP_IF_TRUE -> jumpIfTrue(parameters)
Operation.JUMP_IF_FALSE -> jumpIfFalse(parameters)
Operation.LESS_THAN -> lessThan(parameters)
Operation.EQUALS -> equals(parameters)
Operation.STOP -> stop()
else -> error()
}
}
private fun add(parameters: List<Parameter>) {
val first = load(parameters[0])
val second = load(parameters[1])
val outPointer = parameters[2].first
val updatedMemory = memory.toMutableList()
updatedMemory[outPointer] = first + second
memory = updatedMemory
instructionPointer += 4
}
private fun multiply(parameters: List<Parameter>) {
val first = load(parameters[0])
val second = load(parameters[1])
val outPointer = parameters[2].first
val updatedMemory = memory.toMutableList()
updatedMemory[outPointer] = first * second
memory = updatedMemory
instructionPointer += 4
}
private fun input(parameters: List<Parameter>) {
val input = inputProvider.invoke()
if (input != null) {
val updatedMemory = memory.toMutableList()
updatedMemory[parameters[0].first] = input
memory = updatedMemory
instructionPointer += 2
} else {
throw RuntimeException("Error while reading from stdin")
}
}
private fun output(parameters: List<Parameter>) {
val value = load(parameters[0])
outputConsumer.invoke(value)
instructionPointer += 2
}
private fun jumpIfTrue(parameters: List<Parameter>) {
val first = load(parameters[0])
val second = load(parameters[1])
if (first != 0) {
instructionPointer = second
} else {
instructionPointer += 3
}
}
private fun jumpIfFalse(parameters: List<Parameter>) {
val first = load(parameters[0])
val second = load(parameters[1])
if (first == 0) {
instructionPointer = second
} else {
instructionPointer += 3
}
}
private fun lessThan(parameters: List<Parameter>) {
val first = load(parameters[0])
val second = load(parameters[1])
val outPointer = parameters[2].first
val updatedMemory = memory.toMutableList()
if (first < second) {
updatedMemory[outPointer] = 1
} else {
updatedMemory[outPointer] = 0
}
memory = updatedMemory
instructionPointer += 4
}
private fun equals(parameters: List<Parameter>) {
val first = load(parameters[0])
val second = load(parameters[1])
val outPointer = parameters[2].first
val updatedMemory = memory.toMutableList()
if (first == second) {
updatedMemory[outPointer] = 1
} else {
updatedMemory[outPointer] = 0
}
memory = updatedMemory
instructionPointer += 4
}
private fun stop() {
instructionPointer = -1
}
private fun error() {
throw RuntimeException("Unknown operation")
}
private fun load(parameter: Parameter) =
when (parameter.second) {
ParameterMode.POSITION -> memory[parameter.first]
ParameterMode.IMMEDIATE -> parameter.first
else -> throw RuntimeException("Unknown parameter found")
}
}Next I need a recursive function to create all possible permutations of the phase settings.
fun createPermutations(input: Set<Int>, combination: List<Int>): List<List<Int>> {
val result: MutableList<List<Int>> = mutableListOf()
for (digit in input) {
if (input.size == 1) {
result.add(combination + digit)
} else {
val combinations = createPermutations(input - digit, combination + digit)
result.addAll(combinations)
}
}
return result
}I like how Kotlin allows me to add and remove elements from sets and lists by using + and -.
To read the program from input, I also used the code from day 5.
val program = File("./input.txt").readText().split(",").map { it.toInt() }First Star
To solve the first star I am creating a virtual CPU for each amplifier. Here I used the new possibility to provide an input and an output function to connect the amplifiers. For each combination I am calculating a result and then returning the maximum value which is the result of the first star.
fun runProgramOnAmplifiers(program: List<Int>, phaseSettings: List<Int>): Int {
val amplifier1In = arrayOf(phaseSettings[0], 0).iterator()
var amplifier1Out: Int? = null
val amplifier1 = CPU(program.toList(), { amplifier1In.next() }, { amplifier1Out = it })
amplifier1.run()
val amplifier2In = arrayOf(phaseSettings[1], amplifier1Out).iterator()
var amplifier2Out: Int? = null
val amplifier2 = CPU(program.toList(), { amplifier2In.next() }, { amplifier2Out = it })
amplifier2.run()
val amplifier3In = arrayOf(phaseSettings[2], amplifier2Out).iterator()
var amplifier3Out: Int? = null
val amplifier3 = CPU(program.toList(), { amplifier3In.next() }, { amplifier3Out = it })
amplifier3.run()
val amplifier4In = arrayOf(phaseSettings[3], amplifier3Out).iterator()
var amplifier4Out: Int? = null
val amplifier4 = CPU(program.toList(), { amplifier4In.next() }, { amplifier4Out = it })
amplifier4.run()
val amplifier5In = arrayOf(phaseSettings[4], amplifier4Out).iterator()
var amplifier5Out: Int? = null
val amplifier5 = CPU(program.toList(), { amplifier5In.next() }, { amplifier5Out = it })
amplifier5.run()
return amplifier5Out ?: throw RuntimeException("Result is null")
}
val combinations = createPermutations(setOf(0, 1, 2, 3, 4), emptyList())
val firstStar = combinations.map { runProgramOnAmplifiers(program, it) }.max()
println(firstStar)Second Star
The second star is a little bit more complicated. I would use Kotlin Coroutines, but this would require additional dependencies. I like to implement all my solutions as Kotlin Script, so instead I am using Threads.
For the amplifiers I wrote a class containing the program an input queue and an output queue.
Both queues are blocking, so the threads wait until they get new input.
Then, in runProgramOnAmplifiersWithFeedback, I first initialize the input queues with the phase settings.
Afterwards I am creating the amplifiers by connecting the blocking queues.
I start the threads and provide the initial input to the first amplifier.
I have to wait for all threads to finish bevor I can take the element on the output queue from amplifier 5.
This is the result for the second star, which has to be maximized.
class AmplifierRunnable(
val amplifierId: String,
val program: List<Int>,
val inputQueue: BlockingQueue<Int>,
val outputQueue: BlockingQueue<Int>
) : Runnable {
override fun run() {
val amplifier = CPU(program.toList(), { inputQueue.take() }, { outputQueue.put(it) })
amplifier.run()
//println("Amplifier $amplifierId: $outputQueue")
}
}
fun runProgramOnAmplifiersWithFeedback(program: List<Int>, phaseSettings: List<Int>): Int {
val amp1In = LinkedBlockingDeque<Int>()
amp1In.put(phaseSettings[0])
val amp2In = LinkedBlockingDeque<Int>()
amp2In.put(phaseSettings[1])
val amp3In = LinkedBlockingDeque<Int>()
amp3In.put(phaseSettings[2])
val amp4In = LinkedBlockingDeque<Int>()
amp4In.put(phaseSettings[3])
val amp5In = LinkedBlockingDeque<Int>()
amp5In.put(phaseSettings[4])
val amplifier1 = Thread(AmplifierRunnable("1", program, amp1In, amp2In))
val amplifier2 = Thread(AmplifierRunnable("2", program, amp2In, amp3In))
val amplifier3 = Thread(AmplifierRunnable("3", program, amp3In, amp4In))
val amplifier4 = Thread(AmplifierRunnable("4", program, amp4In, amp5In))
val amplifier5 = Thread(AmplifierRunnable("5", program, amp5In, amp1In))
amplifier1.start()
amplifier2.start()
amplifier3.start()
amplifier4.start()
amplifier5.start()
amp1In.put(0)
amplifier1.join()
amplifier2.join()
amplifier3.join()
amplifier4.join()
amplifier5.join()
return amp1In.take()
}
val combinations2 = createPermutations(setOf(5, 6, 7, 8, 9), emptyList())
val secondStar = combinations2.map { runProgramOnAmplifiersWithFeedback(program, it) }.max()
println(secondStar)Day 08: kotlin
Day 08
This day was fun.
First Star
For the first star I read the image and then split it into layers using the very handy function chunked().
Afterwards I enhance the layers with an index, transform my layeres by counting the zeros and find the layer with the least zeros.
Then I only have to count the ones and twos in that layer.
val encodedImage = File("./input.txt").readText().toCharArray().toList();
val layers = encodedImage.chunked(25 * 6)
val layerWithLeastZeros = layers.withIndex().map { (index, layer) -> index to layer.count { it == '0' } }.minBy { it.second }
val theLayer = layers[layerWithLeastZeros!!.first]
val oneDigits = theLayer.count { it == '1' }
val twoDigits = theLayer.count { it == '2' }
println("First star: ${oneDigits * twoDigits}")Second Star
I had problems with my rendering function, but first things first.
I start by reducing my layers.
To merge them, I define a function mergeLayers.
The function calls zip() to get a pair of chars, first char from the front layer, second char from the back layer.
If the front pixel is transparent, I return the back pixel, otherwise the front pixel.
The reduce() function takes the first and the second layer, merges them and applies the result to the third layer, merges them, …
Now I have to render the resulting reduced layer.
Again I am using chunked() to get the rows of my layer.
In each row I map the pixel to * for white and a blank for black.
The result is printed to the console.
fun mergeLayers(frontLayer: List<Char>, backLayer: List<Char>) = frontLayer.zip(backLayer)
.map { (frontPixel, backPixel) -> if (frontPixel == '2') backPixel else frontPixel }
val reducedLayer = layers.reduce { front, back -> mergeLayers(front, back) }
val rows = reducedLayer.chunked(25)
for (row in rows) {
row.map { pixel -> if (pixel == '1') '*' else ' ' }.forEach { print(it)}
println()
}Day 09: kotlin
Day 09
Most of the time for this days puzzle I spend with small refactorings on my virtual CPU.
I had to add an additional parameter mode and operation to my existing enums.
enum class Operation(val code: Long, val numberOfParameters: Int) {
ADD(1, 3),
MULTIPLY(2, 3),
INPUT(3, 1),
OUTPUT(4, 1),
JUMP_IF_TRUE(5, 2),
JUMP_IF_FALSE(6, 2),
LESS_THAN(7, 3),
EQUALS(8, 3),
RELATIVE_BASE_OFFSET(9, 1),
STOP(99, 0),
ERROR(-1, 0)
}enum class ParameterMode(val code: Char) {
POSITION('0'),
IMMEDIATE('1'),
RELATIVE('2'),
ERROR('?')
}Of course I also had to enhance the parameter processing. I moved all write operations to a write function.
private fun load(parameter: Parameter) =
when (parameter.second) {
ParameterMode.POSITION -> memory[parameter.first.toInt()]
ParameterMode.IMMEDIATE -> parameter.first
ParameterMode.RELATIVE -> memory[(relativeBase + parameter.first).toInt()]
else -> throw RuntimeException("Unknown parameter found")
}
private fun write(parameter: Parameter, value: Long) {
val index = when (parameter.second)
{
ParameterMode.POSITION -> parameter.first.toInt()
ParameterMode.RELATIVE -> (relativeBase + parameter.first).toInt()
else -> throw RuntimeException("Illegal parameter mode for write operation found")
}
val updatedMemory = memory.copyOf()
updatedMemory[index] = value
memory = updatedMemory
}What was actually more complicated was to move from a list of integer values to an array of long values. I had to adopt my CPU at several positions. Thankfully Kotlin as statically typed language helped me a lot.
The updated definition of my CPU looks like this:
class CPU(
val program: List<Long>,
memorySize: Int,
val inputProvider: () -> Long? = {
print("Input: ")
readLine()?.toLong()
},
val outputConsumer: (Long) -> Unit = { value -> println(value) }
) {
private var instructionPointer = 0
private var relativeBase = 0
private var memory = Array(memorySize) { index -> if (index < program.size) program[index] else 0L }As you can see I now have a separate memory variable. It is initialized with a given memory size. During initialization the program is inserted at the start of the memory.
With these changes, I was able to successfully run my Intcode computer:
val program = File("./input.txt").readText().split(",").map { it.toLong() }
val cpu = CPU(program, 2048)
cpu.run()Complete Intcode Computer
typealias Instruction = Long
fun Instruction.opCode(): Long = this.toString().padStart(5, '0').drop(3).toLong()
fun Instruction.parameterModes(): List<ParameterMode> {
val parameterModeCodes = this.toString().padStart(5, '0').reversed().drop(2).toCharArray()
return parameterModeCodes
.map { code ->
ParameterMode.values().find { mode -> mode.code == code } ?: ParameterMode.ERROR
}
}
typealias Parameter = Pair<Long, ParameterMode>
enum class Operation(val code: Long, val numberOfParameters: Int) {
ADD(1, 3),
MULTIPLY(2, 3),
INPUT(3, 1),
OUTPUT(4, 1),
JUMP_IF_TRUE(5, 2),
JUMP_IF_FALSE(6, 2),
LESS_THAN(7, 3),
EQUALS(8, 3),
RELATIVE_BASE_OFFSET(9, 1),
STOP(99, 0),
ERROR(-1, 0)
}
enum class ParameterMode(val code: Char) {
POSITION('0'),
IMMEDIATE('1'),
RELATIVE('2'),
ERROR('?')
}
class CPU(
val program: List<Long>,
memorySize: Int,
val inputProvider: () -> Long? = {
print("Input: ")
readLine()?.toLong()
},
val outputConsumer: (Long) -> Unit = { value -> println(value) }
) {
private var instructionPointer = 0
private var relativeBase = 0
private var memory = Array(memorySize) { index -> if (index < program.size) program[index] else 0L }
fun run() {
instructionPointer = 0;
while (instructionPointer != -1) {
val instruction: Instruction = memory[instructionPointer]
val operation = loadOperation(instruction.opCode())
val parameters = loadParameters(operation, instruction.parameterModes())
process(operation, parameters)
}
}
private fun loadOperation(opCode: Long) = Operation.values().find { it.code == opCode } ?: Operation.ERROR
private fun loadParameters(operation: Operation, parameterModes: List<ParameterMode>): List<Parameter> {
val parameters = mutableListOf<Parameter>()
for ((index, parameterPointer) in ((instructionPointer + 1)..(instructionPointer + operation.numberOfParameters)).withIndex()) {
parameters.add(Parameter(memory[parameterPointer], parameterModes[index]))
}
return parameters
}
private fun process(operation: Operation, parameters: List<Parameter>) {
// activate for debugging: println("$operation with $parameters")
when (operation) {
Operation.ADD -> add(parameters)
Operation.MULTIPLY -> multiply(parameters)
Operation.INPUT -> input(parameters)
Operation.OUTPUT -> output(parameters)
Operation.JUMP_IF_TRUE -> jumpIfTrue(parameters)
Operation.JUMP_IF_FALSE -> jumpIfFalse(parameters)
Operation.LESS_THAN -> lessThan(parameters)
Operation.EQUALS -> equals(parameters)
Operation.RELATIVE_BASE_OFFSET -> relativeBaseOffset(parameters)
Operation.STOP -> stop()
else -> error()
}
}
private fun add(parameters: List<Parameter>) {
val first = load(parameters[0])
val second = load(parameters[1])
write(parameters[2], first + second)
instructionPointer += 4
}
private fun multiply(parameters: List<Parameter>) {
val first = load(parameters[0])
val second = load(parameters[1])
write(parameters[2], first * second)
instructionPointer += 4
}
private fun input(parameters: List<Parameter>) {
val input = inputProvider.invoke()
if (input != null) {
write(parameters[0], input)
instructionPointer += 2
} else {
throw RuntimeException("Error while reading from stdin")
}
}
private fun output(parameters: List<Parameter>) {
val value = load(parameters[0])
outputConsumer.invoke(value)
instructionPointer += 2
}
private fun jumpIfTrue(parameters: List<Parameter>) {
val first = load(parameters[0])
val second = load(parameters[1])
if (first != 0L) {
instructionPointer = second.toInt()
} else {
instructionPointer += 3
}
}
private fun jumpIfFalse(parameters: List<Parameter>) {
val first = load(parameters[0])
val second = load(parameters[1])
if (first == 0L) {
instructionPointer = second.toInt()
} else {
instructionPointer += 3
}
}
private fun lessThan(parameters: List<Parameter>) {
val first = load(parameters[0])
val second = load(parameters[1])
write(parameters[2], if (first < second) 1 else 0)
instructionPointer += 4
}
private fun equals(parameters: List<Parameter>) {
val first = load(parameters[0])
val second = load(parameters[1])
write(parameters[2], if (first == second) 1 else 0)
instructionPointer += 4
}
private fun relativeBaseOffset(parameters: List<Parameter>) {
val offset = load(parameters[0])
relativeBase += offset.toInt()
instructionPointer += 2
}
private fun stop() {
instructionPointer = -1
}
private fun error() {
throw RuntimeException("Unknown operation")
}
private fun load(parameter: Parameter) =
when (parameter.second) {
ParameterMode.POSITION -> memory[parameter.first.toInt()]
ParameterMode.IMMEDIATE -> parameter.first
ParameterMode.RELATIVE -> memory[(relativeBase + parameter.first).toInt()]
else -> throw RuntimeException("Unknown parameter found")
}
private fun write(parameter: Parameter, value: Long) {
val index = when (parameter.second)
{
ParameterMode.POSITION -> parameter.first.toInt()
ParameterMode.RELATIVE -> (relativeBase + parameter.first).toInt()
else -> throw RuntimeException("Illegal parameter mode for write operation found")
}
val updatedMemory = memory.copyOf()
updatedMemory[index] = value
memory = updatedMemory
}
}Day 10: kotlin
Day 10
Only a short documentation this time. The puzzle was really hard to solve for me and it is already late.
First of all I wrote some helper methods to convert the given map into a set of asteroids.
typealias Asteroid = Pair<Int, Int>
fun convertToAsteroidSet(map: List<CharArray>): Set<Asteroid> {
val asteroidSet = mutableSetOf<Asteroid>()
for (row in map.withIndex()) {
for (column in row.value.withIndex()) {
if (column.value == '#') {
asteroidSet.add(Asteroid(column.index, row.index))
}
}
}
return asteroidSet
}And to handle the line of sight.
typealias LineOfSight = Pair<Asteroid, Asteroid>
fun LineOfSight.asteroids(asteroidSet: Set<Asteroid>): List<Asteroid> {
val resultList = mutableListOf(first)
val xDiff = second.first - first.first
val yDiff = second.second - first.second
val otherAsteroids = (asteroidSet - first) - second
if (xDiff == 0) {
val yRange = if (yDiff > 0) (first.second..second.second) else (second.second..first.second)
for (asteroid in otherAsteroids) {
if (asteroid.first == first.first && yRange.contains(asteroid.second)) {
resultList.add(asteroid)
}
}
} else {
val gradient = yDiff.toDouble() / xDiff.toDouble()
val xRange = if (xDiff > 0) (first.first..second.first) else (second.first..first.first)
for (asteroid in otherAsteroids) {
val expectedY = ((asteroid.first - first.first) * gradient) + first.second
if (xRange.contains(asteroid.first) && expectedY == asteroid.second.toDouble()) {
resultList.add(asteroid)
}
}
}
resultList.add(second)
return resultList
}
fun LineOfSight.obstructed(asteroidSet: Set<Asteroid>) = this.asteroids(asteroidSet).size > 2First Star
With this set up, solving the first star war as simple as iterating over all asteroids, calculating the line of sight and check if it is obstructed.
fun firstStar(asteroids: Set<Asteroid>): Asteroid {
val asteroidLosCount = mutableListOf<Pair<Asteroid, Int>>()
for (asteroid in asteroids) {
val otherAsteroids = asteroids - asteroid
var losCount = 0
for (otherAsteroid in otherAsteroids) {
val los = LineOfSight(asteroid, otherAsteroid)
if (!los.obstructed(asteroids)) {
losCount++
}
}
asteroidLosCount.add(Pair(asteroid, losCount))
}
val bestMatch: Pair<Asteroid, Int>? = asteroidLosCount.maxBy { pair -> pair.second }
println("${bestMatch?.first} with ${bestMatch?.second}")
return bestMatch!!.first
}
val asteroids = convertToAsteroidSet(File("./input.txt").readLines().map { it.toCharArray() })
val bestMatch = firstStar(asteroids)Second Star
The second star nearly crushed me, until I checked Michael Simons solution (thanks!) This pointed me to the atan2 function, which is required to sort the asteroids clockwise.
fun secondStar(bestMatch: Asteroid, otherAsteroids: Set<Asteroid>) {
var clockwiseSortedAsteroids = otherAsteroids.toList().sortedBy {
val xDiff = it.first - bestMatch.first
val yDiff = it.second - bestMatch.second
atan2(xDiff.toDouble(), yDiff.toDouble())
}.reversed()
var survivingAsteroids = clockwiseSortedAsteroids.toList()
var destroyCounter = 0
while (clockwiseSortedAsteroids.size > 0) {
for (asteroid in clockwiseSortedAsteroids) {
if (!LineOfSight(bestMatch, asteroid).obstructed(clockwiseSortedAsteroids.toSet())) {
destroyCounter++
survivingAsteroids = survivingAsteroids - asteroid
println("PENG! ($destroyCounter) $asteroid")
}
}
clockwiseSortedAsteroids = survivingAsteroids.toList()
}
}
secondStar(bestMatch, asteroids - bestMatch)Day 11: kotlin
Day 11
Intcode computer is back! 😎
I started by copy-pasting (as every good software engineer does) my Intcode computer from day 9. Find the complete source code of the Intcode computer at the end.
Next I defined an abstraction of the panels to be painted.
My panels consist of coordinates (using Kotlins Pair data type) and a color.
data class Panel(val coordinates: Pair<Int, Int>, var color: Long)Next the painting robot.
I tried to use a Kotlin object, but it seems that Kotlin scripts cannot handle them.
So it is basically a class containing my Intcode computer CPU, its current coordinates, all visited panels, the command state and the direction.
The command state is to tell my robot how to interpret the next output of the CPU.
The readCamera() and next(Long) functions are used as input and output functions for the CPU.
enum class CommandState() {
PAINT,
ROTATE
}
enum class Direction() {
UP,
RIGHT,
DOWN,
LEFT
}
class PaintingRobot(initialColor: Long) {
private var cpu: CPU? = null
private var coordinates = Pair(0, 0)
var visitedPanelSet: Set<Panel> = setOf(Panel(Pair(0, 0), initialColor))
private var commandState = CommandState.PAINT
private var direction = Direction.UP
fun loadProgram(pathname: String) {
val program = File(pathname).readText().split(",").map { it.toLong() }
cpu = CPU(program, 1024, this::readCamera, this::next)
}
fun startRobot() = cpu?.run() ?: throw RuntimeException("Load program first")
private fun readCamera() = findOrCreatePanelAt(coordinates).color
private fun next(command: Long) {
when (commandState) {
CommandState.PAINT -> {
findOrCreatePanelAt(coordinates).color = command
commandState = CommandState.ROTATE
}
CommandState.ROTATE -> {
rotate(command)
move()
commandState = CommandState.PAINT
}
}
}
private fun findOrCreatePanelAt(theCoordinates: Pair<Int, Int>): Panel {
val panel = this.visitedPanelSet.find { it.coordinates == theCoordinates } ?: Panel(theCoordinates, 0)
this.visitedPanelSet = this.visitedPanelSet + panel
return panel
}
private fun rotate(command: Long) {
direction = when (command) {
0L -> when (direction) {
Direction.UP -> Direction.LEFT
Direction.LEFT -> Direction.DOWN
Direction.DOWN -> Direction.RIGHT
Direction.RIGHT -> Direction.UP
}
1L -> when (direction) {
Direction.UP -> Direction.RIGHT
Direction.RIGHT -> Direction.DOWN
Direction.DOWN -> Direction.LEFT
Direction.LEFT -> Direction.UP
}
else -> throw RuntimeException("Unknown rotation command: $command")
}
}
private fun move() {
coordinates = when (direction) {
Direction.UP -> Pair(coordinates.first, coordinates.second + 1)
Direction.RIGHT -> Pair(coordinates.first + 1, coordinates.second)
Direction.DOWN -> Pair(coordinates.first, coordinates.second - 1)
Direction.LEFT -> Pair(coordinates.first - 1, coordinates.second)
}
}
}With everything set up, I can now start to solve the puzzles.
First Star
The first star is as simple as:
-
Load the program
-
Start the robot
-
Check the size of the set containing all visited panels
val firstRobot = PaintingRobot(0)
firstRobot.loadProgram("./input.txt")
firstRobot.startRobot()
println("First star: ${firstRobot.visitedPanelSet.size}")Second Star
For the second star, the robot is initialized with white color (1).
I extract the min and max values of x and y coordinates.
Then I iterate over the x and y values and print the color to the console.
Please note two things:
-
I had to iterate from max y down to min y, because otherwise it prints mirror-inverted letters
-
I am using
!!to disable Kotlins null-check. Don`t do this at home.
val secondRobot = PaintingRobot(1)
secondRobot.loadProgram("./input.txt")
secondRobot.startRobot()
val visitedCoordinates = secondRobot.visitedPanelSet.map { it.coordinates }
val visitedX = visitedCoordinates.map { it.first }
val visitedY = visitedCoordinates.map { it.second }
for (y in visitedY.max()!! downTo visitedY.min()!!) {
for (x in visitedX.min()!!..visitedX.max()!!) {
val color = secondRobot.visitedPanelSet.find { it.coordinates == Pair(x, y) }?.color ?: 0L
if (color == 0L) {
print(" ")
} else {
print("#")
}
}
println()
}Intcode computer
typealias Instruction = Long
fun Instruction.opCode(): Long = this.toString().padStart(5, '0').drop(3).toLong()
fun Instruction.parameterModes(): List<ParameterMode> {
val parameterModeCodes = this.toString().padStart(5, '0').reversed().drop(2).toCharArray()
return parameterModeCodes
.map { code ->
ParameterMode.values().find { mode -> mode.code == code } ?: ParameterMode.ERROR
}
}
typealias Parameter = Pair<Long, ParameterMode>
enum class Operation(val code: Long, val numberOfParameters: Int) {
ADD(1, 3),
MULTIPLY(2, 3),
INPUT(3, 1),
OUTPUT(4, 1),
JUMP_IF_TRUE(5, 2),
JUMP_IF_FALSE(6, 2),
LESS_THAN(7, 3),
EQUALS(8, 3),
RELATIVE_BASE_OFFSET(9, 1),
STOP(99, 0),
ERROR(-1, 0)
}
enum class ParameterMode(val code: Char) {
POSITION('0'),
IMMEDIATE('1'),
RELATIVE('2'),
ERROR('?')
}
class CPU(
val program: List<Long>,
memorySize: Int,
val inputProvider: () -> Long? = {
print("Input: ")
readLine()?.toLong()
},
val outputConsumer: (Long) -> Unit = { value -> println(value) }
) {
private var instructionPointer = 0
private var relativeBase = 0
private var memory = Array(memorySize) { index -> if (index < program.size) program[index] else 0L }
fun run() {
instructionPointer = 0;
while (instructionPointer != -1) {
val instruction: Instruction = memory[instructionPointer]
val operation = loadOperation(instruction.opCode())
val parameters = loadParameters(operation, instruction.parameterModes())
process(operation, parameters)
}
}
private fun loadOperation(opCode: Long) = Operation.values().find { it.code == opCode } ?: Operation.ERROR
private fun loadParameters(operation: Operation, parameterModes: List<ParameterMode>): List<Parameter> {
val parameters = mutableListOf<Parameter>()
for ((index, parameterPointer) in ((instructionPointer + 1)..(instructionPointer + operation.numberOfParameters)).withIndex()) {
parameters.add(Parameter(memory[parameterPointer], parameterModes[index]))
}
return parameters
}
private fun process(operation: Operation, parameters: List<Parameter>) {
// activate for debugging: println("$operation with $parameters")
when (operation) {
Operation.ADD -> add(parameters)
Operation.MULTIPLY -> multiply(parameters)
Operation.INPUT -> input(parameters)
Operation.OUTPUT -> output(parameters)
Operation.JUMP_IF_TRUE -> jumpIfTrue(parameters)
Operation.JUMP_IF_FALSE -> jumpIfFalse(parameters)
Operation.LESS_THAN -> lessThan(parameters)
Operation.EQUALS -> equals(parameters)
Operation.RELATIVE_BASE_OFFSET -> relativeBaseOffset(parameters)
Operation.STOP -> stop()
else -> error()
}
}
private fun add(parameters: List<Parameter>) {
val first = load(parameters[0])
val second = load(parameters[1])
write(parameters[2], first + second)
instructionPointer += 4
}
private fun multiply(parameters: List<Parameter>) {
val first = load(parameters[0])
val second = load(parameters[1])
write(parameters[2], first * second)
instructionPointer += 4
}
private fun input(parameters: List<Parameter>) {
val input = inputProvider.invoke()
if (input != null) {
write(parameters[0], input)
instructionPointer += 2
} else {
throw RuntimeException("Error while reading from stdin")
}
}
private fun output(parameters: List<Parameter>) {
val value = load(parameters[0])
outputConsumer.invoke(value)
instructionPointer += 2
}
private fun jumpIfTrue(parameters: List<Parameter>) {
val first = load(parameters[0])
val second = load(parameters[1])
if (first != 0L) {
instructionPointer = second.toInt()
} else {
instructionPointer += 3
}
}
private fun jumpIfFalse(parameters: List<Parameter>) {
val first = load(parameters[0])
val second = load(parameters[1])
if (first == 0L) {
instructionPointer = second.toInt()
} else {
instructionPointer += 3
}
}
private fun lessThan(parameters: List<Parameter>) {
val first = load(parameters[0])
val second = load(parameters[1])
write(parameters[2], if (first < second) 1 else 0)
instructionPointer += 4
}
private fun equals(parameters: List<Parameter>) {
val first = load(parameters[0])
val second = load(parameters[1])
write(parameters[2], if (first == second) 1 else 0)
instructionPointer += 4
}
private fun relativeBaseOffset(parameters: List<Parameter>) {
val offset = load(parameters[0])
relativeBase += offset.toInt()
instructionPointer += 2
}
private fun stop() {
instructionPointer = -1
}
private fun error() {
throw RuntimeException("Unknown operation")
}
private fun load(parameter: Parameter) =
when (parameter.second) {
ParameterMode.POSITION -> memory[parameter.first.toInt()]
ParameterMode.IMMEDIATE -> parameter.first
ParameterMode.RELATIVE -> memory[(relativeBase + parameter.first).toInt()]
else -> throw RuntimeException("Unknown parameter found")
}
private fun write(parameter: Parameter, value: Long) {
val index = when (parameter.second) {
ParameterMode.POSITION -> parameter.first.toInt()
ParameterMode.RELATIVE -> (relativeBase + parameter.first).toInt()
else -> throw RuntimeException("Illegal parameter mode for write operation found")
}
val updatedMemory = memory.copyOf()
updatedMemory[index] = value
memory = updatedMemory
}
}Day 12: kotlin
Day 12
Well, I think I like the Intcode puzzles more…
First I start by configuring some helper functions.
Their purpose is to implement some basic vector operations by extending Kotlins Triple object.
operator fun Triple<Int, Int, Int>.plus(other: Triple<Int, Int, Int>) =
Triple(this.first + other.first, this.second + other.second, this.third + other.third)
operator fun Triple<Int, Int, Int>.times(scalar: Int) =
Triple(this.first * scalar, this.second * scalar, this.third * scalar)
fun Triple<Int, Int, Int>.energy() = abs(this.first) + abs(this.second) + abs(this.third)Then I define a Moon class.
It handles all the algorithms involved in calculating the position and velocity of the moons.
class Moon(val name: String, var position: Triple<Int, Int, Int>, var velocity: Triple<Int, Int, Int> = Triple(0, 0, 0)) {
fun applyGravity(otherMoon: Moon) {
val (thisX, thisY, thisZ) = this.position
val (otherX, otherY, otherZ) = otherMoon.position
val velocityXUpdate = velocityUpdateValue(thisX, otherX)
val velocityYUpdate = velocityUpdateValue(thisY, otherY)
val velocityZUpdate = velocityUpdateValue(thisZ, otherZ)
val velocityUpdate = Triple(velocityXUpdate, velocityYUpdate, velocityZUpdate)
this.velocity = this.velocity + velocityUpdate
otherMoon.velocity = otherMoon.velocity + (velocityUpdate * -1)
}
private fun velocityUpdateValue(value1: Int, value2: Int): Int {
if (value1 < value2) return 1
if (value1 == value2) return 0
if (value1 > value2) return -1
throw RuntimeException("Should not happen")
}
fun applyVelocity() {
this.position = this.position + this.velocity
}
fun totalEnergy() = potentialEnergy() * kineticEnergy()
private fun potentialEnergy() = this.position.energy()
private fun kineticEnergy() = this.velocity.energy()
override fun toString() = "<$name, $position, $velocity>"
}I also implement a factory function to create the pairs of moons.
fun List<Moon>.toPairOfMoons(): List<Pair<Moon, Moon>> {
val pairs = mutableListOf<Pair<Moon, Moon>>()
if (this.size > 1) {
val moon = this[0]
val otherMoons = this - moon
for (otherMoon in otherMoons) {
pairs.add(Pair(moon, otherMoon))
}
pairs.addAll(otherMoons.toPairOfMoons())
}
return pairs
}And, of course, I need a function to parse the input using regular expressions.
fun String.toTriple() : Triple<Int, Int, Int> {
val regex = "<x=(-?\\d+), y=(-?\\d+), z=(-?\\d+)>".toRegex()
val matchResult = regex.matchEntire(this)
if (matchResult != null) {
return Triple(matchResult.groupValues[1].toInt(), matchResult.groupValues[2].toInt(), matchResult.groupValues[3].toInt())
} else {
throw RuntimeException("Illegal input: $this")
}
}First Star
The first star is as simple as:
-
Load the program
-
Start the robot
-
Check the size of the set containing all visited panels
fun firstStar(initialPositions: List<Triple<Int, Int, Int>>) {
val moons = listOf(
Moon("Io", initialPositions[0]),
Moon("Europa", initialPositions[1]),
Moon("Ganymede", initialPositions[2]),
Moon("Callisto", initialPositions[3])
)
val pairsOfMoons = moons.toPairOfMoons()
for (step in 1..1000) {
for (pairOfMoons in pairsOfMoons) {
pairOfMoons.first.applyGravity(pairOfMoons.second)
}
for (moon in moons) {
moon.applyVelocity()
}
}
val totalSystemEnergy = moons.map { it.totalEnergy() }.sum()
println("First star: $totalSystemEnergy")
}
val initialPositions = File("./input.txt").readLines().map { it.toTriple() }
firstStar(initialPositions.toList())Second Star
For the second star, the robot is initialized with white color (1).
I extract the min and max values of x and y coordinates.
Then I iterate over the x and y values and print the color to the console.
Please note two things:
-
I had to iterate from max y down to min y, because otherwise it prints mirror-inverted letters
-
I am using
!!to disable Kotlins null-check. Don`t do this at home.
class UniverseSnapshot(val moons: List<Moon>) {
fun splitByAxis(): Map<String, String> {
val axisMap = mutableMapOf<String, String>()
axisMap["x"] = moons.map { "(${it.position.first},${it.velocity.first})" }.joinToString(";")
axisMap["y"] = moons.map { "(${it.position.second},${it.velocity.second})" }.joinToString(";")
axisMap["z"] = moons.map { "(${it.position.third},${it.velocity.third})" }.joinToString(";")
return axisMap
}
}
fun secondStar(initialPositions: List<Triple<Int, Int, Int>>) {
val moons = listOf(
Moon("Io", initialPositions[0]),
Moon("Europa", initialPositions[1]),
Moon("Ganymede", initialPositions[2]),
Moon("Callisto", initialPositions[3])
)
val pairsOfMoons = moons.toPairOfMoons()
val initialAxis = UniverseSnapshot(moons).splitByAxis()
val iterationsToComplete = mutableMapOf(
"x" to -1,
"y" to -1,
"z" to -1
)
var count = 0
do {
count++
for (pairOfMoons in pairsOfMoons) {
pairOfMoons.first.applyGravity(pairOfMoons.second)
}
for (moon in moons) {
moon.applyVelocity()
}
val axisMap = UniverseSnapshot(moons).splitByAxis()
axisMap.forEach {(key, value) ->
val countForAxis = iterationsToComplete[key] ?: -1
if (countForAxis < 0) {
if (value == initialAxis[key]) {
iterationsToComplete[key] = count
}
}
}
} while(iterationsToComplete.values.any { it < 0 })
val iterations = iterationsToComplete.values.toList().map { it.toBigInteger() }.reduce { first, second -> leastCommonMultiple(first, second) }
println("Second star: $iterations")
}
fun leastCommonMultiple(first: BigInteger, second: BigInteger): BigInteger {
val multiplier = if (first > second) first else second
var lcm = multiplier
var counter = 1
while (!(lcm % first == 0.toBigInteger() && lcm % second == 0.toBigInteger())) {
lcm = multiplier * counter.toBigInteger()
counter++
}
return lcm
}
secondStar(initialPositions.toList())Day 13: kotlin
Day 13
Yesterdays puzzle took me several hours to solve. So I was a little bit lazy today and only implemented the absolute necessary things. I saw that some people implemented a graphical output for the game. That is pretty cool. Maybe next time.
So I started by implementing the arcade cabinet.
It has a readNext(input) method to read the output from my Intcode computer and a simple draw method which only adds the tile to my virtual screen.
The draw(input) method also handles updating of the score, paddle and ball (see Second Star)
The jostick() method is the input for my Intcode computer (again, see Second Star).
| This implementation already contains code from the second star. |
enum class InputState {
READ_X,
READ_Y,
READ_TILE_ID
}
class ArcadeCabinet {
val screen: MutableSet<Triple<Long, Long, Long>> = mutableSetOf()
private var inputState = InputState.READ_X
private var currentInput = Triple(-1L, -1L, -1L)
private var paddleX = -1L
private var ballX = -1L
var score = 0L
private set
fun readNext(input: Long) {
when (inputState) {
InputState.READ_X -> {
currentInput = Triple(input, -1L, -1L)
inputState = InputState.READ_Y
}
InputState.READ_Y -> {
currentInput = currentInput.copy(second = input)
inputState = InputState.READ_TILE_ID
}
InputState.READ_TILE_ID -> {
currentInput = currentInput.copy(third = input)
inputState = InputState.READ_X
draw(currentInput)
currentInput = Triple(-1L, -1L, -1L)
}
}
}
private fun draw(input: Triple<Long, Long, Long>) {
if (input.first == -1L && input.second == 0L) {
score = input.third
} else {
val previousTile = screen.find { it.first == input.first && it.second == input.second }
if (previousTile != null) {
screen.remove(previousTile)
}
screen.add(input)
if (input.third == 3L) {
paddleX = input.first
}
if (input.third == 4L) {
ballX = input.first
}
}
}
fun joystick() =
when {
paddleX < ballX -> 1L
paddleX > ballX -> -1L
else -> 0L
}
}First Star
The first star is solved by providing the program to the CPU.
The input provider is not used, so I throw a RuntimeException.
I tried to skip this parameter, but it seems that Kotlin script does not support that (a ClassDefNotFound exception was thrown).
The result is the number of block tiles after the program has finished.
val program = File("./input.txt").readText().split(",").map { it.toLong() }
fun firstStar(program: List<Long>) {
val arcadeCabinet = ArcadeCabinet()
CPU(program.toList(), 10000, { throw RuntimeException("Should not happen") }, arcadeCabinet::readNext).run()
println("First star: ${arcadeCabinet.screen.filter { it.third == 2L }.count()}")
}
firstStar(program)Second Star
For the second star I added the joystick() method to provide input for the Intcode computer.
The idea is, that I always synchronize the x position of the paddle with the x position of the ball.
Hence the paddle will reflect the ball.
fun secondStar(program: List<Long>) {
val arcadeCabinet = ArcadeCabinet()
CPU(program.toList(), 10000, arcadeCabinet::joystick, arcadeCabinet::readNext).run()
println("Second star: ${arcadeCabinet.score}")
}
val hackedProgram = program.toMutableList()
hackedProgram[0] = 2
secondStar(hackedProgram)Intcode computer
typealias Instruction = Long
fun Instruction.opCode(): Long = this.toString().padStart(5, '0').drop(3).toLong()
fun Instruction.parameterModes(): List<ParameterMode> {
val parameterModeCodes = this.toString().padStart(5, '0').reversed().drop(2).toCharArray()
return parameterModeCodes
.map { code ->
ParameterMode.values().find { mode -> mode.code == code } ?: ParameterMode.ERROR
}
}
typealias Parameter = Pair<Long, ParameterMode>
enum class Operation(val code: Long, val numberOfParameters: Int) {
ADD(1, 3),
MULTIPLY(2, 3),
INPUT(3, 1),
OUTPUT(4, 1),
JUMP_IF_TRUE(5, 2),
JUMP_IF_FALSE(6, 2),
LESS_THAN(7, 3),
EQUALS(8, 3),
RELATIVE_BASE_OFFSET(9, 1),
STOP(99, 0),
ERROR(-1, 0)
}
enum class ParameterMode(val code: Char) {
POSITION('0'),
IMMEDIATE('1'),
RELATIVE('2'),
ERROR('?')
}
class CPU(
val program: List<Long>,
memorySize: Int,
val inputProvider: () -> Long? = {
print("Input: ")
readLine()?.toLong()
},
val outputConsumer: (Long) -> Unit = { value -> println(value) }
) {
private var instructionPointer = 0
private var relativeBase = 0
private var memory = Array(memorySize) { index -> if (index < program.size) program[index] else 0L }
fun run() {
instructionPointer = 0;
while (instructionPointer != -1) {
val instruction: Instruction = memory[instructionPointer]
val operation = loadOperation(instruction.opCode())
val parameters = loadParameters(operation, instruction.parameterModes())
process(operation, parameters)
}
}
private fun loadOperation(opCode: Long) = Operation.values().find { it.code == opCode } ?: Operation.ERROR
private fun loadParameters(operation: Operation, parameterModes: List<ParameterMode>): List<Parameter> {
val parameters = mutableListOf<Parameter>()
for ((index, parameterPointer) in ((instructionPointer + 1)..(instructionPointer + operation.numberOfParameters)).withIndex()) {
parameters.add(Parameter(memory[parameterPointer], parameterModes[index]))
}
return parameters
}
private fun process(operation: Operation, parameters: List<Parameter>) {
// activate for debugging: println("$operation with $parameters")
when (operation) {
Operation.ADD -> add(parameters)
Operation.MULTIPLY -> multiply(parameters)
Operation.INPUT -> input(parameters)
Operation.OUTPUT -> output(parameters)
Operation.JUMP_IF_TRUE -> jumpIfTrue(parameters)
Operation.JUMP_IF_FALSE -> jumpIfFalse(parameters)
Operation.LESS_THAN -> lessThan(parameters)
Operation.EQUALS -> equals(parameters)
Operation.RELATIVE_BASE_OFFSET -> relativeBaseOffset(parameters)
Operation.STOP -> stop()
else -> error()
}
}
private fun add(parameters: List<Parameter>) {
val first = load(parameters[0])
val second = load(parameters[1])
write(parameters[2], first + second)
instructionPointer += 4
}
private fun multiply(parameters: List<Parameter>) {
val first = load(parameters[0])
val second = load(parameters[1])
write(parameters[2], first * second)
instructionPointer += 4
}
private fun input(parameters: List<Parameter>) {
val input = inputProvider.invoke()
if (input != null) {
write(parameters[0], input)
instructionPointer += 2
} else {
throw RuntimeException("Error while reading from stdin")
}
}
private fun output(parameters: List<Parameter>) {
val value = load(parameters[0])
outputConsumer.invoke(value)
instructionPointer += 2
}
private fun jumpIfTrue(parameters: List<Parameter>) {
val first = load(parameters[0])
val second = load(parameters[1])
if (first != 0L) {
instructionPointer = second.toInt()
} else {
instructionPointer += 3
}
}
private fun jumpIfFalse(parameters: List<Parameter>) {
val first = load(parameters[0])
val second = load(parameters[1])
if (first == 0L) {
instructionPointer = second.toInt()
} else {
instructionPointer += 3
}
}
private fun lessThan(parameters: List<Parameter>) {
val first = load(parameters[0])
val second = load(parameters[1])
write(parameters[2], if (first < second) 1 else 0)
instructionPointer += 4
}
private fun equals(parameters: List<Parameter>) {
val first = load(parameters[0])
val second = load(parameters[1])
write(parameters[2], if (first == second) 1 else 0)
instructionPointer += 4
}
private fun relativeBaseOffset(parameters: List<Parameter>) {
val offset = load(parameters[0])
relativeBase += offset.toInt()
instructionPointer += 2
}
private fun stop() {
instructionPointer = -1
}
private fun error() {
throw RuntimeException("Unknown operation")
}
private fun load(parameter: Parameter) =
when (parameter.second) {
ParameterMode.POSITION -> memory[parameter.first.toInt()]
ParameterMode.IMMEDIATE -> parameter.first
ParameterMode.RELATIVE -> memory[(relativeBase + parameter.first).toInt()]
else -> throw RuntimeException("Unknown parameter found")
}
private fun write(parameter: Parameter, value: Long) {
val index = when (parameter.second) {
ParameterMode.POSITION -> parameter.first.toInt()
ParameterMode.RELATIVE -> (relativeBase + parameter.first).toInt()
else -> throw RuntimeException("Illegal parameter mode for write operation found")
}
val updatedMemory = memory.copyOf()
updatedMemory[index] = value
memory = updatedMemory
}
}