corneil
Corneil du Plessis
GitHub: corneil
Twitter: corneil
Blog : https://www.baeldung.com/author/corneil-duplessis/
Table of Contents
- corneil
- About me
- Day 00: kotlin
- Day 01: kotlin
- Day 02: kotlin
- Day 03: kotlin
- Day 04: kotlin
- Day 05: kotlin
- Day 06: kotlin
- Day 07: kotlin
- Day 08: kotlin
- Day 09: kotlin
- Day 10: kotlin
- Day 11: kotlin
- Day 12: kotlin
- Day 13: kotlin
- Day 14: kotlin
- Day 15: kotlin
- Day 16: kotlin
- Day 17: kotlin
- Day 18: kotlin
- Day 19: kotlin
- Day 20: kotlin
- Day 21: kotlin
- Day 22: kotlin
- Day 23: kotlin
- Day 24: kotlin
- Day 25: kotlin
corneil
About me
Software Architect with #SkinInTheGame at JumpCO
Passionate about developer experience, and an organizer at JoziJUG
I’m also a regular speaker at user groups and conferences in South Africa. I haven’t been lucky enough to land an invite to an
international conference.
I was lucky enough to attend JavaOne in 2005. Sharing the Mosconi centre hall with 15000 people was incredible. It was the 10th birthday of Java and John Gage had the original team on stage.
I work mostly in JVM languages like Java, Groovy, Kotlin and some Scala. My current favourite is Kotlin. My first Java application when into production in early 1999 soon after the release of 1.2. Before Java I did most of my work in C++ for Windows, OS/2 and embedded systems. We were one of the first teams to embed C++ on the 80186.
Before C++ came C, Clipper, Pascal, Fortran and COBOL.
I’m a relative newbie to modern functional programming terminology. However as I learn I realize we did a lot of what would be classified as functional programming that in C and C++.
Day 00: kotlin
Hello World
Hello World!
Kotlin has extension functions that can be used to extend existing classes.
Like in this case File.readText():String.
This function is not available in java.io.File.
The Kotlin compiler will generate the proper call to the function make the relevant object available as thise.
Think of like a named Lambda.
import java.io.File
val input = File("input.txt").readText()
println("Greatings $input")A trick for creating a Gradle project from multiple subprojects in different folders
settings.gradle
def days = ['day00', 'day01', 'day02', 'day03', 'day04', 'day05', 'day06', 'day07']
days.each { day ->
include(":solution-$day")
project(":solution-$day").projectDir = file("../$day/kotlin/corneil")
}Day 01: kotlin
The Tyranny of the Rocket Equation
Part 1 - Calculation of fuel for modules.
The calculation of fuel for a specific module.
fun calculateFuel(mass: Long) = (mass / 3L) - 2LReading file input file.
val massValues = mutableListOf<Long>()
BufferedReader(FileReader(File("input.txt"))).use { reader ->
reader.readLines().forEach { line ->
val mass = line.trim()
if (mass.isNotEmpty()) {
massValues.add(mass.toLong())
}
}
}Calculating the fuel required for the modules.
val moduleFuel = massValues.map { calculateFuel(it) }.sum()
println("Module Fuel=${moduleFuel}")Part2 - Calculation of fuel for fuel and modules.
Calculating the fuel required for the fuel is a recursive function.
fun calculateFuelForMass(mass: Long): Long {
val fuel = calculateFuel(mass)
if (fuel <= 0) {
return 0
}
return fuel + calculateFuelForMass(fuel)
}Solution source
package com.github.corneil.aoc2019.day1
import java.io.BufferedReader
import java.io.File
import java.io.FileReader
// tag::calc1[]
fun calculateFuel(mass: Long) = (mass / 3L) - 2L
// end::calc1[]
// tag::calc3[]
fun calculateFuelForMass(mass: Long): Long {
val fuel = calculateFuel(mass)
if (fuel <= 0) {
return 0
}
return fuel + calculateFuelForMass(fuel)
}
//end::calc3[]
fun main() {
// tag::read[]
val massValues = mutableListOf<Long>()
BufferedReader(FileReader(File("input.txt"))).use { reader ->
reader.readLines().forEach { line ->
val mass = line.trim()
if (mass.isNotEmpty()) {
massValues.add(mass.toLong())
}
}
}
// end::read[]
assert(calculateFuel(100756L) == 33583L)
// tag::calc2[]
val moduleFuel = massValues.map { calculateFuel(it) }.sum()
println("Module Fuel=${moduleFuel}")
// end::calc2[]
assert(calculateFuelForMass(1969L) == 966L)
assert(calculateFuelForMass(100756L) == 50346L)
// tag::calc4[]
val totalFuel = massValues.map { calculateFuelForMass(it) }.sum()
println("Total Fuel=${totalFuel}")
// end::calc4[]
}Day 02: kotlin
1202 Program Alarm
It will be simple to add more operation with the support for an operation lambda.
I find this style of breaking down into functions still useful it worked well 35 years ago in Pascal.
I can see that I might be refactoring elements of the IntCode program into classes as this thing moves forward.
Solution source
package com.github.corneil.aoc2019.day2
import java.io.File
fun readProgram(input: String) = input.split(",").map { it.toInt() }
fun readProgram(input: File) = readProgram(input.readText().trim())
fun deref(input: List<Int>, address: Int): Int = input[input[address]]
fun assign(input: MutableList<Int>, address: Int, value: Int) {
input[input[address]] = value
}
fun applyOperation(input: MutableList<Int>, pc: Int, operation: (Int, Int) -> Int): Int {
val result = operation(deref(input, pc + 1), deref(input, pc + 2))
assign(input, pc + 3, result)
return pc + 4
}
fun readAndExecute(pc: Int, input: MutableList<Int>): Int {
return when (val opcode = input[pc]) {
1 -> applyOperation(input, pc) { a, b -> a + b }
2 -> applyOperation(input, pc) { a, b -> a * b }
99 -> input.size
else -> error("Invalid opcode $opcode")
}
}
fun executeProgram(input: MutableList<Int>): List<Int> {
var pc = 0
while (pc < input.size) {
pc = readAndExecute(pc, input)
}
return input.toList()
}
// We make a copy of the original for testing an iteration.
fun executeIteration(program: List<Int>, noun: Int, verb: Int): List<Int> {
val copyX = program.toMutableList()
copyX[1] = noun
copyX[2] = verb
return executeProgram(copyX)
}
fun main(args: Array<String>) {
val fileName = if (args.size > 1) args[0] else "input.txt"
val program = readProgram(File(fileName)).toMutableList()
val output = executeIteration(program, 12, 2)
println("Result1=${output[0]}")
assert(output[0] == 5866714)
// This is a brute force but with no more than 1000 iteration it isn't a problem. Solvers can wait
mainLoop@ for (i in 0..99) {
for (j in 0..99) {
try {
val result = executeIteration(program, i, j)
if (result[0] == 19690720) {
val answer = 100 * i + j
println("Result=$answer")
break@mainLoop
}
} catch (x: Throwable) {
println("Iteration failed:$x")
}
}
}
}Day 03: kotlin
Crossed Wires
I chose to model a Grid with Cells. Each movement will result in activity on a cell and create them as needed. Steps was later added to the cells for each wire and recorded as the grid was populated. There are some flaws in the when you have 3 wires a total value cannot be used to indicate an intersection. The intersections will have to be recorded in a different mechanism.
Solution source
package com.github.corneil.aoc2019.day3
import java.io.BufferedReader
import java.io.File
import java.io.FileReader
import kotlin.math.abs
import kotlin.math.max
import kotlin.math.min
data class Coord(val x: Int, val y: Int) {
fun distance(target: Coord): Int {
return abs(x - target.x) + abs(y - target.y)
}
}
data class Cell(val coord: Coord, val value: Int, val steps: MutableMap<Int, Int> = mutableMapOf())
fun translateInstruction(instruction: String): Pair<Char, Int> {
val direction = instruction[0]
val amount = instruction.substring(1).toInt()
return Pair(direction, amount)
}
class Grid {
val cells = mutableMapOf(Coord(0, 0) to Cell(Coord(0, 0), 0))
private fun addCell(x: Int, y: Int, value: Int, steps: Int) {
if (!(x == 0 && y == 0)) {
val key = Coord(x, y)
val existing = cells[key]
if (existing != null) {
if (existing.value != value) {
cells[key] = existing.copy(value = value + existing.value)
}
val existingSteps = cells[key]!!.steps[value]
if (existingSteps == null) {
cells[key]!!.steps[value] = steps
}
} else {
cells[key] = Cell(key, value, mutableMapOf(value to steps))
}
}
}
private fun addEntriesX(startX: Int, endX: Int, y: Int, value: Int, steps: Int): Coord {
var stepsCounted = steps
if (startX < endX) {
for (x in startX..endX) {
addCell(x, y, value, stepsCounted)
stepsCounted += 1
}
} else {
for (x in startX downTo endX) {
addCell(x, y, value, stepsCounted)
stepsCounted += 1
}
}
return Coord(endX, y)
}
private fun addEntriesY(startY: Int, endY: Int, x: Int, value: Int, steps: Int): Coord {
var stepsCounted = steps
if (startY < endY) {
for (y in startY..endY) {
addCell(x, y, value, stepsCounted)
stepsCounted += 1
}
} else {
for (y in startY downTo endY) {
addCell(x, y, value, stepsCounted)
stepsCounted += 1
}
}
return Coord(x, endY)
}
fun updateGrid(trace: List<String>, line: Int) {
var position = Coord(0, 0)
var stepsCounted = 0
trace.forEach { instruction ->
val direction = translateInstruction(instruction)
position = when (direction.first) {
'R' -> addEntriesX(position.x, position.x + direction.second, position.y, line, stepsCounted)
'L' -> addEntriesX(position.x, position.x - direction.second, position.y, line, stepsCounted)
'U' -> addEntriesY(position.y, position.y + direction.second, position.x, line, stepsCounted)
'D' -> addEntriesY(position.y, position.y - direction.second, position.x, line, stepsCounted)
else -> error("Unknown instruction $instruction")
}
stepsCounted += direction.second
}
}
fun findNearest(coord: Coord, minValue: Int): Cell {
val closest = cells.values.filter { cell ->
cell.value > minValue
}.minBy { cell ->
coord.distance(cell.coord)
}
requireNotNull(closest) { "Could not find any cells!!!" }
return closest
}
fun findLowestStepsIntersection(minValue: Int): Int {
val best = cells.values.filter { cell ->
cell.value > minValue
}.minBy { cell ->
cell.steps.values.sum()
}
requireNotNull(best) { "Expected a minimum value" }
return best.steps.values.sum()
}
fun findClosestManhattenDistance(coord: Coord, minValue: Int): Int {
return coord.distance(findNearest(coord, minValue).coord)
}
fun printGrid(): List<String> {
val minX = min(cells.values.map { it.coord.x }.min() ?: 0, 0) - 1
val maxX = max(cells.values.map { it.coord.x }.max() ?: 0, 0) + 1
val lines = cells.values.groupBy { it.coord.y }.toSortedMap()
return lines.map { entry ->
val lineOut = StringBuilder()
val lineCells = entry.value.map { it.coord.x to it }.toMap()
for (x in minX..maxX) {
val cellX = lineCells[x]
if (cellX != null) {
lineOut.append(cellX.value.toString())
} else {
lineOut.append('.')
}
}
lineOut.toString()
}.reversed()
}
}
fun stringToInstructions(input: String): List<String> {
return input.split(',').map { it.trim() }
}
fun main(args: Array<String>) {
val fileName = if (args.size > 1) args[0] else "input.txt"
val lines = BufferedReader(FileReader(File(fileName))).readLines().mapNotNull {
val line = it.trim()
if (line.isNotEmpty()) line else null
}
val grid = Grid()
lines.forEachIndexed { index, line ->
grid.updateGrid(stringToInstructions(line), index + 1)
}
val start = Coord(0, 0)
val distance = grid.findClosestManhattenDistance(start, lines.size)
println("Distance=$distance")
val best = grid.findLowestStepsIntersection(lines.size)
// then
println("Best=$best")
}Day 04: kotlin
Secure Container
I decided to keep it simple on not try and use regex to do the validations.
Solution source
package com.github.corneil.aoc2019.day4
fun passwordCriteriaLength(input: String): Boolean {
return input.length == 6
}
fun passwordCriteriaDoubleDigits(input: String): Boolean {
var prevChar = input[0]
for (i in 1 until input.length) {
val c = input[i]
if (c == prevChar) {
return true
}
prevChar = c
}
return false
}
fun passwordCriteriaMustHaveAtLeastOneOnlyDoubleDigitsAndNoMore(input: String): Boolean {
var prevChar = input[0]
var matchCount = 0
for (i in 1 until input.length) {
val c = input[i]
if (c == prevChar) {
matchCount += 1
} else {
if (matchCount == 1) {
return true
}
matchCount = 0
}
prevChar = c
}
return matchCount == 1
}
fun passwordCriteriaIncrease(input: String): Boolean {
var prevChar = input[0]
for (i in 1 until input.length) {
val c = input[i]
if (c < prevChar) {
return false
}
prevChar = c
}
return true
}
val functions1 = arrayOf(
::passwordCriteriaLength,
::passwordCriteriaDoubleDigits,
::passwordCriteriaIncrease
)
val functions2 = arrayOf(
::passwordCriteriaLength,
::passwordCriteriaMustHaveAtLeastOneOnlyDoubleDigitsAndNoMore,
::passwordCriteriaIncrease
)
fun validPassword(input: String): Boolean {
for (validationFunction in functions1) {
if (!validationFunction(input)) {
return false
}
}
return true
}
fun validPassword2(input: String): Boolean {
for (validationFunction in functions2) {
if (!validationFunction(input)) {
return false
}
}
return true
}
fun main() {
val valid = (256310..732736).count { validPassword(it.toString()) }
println("Valid in range=$valid")
val valid2 = (256310..732736).count { validPassword2(it.toString()) }
println("Valid2 in range=$valid2")
}Day 05: kotlin
Sunny with a Chance of Asteroids
I found a phrase in the description ambiguous.
Parameters that an instruction writes to will never be in immediate mode.
When in reality the value refered to in the parameter is always the address. In my reading this means it is always in immediate mode.
I have a class the represents the program counter ProgramCounter and a class for the executing state ProgramState
The program state loads the code into mutable memory and resets the program counter.
Each instruction modifies memory and returns a new program counter.
I couldn’t decide if the program counter belongs in the program state or if it should be passed along.
Solution source
package com.github.corneil.aoc2019.day5
import com.github.corneil.aoc2019.intcode.Program
import com.github.corneil.aoc2019.intcode.readProgram
import java.io.File
fun main(args: Array<String>) {
val fileName = if (args.size > 1) args[0] else "input.txt"
val program = Program(readProgram(File(fileName)))
val result1 = program.executeProgram(mutableListOf(1L))
println("Outputs:${result1.outputs()}")
val result2 = program.executeProgram(mutableListOf(5L))
println("Outputs:${result2.outputs()}")
}IntCode source
package com.github.corneil.aoc2019.intcode
import com.github.corneil.aoc2019.intcode.ParameterMode.IMMEDIATE
import com.github.corneil.aoc2019.intcode.ParameterMode.POSITION
import com.github.corneil.aoc2019.intcode.ParameterMode.RELATIVE
import java.io.File
enum class ParameterMode(val mode: Int) {
POSITION(0),
IMMEDIATE(1),
RELATIVE(2)
}
data class ParameterModes(private val modes: List<ParameterMode>) {
operator fun get(index: Int) = if (modes.size > index) {
modes[index]
} else {
POSITION
}
}
fun parameterMode(mode: Int) = ParameterMode.values().find {
it.mode == mode
} ?: error("Invalid mode $mode")
fun paramModesFrom(mode: Long): ParameterModes {
var remainingMode = mode
val result = mutableListOf<ParameterMode>()
while (remainingMode > 0) {
result.add(parameterMode((remainingMode % 10).toInt()))
remainingMode /= 10
}
return ParameterModes(result)
}
fun readProgram(input: String) = input.split(",").map { it.toLong() }
fun readProgram(input: File) = readProgram(input.readText().trim())
data class ProgramCounter(val pc: Int, val run: Boolean) {
fun add(value: Int): ProgramCounter = copy(pc = pc + value)
fun jump(target: Int): ProgramCounter = copy(pc = target)
fun halt(): ProgramCounter = copy(run = false)
}
typealias InputProvider = () -> Long
typealias OutputProvider = (Long) -> Unit
class ProgramState(
private val memory: MutableList<Long>,
private val inputs: MutableList<Long> = mutableListOf(),
private val fetchInput: InputProvider? = null,
private val outputHandler: OutputProvider? = null
) {
var counter = ProgramCounter(0, true)
private set
var waitingInput = false
private set
private var base = 0L
private val output = mutableListOf<Long>()
fun memory() = memory.toList()
fun memory(index: Int): Long = memory[index]
fun outputs() = output.toList()
fun extractOutput(): List<Long> {
val result = output.toList()
output.clear()
return result
}
fun isHalted() = !counter.run
private fun paramModes() = paramModesFrom(read(counter.pc.toLong()) / 100L)
private fun deref(parameterMode: ParameterMode, address: Long): Long {
return when (parameterMode) {
IMMEDIATE -> address
POSITION -> read(address)
RELATIVE -> read(base + address)
}
}
private fun read(address: Long): Long = if (address < memory.size) memory[address.toInt()] else 0L
private fun assign(address: Long, value: Long) {
require(address >= 0) { "Memory address cannot be negative" }
while (memory.size < address + 1) {
memory.add(0L)
}
memory[address.toInt()] = value
}
private fun paramValue(index: Int): Long {
val parameterModes = paramModes()
return deref(parameterModes[index - 1], read((counter.pc + index).toLong()))
}
private fun paramAddress(index: Int): Long {
val parameterModes = paramModes()
val address = read((counter.pc + index).toLong())
return if (parameterModes[index - 1] == RELATIVE) {
base + address
} else {
address
}
}
private fun applyOperation(operation: (Long, Long) -> Long): ProgramCounter {
val value1 = paramValue(1)
val value2 = paramValue(2)
val result = operation(value1, value2)
assign(paramAddress(3), result)
return counter.add(4)
}
private fun saveInput(): ProgramCounter {
val value = if (inputs.isEmpty() && fetchInput != null) {
fetchInput.invoke()
} else {
if (inputs.isEmpty()) {
waitingInput = true
return counter
} else {
inputs.removeAt(0)
}
}
assign(paramAddress(1), value)
return counter.add(2)
}
private fun operationLessThan(): ProgramCounter {
val value1 = paramValue(1)
val value2 = paramValue(2)
val result = if (value1 < value2) 1 else 0
assign(paramAddress(3), result.toLong())
return counter.add(4)
}
private fun operationEquals(): ProgramCounter {
val value1 = paramValue(1)
val value2 = paramValue(2)
val result = if (value1 == value2) 1 else 0
assign(paramAddress(3), result.toLong())
return counter.add(4)
}
private fun jumpIfTrue(): ProgramCounter {
val value = paramValue(1)
val target = paramValue(2)
return if (value != 0L) counter.jump(target.toInt()) else counter.add(3)
}
private fun jumpIfFalse(): ProgramCounter {
val value = paramValue(1)
val target = paramValue(2)
return if (value == 0L) counter.jump(target.toInt()) else counter.add(3)
}
private fun outputValue(): ProgramCounter {
val value = paramValue(1)
if (outputHandler != null) {
outputHandler.invoke(value)
} else {
output.add(value)
}
return counter.add(2)
}
private fun halt() = counter.halt()
private fun adjustBase(): ProgramCounter {
base += paramValue(1).toInt()
return counter.add(2)
}
private fun readAndExecute(): ProgramCounter {
return when (val opcode = (memory[counter.pc] % 100L).toInt()) {
1 -> applyOperation { a, b -> a + b }
2 -> applyOperation { a, b -> a * b }
3 -> saveInput()
4 -> outputValue()
5 -> jumpIfTrue()
6 -> jumpIfFalse()
7 -> operationLessThan()
8 -> operationEquals()
9 -> adjustBase()
99 -> halt()
else -> error("Invalid opcode $opcode")
}
}
fun reset() {
counter = ProgramCounter(0, true)
}
fun execute(): ProgramState {
waitingInput = false
counter = ProgramCounter(0, true)
while (counter.run && counter.pc < memory.size && !waitingInput) {
counter = readAndExecute()
}
return this
}
// Not that this removes the output from program state and returns the output
fun executeUntilOutput(input: List<Long>): List<Long> {
waitingInput = false
inputs.addAll(input)
while (counter.run && counter.pc < memory.size && output.isEmpty() && !waitingInput) {
counter = readAndExecute()
}
return extractOutput()
}
fun executeUntilInput(input: List<Long>) {
waitingInput = false
inputs.addAll(input)
while (counter.run && counter.pc < memory.size && !waitingInput) {
counter = readAndExecute()
}
}
fun setMemory(index: Int, value: Long) {
memory[index] = value
}
}
class Program(
private val code: List<Long>,
private val globalFetchInput: (() -> Long)? = null,
private val globalOutputHandler: ((Long) -> Unit)? = null
) {
fun executeProgram(
input: List<Long>,
fetchInput: (() -> Long)? = null,
outputHandler: ((Long) -> Unit)? = null
): ProgramState {
val state = ProgramState(
code.toMutableList(),
input.toMutableList(),
fetchInput ?: globalFetchInput,
outputHandler ?: globalOutputHandler
)
state.execute()
return state
}
fun createProgram(
input: List<Long> = emptyList(),
fetchInput: (() -> Long)? = null,
outputHandler: ((Long) -> Unit)? = null
): ProgramState {
return ProgramState(
code.toMutableList(),
input.toMutableList(),
fetchInput ?: globalFetchInput,
outputHandler ?: globalOutputHandler
)
}
}Day 06: kotlin
Universal Orbit Map
My test cases matched the supplied cases.
My answer for the number of transfer was 2 lower than the "correct" answer.
Full source
package com.github.corneil.aoc2019.day6
import java.io.File
class OrbitData {
fun addOrbit(obj: String, orbiting: String) {
assert(orbits[orbiting] == null)
orbits[orbiting] = Orbit(
objects[obj] ?: createObj(obj),
objects[orbiting] ?: createObj(orbiting)
)
}
private fun createObj(obj: String): Orbitable {
val o = Orbitable(obj)
objects[obj] = o
return o
}
val objects: MutableMap<String, Orbitable> = mutableMapOf()
val orbits: MutableMap<String, Orbit> = mutableMapOf()
fun findOrbits(obj: String): List<Orbit> {
val orbiting = orbits[obj]
return if(orbiting == null) emptyList() else listOf(orbiting) + findOrbits(orbiting.centre.name)
}
fun findTransfers(start: String, end: String): List<Pair<Orbitable, Orbitable>> {
val startOrbits = findOrbits(start)
val endOrbits = findOrbits(end)
val shared = startOrbits.find { orbit -> endOrbits.any { it == orbit } }
requireNotNull(shared) { "Expected a shared orbit" }
val inward = startOrbits.subList(0, startOrbits.indexOf(shared))
val outward = endOrbits.subList(0, endOrbits.indexOf(shared))
val transfers = inward.map { it.orbits to it.centre } + outward.map { it.centre to it.orbits }
return transfers.subList(0, transfers.size - 2)
}
fun findOrbit(obj: String): Orbit {
return orbits[obj] ?: error("Expected to find $obj orbiting something")
}
}
data class Orbitable(val name: String)
data class Orbit(
val centre: Orbitable,
val orbits: Orbitable
)
fun prepareData(input: String): List<String> {
return input.split('\n').map { it.trim() }.toList()
}
fun loadOrbits(input: List<String>): OrbitData {
val data = OrbitData()
input.forEach { line ->
val items = line.split(')')
data.addOrbit(items[0], items[1])
}
return data
}
fun main(args: Array<String>) {
val fileName = if (args.size > 1) args[0] else "input.txt"
val orbits = loadOrbits(File(fileName).readLines().map { it.trim() })
val allOrbits = orbits.objects.keys.flatMap { orbits.findOrbits(it) }
println("Orbits=${allOrbits.size}")
val you2san = orbits.findTransfers("YOU", "SAN")
println("YOU->SAN=${you2san.size}")
val you = orbits.findOrbit("YOU")
val san = orbits.findOrbit("SAN")
println("YOU=$you")
println("SAN=$san")
val transfer = orbits.findTransfers(you.centre.name, san.centre.name)
println(transfer.joinToString("\n") { it.first.name + " -> " + it.second.name })
println("Transfers=${transfer.size}")
}Day 07: kotlin
Amplification Circuit
Permutation generation was the biggest challenge. The examples I found of Heap’s Algorithm for generating permutations sent me in circles. Eventually I did a brute force implementation that works.
Solution Source
package com.github.corneil.aoc2019.day7
import com.github.corneil.aoc2019.intcode.Program
import com.github.corneil.aoc2019.intcode.readProgram
import java.io.File
fun phaseAmplifierTest(code: List<Long>, sequence: LongArray): Long {
val program = Program(code)
var amplifierInput = 0L
sequence.forEach { phase ->
val result = program.executeProgram(listOf(phase, amplifierInput))
amplifierInput = result.outputs().first()
}
return amplifierInput
}
fun phaseAmplifierFeedback(code: List<Long>, sequence: LongArray): Long {
val program = Program(code)
var lastOutput = 0L
var amplifierInput = listOf(0L)
val amplifiers = sequence.map { phase -> program.createProgram(listOf(phase)) }
do {
amplifiers.forEach { amp ->
if (!amp.isHalted()) {
val result = amp.executeUntilOutput(amplifierInput)
if (result.isNotEmpty()) {
lastOutput = result.last()
amplifierInput = result
}
}
}
} while (amplifiers.count { !it.isHalted() } == amplifiers.size)
return lastOutput
}
// found on https://rosettacode.org/wiki/Permutations#Kotlin
fun <T> permute(input: List<T>): List<List<T>> {
if (input.size == 1) return listOf(input)
val perms = mutableListOf<List<T>>()
val toInsert = input[0]
for (perm in permute(input.drop(1))) {
for (i in 0..perm.size) {
val newPerm = perm.toMutableList()
newPerm.add(i, toInsert)
perms.add(newPerm)
}
}
return perms
}
fun permutationGeneration(start: Long, end: Long): List<LongArray> {
return permute((start..end).toList()).map { it.toLongArray() }
}
fun main(args: Array<String>) {
val fileName = if (args.size > 1) args[0] else "input.txt"
val code = readProgram(File(fileName))
val maxOutput = permutationGeneration(0L, 4L).map { seq -> phaseAmplifierTest(code, seq) }.max()
println("Max Output = $maxOutput")
val maxOutput2 = permutationGeneration(5L, 9L).map { seq -> phaseAmplifierFeedback(code, seq) }.max()
println("Max Output = $maxOutput2")
}IntCode source
package com.github.corneil.aoc2019.intcode
import com.github.corneil.aoc2019.intcode.ParameterMode.IMMEDIATE
import com.github.corneil.aoc2019.intcode.ParameterMode.POSITION
import com.github.corneil.aoc2019.intcode.ParameterMode.RELATIVE
import java.io.File
enum class ParameterMode(val mode: Int) {
POSITION(0),
IMMEDIATE(1),
RELATIVE(2)
}
data class ParameterModes(private val modes: List<ParameterMode>) {
operator fun get(index: Int) = if (modes.size > index) {
modes[index]
} else {
POSITION
}
}
fun parameterMode(mode: Int) = ParameterMode.values().find {
it.mode == mode
} ?: error("Invalid mode $mode")
fun paramModesFrom(mode: Long): ParameterModes {
var remainingMode = mode
val result = mutableListOf<ParameterMode>()
while (remainingMode > 0) {
result.add(parameterMode((remainingMode % 10).toInt()))
remainingMode /= 10
}
return ParameterModes(result)
}
fun readProgram(input: String) = input.split(",").map { it.toLong() }
fun readProgram(input: File) = readProgram(input.readText().trim())
data class ProgramCounter(val pc: Int, val run: Boolean) {
fun add(value: Int): ProgramCounter = copy(pc = pc + value)
fun jump(target: Int): ProgramCounter = copy(pc = target)
fun halt(): ProgramCounter = copy(run = false)
}
typealias InputProvider = () -> Long
typealias OutputProvider = (Long) -> Unit
class ProgramState(
private val memory: MutableList<Long>,
private val inputs: MutableList<Long> = mutableListOf(),
private val fetchInput: InputProvider? = null,
private val outputHandler: OutputProvider? = null
) {
var counter = ProgramCounter(0, true)
private set
var waitingInput = false
private set
private var base = 0L
private val output = mutableListOf<Long>()
fun memory() = memory.toList()
fun memory(index: Int): Long = memory[index]
fun outputs() = output.toList()
fun extractOutput(): List<Long> {
val result = output.toList()
output.clear()
return result
}
fun isHalted() = !counter.run
private fun paramModes() = paramModesFrom(read(counter.pc.toLong()) / 100L)
private fun deref(parameterMode: ParameterMode, address: Long): Long {
return when (parameterMode) {
IMMEDIATE -> address
POSITION -> read(address)
RELATIVE -> read(base + address)
}
}
private fun read(address: Long): Long = if (address < memory.size) memory[address.toInt()] else 0L
private fun assign(address: Long, value: Long) {
require(address >= 0) { "Memory address cannot be negative" }
while (memory.size < address + 1) {
memory.add(0L)
}
memory[address.toInt()] = value
}
private fun paramValue(index: Int): Long {
val parameterModes = paramModes()
return deref(parameterModes[index - 1], read((counter.pc + index).toLong()))
}
private fun paramAddress(index: Int): Long {
val parameterModes = paramModes()
val address = read((counter.pc + index).toLong())
return if (parameterModes[index - 1] == RELATIVE) {
base + address
} else {
address
}
}
private fun applyOperation(operation: (Long, Long) -> Long): ProgramCounter {
val value1 = paramValue(1)
val value2 = paramValue(2)
val result = operation(value1, value2)
assign(paramAddress(3), result)
return counter.add(4)
}
private fun saveInput(): ProgramCounter {
val value = if (inputs.isEmpty() && fetchInput != null) {
fetchInput.invoke()
} else {
if (inputs.isEmpty()) {
waitingInput = true
return counter
} else {
inputs.removeAt(0)
}
}
assign(paramAddress(1), value)
return counter.add(2)
}
private fun operationLessThan(): ProgramCounter {
val value1 = paramValue(1)
val value2 = paramValue(2)
val result = if (value1 < value2) 1 else 0
assign(paramAddress(3), result.toLong())
return counter.add(4)
}
private fun operationEquals(): ProgramCounter {
val value1 = paramValue(1)
val value2 = paramValue(2)
val result = if (value1 == value2) 1 else 0
assign(paramAddress(3), result.toLong())
return counter.add(4)
}
private fun jumpIfTrue(): ProgramCounter {
val value = paramValue(1)
val target = paramValue(2)
return if (value != 0L) counter.jump(target.toInt()) else counter.add(3)
}
private fun jumpIfFalse(): ProgramCounter {
val value = paramValue(1)
val target = paramValue(2)
return if (value == 0L) counter.jump(target.toInt()) else counter.add(3)
}
private fun outputValue(): ProgramCounter {
val value = paramValue(1)
if (outputHandler != null) {
outputHandler.invoke(value)
} else {
output.add(value)
}
return counter.add(2)
}
private fun halt() = counter.halt()
private fun adjustBase(): ProgramCounter {
base += paramValue(1).toInt()
return counter.add(2)
}
private fun readAndExecute(): ProgramCounter {
return when (val opcode = (memory[counter.pc] % 100L).toInt()) {
1 -> applyOperation { a, b -> a + b }
2 -> applyOperation { a, b -> a * b }
3 -> saveInput()
4 -> outputValue()
5 -> jumpIfTrue()
6 -> jumpIfFalse()
7 -> operationLessThan()
8 -> operationEquals()
9 -> adjustBase()
99 -> halt()
else -> error("Invalid opcode $opcode")
}
}
fun reset() {
counter = ProgramCounter(0, true)
}
fun execute(): ProgramState {
waitingInput = false
counter = ProgramCounter(0, true)
while (counter.run && counter.pc < memory.size && !waitingInput) {
counter = readAndExecute()
}
return this
}
// Not that this removes the output from program state and returns the output
fun executeUntilOutput(input: List<Long>): List<Long> {
waitingInput = false
inputs.addAll(input)
while (counter.run && counter.pc < memory.size && output.isEmpty() && !waitingInput) {
counter = readAndExecute()
}
return extractOutput()
}
fun executeUntilInput(input: List<Long>) {
waitingInput = false
inputs.addAll(input)
while (counter.run && counter.pc < memory.size && !waitingInput) {
counter = readAndExecute()
}
}
fun setMemory(index: Int, value: Long) {
memory[index] = value
}
}
class Program(
private val code: List<Long>,
private val globalFetchInput: (() -> Long)? = null,
private val globalOutputHandler: ((Long) -> Unit)? = null
) {
fun executeProgram(
input: List<Long>,
fetchInput: (() -> Long)? = null,
outputHandler: ((Long) -> Unit)? = null
): ProgramState {
val state = ProgramState(
code.toMutableList(),
input.toMutableList(),
fetchInput ?: globalFetchInput,
outputHandler ?: globalOutputHandler
)
state.execute()
return state
}
fun createProgram(
input: List<Long> = emptyList(),
fetchInput: (() -> Long)? = null,
outputHandler: ((Long) -> Unit)? = null
): ProgramState {
return ProgramState(
code.toMutableList(),
input.toMutableList(),
fetchInput ?: globalFetchInput,
outputHandler ?: globalOutputHandler
)
}
}Day 08: kotlin
Space Image Format
Kotlin made this one very straight forward, especially minBy
Things a learned 30 years ago directly manipulating the screen memory on my PC came in handy.
Thanks to Mr Norton.
Full Source
package com.github.corneil.aoc2019.day8
import java.io.File
typealias ImageLayer = List<Int>
data class Image(val width: Int, val height: Int, val layers: List<ImageLayer>)
fun readImage(width: Int, height: Int, input: String): Image {
val dim = width * height
val layersCount = input.length / dim
val layers = (0 until layersCount).map { l ->
input.substring(l * dim, (l + 1) * dim).map {
it.toString().toInt()
}
}
return Image(width, height, layers)
}
fun printImage(image: Image) {
for (y in 0 until image.height) {
for (x in 0 until image.width) {
val offset = x + (y * image.width)
val pixel = (image.layers.indices).map {
image.layers[it][offset]
}.find { it != 2 } ?: 0
print(if (pixel == 1) "*" else " ")
}
println()
}
println()
}
fun main(args: Array<String>) {
val fileName = if (args.size > 1) args[0] else "input.txt"
val image = readImage(25, 6, File(fileName).readText().trim())
println("Layers=${image.layers.size}")
val minZeros = image.layers.minBy { layer -> layer.count { it == 0 } }
requireNotNull(minZeros) { "Expected to find a layer with 0" }
val result = minZeros.count { it == 1 } * minZeros.count { it == 2 }
println("Result = $result")
printImage(image)
}Day 09: kotlin
Sensor Boost
Updated program to support Long for input and output. Added opcodes. Relative in conjunction with assignment tripped me up a little.
Solution source
package com.github.corneil.aoc2019.day9
import com.github.corneil.aoc2019.intcode.Program
import com.github.corneil.aoc2019.intcode.readProgram
import java.io.File
fun main(args: Array<String>) {
val fileName = if (args.size > 1) args[0] else "input.txt"
val code = readProgram(File(fileName))
val output = Program(code).executeProgram(listOf(1L))
println("Output = ${output.outputs()}")
val output2 = Program(code).executeProgram(listOf(2L))
println("Output = ${output2.outputs()}")
}IntCode source
package com.github.corneil.aoc2019.intcode
import com.github.corneil.aoc2019.intcode.ParameterMode.IMMEDIATE
import com.github.corneil.aoc2019.intcode.ParameterMode.POSITION
import com.github.corneil.aoc2019.intcode.ParameterMode.RELATIVE
import java.io.File
enum class ParameterMode(val mode: Int) {
POSITION(0),
IMMEDIATE(1),
RELATIVE(2)
}
data class ParameterModes(private val modes: List<ParameterMode>) {
operator fun get(index: Int) = if (modes.size > index) {
modes[index]
} else {
POSITION
}
}
fun parameterMode(mode: Int) = ParameterMode.values().find {
it.mode == mode
} ?: error("Invalid mode $mode")
fun paramModesFrom(mode: Long): ParameterModes {
var remainingMode = mode
val result = mutableListOf<ParameterMode>()
while (remainingMode > 0) {
result.add(parameterMode((remainingMode % 10).toInt()))
remainingMode /= 10
}
return ParameterModes(result)
}
fun readProgram(input: String) = input.split(",").map { it.toLong() }
fun readProgram(input: File) = readProgram(input.readText().trim())
data class ProgramCounter(val pc: Int, val run: Boolean) {
fun add(value: Int): ProgramCounter = copy(pc = pc + value)
fun jump(target: Int): ProgramCounter = copy(pc = target)
fun halt(): ProgramCounter = copy(run = false)
}
typealias InputProvider = () -> Long
typealias OutputProvider = (Long) -> Unit
class ProgramState(
private val memory: MutableList<Long>,
private val inputs: MutableList<Long> = mutableListOf(),
private val fetchInput: InputProvider? = null,
private val outputHandler: OutputProvider? = null
) {
var counter = ProgramCounter(0, true)
private set
var waitingInput = false
private set
private var base = 0L
private val output = mutableListOf<Long>()
fun memory() = memory.toList()
fun memory(index: Int): Long = memory[index]
fun outputs() = output.toList()
fun extractOutput(): List<Long> {
val result = output.toList()
output.clear()
return result
}
fun isHalted() = !counter.run
private fun paramModes() = paramModesFrom(read(counter.pc.toLong()) / 100L)
private fun deref(parameterMode: ParameterMode, address: Long): Long {
return when (parameterMode) {
IMMEDIATE -> address
POSITION -> read(address)
RELATIVE -> read(base + address)
}
}
private fun read(address: Long): Long = if (address < memory.size) memory[address.toInt()] else 0L
private fun assign(address: Long, value: Long) {
require(address >= 0) { "Memory address cannot be negative" }
while (memory.size < address + 1) {
memory.add(0L)
}
memory[address.toInt()] = value
}
private fun paramValue(index: Int): Long {
val parameterModes = paramModes()
return deref(parameterModes[index - 1], read((counter.pc + index).toLong()))
}
private fun paramAddress(index: Int): Long {
val parameterModes = paramModes()
val address = read((counter.pc + index).toLong())
return if (parameterModes[index - 1] == RELATIVE) {
base + address
} else {
address
}
}
private fun applyOperation(operation: (Long, Long) -> Long): ProgramCounter {
val value1 = paramValue(1)
val value2 = paramValue(2)
val result = operation(value1, value2)
assign(paramAddress(3), result)
return counter.add(4)
}
private fun saveInput(): ProgramCounter {
val value = if (inputs.isEmpty() && fetchInput != null) {
fetchInput.invoke()
} else {
if (inputs.isEmpty()) {
waitingInput = true
return counter
} else {
inputs.removeAt(0)
}
}
assign(paramAddress(1), value)
return counter.add(2)
}
private fun operationLessThan(): ProgramCounter {
val value1 = paramValue(1)
val value2 = paramValue(2)
val result = if (value1 < value2) 1 else 0
assign(paramAddress(3), result.toLong())
return counter.add(4)
}
private fun operationEquals(): ProgramCounter {
val value1 = paramValue(1)
val value2 = paramValue(2)
val result = if (value1 == value2) 1 else 0
assign(paramAddress(3), result.toLong())
return counter.add(4)
}
private fun jumpIfTrue(): ProgramCounter {
val value = paramValue(1)
val target = paramValue(2)
return if (value != 0L) counter.jump(target.toInt()) else counter.add(3)
}
private fun jumpIfFalse(): ProgramCounter {
val value = paramValue(1)
val target = paramValue(2)
return if (value == 0L) counter.jump(target.toInt()) else counter.add(3)
}
private fun outputValue(): ProgramCounter {
val value = paramValue(1)
if (outputHandler != null) {
outputHandler.invoke(value)
} else {
output.add(value)
}
return counter.add(2)
}
private fun halt() = counter.halt()
private fun adjustBase(): ProgramCounter {
base += paramValue(1).toInt()
return counter.add(2)
}
private fun readAndExecute(): ProgramCounter {
return when (val opcode = (memory[counter.pc] % 100L).toInt()) {
1 -> applyOperation { a, b -> a + b }
2 -> applyOperation { a, b -> a * b }
3 -> saveInput()
4 -> outputValue()
5 -> jumpIfTrue()
6 -> jumpIfFalse()
7 -> operationLessThan()
8 -> operationEquals()
9 -> adjustBase()
99 -> halt()
else -> error("Invalid opcode $opcode")
}
}
fun reset() {
counter = ProgramCounter(0, true)
}
fun execute(): ProgramState {
waitingInput = false
counter = ProgramCounter(0, true)
while (counter.run && counter.pc < memory.size && !waitingInput) {
counter = readAndExecute()
}
return this
}
// Not that this removes the output from program state and returns the output
fun executeUntilOutput(input: List<Long>): List<Long> {
waitingInput = false
inputs.addAll(input)
while (counter.run && counter.pc < memory.size && output.isEmpty() && !waitingInput) {
counter = readAndExecute()
}
return extractOutput()
}
fun executeUntilInput(input: List<Long>) {
waitingInput = false
inputs.addAll(input)
while (counter.run && counter.pc < memory.size && !waitingInput) {
counter = readAndExecute()
}
}
fun setMemory(index: Int, value: Long) {
memory[index] = value
}
}
class Program(
private val code: List<Long>,
private val globalFetchInput: (() -> Long)? = null,
private val globalOutputHandler: ((Long) -> Unit)? = null
) {
fun executeProgram(
input: List<Long>,
fetchInput: (() -> Long)? = null,
outputHandler: ((Long) -> Unit)? = null
): ProgramState {
val state = ProgramState(
code.toMutableList(),
input.toMutableList(),
fetchInput ?: globalFetchInput,
outputHandler ?: globalOutputHandler
)
state.execute()
return state
}
fun createProgram(
input: List<Long> = emptyList(),
fetchInput: (() -> Long)? = null,
outputHandler: ((Long) -> Unit)? = null
): ProgramState {
return ProgramState(
code.toMutableList(),
input.toMutableList(),
fetchInput ?: globalFetchInput,
outputHandler ?: globalOutputHandler
)
}
}Day 10: kotlin
Monitoring Station
Thanks to Michael Simons I could finish the 2nd part.
Solution source
package com.github.corneil.aoc2019.day10
import java.io.File
import java.math.BigDecimal
import java.math.RoundingMode.HALF_EVEN
import kotlin.math.atan2
import kotlin.math.max
import kotlin.math.pow
import kotlin.math.sqrt
data class Coord(val x: Int, val y: Int)
data class AsteroidMap(val width: Int, val height: Int, val asteroidLocations: List<Coord>) {
fun contains(point: Coord): Boolean {
return point.y >= 0 && point.y < height && point.x in 0 until width
}
}
fun readMap(input: List<String>): AsteroidMap {
var width = 0
val result = mutableListOf<Coord>()
input.forEachIndexed { y, line ->
line.trim().forEachIndexed { x, c ->
width = max(width, x + 1)
if (c == '#') {
result.add(Coord(x, y))
}
}
}
return AsteroidMap(width, input.size, result)
}
// I had to look at other solutions to do the 2nd part. Tx Michael Simons
fun direction(start: Coord, end: Coord) = Coord(end.x - start.x, end.y - start.y)
fun distance(pt: Coord): Double = sqrt(pt.x.toDouble().pow(2.0) + pt.y.toDouble().pow(2.0))
typealias Normalized = Pair<BigDecimal, BigDecimal>
fun normalized(pt: Coord): Normalized {
val dist = distance(pt)
return Pair(
BigDecimal(pt.x.toDouble() / dist).setScale(4, HALF_EVEN),
BigDecimal(pt.y / dist).setScale(4, HALF_EVEN)
)
}
fun prepareOtherAsteroids(map: AsteroidMap, coord: Coord): Map<Normalized, MutableList<Pair<Coord, Double>>> {
val result = mutableMapOf<Normalized, MutableList<Pair<Coord, Double>>>()
map.asteroidLocations.filter { it != coord }.forEach {
val dir = direction(coord, it)
val dist = distance(dir)
val norm = normalized(dir)
val target = Pair(it, dist)
if (result.containsKey(norm)) {
result[norm]!!.add(target)
} else {
result[norm] = mutableListOf(target)
}
}
result.forEach { entry ->
entry.value.sortBy { it.second }
}
return result
}
fun findLineOfSightCount(map: AsteroidMap, coord: Coord): Int {
return prepareOtherAsteroids(map, coord).size
}
fun shootInOrder(map: AsteroidMap, laser: Coord): List<Coord> {
val list = prepareOtherAsteroids(map, laser)
val visiting = list.keys.sortedBy { atan2(it.first.toDouble(), it.second.toDouble()) }.reversed()
val shot = mutableListOf<Coord>()
while (shot.size < map.asteroidLocations.size - 1) {
visiting.forEach { direction ->
val targets = list[direction] ?: mutableListOf()
if (targets.isNotEmpty()) {
shot.add(targets.first().first)
targets.removeAt(0)
}
}
}
return shot
}
fun main(args: Array<String>) {
val fileName = if (args.size > 1) args[0] else "input.txt"
val map = readMap(File(fileName).readLines().map { it.trim() })
val counts = map.asteroidLocations.map { it to findLineOfSightCount(map, it) }
val best = counts.maxBy { it.second }
println("Best = $best")
val shot = shootInOrder(map, best!!.first)
val shot200 = shot[199]
val answer = shot200.x * 100 + shot200.y
println("Answer=$answer")
}Normalizing the angle and then using atan2 to order to angles made simple work of the rest.
You do not want to know which depths I have explored today!
Day 11: kotlin
Space Police
Robot source
package com.github.corneil.aoc2019.day11
import com.github.corneil.aoc2019.day11.DIRECTION.EAST
import com.github.corneil.aoc2019.day11.DIRECTION.NORTH
import com.github.corneil.aoc2019.day11.DIRECTION.SOUTH
import com.github.corneil.aoc2019.day11.DIRECTION.WEST
import com.github.corneil.aoc2019.intcode.Program
import com.github.corneil.aoc2019.intcode.readProgram
import java.io.File
enum class DIRECTION(val direction: Char) {
NORTH('^'),
EAST('>'),
SOUTH('v'),
WEST('<')
}
data class Cell(val color: Int = 0, val painted: Boolean = false)
data class Coord(val x: Int, val y: Int)
data class Robot(var position: Coord, var direction: DIRECTION) {
fun turn(direction: Int) {
if (direction == 0) {
turnLeft()
} else {
turnRight()
}
advance()
}
fun advance() {
position = when (direction) {
NORTH -> position.copy(y = position.y - 1)
EAST -> position.copy(x = position.x + 1)
SOUTH -> position.copy(y = position.y + 1)
WEST -> position.copy(x = position.x - 1)
}
}
fun turnLeft() {
direction = when (direction) {
NORTH -> WEST
WEST -> SOUTH
SOUTH -> EAST
EAST -> NORTH
}
}
fun turnRight() {
direction = when (direction) {
NORTH -> EAST
EAST -> SOUTH
SOUTH -> WEST
WEST -> NORTH
}
}
}
data class Grid(val cells: MutableMap<Coord, Cell> = mutableMapOf()) {
fun cellColor(pos: Coord): Int {
val cell = cells[pos] ?: Cell()
return cell.color
}
fun paintCell(pos: Coord, color: Int) {
cells[pos] = Cell(color, true)
}
}
fun runRobot(input: List<Long>, startingColor: Int): Int {
val robot = Robot(Coord(0, 0), NORTH)
val grid = Grid()
var outputState = false
val code = Program(input)
val program = code.createProgram(listOf(startingColor.toLong()), fetchInput = {
grid.cellColor(robot.position).toLong()
}) { output ->
if (!outputState) {
grid.paintCell(robot.position, output.toInt())
outputState = true
} else {
robot.turn(output.toInt())
outputState = false
}
}
do {
program.execute()
} while (!program.isHalted())
printGrid(grid)
return grid.cells.values.count { it.painted }
}
fun printGrid(grid: Grid) {
val maxX = grid.cells.keys.maxBy { it.x }?.x ?: 0
val minX = grid.cells.keys.minBy { it.x }?.x ?: 0
val maxY = grid.cells.keys.maxBy { it.y }?.y ?: 0
val minY = grid.cells.keys.minBy { it.y }?.y ?: 0
for (y in minY..maxY) {
for (x in minX..maxX) {
val color = grid.cellColor(Coord(x, y))
print(if (color == 0) ' ' else '#')
}
println()
}
}
fun main(args: Array<String>) {
val fileName = if (args.size > 1) args[0] else "input.txt"
val code = readProgram(File(fileName))
val painted = runRobot(code, 0)
println("Painted = $painted")
runRobot(code, 1)
}IntCode source
package com.github.corneil.aoc2019.intcode
import com.github.corneil.aoc2019.intcode.ParameterMode.IMMEDIATE
import com.github.corneil.aoc2019.intcode.ParameterMode.POSITION
import com.github.corneil.aoc2019.intcode.ParameterMode.RELATIVE
import java.io.File
enum class ParameterMode(val mode: Int) {
POSITION(0),
IMMEDIATE(1),
RELATIVE(2)
}
data class ParameterModes(private val modes: List<ParameterMode>) {
operator fun get(index: Int) = if (modes.size > index) {
modes[index]
} else {
POSITION
}
}
fun parameterMode(mode: Int) = ParameterMode.values().find {
it.mode == mode
} ?: error("Invalid mode $mode")
fun paramModesFrom(mode: Long): ParameterModes {
var remainingMode = mode
val result = mutableListOf<ParameterMode>()
while (remainingMode > 0) {
result.add(parameterMode((remainingMode % 10).toInt()))
remainingMode /= 10
}
return ParameterModes(result)
}
fun readProgram(input: String) = input.split(",").map { it.toLong() }
fun readProgram(input: File) = readProgram(input.readText().trim())
data class ProgramCounter(val pc: Int, val run: Boolean) {
fun add(value: Int): ProgramCounter = copy(pc = pc + value)
fun jump(target: Int): ProgramCounter = copy(pc = target)
fun halt(): ProgramCounter = copy(run = false)
}
typealias InputProvider = () -> Long
typealias OutputProvider = (Long) -> Unit
class ProgramState(
private val memory: MutableList<Long>,
private val inputs: MutableList<Long> = mutableListOf(),
private val fetchInput: InputProvider? = null,
private val outputHandler: OutputProvider? = null
) {
var counter = ProgramCounter(0, true)
private set
var waitingInput = false
private set
private var base = 0L
private val output = mutableListOf<Long>()
fun memory() = memory.toList()
fun memory(index: Int): Long = memory[index]
fun outputs() = output.toList()
fun extractOutput(): List<Long> {
val result = output.toList()
output.clear()
return result
}
fun isHalted() = !counter.run
private fun paramModes() = paramModesFrom(read(counter.pc.toLong()) / 100L)
private fun deref(parameterMode: ParameterMode, address: Long): Long {
return when (parameterMode) {
IMMEDIATE -> address
POSITION -> read(address)
RELATIVE -> read(base + address)
}
}
private fun read(address: Long): Long = if (address < memory.size) memory[address.toInt()] else 0L
private fun assign(address: Long, value: Long) {
require(address >= 0) { "Memory address cannot be negative" }
while (memory.size < address + 1) {
memory.add(0L)
}
memory[address.toInt()] = value
}
private fun paramValue(index: Int): Long {
val parameterModes = paramModes()
return deref(parameterModes[index - 1], read((counter.pc + index).toLong()))
}
private fun paramAddress(index: Int): Long {
val parameterModes = paramModes()
val address = read((counter.pc + index).toLong())
return if (parameterModes[index - 1] == RELATIVE) {
base + address
} else {
address
}
}
private fun applyOperation(operation: (Long, Long) -> Long): ProgramCounter {
val value1 = paramValue(1)
val value2 = paramValue(2)
val result = operation(value1, value2)
assign(paramAddress(3), result)
return counter.add(4)
}
private fun saveInput(): ProgramCounter {
val value = if (inputs.isEmpty() && fetchInput != null) {
fetchInput.invoke()
} else {
if (inputs.isEmpty()) {
waitingInput = true
return counter
} else {
inputs.removeAt(0)
}
}
assign(paramAddress(1), value)
return counter.add(2)
}
private fun operationLessThan(): ProgramCounter {
val value1 = paramValue(1)
val value2 = paramValue(2)
val result = if (value1 < value2) 1 else 0
assign(paramAddress(3), result.toLong())
return counter.add(4)
}
private fun operationEquals(): ProgramCounter {
val value1 = paramValue(1)
val value2 = paramValue(2)
val result = if (value1 == value2) 1 else 0
assign(paramAddress(3), result.toLong())
return counter.add(4)
}
private fun jumpIfTrue(): ProgramCounter {
val value = paramValue(1)
val target = paramValue(2)
return if (value != 0L) counter.jump(target.toInt()) else counter.add(3)
}
private fun jumpIfFalse(): ProgramCounter {
val value = paramValue(1)
val target = paramValue(2)
return if (value == 0L) counter.jump(target.toInt()) else counter.add(3)
}
private fun outputValue(): ProgramCounter {
val value = paramValue(1)
if (outputHandler != null) {
outputHandler.invoke(value)
} else {
output.add(value)
}
return counter.add(2)
}
private fun halt() = counter.halt()
private fun adjustBase(): ProgramCounter {
base += paramValue(1).toInt()
return counter.add(2)
}
private fun readAndExecute(): ProgramCounter {
return when (val opcode = (memory[counter.pc] % 100L).toInt()) {
1 -> applyOperation { a, b -> a + b }
2 -> applyOperation { a, b -> a * b }
3 -> saveInput()
4 -> outputValue()
5 -> jumpIfTrue()
6 -> jumpIfFalse()
7 -> operationLessThan()
8 -> operationEquals()
9 -> adjustBase()
99 -> halt()
else -> error("Invalid opcode $opcode")
}
}
fun reset() {
counter = ProgramCounter(0, true)
}
fun execute(): ProgramState {
waitingInput = false
counter = ProgramCounter(0, true)
while (counter.run && counter.pc < memory.size && !waitingInput) {
counter = readAndExecute()
}
return this
}
// Not that this removes the output from program state and returns the output
fun executeUntilOutput(input: List<Long>): List<Long> {
waitingInput = false
inputs.addAll(input)
while (counter.run && counter.pc < memory.size && output.isEmpty() && !waitingInput) {
counter = readAndExecute()
}
return extractOutput()
}
fun executeUntilInput(input: List<Long>) {
waitingInput = false
inputs.addAll(input)
while (counter.run && counter.pc < memory.size && !waitingInput) {
counter = readAndExecute()
}
}
fun setMemory(index: Int, value: Long) {
memory[index] = value
}
}
class Program(
private val code: List<Long>,
private val globalFetchInput: (() -> Long)? = null,
private val globalOutputHandler: ((Long) -> Unit)? = null
) {
fun executeProgram(
input: List<Long>,
fetchInput: (() -> Long)? = null,
outputHandler: ((Long) -> Unit)? = null
): ProgramState {
val state = ProgramState(
code.toMutableList(),
input.toMutableList(),
fetchInput ?: globalFetchInput,
outputHandler ?: globalOutputHandler
)
state.execute()
return state
}
fun createProgram(
input: List<Long> = emptyList(),
fetchInput: (() -> Long)? = null,
outputHandler: ((Long) -> Unit)? = null
): ProgramState {
return ProgramState(
code.toMutableList(),
input.toMutableList(),
fetchInput ?: globalFetchInput,
outputHandler ?: globalOutputHandler
)
}
}Day 12: kotlin
The N-Body Problem
Part 1
The first part was fairly easy.
class Moon(
val id: Int,
val pos: Position,
val vel: Velocity
) {
fun move() {
pos.x += vel.x
pos.y += vel.y
pos.z += vel.z
}
fun applyGravity(moons: List<Moon>) {
vel.x += moons.count { pos.x < it.pos.x } - moons.count { pos.x > it.pos.x }
vel.y += moons.count { pos.y < it.pos.y } - moons.count { pos.y > it.pos.y }
vel.z += moons.count { pos.z < it.pos.z } - moons.count { pos.z > it.pos.z }
}
fun totalEnergy(): Int = pos.potentialEnergy() * vel.kineticEnergy()
}
class Orbits(val moons: List<Moon> ) {
fun advanceOrbit() {
moons.forEach { moon ->
moon.applyGravity(moons)
}
moons.forEach { moon ->
moon.move()
}
}
fun totalEnergy() = moons.sumBy { it.totalEnergy() }
}
fun main() {
// input not shown
val orbits = readOrbits(input.split('\n'))
repeat(1000) {
orbits.advanceOrbits()
}
val totalEnergy = orbits.totalEnergy()
println("Total Energy=$totalEnergy")
}Part 2
This was much more difficult.
class Orbit {
// additional functions
fun copy() = Orbits(moons.map { it.copy() })
fun sameAs(original: Orbits): Boolean {
return moons.filterIndexed { index, moon ->
val orig = original.moons[index]
moon.pos == orig.pos && moon.vel == orig.vel
}.count() == moons.size
}
}
// Brute force counting
val orbits = readOrbits(input.split('\n'))
val original = orbits.copy()
var count = 0
do {
orbits.advanceOrbit()
count++
} while (!orbits.sameAs(original))This doesn’t work because the number seems to be much higher as described in problem statement.
I first tried to optimize the code but realized there has to be a different solution.
The hint was that each pair of position and velocity will cycle separately. We then need to find the lowest common multiplier of the cycles.
Extracting a snapshot of each axis into a map of list of pairs of ints. Advance the orbits until a snapshot matches and you have a cycle count.
I refactored the Position and Velocity to IntArray typealias as Axis to reduce the amount of code for snapshot and calcuations in orbit.
typealias SnapShot = List<Pair<Int, Int>>
typealias Axis = IntArray
class Moon {
// additional function
fun snapShot(index: Int) = Pair(pos[index], vel[index])
}
class Orbit {
// additional functions
fun snapShot(index: Int): SnapShot {
return moons.map { it.snapShot(index) }
}
fun makeSnapShot(): Map<Int, SnapShot> =
(0..2).map {
it to snapShot(it)
}.toMap()
}
fun findCycles(orbits: Orbits): List<Long> {
val snap = orbits.makeSnapShot().toMutableMap()
val cycle = mutableListOf<Long>()
var counter = 0L
do {
orbits.advanceOrbit()
counter++
for (x in 0..2) {
if (snap.containsKey(x)) {
if (snap[x] == orbits.snapShot(x)) {
println("Cycle[$x]=$counter")
cycle.add(counter)
snap.remove(x)
}
}
}
} while (snap.isNotEmpty())
return cycle
}BigInteger to the rescue. This will find the lowest common multiplier of each element and the following in the list.
fun lowestCommonMultiplier(v1: BigInteger, v2: BigInteger): BigInteger {
return (v1 * v2).abs() / v1.gcd(v2)
}
fun lowestCommonMultiplier(list: List<BigInteger>): BigInteger {
return if (list.size == 2) {
lowestCommonMultiplier(list[0], list[1])
} else {
val lcds = mutableListOf<BigInteger>()
for (i in 0 until list.size - 1) {
lcds.add(lowestCommonMultiplier(list[i], list[i + 1]))
}
lowestCommonMultiplier(lcds)
}
}Solution Source
package com.github.corneil.aoc2019.day12
import java.math.BigInteger
import java.util.*
import kotlin.math.abs
typealias Axis = IntArray
fun Axis.energy(): Int = this.sumBy { abs(it) }
fun Axis.copy() = this.toList().toIntArray()
class Moon(
val id: Int,
val pos: Axis,
val vel: Axis
) {
init {
require(pos.size == 3)
require(vel.size == 3)
}
fun applyGravity(moons: List<Moon>) {
for (i in 0..2) {
vel[i] += moons.count { pos[i] < it.pos[i] } - moons.count { pos[i] > it.pos[i] }
}
}
fun move() {
for (i in 0..2) {
pos[i] += vel[i]
}
}
fun totalEnergy(): Int = pos.energy() * vel.energy()
fun copy() = Moon(id, pos.copy(), vel.copy())
fun snapShot(index: Int) = Pair(pos[index], vel[index])
override fun equals(other: Any?): Boolean {
if (this === other) return true
if (javaClass != other?.javaClass) return false
other as Moon
if (!pos.contentEquals(other.pos)) return false
if (!vel.contentEquals(other.vel)) return false
return true
}
override fun hashCode(): Int {
var result = pos.contentHashCode()
result = 31 * result + vel.contentHashCode()
return result
}
}
typealias SnapShot = List<Pair<Int, Int>>
class Orbits(val moons: List<Moon>) {
fun advanceOrbit() {
moons.forEach { moon ->
moon.applyGravity(moons)
}
moons.forEach { moon ->
moon.move()
}
}
fun totalEnergy() = moons.sumBy { it.totalEnergy() }
fun sameAs(original: Orbits): Boolean {
return moons.filterIndexed { index, moon ->
val orig = original.moons[index]
moon == orig
}.count() == moons.size
}
fun copy() = Orbits(moons.map { it.copy() })
fun snapShot(index: Int): SnapShot {
return moons.map { it.snapShot(index) }
}
fun makeSnapShot(): Map<Int, SnapShot> = (0..2).map { it to snapShot(it) }.toMap()
}
fun readBlock(line: String): Map<String, String> {
val tokens = StringTokenizer(line, "=,<>", true).toList().map { it as String }
var name = ""
var value = ""
val result = mutableMapOf<String, String>()
for (i in tokens.indices) {
when (tokens[i]) {
"=" -> {
name = tokens[i - 1].trim()
require(name.isNotEmpty()) { "Expected name to be not empty" }
value = tokens[i + 1].trim()
require(value.isNotEmpty()) { "Expected value for $name to be not empty" }
}
">", "," -> result[name] = value
else -> Unit
}
}
return result
}
fun readOrbits(lines: List<String>): Orbits {
return Orbits(lines.map { line ->
readBlock(line).map { it.key to it.value.toInt() }.toMap()
}.map {
arrayOf(it["x"] ?: error("Expected x"), it["y"] ?: error("expected y"), it["z"] ?: error("expected z")).toIntArray()
}.mapIndexed { i, pos ->
Moon(i, pos, arrayOf(0, 0, 0).toIntArray())
})
}
fun mapAxis(input: Map<String, String>): Axis {
return input.map {
it.key to it.value.toInt()
}.toMap().let {
arrayOf(it["x"] ?: error("expected x"), it["y"] ?: error("expected y"), it["z"] ?: error("expected z")).toIntArray()
}
}
fun readPosition(line: String): Pair<Axis, Axis> {
val position = mapAxis(readBlock(line.substringAfter("pos=").substringBefore(", vel=")))
val velocity = mapAxis(readBlock(line.substringAfter("vel=")))
return Pair(position, velocity)
}
// Find how often each axis cycles by comparing to a snapshot of the start.
fun findCycles(orbits: Orbits): List<Long> {
val snap = orbits.makeSnapShot().toMutableMap()
val cycle = mutableListOf<Long>()
var counter = 0L
do {
orbits.advanceOrbit()
counter++
for (x in 0..2) {
if (snap.containsKey(x) && snap[x] == orbits.snapShot(x)) {
println("Cycle[$x]=$counter")
cycle.add(counter)
snap.remove(x)
}
}
} while (snap.isNotEmpty())
return cycle
}
fun lowestCommonMultiplier(v1: BigInteger, v2: BigInteger): BigInteger {
return (v1 * v2).abs() / v1.gcd(v2)
}
// This will work for any number of values
fun lowestCommonMultiplier(list: List<BigInteger>): BigInteger {
return if (list.size == 2) {
lowestCommonMultiplier(list[0], list[1])
} else {
val lcds = mutableListOf<BigInteger>()
for (i in 0 until list.size - 1) {
lcds.add(lowestCommonMultiplier(list[i], list[i + 1]))
}
lowestCommonMultiplier(lcds)
}
}
fun main() {
val input = """
<x=14, y=2, z=8>
<x=7, y=4, z=10>
<x=1, y=17, z=16>
<x=-4, y=-1, z=1>
""".trimIndent()
val orbits = readOrbits(input.split('\n'))
val original = orbits.copy()
repeat(1000) {
orbits.advanceOrbit()
}
val totalEnergy = orbits.totalEnergy()
println("Total Energy=$totalEnergy")
// Ensure still valid after refactoring
require(totalEnergy == 9139)
val totalOrbits = lowestCommonMultiplier(findCycles(original).map { it.toBigInteger() })
println("Total = $totalOrbits")
// Ensure still valid after refactoring
require(totalOrbits == BigInteger("420788524631496"))
}Test Code
package com.github.corneil.aoc2019.day12
import assertk.assertThat
import assertk.assertions.isEqualTo
import org.junit.Test
class TestNBodyProblem {
@Test
fun test1() {
val input = """
<x=-1, y=0, z=2>
<x=2, y=-10, z=-7>
<x=4, y=-8, z=8>
<x=3, y=5, z=-1>
""".trimIndent()
val orbits = readOrbits(input.split('\n'))
val step0 = """
pos=<x=-1, y= 0, z= 2>, vel=<x= 0, y= 0, z= 0>
pos=<x= 2, y=-10, z=-7>, vel=<x= 0, y= 0, z= 0>
pos=<x= 4, y= -8, z= 8>, vel=<x= 0, y= 0, z= 0>
pos=<x= 3, y= 5, z=-1>, vel=<x= 0, y= 0, z= 0>
""".trimIndent()
assertPositionAndVelocity(orbits, step0.split('\n').map { readPosition(it) })
orbits.advanceOrbit()
val step1 = """
pos=<x= 2, y=-1, z= 1>, vel=<x= 3, y=-1, z=-1>
pos=<x= 3, y=-7, z=-4>, vel=<x= 1, y= 3, z= 3>
pos=<x= 1, y=-7, z= 5>, vel=<x=-3, y= 1, z=-3>
pos=<x= 2, y= 2, z= 0>, vel=<x=-1, y=-3, z= 1>
""".trimIndent()
assertPositionAndVelocity(orbits, step1.split('\n').map { readPosition(it) })
orbits.advanceOrbit()
val step2 = """
pos=<x= 5, y=-3, z=-1>, vel=<x= 3, y=-2, z=-2>
pos=<x= 1, y=-2, z= 2>, vel=<x=-2, y= 5, z= 6>
pos=<x= 1, y=-4, z=-1>, vel=<x= 0, y= 3, z=-6>
pos=<x= 1, y=-4, z= 2>, vel=<x=-1, y=-6, z= 2>
""".trimIndent()
assertPositionAndVelocity(orbits, step2.split('\n').map { readPosition(it) })
orbits.advanceOrbit()
val step3 = """
pos=<x= 5, y=-6, z=-1>, vel=<x= 0, y=-3, z= 0>
pos=<x= 0, y= 0, z= 6>, vel=<x=-1, y= 2, z= 4>
pos=<x= 2, y= 1, z=-5>, vel=<x= 1, y= 5, z=-4>
pos=<x= 1, y=-8, z= 2>, vel=<x= 0, y=-4, z= 0>
""".trimIndent()
assertPositionAndVelocity(orbits, step3.split('\n').map { readPosition(it) })
for (i in 4..10) {
orbits.advanceOrbit()
}
val step10 = """
pos=<x= 2, y= 1, z=-3>, vel=<x=-3, y=-2, z= 1>
pos=<x= 1, y=-8, z= 0>, vel=<x=-1, y= 1, z= 3>
pos=<x= 3, y=-6, z= 1>, vel=<x= 3, y= 2, z=-3>
pos=<x= 2, y= 0, z= 4>, vel=<x= 1, y=-1, z=-1>
""".trimIndent()
assertPositionAndVelocity(orbits, step10.split('\n').map { readPosition(it) })
val totalEnergy = orbits.totalEnergy()
assertThat(totalEnergy).isEqualTo(179)
}
@Test
fun test2() {
val input = """<x=-1, y=0, z=2>
<x=2, y=-10, z=-7>
<x=4, y=-8, z=8>
<x=3, y=5, z=-1>""".trimIndent()
val orbits = readOrbits(input.split('\n'))
val original = orbits.copy()
var count = 0
do {
orbits.advanceOrbit()
count++
} while (!orbits.sameAs(original))
println("Count=$count")
assertThat(count).isEqualTo(2772)
}
@Test
fun test3() {
val input = """<x=-1, y=0, z=2>
<x=2, y=-10, z=-7>
<x=4, y=-8, z=8>
<x=3, y=5, z=-1>""".trimIndent()
val orbits = readOrbits(input.split('\n'))
val count = lowestCommonMultiplier(findCycles(orbits).map { it.toBigInteger() })
println("Count=$count")
assertThat(count).isEqualTo(2772.toBigInteger())
}
@Test
fun test4() {
val input = """
<x=-8, y=-10, z=0>
<x=5, y=5, z=10>
<x=2, y=-7, z=3>
<x=9, y=-8, z=-3>
""".trimIndent()
val orbits = readOrbits(input.split('\n'))
val count = lowestCommonMultiplier(findCycles(orbits).map { it.toBigInteger() })
println("Count=$count")
assertThat(count).isEqualTo(4686774924.toBigInteger())
}
private fun assertPositionAndVelocity(
orbits: Orbits,
positions1: List<Pair<Axis, Axis>>
) {
orbits.moons.forEachIndexed { index, moon ->
assertThat(moon.pos).isEqualTo(positions1[index].first)
assertThat(moon.vel).isEqualTo(positions1[index].second)
}
}
}Day 13: kotlin
Care Package
Part 1
The first part was simple leveraging previous components.
Part 2
I used the JANSI library from http://fusesource.github.io/jansi/
to control screen output and added an output handler that only prints the modified cells.
I added a fetchHandler to provide the input keeping the paddle under the ball. Then I realized the program doesn’t stop running when all the blocks are cleared so I adapted the IntCode computer to exit waiting for input and then the next input is determined after checking if there are any blocks left.
Running
cd corneil
./gradlew :solution-day13:build
tar xvf ../day13/kotlin/corneil/build/distributions/solution-day13.tar
cp ../day13/kotlin/corneil/input.txt .
./solution-day13/bin/solution-day13
Solution Source
package com.github.corneil.aoc2019.day13
import com.github.corneil.aoc2019.day13.TILE.BALL
import com.github.corneil.aoc2019.day13.TILE.BLOCK
import com.github.corneil.aoc2019.day13.TILE.EMPTY
import com.github.corneil.aoc2019.day13.TILE.PADDLE
import com.github.corneil.aoc2019.day13.TILE.WALL
import com.github.corneil.aoc2019.intcode.Program
import com.github.corneil.aoc2019.intcode.readProgram
import org.fusesource.jansi.Ansi
import org.fusesource.jansi.Ansi.Color.BLACK
import org.fusesource.jansi.Ansi.Color.WHITE
import org.fusesource.jansi.Ansi.Erase.FORWARD
import org.fusesource.jansi.AnsiConsole
import java.io.File
enum class TILE(val tile: Int) {
EMPTY(0),
WALL(1),
BLOCK(2),
PADDLE(3),
BALL(4)
}
fun fromValue(input: Int): TILE {
for (v in TILE.values()) {
if (input == v.tile) {
return v
}
}
error("Invalid TILE $input")
}
data class Coord(val x: Int, val y: Int)
data class Cell(val pos: Coord, val tile: TILE)
data class Grid(var score: Int, val cells: MutableMap<Coord, Cell> = mutableMapOf()) {
fun setTile(pos: Coord, tile: TILE): Cell {
val cell = Cell(pos, tile)
cells[pos] = cell
return cell
}
fun hasBlocks(): Boolean {
return cells.values.any { it.tile == BLOCK }
}
fun findTile(tile: TILE): Coord {
return cells.values.find { it.tile == tile }?.pos ?: Coord(-1, -1)
}
}
fun printCell(cell: Cell) {
print(Ansi.ansi().saveCursorPosition().cursor(cell.pos.y, cell.pos.x))
when (cell.tile) {
EMPTY -> print(Ansi.ansi().render(" "))
WALL -> print(Ansi.ansi().render("#"))
BLOCK -> print(Ansi.ansi().bg(WHITE).fg(BLACK).render("$").reset())
PADDLE -> print(Ansi.ansi().render("_"))
BALL -> print(Ansi.ansi().render("o"))
}
print(Ansi.ansi().restoreCursorPosition())
}
fun determineInput(grid: Grid): Int {
val maxY = grid.cells.keys.maxBy { it.y }?.y ?: 40
val ball = grid.findTile(BALL)
val paddle = grid.findTile(PADDLE)
return when {
ball.x > paddle.x -> {
print(Ansi.ansi().cursor(maxY, 1).fgBlue().render(">> ").reset())
1
}
ball.x < paddle.x -> {
print(Ansi.ansi().cursor(maxY, 1).fgGreen().render("<< ").reset())
-1
}
else -> {
print(Ansi.ansi().cursor(maxY, 1).render(".. "))
0
}
}
}
fun runGame(code: List<Long>): Grid {
print(Ansi.ansi().eraseScreen())
val grid = Grid(0)
val program = Program(code)
val output = mutableListOf<Long>()
val state = program.executeProgram(emptyList()) {
// outputHandler
output.add(it)
if (output.size == 3) {
val x = output.removeAt(0).toInt()
val y = output.removeAt(0).toInt()
val tile = output.removeAt(0).toInt()
if (x == -1 && y == 0) {
grid.score = tile
print(Ansi.ansi().cursor(0, 0).render(grid.score.toString() + " ").eraseLine(FORWARD))
} else {
val cell = grid.setTile(Coord(x, y), fromValue(tile))
printCell(cell)
}
}
}
val input = mutableListOf<Long>()
do {
state.executeUntilInput(input)
input.clear()
if (grid.score > 0 && !grid.hasBlocks()) {
println(Ansi.ansi().eraseScreen().render("Score:${grid.score}!!"))
break
}
input.add(determineInput(grid).toLong())
} while (!state.isHalted())
return grid
}
fun main(args: Array<String>) {
AnsiConsole.systemInstall()
val fileName = if (args.size > 1) args[1] else "input.txt"
val code = readProgram(File(fileName))
val grid = runGame(code)
val tiles = grid.cells.count { it.value.tile == BLOCK }
println("Tiles = $tiles")
val free = code.toMutableList()
free[0] = 2L
runGame(free)
AnsiConsole.systemUninstall()
}Day 14: kotlin
Space Stoichiometry
Part 1
This was relatively easy and I was number 996 to get Star 1.
Part 2
This took a little longer. I had a mistake and it ran very long. Then I thought there was some trick to it. This led me astray for a while until I found the mistake and saw the straight forward solution doesn’t run that long.
I did add some optimisation to reduce the time.
Solution Source
package com.github.corneil.aoc2019.day14
import java.io.File
typealias ChemicalQty = Pair<Long, String>
data class ReactionFormula(val inputs: List<ChemicalQty>, val output: ChemicalQty)
fun readChemicalQty(it: String): ChemicalQty {
val tokens = it.trim().split(" ")
require(tokens.size == 2)
return ChemicalQty(tokens[0].toLong(), tokens[1].trim())
}
fun readReaction(input: String): ReactionFormula {
val inputs = input.substringBefore("=>").split(",").map {
readChemicalQty(it)
}
return ReactionFormula(inputs, readChemicalQty(input.substringAfter("=>")))
}
fun readReactions(input: List<String>) = input.map { readReaction(it) }
fun add(value: MutableMap<String, Long>, output: ChemicalQty) {
val qty = value[output.second]
if (qty != null) {
value[output.second] = qty + output.first
} else {
value[output.second] = output.first
}
}
fun produce(
output: ChemicalQty,
formulae: Map<String, ReactionFormula>,
sideEffect: MutableMap<String, Long>,
used: MutableMap<String, Long>
) {
val remain = sideEffect[output.second]
if (remain != null && remain > 0L) {
useRemainingChemicals(remain, output, formulae, sideEffect, used)
} else {
val formula = formulae[output.second]
if (formula != null) {
applyFormula(output, formula, formulae, sideEffect, used)
} else {
// This is usually the ORE
add(used, output)
}
}
}
fun useRemainingChemicals(
remain: Long,
output: ChemicalQty,
formulae: Map<String, ReactionFormula>,
sideEffect: MutableMap<String, Long>,
used: MutableMap<String, Long>
) {
if (remain >= output.first) {
val qty = remain - output.first
sideEffect[output.second] = qty
require(qty >= 0) { "Expected Qty to be zero or greater for ${output.second} not $qty" }
} else {
sideEffect.remove(output.second)
produce(ChemicalQty(output.first - remain, output.second), formulae, sideEffect, used)
}
}
fun applyFormula(
output: ChemicalQty,
formula: ReactionFormula,
formulae: Map<String, ReactionFormula>,
sideEffect: MutableMap<String, Long>,
used: MutableMap<String, Long>
) {
val repeats = if (output.first < formula.output.first) {
1L
} else {
output.first / formula.output.first +
if (output.first % formula.output.first == 0L) 0L else 1L
}
val produced = apply(formula, repeats, formulae, sideEffect, used)
if (output.first < produced.first) {
sideEffect[output.second] = produced.first - output.first
}
}
fun apply(
formula: ReactionFormula,
repeats: Long,
formulae: Map<String, ReactionFormula>,
sideEffect: MutableMap<String, Long>,
used: MutableMap<String, Long>
): ChemicalQty {
formula.inputs.forEach {
produce(ChemicalQty(it.first * repeats, it.second), formulae, sideEffect, used)
}
return ChemicalQty(formula.output.first * repeats, formula.output.second)
}
fun determineInputForOutput(input: String, output: ChemicalQty, formulae: List<ReactionFormula>): Long {
val formula = formulae.map { it.output.second to it }.toMap()
val used = mutableMapOf<String, Long>()
val sideEffect = mutableMapOf<String, Long>()
produce(output, formula, sideEffect, used)
println("$output = $used, Side Effects = $sideEffect")
return used[input] ?: 0L
}
fun executeReactions(
increment: Long,
input: ChemicalQty,
output: String,
formula: Map<String, ReactionFormula>,
used: MutableMap<String, Long>
): Pair<Long, Long> {
val sideEffect = mutableMapOf<String, Long>()
var inc = increment
var counter = 0L
while (input.first > used[input.second] ?: 0L) {
produce(ChemicalQty(inc, output), formula, sideEffect, used)
counter += inc
if (counter % 10000L == 0L) {
print("produce $output for $input = $counter\r")
}
val usedSoFar = used[input.second] ?: 0L
if (inc == 100L && (10L * usedSoFar / input.first > 7L)) {
inc = 10L
} else if (inc == 10L && (10L * usedSoFar / input.first > 8L)) {
inc = 1L
}
}
println("Used = $used, Side Effect = $sideEffect")
return Pair(counter, inc)
}
fun determineOuputForInput(input: ChemicalQty, output: String, formulae: List<ReactionFormula>): Long {
val formula = formulae.map { it.output.second to it }.toMap()
val used = mutableMapOf<String, Long>()
var increment = 1000L // Start with 100 and drop down to save some time
var counter: Long
do {
increment /= 10L
val pair = executeReactions(increment, input, output, formula, used)
counter = pair.first
increment = pair.second
} while (increment > 1L) // If last increment isn't 1 redo
val result = if (used[input.second] == input.first) counter else counter - 1L
println("output $input = $result")
return result
}
fun main(args: Array<String>) {
val fileName = if (args.size > 1) args[0] else "input.txt"
val formulae = readReactions(File(fileName).readLines())
val output = determineInputForOutput("ORE", ChemicalQty(1L, "FUEL"), formulae)
println("Output = ORE = $output")
require(output == 612880L) // ensure check for refactoring
val fuel = determineOuputForInput(ChemicalQty(1000000000000L, "ORE"), "FUEL", formulae)
println("Fuel = $fuel")
require(fuel == 2509120L)
}Test Code
package com.github.corneil.aoc2019.day14
import assertk.assertThat
import assertk.assertions.isEqualTo
import org.junit.Test
class TestStoichiometry {
@Test
fun test1() {
val input = """
10 ORE => 10 A
1 ORE => 1 B
7 A, 1 B => 1 C
7 A, 1 C => 1 D
7 A, 1 D => 1 E
7 A, 1 E => 1 FUEL
""".trimIndent()
val formulae = readReactions(input.split('\n'))
val output = determineInputForOutput("ORE", ChemicalQty(1L, "FUEL"), formulae)
assertThat(output).isEqualTo(31L)
}
@Test
fun test2() {
val input = """
9 ORE => 2 A
8 ORE => 3 B
7 ORE => 5 C
3 A, 4 B => 1 AB
5 B, 7 C => 1 BC
4 C, 1 A => 1 CA
2 AB, 3 BC, 4 CA => 1 FUEL
""".trimIndent()
val formulae = readReactions(input.split('\n'))
val output = determineInputForOutput("ORE", ChemicalQty(1L, "FUEL"), formulae)
assertThat(output).isEqualTo(165L)
}
@Test
fun test3() {
val input = """
157 ORE => 5 NZVS
165 ORE => 6 DCFZ
44 XJWVT, 5 KHKGT, 1 QDVJ, 29 NZVS, 9 GPVTF, 48 HKGWZ => 1 FUEL
12 HKGWZ, 1 GPVTF, 8 PSHF => 9 QDVJ
179 ORE => 7 PSHF
177 ORE => 5 HKGWZ
7 DCFZ, 7 PSHF => 2 XJWVT
165 ORE => 2 GPVTF
3 DCFZ, 7 NZVS, 5 HKGWZ, 10 PSHF => 8 KHKGT
""".trimIndent()
val formulae = readReactions(input.split('\n'))
val output = determineInputForOutput("ORE", ChemicalQty(1L, "FUEL"), formulae)
assertThat(output).isEqualTo(13312L)
val fuel = determineOuputForInput(ChemicalQty(1000000000000L, "ORE"), "FUEL", formulae)
assertThat(fuel).isEqualTo(82892753L)
}
@Test
fun test4() {
val input = """
2 VPVL, 7 FWMGM, 2 CXFTF, 11 MNCFX => 1 STKFG
17 NVRVD, 3 JNWZP => 8 VPVL
53 STKFG, 6 MNCFX, 46 VJHF, 81 HVMC, 68 CXFTF, 25 GNMV => 1 FUEL
22 VJHF, 37 MNCFX => 5 FWMGM
139 ORE => 4 NVRVD
144 ORE => 7 JNWZP
5 MNCFX, 7 RFSQX, 2 FWMGM, 2 VPVL, 19 CXFTF => 3 HVMC
5 VJHF, 7 MNCFX, 9 VPVL, 37 CXFTF => 6 GNMV
145 ORE => 6 MNCFX
1 NVRVD => 8 CXFTF
1 VJHF, 6 MNCFX => 4 RFSQX
176 ORE => 6 VJHF
""".trimIndent()
val formulae = readReactions(input.split('\n'))
val output = determineInputForOutput("ORE", ChemicalQty(1L, "FUEL"), formulae)
assertThat(output).isEqualTo(180697L)
val fuel = determineOuputForInput(ChemicalQty(1000000000000L, "ORE"), "FUEL", formulae)
assertThat(fuel).isEqualTo(5586022L)
}
@Test
fun test5() {
val input = """
171 ORE => 8 CNZTR
7 ZLQW, 3 BMBT, 9 XCVML, 26 XMNCP, 1 WPTQ, 2 MZWV, 1 RJRHP => 4 PLWSL
114 ORE => 4 BHXH
14 VRPVC => 6 BMBT
6 BHXH, 18 KTJDG, 12 WPTQ, 7 PLWSL, 31 FHTLT, 37 ZDVW => 1 FUEL
6 WPTQ, 2 BMBT, 8 ZLQW, 18 KTJDG, 1 XMNCP, 6 MZWV, 1 RJRHP => 6 FHTLT
15 XDBXC, 2 LTCX, 1 VRPVC => 6 ZLQW
13 WPTQ, 10 LTCX, 3 RJRHP, 14 XMNCP, 2 MZWV, 1 ZLQW => 1 ZDVW
5 BMBT => 4 WPTQ
189 ORE => 9 KTJDG
1 MZWV, 17 XDBXC, 3 XCVML => 2 XMNCP
12 VRPVC, 27 CNZTR => 2 XDBXC
15 KTJDG, 12 BHXH => 5 XCVML
3 BHXH, 2 VRPVC => 7 MZWV
121 ORE => 7 VRPVC
7 XCVML => 6 RJRHP
5 BHXH, 4 VRPVC => 5 LTCX
""".trimIndent()
val formulae = readReactions(input.split('\n'))
val output = determineInputForOutput("ORE", ChemicalQty(1L,"FUEL"), formulae)
assertThat(output).isEqualTo(2210736L)
val fuel = determineOuputForInput(ChemicalQty(1000000000000L, "ORE"), "FUEL", formulae)
assertThat(fuel).isEqualTo(460664L)
}
}Day 15: kotlin
Oxygen System
Part 1
After spending half a day trying to get it working with the wrong input file, I eventually realized I need to just walk the maze with a simple strategy to discover the structure and then use a Graph shortest path algorithm to solve.
I found a reasonable implementation of Dijkstra’s algoritm at http://rosettacode.org/wiki/Dijkstra%27s_algorithm#Kotlin I made if Generic so now I can reuse as I need.
Run with -p to see the robot walk the maze.
Solution Source
package com.github.corneil.aoc2019.day15
import com.github.corneil.aoc2019.common.Graph
import com.github.corneil.aoc2019.common.Graph.Edge
import com.github.corneil.aoc2019.day15.DIRECTION.EAST
import com.github.corneil.aoc2019.day15.DIRECTION.NORTH
import com.github.corneil.aoc2019.day15.DIRECTION.SOUTH
import com.github.corneil.aoc2019.day15.DIRECTION.WEST
import com.github.corneil.aoc2019.day15.RobotStatus.MOVED
import com.github.corneil.aoc2019.day15.RobotStatus.OXYGEN
import com.github.corneil.aoc2019.day15.RobotStatus.UNKNOWN
import com.github.corneil.aoc2019.day15.RobotStatus.WALL
import com.github.corneil.aoc2019.day15.STRATEGY.ALTERNATE
import com.github.corneil.aoc2019.day15.STRATEGY.LEFT
import com.github.corneil.aoc2019.day15.STRATEGY.RANDOM
import com.github.corneil.aoc2019.day15.STRATEGY.RIGHT
import com.github.corneil.aoc2019.intcode.Program
import com.github.corneil.aoc2019.intcode.readProgram
import org.fusesource.jansi.Ansi
import org.fusesource.jansi.AnsiConsole
import java.io.File
import kotlin.random.Random
data class Coord(val x: Int, val y: Int) : Comparable<Coord> {
override fun compareTo(other: Coord): Int {
var result = y.compareTo(other.y)
if (result == 0) {
result = x.compareTo(other.x)
}
return result
}
fun move(direction: DIRECTION): Coord {
return when (direction) {
NORTH -> copy(y = y - 1)
SOUTH -> copy(y = y + 1)
EAST -> copy(x = x + 1)
WEST -> copy(x = x - 1)
}
}
}
enum class DIRECTION(val value: Int) {
NORTH(1),
SOUTH(2),
WEST(3),
EAST(4);
fun nextLeft(): DIRECTION = when (this) {
NORTH -> WEST
WEST -> SOUTH
SOUTH -> EAST
EAST -> NORTH
}
fun nextRight(): DIRECTION = when (this) {
NORTH -> EAST
EAST -> SOUTH
SOUTH -> WEST
WEST -> NORTH
}
}
enum class STRATEGY {
LEFT,
RIGHT,
ALTERNATE,
RANDOM
}
fun direction(direction: DIRECTION): String {
return when (direction) {
NORTH -> "^"
WEST -> "<"
SOUTH -> "v"
EAST -> ">"
}
}
fun directionFrom(input: Int): DIRECTION {
return DIRECTION.values().find { it.value == input } ?: error("Invalid direction $input")
}
enum class RobotStatus(val input: Int) {
WALL(0),
MOVED(1),
OXYGEN(2),
UNKNOWN(-1)
}
fun robotStatusFrom(input: Int): RobotStatus {
return RobotStatus.values().find { it.input == input } ?: error("Invalid RobotStatus $input")
}
val random = Random(System.currentTimeMillis())
data class Cell(val pos: Coord, val status: RobotStatus, var visits: Int = 0)
class Robot(
var location: Coord,
dir: DIRECTION,
var prevLocation: Coord = Coord(0, 0),
var prev: DIRECTION = NORTH,
var moves: Int = 0,
var prevChoice: Boolean = false
) {
var direction: DIRECTION = dir
set(value) {
prev = direction
field = value
}
fun move() {
prevLocation = location
location = location.move(direction)
moves += 1
}
fun next(strategy: STRATEGY): DIRECTION {
prev = direction
return when (strategy) {
LEFT -> direction.nextLeft()
RIGHT -> direction.nextRight()
ALTERNATE -> {
val choice = if (prevChoice) direction.nextRight() else direction.nextLeft()
prevChoice = !prevChoice
choice
}
RANDOM -> directionFrom(random.nextInt(4) + 1)
}
}
}
data class Grid(
val cells: MutableMap<Coord, Cell> = mutableMapOf(),
var maxX: Int = 0,
var minX: Int = 0,
var maxY: Int = 0,
var minY: Int = 0
) {
fun determineSize() {
maxX = (cells.keys.maxBy { it.x }?.x ?: 0)
minX = (cells.keys.minBy { it.x }?.x ?: 0)
maxY = (cells.keys.maxBy { it.y }?.y ?: 0)
minY = (cells.keys.minBy { it.y }?.y ?: 0)
}
fun printCell(cell: Cell, robot: Robot) {
when {
cell.status == UNKNOWN -> print(" ")
cell.pos == robot.location &&
cell.status == WALL -> print("%")
cell.status == WALL -> print("#")
cell.pos == robot.location &&
cell.status == MOVED -> print(direction(robot.direction))
cell.status == MOVED -> print(".")
cell.status == OXYGEN -> print("O")
}
}
fun printGrid(robot: Robot) {
determineSize()
print(Ansi.ansi().eraseScreen().cursor(1, 1))
for (y in minY..maxY) {
for (x in minX..maxX) {
val location = Coord(x, y)
val cell = cells[location] ?: Cell(location, UNKNOWN)
printCell(cell, robot)
}
println()
}
}
fun setStatus(pos: Coord, status: RobotStatus): Cell {
val cell = cells[pos] ?: Cell(pos, status)
if (status != UNKNOWN) {
cell.visits += 1
}
cells[pos] = cell
return cell
}
fun findPosition(robot: Robot, direction: DIRECTION): Coord {
return robot.location.move(direction)
}
fun goStraightOrFindOpen(robot: Robot): DIRECTION {
val location = findPosition(robot, robot.direction)
val cell = cells[location] ?: Cell(location, UNKNOWN)
if (cell.status == UNKNOWN) {
return robot.direction
}
return findOpenSpace(robot)
}
fun findOpenSpace(robot: Robot): DIRECTION {
var test = robot.direction
val tried = mutableSetOf<Cell>()
val valid = mutableSetOf<Pair<DIRECTION, Cell>>()
do {
val location = findPosition(robot, test)
val cell = cells[location] ?: Cell(location, UNKNOWN)
tried.add(cell)
if (cell.status == MOVED || cell.status == UNKNOWN) {
valid.add(Pair(test, cell))
}
test = test.nextRight()
} while (test != robot.direction)
if (valid.isNotEmpty()) {
return findMinVisit(valid)
}
error("Cannot move from ${robot.location} tried:$tried")
}
fun findMinVisit(valid: Collection<Pair<DIRECTION, Cell>>): DIRECTION {
val minVisit = valid.minBy { it.second.visits }!!
val minVisits = valid.filter { it.second.visits == minVisit.second.visits }
if (minVisits.size > 1) {
return minVisits[random.nextInt(minVisits.size)].first
}
return minVisit.first
}
fun modified(maxX: Int, minX: Int, maxY: Int, minY: Int): Boolean {
return this.maxX != maxX || this.minX != minX || this.maxY != maxY || this.minY != minY
}
fun isComplete(): Boolean {
determineSize()
val width = maxX - minX
val height = maxY - minY
val hasOxygen = cells.values.any { it.status == OXYGEN }
return width * height == cells.size && hasOxygen
}
}
fun determinResponse(grid: Grid, robot: Robot, status: RobotStatus, strategy: STRATEGY): Int {
grid.setStatus(grid.findPosition(robot, robot.direction), status)
if (status != WALL) {
robot.move()
}
return when (status) {
OXYGEN, MOVED -> grid.goStraightOrFindOpen(robot).value
WALL -> grid.findOpenSpace(robot).value
else -> error("Unexpected response:$status")
}
}
fun printGrid(grid: Grid, robot: Robot, cell: Cell?, printAll: Boolean) {
val maxX = (grid.cells.keys.maxBy { it.x }?.x ?: 0)
val minX = (grid.cells.keys.minBy { it.x }?.x ?: 0)
val maxY = (grid.cells.keys.maxBy { it.y }?.y ?: 0)
val minY = (grid.cells.keys.minBy { it.y }?.y ?: 0)
if (printAll || grid.modified(maxX, minX, maxY, minY)) {
grid.printGrid(robot)
} else {
if (cell != null) {
print(Ansi.ansi().cursor(cell.pos.y - minY + 1, cell.pos.x - minX + 1))
grid.printCell(cell, robot)
}
}
val totalVisits = grid.cells.values.sumBy { it.visits }
print(Ansi.ansi().cursor(maxY - minY + 2, 1).render("Total Visits:$totalVisits, Cells = ${grid.cells.size}"))
}
data class OperationRecord(val start: Coord, val direction: DIRECTION, val response: RobotStatus, val end: Coord)
fun discoverGrid(
printOutput: Boolean,
code: List<Long>,
initial: DIRECTION,
strategy: STRATEGY,
grid: Grid
): List<OperationRecord> {
print(Ansi.ansi().eraseScreen())
val robot = Robot(Coord(0, 0), initial)
val program = Program(code).createProgram()
val record = mutableListOf<OperationRecord>()
do {
if (printOutput) {
printGrid(grid, robot, grid.cells[robot.prevLocation], false)
printGrid(grid, robot, grid.cells[robot.location], false)
}
val start = robot.location
val initialDirection = robot.direction
val output = program.executeUntilOutput(listOf(initialDirection.value.toLong()))
val response = robotStatusFrom(output.first().toInt())
val direction = determinResponse(grid, robot, response, strategy)
robot.direction = directionFrom(direction)
record.add(OperationRecord(start, initialDirection, response, robot.location))
if (printOutput) {
printGrid(grid, robot, grid.cells[robot.prevLocation.move(robot.prev)], false)
}
} while (!grid.isComplete())
printGrid(grid, robot, grid.cells[robot.location], true)
return record
}
fun main(args: Array<String>) {
var printOutput = false
AnsiConsole.systemInstall()
if (args.contains("-p")) {
printOutput = true
}
val code = readProgram(File("input.txt"))
var grid = Grid()
val edges = mutableListOf<Edge<Coord>>()
val result = discoverGrid(printOutput, code, NORTH, LEFT, grid)
result.forEach { record ->
edges.add(Edge(record.start, record.end, 1))
}
var oxygenLocation = result.find { it.response == OXYGEN }?.end
requireNotNull(oxygenLocation) { "Could not find Oxygen" }
val spaces = result.filter { it.response == MOVED || it.response == OXYGEN }.map { it.end }
println("\nRecords=${result.size}")
println("Edges=${edges.size}")
val robotLocation = result.first().start
val graph = Graph(edges, true)
val path = graph.findPath(robotLocation, oxygenLocation!!)
println("From ${path.first()} -> ${path.last()}")
val moves = path.last().second
println("Moves=$moves")
require(moves == 250)
val graph2 = Graph(edges, true)
graph2.dijkstra(oxygenLocation)
val distances = spaces.mapNotNull {
val path = graph2.findPath(it)
path.lastOrNull()
}
val furthest = distances.maxBy { it.second }
println("Furthest=$furthest")
val minutes = furthest!!.second
println("Minutes = $minutes")
require(minutes == 332)
AnsiConsole.systemUninstall()
}Day 16: kotlin
Flawed Frequency Transmission
Part 1
I got to the first part in about an hour
Part 2
After seeing that we now have input of 650 characters that has to be repeated 10000 times to be the input signal I realized that 42Â 249Â 993Â 500Â 000 calculations for a single phase is going to be a problem.
It looks like the name FFT is the hint because there are parts of Fast fourier transform that uses a technique called Chinese number theorem to reduce the number of calculations.
I just need to figure out how it works. It is a public holiday. My brain is also on holiday. Will revisit this when I feel sharper.
Turns out that because of the size the mutliplier from the base pattern isn’t in the picture. It becomes like an inverted Pascal tower. Accumulating from the end include the digit before the offset.
Solution Source
package com.github.corneil.aoc2019.day16
import kotlin.math.abs
val basePattern = arrayOf(0, 1, 0, -1).toIntArray()
val bpLen = basePattern.size
inline fun expand(index: Int, pos: Int): Int {
val offset = ((index + 1) / pos % bpLen)
return basePattern[offset]
}
fun calculatePhasePart(value: String, offset: Int): String {
val input = (offset until value.length).map { index ->
value[index].toString().toLong()
}.toMutableList()
val result = StringBuilder(value.length)
result.append(value.substring(0 until offset))
for (i in (input.size - 2) downTo 0) {
input[i] = abs(input[i] + input[i + 1]) % 10L
}
input.forEach {
result.append(it)
}
return result.toString()
}
fun calculatePhase(value: String): String {
val input = value.map { it.toString().toLong() }.toTypedArray().toLongArray()
var result = StringBuilder()
val size = input.size
for (pos in 1..size) {
var line = 0L
for (index in 0 until size) {
val mul = expand(index, pos)
if (mul != 0) {
line += input[index % input.size] * mul.toLong()
}
}
result.append(abs(line) % 10L)
}
return result.toString()
}
fun calculatePhases(value: String, phases: Int): String {
var input = value
var phase = 0
repeat(phases) {
phase += 1
print("Phase=$phase:${input.length}\r")
input = calculatePhase(input)
require(input.length == value.length)
}
println("Phase=$phase:${input.length}")
return input
}
fun calculatePhasesPart(value: String, phases: Int, offset: Int): String {
var input = value
repeat(phases) {
input = calculatePhasePart(input, offset)
}
return input
}
fun createSignal(input: String, repeats: Int): String {
val result = StringBuilder()
repeat(repeats) {
result.append(input)
}
return result.toString()
}
fun interpretSignal(input: String): String {
val offset = input.substring(0, 7).toInt()
val signal = createSignal(input, 10000)
val message = calculatePhasesPart(signal, 100, offset)
return message.substring(offset until offset + 8)
}
fun main(args: Array<String>) {
val input =
"59796332430280528211060657577039744056609636505111313336094865900635343682296702094018432765613019371234483818415934914575717134617783515237300919201989706451524069044921384738930172026234872525254689609787752401342687098918804210494391161531008341329016626922990938854681575317559821067933058630688365067790812341475168200215494963690593873250884807840611487288560291748414160551508979374335267106414602526249401281066501677212002980616711058803845336067123298983258010079178111678678796586176705130938139337603538683803154824502761228184209473344607055926120829751532887810487164482307564712692208157118923502010028250886290873995577102178526942152"
val result = calculatePhases(input, 100)
val answer1 = result.substring(0, 8)
println("Result=$answer1")
require(answer1 == "36627552") // ensure not broken
val answer2 = interpretSignal(input)
println("Message=$answer2")
require(answer2 == "79723033") // Ensure not broken
}Test Code
package com.github.corneil.aoc2019.day16
import assertk.assertThat
import assertk.assertions.isEqualTo
import org.junit.Test
class TestFFT {
@Test
fun testExpandShift() {
val expanded = (0 until 12).map { expand(it, 2) }
assertThat(expanded).isEqualTo(listOf(0, 1, 1, 0, 0, -1, -1, 0, 0, 1, 1, 0))
val expanded2 = (0 until 12).map { expand(it, 3) }
assertThat(expanded2).isEqualTo(listOf(0, 0, 1, 1, 1, 0, 0, 0, -1, -1, -1, 0))
}
@Test
fun test1() {
val input = "12345678"
val p1 = calculatePhase(input)
assertThat(p1).isEqualTo("48226158")
val p2 = calculatePhase(p1)
assertThat(p2).isEqualTo("34040438")
val p3 = calculatePhase(p2)
assertThat(p3).isEqualTo("03415518")
val p4 = calculatePhase(p3)
assertThat(p4).isEqualTo("01029498")
}
@Test
fun test2() {
val result = calculatePhases("80871224585914546619083218645595", 100)
assertThat(result.substring(0, 8)).isEqualTo("24176176")
val result2 = calculatePhases("19617804207202209144916044189917", 100)
assertThat(result2.substring(0, 8)).isEqualTo("73745418")
val result3 = calculatePhases("69317163492948606335995924319873", 100)
assertThat(result3.substring(0, 8)).isEqualTo("52432133")
}
@Test
fun test3() {
val result = interpretSignal("03036732577212944063491565474664")
assertThat(result).isEqualTo("84462026")
}
@Test
fun test4() {
val result = interpretSignal("02935109699940807407585447034323")
assertThat(result).isEqualTo("78725270")
}
@Test
fun test5() {
val result = interpretSignal("03081770884921959731165446850517")
assertThat(result).isEqualTo("53553731")
}
}Day 17: kotlin
Set and Forget
Part 1
First part went quick. My algorithm found 7 solutions for the sample input.
Part 2
I had a solution that I could trace by hand but it would fail all the time. Eventually I created a new instance of the program before executing the cleaning program and it worked!
Solution Source
package com.github.corneil.aoc2019.day17
import com.github.corneil.aoc2019.common.Combinations
import com.github.corneil.aoc2019.intcode.Program
import com.github.corneil.aoc2019.intcode.ProgramState
import com.github.corneil.aoc2019.intcode.readProgram
import java.io.File
import java.io.PrintWriter
import java.io.StringWriter
import kotlin.math.abs
data class Robot(val pos: Coord, val direction: Char)
data class Coord(val x: Int, val y: Int) {
fun left() = copy(x = x - 1)
fun right() = copy(x = x + 1)
fun top() = copy(y = y - 1)
fun bottom() = copy(y = y + 1)
fun surrounds() = listOf(left(), right(), top(), bottom())
fun north(distance: Int) = copy(y = y - distance)
fun south(distance: Int) = copy(y = y + distance)
fun west(distance: Int) = copy(x = x - distance)
fun east(distance: Int) = copy(x = x + distance)
fun distance(target: Coord): Int = abs(target.x - x) + abs(target.y - y)
}
data class Movement(val movement: Char, val distance: Int) {
fun output() = if (movement.toInt() != 0) "$movement,$distance" else "$distance"
}
data class CleaningProgram(val mainRoutine: List<Char>, val subroutines: Map<Char, List<Movement>>) {
init {
require(mainRoutine.toSet() == subroutines.keys)
}
fun printToString(): String {
val sw = StringWriter()
sw.use {
PrintWriter(it).use { pw ->
val main = mainString()
pw.println("Main Routine=${main}: ${createIntCodeInput(main)}")
names().forEach { name ->
val functionString = subRoutine(name)
val functionInput = createIntCodeInput(functionString)
pw.println("Function $name: $functionString: $functionInput")
}
}
}
return sw.toString()
}
fun names() = subroutines.keys.toList().sorted()
fun mainString(): String = mainRoutine.joinToString(",")
fun subRoutine(name: Char): String =
(subroutines[name] ?: error("Expected $name in $subroutines")).joinToString(",") { it.output() }
fun movements(): List<Movement> {
return mainRoutine.flatMap { subroutines[it] ?: error("Expected $it in $subroutines") }
}
}
class Grid(val cells: MutableMap<Coord, Char> = mutableMapOf()) {
fun printToString(): String {
val sw = StringWriter()
sw.use {
PrintWriter(sw).use { pw ->
val maxY = cells.keys.maxBy { it.y }?.y ?: 0
val maxX = cells.keys.maxBy { it.x }?.x ?: 0
for (y in 0..maxY) {
for (x in 0..maxX) {
val cell = cells[Coord(x, y)] ?: ' '
pw.print(cell)
}
pw.println()
}
}
}
return sw.toString()
}
}
fun loadGrid(output: List<Long>): Grid {
val grid = Grid()
var x = 0
var y = 0
output.forEach { out ->
if (out == 10L) {
x = 0
y += 1
} else {
val coord = Coord(x, y)
x += 1
grid.cells[coord] = out.toChar()
}
}
return grid
}
fun isScaffold(c: Char) = when (c) {
'#', '^', '>', 'v', '<' -> true
else -> false
}
fun isRobot(c: Char) = when (c) {
'^', '>', 'v', '<' -> true
else -> false
}
fun isIntersection(coord: Coord, grid: Grid): Boolean {
val left = grid.cells[coord.left()] ?: ' '
val right = grid.cells[coord.right()] ?: ' '
val top = grid.cells[coord.top()] ?: ' '
val bottom = grid.cells[coord.bottom()] ?: ' '
return isScaffold(left) && isScaffold(right) && isScaffold(top) && isScaffold(bottom)
}
fun calculateAlignment(grid: Grid): Long {
val intersections = grid.cells.filter { isScaffold(it.value) && isIntersection(it.key, grid) }
return intersections.keys.map { it.x * it.y }.sum().toLong()
}
fun robotLocation(grid: Grid): Coord {
val locs = grid.cells.filter { isRobot(it.value) }
require(locs.size == 1)
return locs.keys.first()
}
fun turnLeft(direction: Char): Char {
return when (direction) {
'^' -> '<'
'>' -> '^'
'v' -> '>'
'<' -> 'v'
else -> error("Invalid direction $direction")
}
}
fun turnRight(direction: Char): Char {
return when (direction) {
'^' -> '>'
'>' -> 'v'
'v' -> '<'
'<' -> '^'
else -> error("Invalid direction $direction")
}
}
fun nextMovement(direction: Char, movement: Char): Char {
return if (movement == 'L') {
turnLeft(direction)
} else {
turnRight(direction)
}
}
fun determineMovement(robotDirection: Char, direction: Char): Char {
return when {
robotDirection == direction -> 0.toChar()
turnLeft(robotDirection) == direction -> 'L'
turnRight(robotDirection) == direction -> 'R'
else -> '*'
}
}
fun determineDirection(robot: Coord, next: Coord): Char {
return when {
robot.x == next.x && next.y > robot.y -> 'v'
robot.x == next.x && next.y < robot.y -> '^'
robot.y == next.y && next.x > robot.x -> '>'
robot.y == next.y && next.x < robot.x -> '<'
else -> error("Expect difference $robot, $next")
}
}
fun isValidDirection(robotDirection: Char, robot: Coord, next: Coord): Boolean {
val direction = determineDirection(robot, next)
return determineMovement(robotDirection, direction) != '*'
}
fun scaffoldDirection(robot: Robot, grid: Grid): Movement? {
val surrounds = robot.pos.surrounds().toSet()
val potential = grid.cells.filter {
surrounds.contains(it.key)
}.filter {
isScaffold(it.value)
}.filter {
isValidDirection(robot.direction, robot.pos, it.key)
}.toMutableMap()
val movements = potential.map {
createMovementUntilEnd(robot, it.key, grid)
}
if (movements.size > 1) {
println("Found multiple movements:$movements")
}
return movements.maxBy { it.distance }
}
fun createMovementUntilEnd(robot: Robot, next: Coord, grid: Grid): Movement {
val diffX = next.x - robot.pos.x
val diffY = next.y - robot.pos.y
var step = Coord(next.x + diffX, next.y + diffY)
while (isScaffold(grid.cells[step] ?: ' ')) {
step = step.copy(x = step.x + diffX, y = step.y + diffY)
}
val movement = determineMovement(robot.direction, determineDirection(robot.pos, next))
return Movement(movement, step.distance(next))
}
fun determineRouteInstructions(grid: Grid): List<Movement> {
val result = mutableListOf<Movement>()
val robotLocation = robotLocation(grid)
val robotDirection = grid.cells[robotLocation] ?: error("Expected robot at $robotLocation")
var robot = Robot(robotLocation, robotDirection)
do {
val direction = scaffoldDirection(robot, grid)
if (direction == null) {
println("End = $robot")
break
}
result.add(direction)
robot = walk(robot, direction)
} while (true)
return result
}
fun walk(robot: Robot, direction: Movement): Robot {
val newDirection = nextMovement(robot.direction, direction.movement)
val newLocation = when (newDirection) {
'^' -> robot.pos.north(direction.distance)
'>' -> robot.pos.east(direction.distance)
'v' -> robot.pos.south(direction.distance)
'<' -> robot.pos.west(direction.distance)
else -> error("Invalid direction $newDirection")
}
return Robot(newLocation, newDirection)
}
data class Attempt(var name: Char, val movements: List<Movement>) {
fun output() = movements.joinToString(",") { it.output() }
fun len() = output().length
override fun equals(other: Any?): Boolean {
if (this === other) return true
if (javaClass != other?.javaClass) return false
other as Attempt
if (movements != other.movements) return false
return true
}
override fun hashCode(): Int {
return movements.hashCode()
}
}
fun attemptMove(attempt: Attempt, movements: List<Movement>): Boolean {
if (attempt.movements.size <= movements.size) {
val compare = movements.subList(0, attempt.movements.size)
return attempt.movements == compare
}
return false
}
fun attemptRoute(sets: Set<Attempt>, movements: List<Movement>): Pair<Boolean, List<Char>> {
for (attempt in sets) {
if (attemptMove(attempt, movements)) {
if (attempt.movements.size == movements.size) {
return Pair(true, listOf(attempt.name))
}
val attemptMovements = movements.subList(attempt.movements.size, movements.lastIndex + 1)
val result = attemptRoute(sets, attemptMovements)
if (result.first) {
return Pair(true, listOf(attempt.name) + result.second)
}
}
}
return Pair(false, emptyList())
}
fun checkValidAndResults(sets: Set<Attempt>, movements: List<Movement>): Pair<Boolean, List<Attempt>> {
val attemptMap = sets.map { it.name to it }.toMap()
val result = attemptRoute(sets, movements)
return Pair(result.first, result.second.map { attemptMap[it] ?: error("Expected $it in $attemptMap") })
}
fun createIntCodeInput(functionString: String) = functionString.map { it.toLong() } + 10L
fun createCleaningProgram(instructionSet: Pair<Set<Attempt>, List<Attempt>>): CleaningProgram {
val names = instructionSet.first.map { it to it.name }.toMap()
require(instructionSet.second.all { names.keys.contains(it) })
require(names.size == names.size)
val mainRoutine = instructionSet.second.map { names[it] ?: error("Expected $it in $names") }
require(mainRoutine.toSet().size == names.size)
val subroutines = names.keys.map { it.name to it.movements }.toMap()
return CleaningProgram(mainRoutine, subroutines)
}
fun findRepeating(
totalSets: Int,
maxOutput: Int,
movements: List<Movement>
): List<CleaningProgram> {
val attempts = createAttempts(movements, maxOutput)
println("Potential Subroutines = ${attempts.size}")
val attemptArray = attempts.keys.toTypedArray()
val combinations = Combinations(totalSets, attempts.size)
val attemptSets = combinations.combinations.map { combination ->
combination.mapIndexed { index, attempt ->
attemptArray[attempt].copy(name = ('A'.toInt() + index).toChar())
}.toSet()
}
println("Testing combinations = ${attemptSets.size}")
val validCombinations = attemptSets.map {
Pair(it, checkValidAndResults(it, movements))
}.filter {
it.second.first && it.second.second.size * 2 <= maxOutput
}.map {
Pair(it.first, it.second.second)
}.sortedBy { it.second.size }
println("Valid Combindations=${validCombinations.size}")
val programs = validCombinations.map { createCleaningProgram(it) }
programs.forEachIndexed { index, cleaningProgram ->
print("Valid:$index:")
println(cleaningProgram.printToString())
require(movements == cleaningProgram.movements()) { "Expected $movements == ${cleaningProgram.movements()}" }
}
return programs
}
fun createAttempts(
movements: List<Movement>,
maxOutput: Int
): MutableMap<Attempt, Int> {
val attempts = mutableMapOf<Attempt, Int>()
for (i in movements.indices) {
for (j in (i + 2)..movements.size) {
val attempt = Attempt(0.toChar(), movements.subList(i, j))
if (attempt.len() < maxOutput) {
val count = attempts[attempt] ?: 0
attempts[attempt] = count + 1
}
}
}
return attempts
}
fun executeInstructions(program: ProgramState, cleaningProgram: CleaningProgram) {
program.setMemory(0, 2L)
program.reset()
println(cleaningProgram.printToString())
val totalInput = mutableListOf<Long>()
totalInput.addAll(createIntCodeInput(cleaningProgram.mainString()))
cleaningProgram.names().forEach { name ->
totalInput.addAll(createIntCodeInput(cleaningProgram.subRoutine(name)))
}
totalInput.addAll(createIntCodeInput("n"))
println("All Input = $totalInput")
do {
program.executeUntilInput(totalInput)
val output = program.extractOutput()
if (output.size == 1) {
println("Output=\n$output")
} else {
val str = output.joinToString("") { if (it < 256L) it.toChar().toString() else it.toString() }
println(str)
}
totalInput.clear()
} while (!program.isHalted())
}
fun main() {
val code = readProgram(File("input.txt"))
val program = Program(code).executeProgram(emptyList())
val grid = loadGrid(program.extractOutput())
println(grid.printToString())
val ap = calculateAlignment(grid)
println("Alignment Parameter = $ap")
val movements = determineRouteInstructions(grid)
val instructions = movements.joinToString(",") { it.output() }
println("Movements:$instructions")
val programs = findRepeating(3, 20, movements)
programs.forEach { cleaningProgram ->
executeInstructions(Program(code).createProgram(), cleaningProgram)
}
}Test Source
package com.github.corneil.aoc2019.day17
import assertk.assertThat
import assertk.assertions.isEqualTo
import org.junit.Test
import kotlin.test.assertTrue
class TestRobot {
@Test
fun testLoad() {
val input = """
#######...#####
#.....#...#...#
#.....#...#...#
......#...#...#
......#...###.#
......#.....#.#
^########...#.#
......#.#...#.#
......#########
........#...#..
....#########..
....#...#......
....#...#......
....#...#......
....#####......
""".trimIndent()
val output = input.map { it.toLong() }
val grid = loadGrid(output)
println(grid.printToString())
val movements = determineRouteInstructions(grid)
val mov = movements.map { it.output() }.joinToString(",")
println("Movements=$mov")
assertThat(mov).isEqualTo("R,8,R,8,R,4,R,4,R,8,L,6,L,2,R,4,R,4,R,8,R,8,R,8,L,6,L,2")
var found = false
val instructionSets = findRepeating(3, 20, movements)
instructionSets.forEach { instructionSet ->
println(instructionSet.printToString())
val routines = instructionSet.names().map { instructionSet.subRoutine(it) }.toSet()
if (routines.contains("R,8,R,8") &&
routines.contains("R,4,R,4,R,8") &&
routines.contains("L,6,L,2")
) {
found = true
}
}
assertTrue(found)
}
}Day 18: kotlin
Many-Worlds Interpretation
Part 1
This is like the traveling salesman. I could not get an algorithm that passed all the tests. The one that had some success ran far too long. Too many permutations to consider.
Trying to think how a search will work when the tree is not a binary tree.
I now have a recursive search that works but runs a long.
Started looking around at solutions by other people and found one I could understand and why I as failing. Thanks to https://github.com/0legg
Solution source
package com.github.corneil.aoc2019.day18
import com.github.corneil.aoc2019.common.permutations
import java.io.File
import java.util.*
fun BitSet.copy(extra: BitSet? = null): BitSet {
val result = BitSet(this.size())
result.or(this)
if (extra != null) {
result.or(extra)
}
return result
}
data class Coord(val x: Int, val y: Int) : Comparable<Coord> {
fun left() = copy(x = x - 1)
fun right() = copy(x = x + 1)
fun top() = copy(y = y - 1)
fun bottom() = copy(y = y + 1)
fun surrounds() = listOf(left(), right(), top(), bottom())
override fun compareTo(other: Coord): Int {
var result = x.compareTo(other.x)
if (result == 0) {
result = y.compareTo(other.y)
}
return result
}
override fun toString(): String {
return "Coord($x,$y)"
}
}
data class Cell(val c: Char, val pos: Coord) : Comparable<Cell> {
override fun compareTo(other: Cell): Int {
var result = c.compareTo(other.c)
if (result == 0) {
result = pos.compareTo(other.pos)
}
return result
}
fun isDoor() = c.isLetter() && c.isUpperCase()
fun isKey() = c.isLetter() && c.isLowerCase()
fun isEntrance() = c == '@' || c.isDigit()
fun isWall() = c == '#'
fun toBit(): Int {
return when {
isKey() -> c - 'a'
isDoor() -> c - 'A'
else -> error("Didn't expected to support toBit for $c")
}
}
fun toBitSet(): BitSet {
val result = BitSet()
if (isKey() || isDoor()) {
result.set(toBit())
}
return result
}
fun isFloor(): Boolean {
return c == '.'
}
override fun toString(): String {
return "Cell($c:${pos.x},${pos.y})"
}
}
data class Route(val node: Cell, val distance: Int, val doors: BitSet = BitSet(26)) {
override fun toString(): String {
return "Route(node=$node, distance=$distance, doors=$doors)"
}
fun makeCopy(node: Cell, distance: Int, doors: BitSet? = null): Route {
return Route(node, distance, doors ?: this.doors.copy())
}
}
data class Step(val node: Cell, val distance: Int, val visits: BitSet = BitSet(26)) {
override fun toString(): String {
return "Step(${node.c}, $distance, $visits)"
}
}
data class MultiStep(val nodes: Set<Cell>, val distance: Int, val visits: BitSet = BitSet(26)) {
override fun toString(): String {
return "MultiStep(${nodes.map { it.c }.joinToString(",")}, $distance, $visits)"
}
}
data class Visit(val distance: Int, val doors: BitSet) {
override fun toString(): String {
return "Visit($distance, $doors)"
}
}
data class Grid(val cells: MutableMap<Coord, Cell>) {
fun printToString(): String {
val output = StringBuilder()
val maxX = cells.keys.maxBy { it.x }?.x ?: error("Expected cells")
val maxY = cells.keys.maxBy { it.y }?.y ?: error("Expected cells")
for (y in 0..maxY) {
for (x in 0..maxX) {
output.append(cells[Coord(x, y)]?.c ?: ' ')
}
output.append('\n')
}
return output.toString()
}
}
class World(val grid: Grid) {
private val keys: Set<Cell> = grid.cells.values.filter { it.isKey() }.toSet()
private val doors: Set<Cell> = grid.cells.values.filter { it.isDoor() }.toSet()
private val entrances: Set<Cell> = grid.cells.values.filter { it.isEntrance() }.toSet()
val route = mutableMapOf<Cell, MutableMap<Cell, Visit>>()
init {
createRoute()
}
private fun createRoute() {
val nodes = keys() + entrances()
nodes.forEach { node ->
val queue = ArrayDeque(listOf(Route(node, 0)))
val visited = mutableSetOf(node.pos)
while (queue.isNotEmpty()) {
val current = queue.pop()
current.node.pos.surrounds().mapNotNull {
grid.cells[it]
}.filterNot {
it.isWall()
}.filterNot {
visited.contains(it.pos)
}.forEach { next ->
visited.add(next.pos)
when {
next.isDoor() -> {
val doors = current.doors.copy(next.toBitSet())
queue.add(current.makeCopy(next, current.distance + 1, doors))
}
next.isKey() -> {
val routeMap = route[node] ?: mutableMapOf()
if (routeMap.isEmpty()) {
route[node] = routeMap
}
routeMap[next] = Visit(current.distance + 1, current.doors)
queue.add(current.makeCopy(next, current.distance + 1))
}
next.isEntrance() || next.isFloor() -> {
queue.add(current.makeCopy(next, current.distance + 1))
}
else -> error("Unexpected $next")
}
}
}
}
}
fun keys(): Set<Cell> = keys
fun doors(): Set<Cell> = doors
fun entrances(): Set<Cell> = entrances
fun entrance(): Cell = entrances.first()
}
fun findPath(progress: Boolean, world: World, start: Cell): Int {
val visited = mutableMapOf<Pair<Cell, BitSet>, Int>()
val allVisits = BitSet(world.keys().size)
var visits = 0
world.keys().forEach { allVisits.or(it.toBitSet()) }
println("All Visits:$allVisits")
val combinations = permutations(world.keys().size)
println("Combinations:$combinations")
println("Start:$start")
if (progress) {
println("Routes:")
world.route.forEach { route ->
println("Route:${route.key}")
route.value.forEach { entry ->
print("\t")
println(entry)
}
}
}
val comparator = compareByDescending<Step> { it.visits.cardinality() }.thenBy { it.distance }
val queue = PriorityQueue<Step>(world.keys().size * world.doors().size, comparator)
queue.add(Step(start, 0))
var best = Int.MAX_VALUE
while (queue.isNotEmpty()) {
val step = queue.poll()
if (step.distance >= best) {
continue
}
if (progress) println("Checking $step")
world.route[step.node].orEmpty().asSequence().filterNot { entry ->
// only those we haven't visited yet
val key = entry.key
if (key.isKey()) {
step.visits[key.toBit()]
} else {
false
}.also {
if (progress) println("FilterNot#1:$it = $step -> $entry")
}
}.filter { entry ->
// if door for which we have a key
if (entry.key.isKey()) {
val doors = entry.value.doors.copy()
doors.andNot(step.visits)
if (progress) println("Checking Door ${entry.value.doors} for ${step.visits}")
doors.cardinality() == 0
} else {
true
}.also { if (progress) println("Doors#2:$it = $step -> $entry") }
}.map { entry ->
// Create a new Step
val visits = step.visits.copy(entry.key.toBitSet())
Step(entry.key, entry.value.distance + step.distance, visits)
.also { if (progress) println("Next Step#3:$entry -> $it") }
}.filter { bestStep ->
// Allow where total distance is better than best
val result = bestStep.distance < best
result.also { if (progress) println("Better#4:$it = $step -> $bestStep") }
}.filter { bestStep ->
// where visited is better
val key = Pair(bestStep.node, bestStep.visits)
val result = bestStep.distance < visited[key] ?: Int.MAX_VALUE
result.also { if (progress) println("Filter#5:$it = $step -> $bestStep") }
}.forEach {
visits += 1
val key = Pair(it.node, it.visits)
if (progress) println("Step=$step, Node=$it, Key=$key")
visited[key] = it.distance // record best visit
if (it.visits == allVisits) {
best = minOf(best, it.distance)
if (progress) println("Best=$it, Queue:$queue")
queue.removeIf { step -> step.distance >= best }
} else {
queue.offer(it)
}
if (progress) println("Queue:$queue")
}
}
println("Visits=$visits")
return best
}
data class MultiRoute(val from: Cell, val route: Cell, val visit: Visit)
fun findPathMultipleEntrances(progress: Boolean, world: World, start: Set<Cell>): Int {
val visited = mutableMapOf<Pair<Set<Cell>, BitSet>, Int>()
val allVisits = BitSet(world.keys().size)
var visits = 0
world.keys().forEach { allVisits.or(it.toBitSet()) }
println("All Visits:$allVisits")
val combinations = permutations(world.keys().size)
println("Combinations:$combinations")
println("Start:$start")
if (progress) {
println("Routes:")
world.route.forEach { route ->
println("Route:${route.key}")
route.value.forEach { entry ->
print("\t")
println(entry)
}
}
}
val comparator = compareByDescending<MultiStep> { it.visits.cardinality() }.thenBy { it.distance }
val queue = PriorityQueue<MultiStep>(world.keys().size * world.doors().size, comparator)
queue.add(MultiStep(start, 0))
var best = Int.MAX_VALUE
while (queue.isNotEmpty()) {
val step = queue.poll()
if (step.distance >= best) {
continue
}
if (progress) {
println("Checking $step")
}
step.nodes.flatMap { node ->
world.route[node].orEmpty().map { MultiRoute(node, it.key, it.value) }
}.asSequence().filterNot { entry ->
// only those we haven't visited yet
val key = entry.route
val result = if (key.isKey()) step.visits[key.toBit()] else false
result.also { if (progress) println("FilterNot#1:$it = $step -> $entry") }
}.filter { entry ->
// if door for which we have a key
if (entry.route.isKey()) {
val doors = entry.visit.doors.copy()
doors.andNot(step.visits)
if (progress) println("Checking Door ${entry.visit.doors} for ${step.visits}")
doors.cardinality() == 0
} else {
true
}.also { if (progress) println("Doors#2:$it = $step -> $entry") }
}.map { route ->
// Create a new Step
val visits = step.visits.copy(route.route.toBitSet())
MultiStep(step.nodes - route.from + route.route, route.visit.distance + step.distance, visits).also {
if (progress) println("Next Step#3:$route -> $it")
}
}.filter { bestStep ->
// Allow where total distance is better than best
val result = bestStep.distance < best
result.also { if (progress) println("Better#4:$it = $step -> $bestStep") }
}.filter { bestStep ->
// where visited is better
val key = Pair(bestStep.nodes, bestStep.visits)
val result = bestStep.distance < visited[key] ?: Int.MAX_VALUE
result.also { if (progress) println("Filter#5:$it = $step -> $bestStep") }
}.forEach {
visits += 1
val key = Pair(it.nodes, it.visits)
if (progress) println("Step=$step, Node=$it, Key=$key")
visited[key] = it.distance // record best visit
if (it.visits == allVisits) {
best = minOf(best, it.distance)
if (progress) {
println("Best=$it")
println("Queue:$queue")
}
queue.removeIf { step -> step.distance >= best }
} else {
queue.offer(it)
}
if (progress) {
println("Queue:$queue")
}
}
}
println("Visits=$visits")
return best
}
fun findKeys(progress: Boolean, grid: Grid): Int {
val world = World(grid)
println("Grid:${grid.cells.size}")
var start = world.entrance()
println("Entrance:${world.entrance()}")
val combinations = permutations(world.keys().size)
println("Combinations:$combinations")
val keys = world.keys()
println("Keys:${keys.size}:${keys.map { it.c }.joinToString(", ")}")
val doors = world.doors()
println("Doors:${doors.size}:${doors.map { it.c }.joinToString(", ")}")
println("------------------------------------")
val result = findPath(progress, world, start)
println("=====================")
println("Steps=${result}")
return result
}
fun findKeysMultipleEntrances(progress: Boolean, grid: Grid): Int {
val world = World(grid)
println("Grid:${grid.cells.size}")
var start = world.entrances()
println("Entrances:$start")
val combinations = permutations(world.keys().size)
println("Combinations:$combinations")
val keys = world.keys()
println("Keys:${keys.size}:${keys.map { it.c }.joinToString(", ")}")
val doors = world.doors()
println("Doors:${doors.size}:${doors.map { it.c }.joinToString(", ")}")
println("------------------------------------")
val result = findPathMultipleEntrances(progress, world, start)
println("=====================")
println("Steps=${result}")
return result
}
fun readGrid(input: String): Grid {
var loc = Coord(0, 0)
var cells = mutableMapOf<Coord, Cell>()
input.forEach { c ->
if (c == '\n') {
loc = loc.copy(y = loc.y + 1, x = 0)
} else {
cells[loc] = Cell(c, loc)
loc = loc.copy(x = loc.x + 1)
}
}
return Grid(cells)
}
fun modifyBots(grid: Grid): Grid {
val cells = grid.cells.toMap().toMutableMap()
val entrances = grid.cells.values.filter { it.isEntrance() }.toSet()
require(entrances.size == 1)
val entrance = entrances.first()
cells[entrance.pos] = entrance.copy(c = '#')
entrance.pos.surrounds().forEach {
cells[it] = Cell('#', it)
}
val replacements = mutableListOf<Cell>()
replacements.add(entrance.copy(c = '1', pos = Coord(entrance.pos.x - 1, entrance.pos.y - 1)))
replacements.add(entrance.copy(c = '2', pos = Coord(entrance.pos.x + 1, entrance.pos.y - 1)))
replacements.add(entrance.copy(c = '3', pos = Coord(entrance.pos.x - 1, entrance.pos.y + 1)))
replacements.add(entrance.copy(c = '4', pos = Coord(entrance.pos.x + 1, entrance.pos.y + 1)))
replacements.forEach {
cells[it.pos] = it
}
return Grid(cells)
}
fun main(args: Array<String>) {
val progress = args.toSet().contains("-p")
val input = File("input.txt").readText()
val grid = readGrid(input)
println(grid.printToString())
val distance = findKeys(progress, grid)
println("Distance = $distance")
require(distance == 5068) // ensure refactoring is still working
val grid2 = modifyBots(grid)
println(grid2.printToString())
val distance2 = findKeysMultipleEntrances(progress, grid2)
println("Distance Multiple = $distance2")
require(distance2 == 1966)
}Test Source
package com.github.corneil.aoc2019.day18
import assertk.assertThat
import assertk.assertions.isEqualTo
import org.junit.Test
class TestMapWalker {
@Test
fun test1() {
val input = """
#########
#b.A.@.a#
#########
""".trimIndent()
val grid = readGrid(input)
val distance = findKeys(true, grid)
println("Steps = $distance")
assertThat(distance).isEqualTo(8)
}
@Test
fun test2() {
val input = """
########################
#f.D.E.e.C.b.A.@.a.B.c.#
######################.#
#d.....................#
########################
""".trimIndent()
val grid = readGrid(input)
val distance = findKeys(true, grid)
assertThat(distance).isEqualTo(86)
}
@Test
fun test3() {
val input = """
########################
#...............b.C.D.f#
#.######################
#.....@.a.B.c.d.A.e.F.g#
########################
""".trimIndent()
val grid = readGrid(input)
val distance = findKeys(true, grid)
assertThat(distance).isEqualTo(132)
}
@Test
fun test4() {
val input = """
#################
#i.G..c...e..H.p#
########.########
#j.A..b...f..D.o#
########@########
#k.E..a...g..B.n#
########.########
#l.F..d...h..C.m#
#################
""".trimIndent()
val grid = readGrid(input)
val distance = findKeys(System.getProperty("print.progress", "false").toBoolean(), grid)
assertThat(distance).isEqualTo(136)
}
@Test
fun test5() {
val input = """
########################
#@..............ac.GI.b#
###d#e#f################
###A#B#C################
###g#h#i################
########################
""".trimIndent()
val grid = readGrid(input)
val distance = findKeys(true, grid)
assertThat(distance).isEqualTo(81)
}
@Test
fun test6() {
val input = """
#######
#a.#Cd#
##@#@##
#######
##@#@##
#cB#Ab#
#######
""".trimIndent()
val grid = readGrid(input)
val distance = findKeysMultipleEntrances(true, grid)
assertThat(distance).isEqualTo(8)
}
@Test
fun test7() {
val input = """
###############
#d.ABC.#.....a#
######...######
######.@.######
######...######
#b.....#.....c#
###############
""".trimIndent()
val grid = modifyBots(readGrid(input))
println(grid.printToString())
val distance = findKeysMultipleEntrances(true, grid)
assertThat(distance).isEqualTo(24)
}
@Test
fun test8() {
val input = """
#############
#DcBa.#.GhKl#
#.###...#I###
#e#d#.@.#j#k#
###C#...###J#
#fEbA.#.FgHi#
#############
""".trimIndent()
val map = modifyBots(readGrid(input))
println(map.printToString())
val distance = findKeysMultipleEntrances(true, map)
assertThat(distance).isEqualTo(32)
}
@Test
fun test9() {
val input = """
#############
#g#f.D#..h#l#
#F###e#E###.#
#dCba...BcIJ#
#####.@.#####
#nK.L...G...#
#M###N#H###.#
#o#m..#i#jk.#
#############
""".trimIndent()
val map = modifyBots(readGrid(input))
println(map.printToString())
val distance = findKeysMultipleEntrances(true, map)
assertThat(distance).isEqualTo(72)
}
}Day 19: kotlin
Tractor Beam
Part 1
First part went quick.
Part 2
If I try my algorithm on the same my answer is out by 2 on x and y. I have counted it by hand and I disagree with the sample explanation. I may be wrong?
Yes, I was a classic off by one error.
Solution Source
package com.github.corneil.aoc2019.day19
import com.github.corneil.aoc2019.intcode.Program
import com.github.corneil.aoc2019.intcode.readProgram
import java.io.File
import java.io.PrintWriter
import java.io.StringWriter
data class Coord(val x: Int, val y: Int)
class Grid(val cells: MutableMap<Coord, Char> = mutableMapOf()) {
fun printToString(): String {
val sw = StringWriter()
sw.use {
PrintWriter(sw).use { pw ->
val maxY = cells.keys.maxBy { it.y }?.y ?: 0
val maxX = cells.keys.maxBy { it.x }?.x ?: 0
for (y in 0..maxY) {
pw.print(String.format("%02d ", y))
for (x in 0..maxX) {
val cell = cells[Coord(x, y)] ?: ' '
pw.print(cell)
}
pw.println()
}
}
}
return sw.toString()
}
fun tractorActiveLine(y: Int): Pair<Coord, Coord> {
val line = cells.entries.filter { it.key.y == y }.filter { it.value == '#' }.map { it.key }
if (line.isEmpty()) {
return Pair(Coord(0, 0), Coord(0, 0))
}
val start = line.minBy { it.x } ?: error("Expected values for $y")
val end = line.maxBy { it.x } ?: error("Expected values for $y")
return Pair(start, end)
}
}
fun readGrid(input: String): Grid {
val grid = Grid()
var x = 0
var y = 0
input.forEach { c ->
when (c) {
'\n' -> {
if (grid.cells.isNotEmpty()) {
y += 1
}
x = 0
}
'.', '#' -> {
grid.cells[Coord(x, y)] = c
x += 1
}
}
}
return grid
}
fun scanGrid(code: List<Long>, width: Int, height: Int): Grid {
val grid = Grid()
scanGrid(code, grid, 0, width - 1, 0, height - 1)
return grid
}
fun scanGrid(code: List<Long>, grid: Grid, left: Int, right: Int, top: Int, bottom: Int) {
for (x in left..right) {
for (y in top..bottom) {
scanCoord(code, x, y, grid)
}
}
}
fun scanCoord(code: List<Long>, x: Int, y: Int, grid: Grid): Char {
val program = Program(code).createProgram()
val output = program.executeUntilOutput(listOf(x.toLong(), y.toLong()))
require(output.size == 1)
val out = output.first()
val cell = when (out) {
0L -> '.'
1L -> '#'
else -> ('0' + out.toInt())
}
grid.cells[Coord(x, y)] = cell
return cell
}
fun scanStanta(code: List<Long>, size: Int): Long {
val grid = scanGrid(code, size + 2, size + 2)
var top = size + 1
do {
print("Scan=${top}\r")
scanLine(2, code, top, grid)
val result = checkSolution(grid, size, top)
if (result != 0L) {
return result
}
top += 1
} while (true)
}
fun checkSolution(grid: Grid, size: Int, start: Int = size + 1): Long {
val exit = Pair(Coord(0, 0), Coord(0, 0))
var maxY = grid.cells.keys.maxBy { it.y }?.y ?: error("Expected values")
for (top in (start)..maxY) {
val last = grid.tractorActiveLine(top)
if (last == exit) {
error("No solution")
}
val first = grid.tractorActiveLine(top - size + 1)
if (last.first.x == (first.second.x - size) + 1) {
println("\nFirst = $first, Last = $last")
return (last.first.x.toLong() * 10000L) + first.first.y.toLong()
}
}
return 0
}
fun scanLine(left: Int, code: List<Long>, top: Int, grid: Grid) {
var x = left - 2
do {
val c = scanCoord(code, x, top, grid)
x += 1
} while (c == '.')
do {
val c = scanCoord(code, x, top, grid)
x += 1
} while (c == '#')
}
fun main() {
val code = readProgram(File("input.txt"))
val grid = scanGrid(code, 50, 50)
println(grid.printToString())
val affected = grid.cells.values.count { it == '#' }
println("Affected = $affected")
require(affected == 126)
val loc = scanStanta(code, 100)
println("Answer = $loc")
require(loc == 11351625L)
}Test Source
package com.github.corneil.aoc2019.day19
import assertk.assertThat
import assertk.assertions.isEqualTo
import org.junit.Test
class TestRobot {
@Test
fun testLoad() {
val input = """#.........
.#........
..##......
..###....
....###...
.....####.
......####
......####
.......###
........##
""".trimIndent()
val grid = readGrid(input)
val output = grid.printToString()
println(output)
val affected = grid.cells.values.count { it == '#' }
assertThat(affected).isEqualTo(27)
}
@Test
fun test2() {
val input = """
#.......................................
.#......................................
..##....................................
...###..................................
....###.................................
.....####...............................
......#####.............................
......######............................
.......#######..........................
........########........................
.........#########......................
..........#########.....................
...........##########...................
...........############.................
............############................
.............#############..............
..............##############............
...............###############..........
................###############.........
................#################.......
.................##################.....
..................##################....
...................###################..
....................####################
.....................###################
.....................###################
......................##################
.......................#################
........................################
.........................###############
..........................##############
..........................##############
...........................#############
............................############
.............................###########
""".trimIndent()
val grid = readGrid(input)
println(grid.printToString())
val exit = Pair(Coord(0, 0), Coord(0, 0))
val result = checkSolution(grid,10)
assertThat(result).isEqualTo(250020L) // My view is that is should be 270022
}
}Day 20: kotlin
Donut Maze
Part 1
My previous work on the mazes came in handy for this one. I had to identify the tiles that were portal and add edges to connect them to each other.
Part 2
In this case I would create an inner Grid and connect all the inner portal tiles or the outer grid to the outer portal tiles of the inner grid. If I don’t find a solution then I add another inner grid.
Had to increase the stack size on JVM for the final solution.
Solution source
package com.github.corneil.aoc2019.day20
import com.github.corneil.aoc2019.common.Graph
import com.github.corneil.aoc2019.common.Graph.Edge
import java.io.File
import java.io.PrintWriter
import java.io.StringWriter
import kotlin.math.abs
import kotlin.math.min
data class Coord(val x: Int, val y: Int) : Comparable<Coord> {
fun left() = copy(x = x - 1)
fun right() = copy(x = x + 1)
fun top() = copy(y = y - 1)
fun bottom() = copy(y = y + 1)
fun surrounds() = listOf(left(), right(), top(), bottom())
fun distance(target: Coord): Int = abs(target.x - x) + abs(target.y - y)
override fun compareTo(other: Coord): Int {
var result = x.compareTo(other.x)
if (result == 0) {
result = y.compareTo(other.y)
}
return result
}
}
data class Cell(
val c: Char,
val pos: Coord,
val level: Int = 0,
val portal: Boolean = false,
val name: String = c.toString(),
val outer: Boolean = false
) : Comparable<Cell> {
fun isFloor() = c == '.'
fun isWall() = c == '#'
override fun toString(): String {
return "Cell($name:${pos.x},${pos.y},level=$level)"
}
override fun compareTo(other: Cell): Int {
var result = level.compareTo(other.level)
if (result == 0) {
result = pos.compareTo(other.pos)
}
return result
}
override fun equals(other: Any?): Boolean {
if (this === other) return true
other as Cell
if (level != other.level) return false
if (pos != other.pos) return false
return true
}
override fun hashCode(): Int {
var result = pos.hashCode()
result = 31 * result + level
return result
}
}
data class Grid(val cells: MutableMap<Coord, Cell>) {
fun findByName() = cells.values.filter { !it.isWall() }.groupBy { it.name }
fun maxY(): Int = cells.keys.maxBy { it.y }?.y ?: 0
fun maxX(): Int = cells.keys.maxBy { it.x }?.x ?: 0
fun portals(): Map<String, List<Cell>> = cells.values.filter { it.portal }.groupBy { it.name }
fun outerPortals(): Map<String, Cell> = cells.values.filter { it.portal && it.outer }.associateBy { it.name }
fun innerPortals(): Map<String, Cell> = cells.values.filter { it.portal && !it.outer }.associateBy { it.name }
fun fromEdge(cell: Cell): Int = min(min(cell.pos.x, maxX() - cell.pos.x), min(cell.pos.y, maxY() - cell.pos.y))
fun printToString(): String {
val sw = StringWriter()
sw.use {
PrintWriter(sw).use { pw ->
val maxY = maxY()
val maxX = maxX()
for (y in 0..maxY) {
pw.print(String.format("%02d ", y))
for (x in 0..maxX) {
val cell = cells[Coord(x, y)]?.c ?: ' '
pw.print(cell)
}
pw.println()
}
}
}
return sw.toString()
}
}
fun labelPortals(grid: Grid) {
val portals = mutableMapOf<Coord, Cell>()
grid.cells.entries.forEach {
if (it.value.isFloor()) {
val top = grid.cells[it.key.top()]
val left = grid.cells[it.key.left()]
val right = grid.cells[it.key.right()]
val bottom = grid.cells[it.key.bottom()]
when {
top != null && top.c.isLetter() -> {
val next = grid.cells[top.pos.top()] ?: error("Expected letter at ${top.pos.top()}")
val name = "${next.c}${top.c}"
portals[it.key] = it.value.copy(portal = true, name = name)
}
left != null && left.c.isLetter() -> {
val next = grid.cells[left.pos.left()] ?: error("Expected letter at ${left.pos.left()}")
val name = "${next.c}${left.c}"
portals[it.key] = it.value.copy(portal = true, name = name)
}
right != null && right.c.isLetter() -> {
val next = grid.cells[right.pos.right()] ?: error("Expected letter at ${right.pos.right()}")
val name = "${right.c}${next.c}"
portals[it.key] = it.value.copy(portal = true, name = name)
}
bottom != null && bottom.c.isLetter() -> {
val next = grid.cells[bottom.pos.bottom()] ?: error("Expected letter at ${bottom.pos.bottom()}")
val name = "${bottom.c}${next.c}"
portals[it.key] = it.value.copy(portal = true, name = name)
}
}
}
}
val nonPortal = mutableSetOf<Cell>()
portals.entries.groupBy {
it.value.name
}.entries.forEach {
val cells = it.value.map { it.value }
if (cells.size == 2) {
val first = cells.first()
val last = cells.last()
if (grid.fromEdge(first) < grid.fromEdge(last)) {
portals[first.pos] = first.copy(outer = true)
} else {
portals[last.pos] = last.copy(outer = true)
}
} else {
nonPortal.addAll(cells)
}
}
nonPortal.forEach {
portals.remove(it.pos)
grid.cells[it.pos] = it.copy(portal = false)
}
grid.cells.putAll(portals)
}
fun readGrid(input: String): Grid {
var loc = Coord(0, 0)
var cells = mutableMapOf<Coord, Cell>()
input.forEach { c ->
if (c == '\n') {
loc = loc.copy(y = loc.y + 1, x = 0)
} else {
if (!c.isWhitespace()) {
cells[loc] = Cell(c, loc)
}
loc = loc.copy(x = loc.x + 1)
}
}
val map = Grid(cells)
labelPortals(map)
return map
}
fun createEdges(map: Grid): List<Edge<Cell>> {
val edges = mutableListOf<Edge<Cell>>()
map.cells.values.forEach { centre ->
if (!centre.isWall()) {
centre.pos.surrounds().forEach { neighbour ->
val cell = map.cells[neighbour]
if (cell != null && !cell.isWall()) {
edges.add(Edge(centre, cell, cell.pos.distance(centre.pos)))
}
}
}
}
map.portals().forEach {
if (it.value.size == 2) {
edges.add(Edge(it.value[0], it.value[1], 1))
} else if (it.value.size > 2) {
error("More than 2 Cells ${it}")
}
}
return edges
}
fun createEdgesRecursive(outer: Grid, inner: Grid): List<Edge<Cell>> {
val maxY = outer.maxY()
val maxX = outer.maxX()
val edges = mutableListOf<Edge<Cell>>()
outer.cells.values.forEach { centre ->
if (!centre.isWall()) {
centre.pos.surrounds().forEach { neighbour ->
val cell = outer.cells[neighbour]
if (cell != null && !cell.isWall() && !cell.outer) {
edges.add(Edge(centre, cell, cell.pos.distance(centre.pos)))
}
}
}
}
val innerPortals = inner.outerPortals()
outer.innerPortals().forEach {
val inner = innerPortals[it.key] ?: error("Expected to find ${it.key}")
edges.add(Edge(it.value, inner, 1))
}
return edges
}
fun findRouteRecursive(grid: Grid, start: String, end: String): List<Pair<Cell, Int>> {
val levels = mutableListOf<Grid>()
levels.add(grid)
val edges = mutableListOf<Edge<Cell>>()
val named = grid.findByName()
val startCell = named[start] ?: error("Expected portal named:$start")
require(startCell.size == 1) { "Expected only one named ${start}" }
val endCell = named[end] ?: error("Expected portal name:$end")
require(endCell.size == 1) { "Expected only one name ${end}" }
do {
val outer = levels.last()
val inner =
Grid(outer.cells.values.map { it.copy(level = it.level + 1) }.map { it.pos to it }.toMap().toMutableMap())
levels.add(inner)
edges.addAll(createEdgesRecursive(outer, inner))
println("Levels = ${levels.size}, Edges=${edges.size}")
val graph = Graph(edges, false)
val path = graph.findPath(startCell.first(), endCell.first())
if (path.isNotEmpty()) {
return path
}
} while (true)
}
fun findRoute(grid: Grid, start: String, end: String): List<Pair<Cell, Int>> {
val named = grid.findByName()
val startCell = named[start] ?: error("Expected portal named:$start")
require(startCell.size == 1) { "Expected only one named ${start}" }
val endCell = named[end] ?: error("Expected portal name:$end")
require(endCell.size == 1) { "Expected only one name ${end}" }
val graph = Graph(createEdges(grid), false)
val path = graph.findPath(startCell.first(), endCell.first())
require(path.isNotEmpty()) { "Could not find path from $start to $end" }
return path
}
fun main() {
val grid = readGrid(File("input.txt").readText())
println(grid.printToString())
var prevDistance = 0
var prevName = "AA:0"
val route = findRoute(grid, "AA", "ZZ")
val steps = route.map { it.first.name }.joinToString(" , ")
val count = route.last().second
route.filter { it.first.portal }.forEach {
val distance = it.second - prevDistance
prevDistance = it.second
val name = "${it.first.name}:${it.first.level}"
println("$prevName -> $name = $distance")
prevName = name
}
println("$prevName -> ZZ:0 = ${count - prevDistance}")
println("Count=$count")
require(count == 522)
println("Recursive Solition")
val rRoute = findRouteRecursive(grid, "AA", "ZZ")
val rCount = rRoute.last().second
prevDistance = 0
prevName = "AA:0"
println("Steps:")
rRoute.filter { it.first.portal }.forEach {
val distance = it.second - prevDistance
prevDistance = it.second
val name = "${it.first.name}:${it.first.level}"
println("$prevName -> $name = $distance")
prevName = name
}
println("$prevName -> ZZ:0 = ${rCount - prevDistance}")
println("Count = $rCount")
require(rCount == 6300)
}Test Source
package com.github.corneil.aoc2019.day20
import assertk.assertThat
import assertk.assertions.isEqualTo
import org.junit.Test
class TestGridWalker {
@Test
fun test1() {
val input = """
# A
# A
# #######.#########
# #######.........#
# #######.#######.#
# #######.#######.#
# #######.#######.#
# ##### B ###.#
#BC...## C ###.#
# ##.## ###.#
# ##...DE F ###.#
# ##### G ###.#
# #########.#####.#
#DE..#######...###.#
# #.#########.###.#
#FG..#########.....#
# ###########.#####
# Z
# Z
"""
val grid = readGrid(input)
println(grid.printToString())
val route = findRoute(grid, "AA", "ZZ")
val steps = route.map { it.first.name }.joinToString(",")
val count = route.last().second
println("Steps = $steps")
assertThat(count).isEqualTo(23)
}
@Test
fun test2() {
val input = """
Z L X W C
Z P Q B K
###########.#.#.#.#######.###############
#...#.......#.#.......#.#.......#.#.#...#
###.#.#.#.#.#.#.#.###.#.#.#######.#.#.###
#.#...#.#.#...#.#.#...#...#...#.#.......#
#.###.#######.###.###.#.###.###.#.#######
#...#.......#.#...#...#.............#...#
#.#########.#######.#.#######.#######.###
#...#.# F R I Z #.#.#.#
#.###.# D E C H #.#.#.#
#.#...# #...#.#
#.###.# #.###.#
#.#....OA WB..#.#..ZH
#.###.# #.#.#.#
CJ......# #.....#
####### #######
#.#....CK #......IC
#.###.# #.###.#
#.....# #...#.#
###.### #.#.#.#
XF....#.# RF..#.#.#
#####.# #######
#......CJ NM..#...#
###.#.# #.###.#
RE....#.# #......RF
###.### X X L #.#.#.#
#.....# F Q P #.#.#.#
###.###########.###.#######.#########.###
#.....#...#.....#.......#...#.....#.#...#
#####.#.###.#######.#######.###.###.#.#.#
#.......#.......#.#.#.#.#...#...#...#.#.#
#####.###.#####.#.#.#.#.###.###.#.###.###
#.......#.....#.#...#...............#...#
#############.#.#.###.###################
A O F N
A A D M
"""
val grid = readGrid(input)
println(grid.printToString())
val innerPortals = grid.innerPortals()
grid.outerPortals().values.forEach {outer ->
val inner = innerPortals[outer.name] ?: error("Expected to find Inner Portal ${outer.name}")
println("${outer.name}:${outer.pos.x},${outer.pos.y}:${inner.pos.x},${inner.pos.y}")
}
val route = findRouteRecursive(grid, "AA", "ZZ")
var prevDistance = 0
var prevName = "AA:0"
val count = route.last().second
println("Steps:")
route.filter { it.first.portal }.forEach {
val distance = it.second - prevDistance
prevDistance = it.second
val name = "${it.first.name}:${it.first.level}"
println("$prevName -> $name = $distance")
prevName = name
}
println("$prevName -> ZZ:0 = ${count - prevDistance}")
println("Total:$count")
assertThat(count).isEqualTo(396)
}
}Day 21: kotlin
Springdroid Adventure
Thanks for mainframe assembler and boolean logic in 1981!
Solution Source
package com.github.corneil.aoc2019.day21
import com.github.corneil.aoc2019.intcode.Program
import com.github.corneil.aoc2019.intcode.readProgram
import java.io.File
fun makeInput(input: String): List<Long> {
val lines = input.trim().split('\n')
return lines.map { it.trim().map { it.toLong() } + 10L }.flatten()
}
fun printOutput(output: List<Long>): String {
return output.map { if (it.toInt() < 256) it.toChar().toString() else it.toString() }.joinToString("")
}
fun reportHullDamage(code: List<Long>, springCode:String): Int {
val program = Program(code)
val state = program.createProgram()
val input = mutableListOf<Long>()
input.addAll(makeInput(springCode))
var result = 0
do {
state.executeUntilInput(input)
input.clear()
val output = state.extractOutput()
result += output.filter { it > 256 }.sum().toInt()
println(output)
val str = printOutput(output)
println(str)
} while (!state.isHalted())
return result;
}
fun main() {
val code = readProgram(File("input.txt"))
val springCode1 = """
NOT A J
NOT B T
AND D T
OR T J
NOT C T
OR T J
AND D J
WALK
""".trimIndent()
val damage1 = reportHullDamage(code, springCode1)
println("Damage:$damage1")
val springCode2 = """
NOT A J
NOT B T
AND D T
OR T J
NOT C T
OR T J
NOT A T
OR T J
AND H J
OR E J
AND D J
RUN
""".trimIndent()
val damage2 = reportHullDamage(code, springCode2)
println("Damage:$damage2")
}Day 22: kotlin
Slam Shuffle
Part 1
This was interesting and reasonable.
Part 2
It was obvious that I would need to change the code to calculate the indexes and reverse versions of all the functions.
After implementing functions to calculate the transformations I realized that reverse modulus is problematic.
I am not equipped for Advent of Math.
My first implementation breaks down in some cases and since it is a modular function I don’t know of any solver techniques that would even help.
With the large numbers if Long is going to have potential issues.
So I’m using BigInteger for the parts that may have a problem.
Ouch! This took some time.
I had to update my test cases so the deck size was prime.
Thanks to https://github.com/ephemient I found a solution I could understand!
Solution Source
package com.github.corneil.aoc2019.day22
import com.github.corneil.aoc2019.day22.Instruction.Cut
import com.github.corneil.aoc2019.day22.Instruction.Increment
import com.github.corneil.aoc2019.day22.Instruction.Reverse
import java.io.File
import java.math.BigInteger
infix fun BigInteger.`%%`(b: BigInteger): BigInteger {
val r = this % b
return if (r < BigInteger.ZERO) r + b else r
}
infix fun Long.`%%`(b: Long): Long {
return (this.toBigInteger() `%%` b.toBigInteger()).toLong()
}
sealed class Instruction {
data class Increment(val inc: Int) : Instruction()
data class Cut(val n: Int) : Instruction()
object Reverse : Instruction()
}
fun parse(input: String): Instruction {
val r = mapOf<String, (MatchResult) -> Instruction>(
"deal into new stack" to { _ -> Reverse },
"deal with increment (\\d+)" to { s -> Increment(s.groupValues.get(1).toInt()) },
"cut (-?\\d+)" to { s -> Cut(s.groupValues.get(1).toInt()) }
)
return r.entries.find {
it.key.toRegex().matches(input)
}?.let {
it.value(it.key.toRegex().matchEntire(input)!!)
} ?: error("Could not determine $input")
}
fun reverseIndex(index: Long, deck: Long, iterations: Long = 1L): Long {
return if (iterations % 2L == 0L)
index
else
deck - (index + 1)
}
fun reverse(deck: Array<Int>): Array<Int> {
println("deal into new stack")
val result = Array<Int>(deck.size) { -1 }
for (i in 0 until deck.size) {
val newIndex = reverseIndex(i.toLong(), deck.size.toLong())
result[newIndex.toInt()] = deck[i]
}
return result
}
fun cutIndex(index: Long, n: Int, deck: Long, iterations: Long = 1L): Long {
val i = index.toBigInteger()
val cn = n.toBigInteger()
val d = deck.toBigInteger()
val N = iterations.toBigInteger()
return ((N * (i - cn)) `%%` d).toLong()
}
fun cut(deck: Array<Int>, n: Int): Array<Int> {
println("cut $n")
val result = Array<Int>(deck.size) { -1 }
for (i in 0 until deck.size) {
val newIndex = cutIndex(i.toLong(), n, deck.size.toLong(), 1)
result[newIndex.toInt()] = deck[i]
}
return result
}
fun incrementIndex(index: Long, inc: Int, deck: Long, iterations: Long = 1L): Long {
if (index == 0L) {
return 0L
}
val N = iterations.toBigInteger()
val i = index.toBigInteger()
val c = inc.toBigInteger()
val d = deck.toBigInteger()
return (N * i * c `%%` d).toLong()
}
fun increment(deck: Array<Int>, inc: Int): Array<Int> {
println("deal with increment $inc")
val result = Array<Int>(deck.size) { -1 }
for (i in 0 until deck.size) {
val newIndex = incrementIndex(i.toLong(), inc, deck.size.toLong())
result[newIndex.toInt()] = deck[i]
}
return result
}
fun shuffle(input: String, deck: Array<Int>): Array<Int> {
val instruction = parse(input)
return when (instruction) {
is Instruction.Reverse -> reverse(deck)
is Instruction.Increment -> increment(deck, instruction.inc)
is Instruction.Cut -> cut(deck, instruction.n)
else -> error("Unknown instruction $instruction")
}
}
fun shuffleFrom(lines: List<String>, deck: Array<Int>, printIntermediate: Boolean = false): Array<Int> {
var result = deck
lines.forEach {
val before = result.toList().toSet()
result = shuffle(it, result)
if (printIntermediate) {
println(result.joinToString(","))
}
val after = result.toList().toSet()
require(before == after) {
"Cards missing $before -> $after"
}
}
return result
}
data class Operation(
val deck: BigInteger,
val increment: BigInteger = BigInteger.ONE,
val offset: BigInteger = BigInteger.ZERO
) {
constructor(
deck: Long,
increment: Long = 1L,
offset: Long = 0L
) : this(deck.toBigInteger(), increment.toBigInteger(), offset.toBigInteger())
operator fun times(right: Operation): Operation {
return copy(
increment = increment * right.increment `%%` deck,
offset = ((offset * right.increment `%%` deck) + right.offset) `%%` deck
)
}
fun pow(x: Long): Operation {
require(x >= 0L)
return when {
x == 0L -> Operation(this.deck)
x % 2L == 0L -> (this * this).pow(x / 2L)
else -> this * pow(x - 1L)
}
}
}
fun shuffleOperations(
lines: List<String>,
deck: Long
): Operation {
var r = Operation(deck)
lines.forEach { line ->
println("Reversing $line")
val s = parse(line)
r = when (s) {
is Reverse -> {
r.copy(increment = -r.increment `%%` r.deck, offset = (-r.offset - BigInteger.ONE) `%%` r.deck)
}
is Cut -> {
val n = s.n.toBigInteger()
r.copy(offset = (r.offset - n) `%%` r.deck)
}
is Increment -> {
val inc = s.inc.toBigInteger()
r.copy(
offset = r.offset * inc `%%` r.deck,
increment = r.increment * inc `%%` r.deck
)
}
}
}
return r
}
fun getIndex(s: Operation, index: Long): Long {
val x = index.toBigInteger()
return (((s.increment * x `%%` s.deck) + s.offset) `%%` s.deck).toLong()
}
fun getReverseIndex(s: Operation, index: Long): Long {
require(s.deck.isProbablePrime(10))
return getIndex(s.pow(s.deck.toLong() - 2L), index)
}
fun applyShuffleReverse(lines: List<String>, index: List<Long>, deck: Long, iterations: Long = 1L): List<Long> {
require(deck > 0L) { "Deck must have a positive length not $deck" }
require(iterations > 0L) { "Iteration must be positive not $iterations" }
require(index.all { it >= 0L }) { "Index must be 0 or greater not $index" }
val s = shuffleOperations(lines, deck)
val x = s.pow(iterations)
return index.map {
getReverseIndex(x, it)
}
}
fun applyShuffle(lines: List<String>, index: List<Long>, deck: Long, iterations: Long = 1L): List<Long> {
require(deck > 0L) { "Deck must have a positive length not $deck" }
require(iterations > 0L) { "Iteration must be positive not $iterations" }
require(index.all { it >= 0L }) { "Index must be 0 or greater not $index" }
val s = shuffleOperations(lines, deck)
return index.map {
getIndex(s, it)
}
}
fun main() {
val input = File("input.txt").readLines().map { it.trim() }.filter { it.length > 0 }
require(input.size == 100) { "Expected 100 lines not ${input.size}" }
val deck = (0 until 10007).toList().toTypedArray()
require(deck.indexOf(2019) == 2019)
val result = shuffleFrom(input, deck)
val index = result.indexOf(2019)
val index2 = result.indexOf(2020)
println("Result[2019] = $index, Result[2020] = $index2")
require(index == 7545)
require(index2 == 5078)
// Testing index calculations on same data
val index3 = applyShuffle(input, listOf(2019L, 2020L), deck.size.toLong(), 1L)
require(index3[0] == 7545L) { "Expected ${index3[0]} to be 7545" }
require(index3[1] == 5078L) { "Expected ${index3[1]} to be 5078" }
// Testing reverse on same data
val reverse = applyShuffleReverse(input, listOf(7545L, 5078), deck.size.toLong(), 1L)
val reverseValue = deck[reverse[0]!!.toInt()]
val reverseValue2 = deck[reverse[1]!!.toInt()]
require(reverse.first() == 2019L) { "Expected ${reverse.first()} to be 2019" }
// Large inputs
val largeDeck = 119_315_717_514_047L
val iterations = 101_741_582_076_661L
val largeIndex = applyShuffleReverse(input, listOf(2020L), largeDeck, iterations)
println("Large Number = ${largeIndex.first()}")
require(largeIndex.first() == 12_706_692_375_144L)
}Test Source
import assertk.assertThat
import assertk.assertions.isEqualTo
import com.github.corneil.aoc2019.day22.applyShuffleReverse
import com.github.corneil.aoc2019.day22.cut
import com.github.corneil.aoc2019.day22.cutIndex
import com.github.corneil.aoc2019.day22.increment
import com.github.corneil.aoc2019.day22.incrementIndex
import com.github.corneil.aoc2019.day22.reverse
import com.github.corneil.aoc2019.day22.reverseIndex
import com.github.corneil.aoc2019.day22.shuffleFrom
import org.junit.Test
class TestShuffle {
@Test
fun test1() {
val deck = (0..9).toList().toTypedArray()
val result = reverse(deck)
val expected = (9 downTo 0).toList().toTypedArray()
println("Result = ${result.toList()}")
assertThat(result.toList()).isEqualTo(expected.toList())
val check = Array<Int>(deck.size) { -1 }
for (i in 0 until deck.size) {
val index = reverseIndex(i.toLong(), deck.size.toLong())
check[index.toInt()] = deck[i]
}
assertThat(check.toList()).isEqualTo(expected.toList())
}
@Test
fun test2() {
val deck = (0..9).toList().toTypedArray()
val result = cut(deck, 3)
val expected = arrayOf(3, 4, 5, 6, 7, 8, 9, 0, 1, 2)
println("Cut:${result.toList()}")
assertThat(result.toList()).isEqualTo(expected.toList())
expected.forEachIndexed { index, i ->
val reverseIndex = cutIndex(index.toLong(), -3, deck.size.toLong())
assertThat(deck[reverseIndex.toInt()] == i)
}
val check = Array<Int>(deck.size) { -1 }
for (i in 0 until deck.size) {
val index = cutIndex(i.toLong(), 3, deck.size.toLong())
check[index.toInt()] = deck[i]
}
assertThat(check.toList()).isEqualTo(expected.toList())
}
@Test
fun test2_cut8() {
val deck = (0..9).toList().toTypedArray()
val result = cut(deck, 8)
val expected = arrayOf(8, 9, 0, 1, 2, 3, 4, 5, 6, 7)
println("Cut:${result.toList()}")
assertThat(result.toList()).isEqualTo(expected.toList())
val check = Array<Int>(deck.size) { -1 }
for (i in 0 until deck.size) {
val index = cutIndex(i.toLong(), 8, deck.size.toLong())
check[index.toInt()] = deck[i]
}
assertThat(check.toList()).isEqualTo(expected.toList())
}
@Test
fun test3() {
val deck = (0..9).toList().toTypedArray()
val result = cut(deck, -1)
val expected = arrayOf(9, 0, 1, 2, 3, 4, 5, 6, 7, 8)
println("Cut:${result.toList()}")
assertThat(result.toList()).isEqualTo(expected.toList())
val check = Array<Int>(deck.size) { -1 }
for (i in 0 until deck.size) {
val index = cutIndex(i.toLong(), -1, deck.size.toLong())
check[index.toInt()] = deck[i]
}
assertThat(check.toList()).isEqualTo(expected.toList())
}
@Test
fun test4() {
val deck = (0..9).toList().toTypedArray()
val result = increment(deck, 3)
val expected = arrayOf(0, 7, 4, 1, 8, 5, 2, 9, 6, 3)
println("Increment:${result.toList()}")
assertThat(result.toList()).isEqualTo(expected.toList())
val check = Array<Int>(deck.size) { -1 }
for (i in 0 until deck.size) {
val index = incrementIndex(i.toLong(), 3, deck.size.toLong())
check[index.toInt()] = deck[i]
}
assertThat(check.toList()).isEqualTo(expected.toList())
}
@Test
fun test4inc9() {
val deck = (0..9).toList().toTypedArray()
val result = increment(deck, 9)
val expected = arrayOf(0, 9, 8, 7, 6, 5, 4, 3, 2, 1)
println("Increment:${result.toList()}")
assertThat(result.toList()).isEqualTo(expected.toList())
val check = Array<Int>(deck.size) { -1 }
for (i in 0 until deck.size) {
val index = incrementIndex(i.toLong(), 9, deck.size.toLong())
check[index.toInt()] = deck[i]
}
assertThat(check.toList()).isEqualTo(expected.toList())
}
@Test
fun test5() {
val deck = (0..10).toList().toTypedArray()
val input = """
deal with increment 7
deal into new stack
deal into new stack
""".trimIndent().split('\n').map { it.trim() }.filter { it.isNotEmpty() }
val result = shuffleFrom(input, deck, true)
println("Result:${result.toList()}")
val expected = arrayOf(0, 8, 5, 2, 10, 7, 4, 1, 9, 6, 3)
assertThat(result.toList()).isEqualTo(expected.toList())
val check = Array<Int>(deck.size) { -1 }
applyShuffleReverse(input, (0L until deck.size.toLong()).toList(), deck.size.toLong())
.forEachIndexed { index, l ->
check[l.toInt()] = expected[index]
}
assertThat(check.toList()).isEqualTo(deck.toList())
}
@Test
fun test5_reverse() {
val deck = (0..10).toList().toTypedArray()
val input = """
deal into new stack
deal into new stack
""".trimIndent().split('\n').map { it.trim() }.filter { it.isNotEmpty() }
val result = shuffleFrom(input, deck, true)
println("Result:${result.toList()}")
val expected = arrayOf(0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10)
assertThat(result.toList()).isEqualTo(expected.toList())
val check = Array<Int>(deck.size) { -1 }
applyShuffleReverse(input, (0L until deck.size.toLong()).toList(), deck.size.toLong())
.forEachIndexed { index, l ->
check[l.toInt()] = expected[index]
}
assertThat(check.toList()).isEqualTo(deck.toList())
}
@Test
fun test6() {
val deck = (0..10).toList().toTypedArray()
val input = """
deal with increment 7
cut -2
deal with increment 9
""".trimIndent().split('\n').map { it.trim() }.filter { it.isNotEmpty() }
val result = shuffleFrom(input, deck)
println("Result:${result.toList()}")
val expected = arrayOf(6, 2, 9, 5, 1, 8, 4, 0, 7, 3, 10)
assertThat(result.toList()).isEqualTo(expected.toList())
val check = Array<Int>(deck.size) { -1 }
applyShuffleReverse(input, (0L until deck.size.toLong()).toList(), deck.size.toLong())
.forEachIndexed { index, l ->
check[l.toInt()] = expected[index]
}
assertThat(check.toList()).isEqualTo(deck.toList())
}
@Test
fun test6_inc7_cut2() {
val deck = (0..10).toList().toTypedArray()
val input = """
cut -2
deal with increment 7
""".trimIndent().split('\n').map { it.trim() }.filter { it.isNotEmpty() }
val result = shuffleFrom(input, deck)
println("Result:${result.toList()}")
val expected = arrayOf(9, 6, 3, 0, 8, 5, 2, 10, 7, 4, 1)
assertThat(result.toList()).isEqualTo(expected.toList())
val check = Array<Int>(deck.size) { -1 }
applyShuffleReverse(input, (0L until deck.size.toLong()).toList(), deck.size.toLong())
.forEachIndexed { index, l ->
check[l.toInt()] = expected[index]
}
assertThat(check.toList()).isEqualTo(deck.toList())
}
@Test
fun test6_inc7() {
val deck = (0..10).toList().toTypedArray()
val input = """
deal with increment 7
""".trimIndent().split('\n').map { it.trim() }.filter { it.isNotEmpty() }
val result = shuffleFrom(input, deck)
println("Start:${result.toList()}")
val expected = arrayOf(0, 8, 5, 2, 10, 7, 4, 1, 9, 6, 3)
assertThat(result.toList()).isEqualTo(expected.toList())
val check = Array<Int>(deck.size) { -1 }
applyShuffleReverse(input, (0L until deck.size.toLong()).toList(), deck.size.toLong())
.forEachIndexed { index, l ->
check[l.toInt()] = expected[index]
}
assertThat(check.toList()).isEqualTo(deck.toList())
}
@Test
fun test6_inc9() {
val deck = (0..10).toList().toTypedArray()
val input = """
deal with increment 9
""".trimIndent().split('\n').map { it.trim() }.filter { it.isNotEmpty() }
val result = shuffleFrom(input, deck)
println("Start:${result.toList()}")
val expected = arrayOf(0, 5, 10, 4, 9, 3, 8, 2, 7, 1, 6)
assertThat(result.toList()).isEqualTo(expected.toList())
val check = Array<Int>(deck.size) { -1 }
applyShuffleReverse(input, (0L until deck.size.toLong()).toList(), deck.size.toLong())
.forEachIndexed { index, l ->
check[l.toInt()] = expected[index]
}
assertThat(check.toList()).isEqualTo(deck.toList())
}
@Test
fun test7() {
val deck = (0..10).toList().toTypedArray()
val input = """
deal into new stack
cut -2
deal with increment 7
cut 8
cut -4
deal with increment 7
cut 3
deal with increment 9
deal with increment 3
cut -1
""".trimIndent().split('\n').map { it.trim() }.filter { it.isNotEmpty() }
require(input.size == 10)
val result = shuffleFrom(input, deck, true)
val expected2 =
cut(increment(increment(cut(increment(cut(cut(increment(cut(reverse(deck), -2), 7), 8), -4), 7), 3), 9), 3), -1)
println("Result:${result.toList()}")
assertThat(result.toList()).isEqualTo(expected2.toList())
println("Expected 2 = ${expected2.toList()}")
val expected = arrayOf(1, 8, 4, 0, 7, 3, 10, 6, 2, 9, 5)
assertThat(result.toList()).isEqualTo(expected.toList())
val check = Array<Int>(deck.size) { -1 }
applyShuffleReverse(input, (0L until deck.size.toLong()).toList(), deck.size.toLong())
.forEachIndexed { index, l ->
check[l.toInt()] = expected[index]
}
assertThat(check.toList()).isEqualTo(deck.toList())
}
@Test
fun testinc_9_reverse() {
val deck = arrayOf(0, 5, 10, 4, 9, 3, 8, 2, 7, 1, 6)
val input = """
deal with increment 9
""".trimIndent().split('\n').map { it.trim() }.filter { it.isNotEmpty() }
println("Deck:${deck.toList()}")
val expected = (0..10).toList().toTypedArray()
var check = shuffleFrom(input, expected)
println("Check:${check.toList()}")
assertThat(check.toList()).isEqualTo(deck.toList())
val result = Array<Int>(deck.size) { -1 }
applyShuffleReverse(input, (0L until deck.size.toLong()).toList(), deck.size.toLong(), 1L)
.forEachIndexed { index, l ->
result[l.toInt()] = deck[index]
}
println("Result:${result.toList()}")
if (result.toSet() != expected.toSet()) {
println("Missing values ${expected.toSet() - result.toSet()}")
}
assertThat(result.toList()).isEqualTo(expected.toList())
}
}Day 23: kotlin
Category Six
Previous work on IntCode paid off!!
Solution Source
package com.github.corneil.aoc2019.day23
import com.github.corneil.aoc2019.intcode.Program
import com.github.corneil.aoc2019.intcode.ProgramState
import com.github.corneil.aoc2019.intcode.readProgram
import java.io.File
data class Packet(val x: Long, val y: Long)
class NetWorkController(val address: Long) {
val inputQueue: MutableList<Long> = mutableListOf()
val outputQueue: MutableList<Long> = mutableListOf()
fun provideInput(): List<Long> {
return if (inputQueue.isNotEmpty()) {
val result = inputQueue.toList()
inputQueue.clear()
result
} else {
listOf(-1L)
}
}
fun hasPacket() = outputQueue.size >= 3
fun readAddress() = outputQueue.removeAt(0)
fun readPacket(): Packet {
val x = outputQueue.removeAt(0)
val y = outputQueue.removeAt(0)
return Packet(x, y)
}
fun idle() = inputQueue.isEmpty()
fun send(packet: Packet) {
inputQueue.add(packet.x)
inputQueue.add(packet.y)
}
}
typealias Network = Map<Long, Pair<NetWorkController, ProgramState>>
fun createComputers(code: List<Long>, addresses: IntRange): Network {
return addresses.map {
val netWorkController = NetWorkController(it.toLong())
val state = Program(code).createProgram(listOf(it.toLong()))
Pair(netWorkController, state)
}.associate { it.first.address to it }
}
fun runNetwork(network: Network, terminate: (Long, Packet) -> Boolean) {
var nat: Packet? = null
do {
for (item in network.values) {
val nic = item.first
val programState = item.second
programState.executeUntilInput(nic.provideInput())
nic.outputQueue.addAll(programState.extractOutput())
while (nic.hasPacket()) {
val address = nic.readAddress()
val packet = nic.readPacket()
if (terminate(address, packet)) {
return
}
if (address == 255L) {
nat = packet
println("NAT:SAVE:$packet")
} else {
val destination = network[address] ?: error("Cannot find NIC $address")
destination.first.send(packet)
println("Send:$address:$packet")
}
}
}
if (network.values.all { it.first.idle() }) {
requireNotNull(nat) { "Expected NAT packet waiting when idle" }
network[0]?.first?.send(nat) ?: error("Cannot find NIC:0")
println("NAT:SEND:$nat")
if (terminate(0, nat)) {
return
}
}
} while (network.values.all { !it.second.isHalted() })
}
fun main() {
val code = readProgram(File("input.txt"))
val a1 = solution1(code)
println("First Packet Y = $a1")
require(a1 == 22877L)
val a2 = solution2(code)
println("NAT Y twice = $a2")
require(a2 == 15210L)
}
fun solution2(code: List<Long>): Long {
var lastNAT: Packet? = null
val network = createComputers(code, 0..49)
var answer = -1L
runNetwork(network) { address, packet ->
var terminate = false
if (address == 0L) {
if (lastNAT == null) {
lastNAT = packet
} else {
if (packet.y == lastNAT?.y) {
answer = packet.y
terminate = true
}
lastNAT = packet
}
}
terminate
}
return answer
}
fun solution1(code: List<Long>): Long {
val network = createComputers(code, 0..49)
var answer = -1L
runNetwork(network) { address, packet ->
var terminate = false
if (address == 255L) {
answer = packet.y
terminate = true
}
terminate
}
return answer
}Day 24: kotlin
Planet of Discord
Part 1
This one was interesting. I realized from the start that fitting the representation of the grid into a BitSet or even a 32 bit value will be efficient when it needs to scale. Finding the same pattern again was easy.
Part 2
I did some refactoring to provide the grid with the possibility of multiple levels and a derived class that will handle the recursive levels.
Solution Source
package com.github.corneil.aoc2019.day24
import java.io.File
import java.io.PrintWriter
import java.io.StringWriter
import java.util.*
data class Coord(val x: Int, val y: Int, val level: Int = 0) {
fun left() = copy(x = x - 1)
fun right() = copy(x = x + 1)
fun top() = copy(y = y - 1)
fun bottom() = copy(y = y + 1)
fun surrounds() = listOf(left(), right(), top(), bottom())
fun pos(width: Int) = (x + 1) + (y * (width))
fun inGrid(width: Int, height: Int) = x >= 0 && x < width && y >= 0 && y < height
}
open class Grid(val width: Int = 5, val height: Int = 5) {
val levels = mutableMapOf<Int, BitSet>()
open fun levels(): List<Int> {
return levels.keys.sorted()
}
open fun setBug(coord: Coord, live: Boolean) {
if (coord.inGrid(width, height)) {
val pos = coord.pos(width)
if (pos >= 0) {
val cells = levels[coord.level]
if (cells == null) {
val newCells = BitSet()
newCells[pos] = live
levels[coord.level] = newCells
} else {
cells[pos] = live
}
}
}
}
open fun getBug(coord: Coord): Boolean {
return if (coord.inGrid(width, height)) {
val pos = coord.pos(width)
val cells = levels[coord.level]
if (cells != null && pos >= 0) {
cells[pos]
} else false
} else false
}
open fun surrounds(loc: Coord): List<Coord> {
return loc.surrounds().filter { it.inGrid(width, height) }
}
fun totalBugs(): Int {
return levels().map { countBugs(it) }.sum()
}
fun countBugs(level: Int): Int {
val cells = levels[level] ?: BitSet()
return (0 until cells.size()).map { cells[it] }.filter { it }.count()
}
fun stepLife() {
val allLevels = levels()
val bugCount = mutableMapOf<Coord, Int>()
for (level in allLevels) {
getBugCount(level, bugCount)
}
for (level in allLevels) {
changeLife(level, bugCount)
}
}
open fun ignore(coord: Coord): Boolean = false
fun changeLife(level: Int, bugCount: MutableMap<Coord, Int>) {
for (y in 0 until height) {
for (x in 0 until width) {
val pos = Coord(x, y, level)
if (!ignore(pos)) {
val bugs = bugCount[pos] ?: 0
if (getBug(pos)) {
if (bugs != 1) {
setBug(pos, false)
}
} else {
if (bugs >= 1 && bugs <= 2) {
setBug(pos, true)
}
}
}
}
}
}
fun getBugCount(level: Int, bugCount: MutableMap<Coord, Int>) {
for (y in 0 until height) {
for (x in 0 until width) {
val loc = Coord(x, y, level)
if (!ignore(loc)) {
bugCount[loc] = surrounds(loc).filter { getBug(it) }.count()
}
}
}
}
open fun getSymbol(loc: Coord): Char {
return if (getBug(loc)) '#' else '.'
}
fun printToString(level: Int = 0): String {
val sw = StringWriter()
sw.use {
PrintWriter(sw).use { pw ->
for (y in 0 until height) {
for (x in 0 until width) {
val loc = Coord(x, y, level)
val cell = getSymbol(loc)
pw.print(cell)
}
pw.println()
}
}
}
return sw.toString()
}
fun bioDiversity(level: Int = 0): Long {
var bit = 0
var bd = 0L
val cells = levels[level] ?: BitSet()
do {
val index = cells.nextSetBit(bit)
if (index >= 0) {
bd += 2.toBigInteger().pow(index - 1).toLong()
bit = index + 1
} else {
break;
}
} while (true)
return bd
}
fun bioDiversity(coord: Coord): Long {
val pos = coord.pos(width)
return 2.toBigInteger().pow(pos - 1).toLong()
}
}
class RecursiveGrid : Grid() {
override fun ignore(coord: Coord): Boolean {
return coord.x == width / 2 && coord.y == height / 2
}
override fun surrounds(loc: Coord): List<Coord> {
val result = mutableListOf<Coord>()
val cells = loc.surrounds()
val halfWidth = width / 2
val halfHeight = height / 2
cells.forEach { cell ->
when {
cell.x < 0 -> {
result.add(Coord(x = halfWidth - 1, y = halfHeight, level = cell.level - 1))
}
cell.x >= width -> {
result.add(Coord(x = halfWidth + 1, y = halfHeight, level = cell.level - 1))
}
cell.y < 0 -> {
result.add(Coord(x = halfWidth, y = halfHeight - 1, level = cell.level - 1))
}
cell.y >= height -> {
result.add(Coord(x = halfWidth, y = halfHeight + 1, level = cell.level - 1))
}
cell.x == halfHeight && cell.y == halfWidth -> {
when {
loc.left() == cell -> (0 until height).forEach {
result.add(Coord(width - 1, it, cell.level + 1))
}
loc.right() == cell -> (0 until height).forEach {
result.add(Coord(0, it, cell.level + 1))
}
loc.top() == cell -> (0 until width).forEach {
result.add(Coord(it, height - 1, cell.level + 1))
}
loc.bottom() == cell -> (0 until width).forEach {
result.add(Coord(it, 0, cell.level + 1))
}
else -> error("Expected $cell to be around $loc")
}
}
else -> result.add(cell)
}
}
return result.toList()
}
override fun setBug(coord: Coord, live: Boolean) {
require(coord.inGrid(width, height)) { "setBug invoked with location outside grid $coord" }
if (!ignore(coord)) {
super.setBug(coord, live)
}
}
override fun getBug(coord: Coord): Boolean {
require(coord.inGrid(width, height)) { "getBug invoked with location outside grid $coord" }
return super.getBug(coord)
}
override fun getSymbol(loc: Coord): Char {
return when {
loc.x == width / 2 && loc.y == width / 2 -> '?'
else -> super.getSymbol(loc)
}
}
override fun levels(): List<Int> {
val allLevels = super.levels().toMutableList()
val minLevel = allLevels.min()!!
val maxLevel = allLevels.max()!!
if (countBugs(minLevel) > 0) {
allLevels.add(minLevel - 1)
}
if (countBugs(maxLevel) > 0) {
allLevels.add(maxLevel + 1)
}
return allLevels.toList().sorted()
}
}
fun readGrid(input: String, grid: Grid): Grid {
val cells = mutableMapOf<Coord, Char>()
var x = 0
var y = 0
input.forEach { c ->
when (c) {
'\n' -> {
y += 1
x = 0
}
'.' -> {
x += 1
}
'#' -> {
val loc = Coord(x, y)
grid.setBug(loc, true)
x += 1
}
}
}
return grid
}
fun readGrid(input: String) = readGrid(input, Grid())
fun readRecursiveGrid(input: String) = readGrid(input, RecursiveGrid())
fun main() {
val input = File("input.txt").readText()
val grid = readGrid(input)
val bioSet = mutableSetOf<Long>()
var lastBD = 0L
do {
grid.stepLife()
val bd = grid.bioDiversity()
lastBD = bd
if (bioSet.contains(bd)) {
println(grid.printToString())
break
} else {
bioSet.add(bd)
}
} while (true)
println("BD = $lastBD")
require(lastBD == 28717468L)
val recursiveGrid = readRecursiveGrid(input)
repeat(200) {
recursiveGrid.stepLife()
}
val totalBugs = recursiveGrid.totalBugs()
println("Total = $totalBugs")
}Test Source
package com.github.corneil.aoc2019.day19
import assertk.assertThat
import assertk.assertions.isEqualTo
import com.github.corneil.aoc2019.day24.Coord
import com.github.corneil.aoc2019.day24.Grid
import com.github.corneil.aoc2019.day24.readGrid
import com.github.corneil.aoc2019.day24.readRecursiveGrid
import org.junit.Test
class TestBugsLife {
@Test
fun testLoad() {
val grid = Grid(5, 5)
grid.setBug(Coord(0, 3), true)
grid.setBug(Coord(1, 4), true)
val bd1 = grid.bioDiversity(Coord(0, 3))
assertThat(bd1).isEqualTo(32768L)
val bd2 = grid.bioDiversity(Coord(1, 4))
assertThat(bd2).isEqualTo(2097152L)
val total = grid.bioDiversity()
assertThat(total).isEqualTo(2129920L)
}
@Test
fun testStep1() {
val input = """
....#
#..#.
#..##
..#..
#....
""".trimIndent()
val grid = readGrid(input)
println(grid.printToString())
grid.stepLife()
val result = grid.printToString().trim()
println(result)
val expected = readGrid(
"""
#..#.
####.
###.#
##.##
.##..
""".trimIndent()
)
assertThat(grid.bioDiversity()).isEqualTo(expected.bioDiversity())
}
@Test
fun testStep4() {
val input = """
....#
#..#.
#..##
..#..
#....
""".trimIndent()
val grid = readGrid(input)
repeat(4) {
grid.stepLife()
}
val result = grid.printToString().trim()
println(result)
val expected = readGrid(
"""
####.
....#
##..#
.....
##...
""".trimIndent()
)
assertThat(grid.bioDiversity()).isEqualTo(expected.bioDiversity())
}
@Test
fun testRepeat() {
val input = """
....#
#..#.
#..##
..#..
#....
""".trimIndent()
val grid = readGrid(input)
val bioSet = mutableSetOf<Long>()
var lastBD = 0L
do {
grid.stepLife()
val bd = grid.bioDiversity()
lastBD = bd
if (bioSet.contains(bd)) {
println(grid.printToString())
break
} else {
bioSet.add(bd)
}
} while (true)
assertThat(lastBD).isEqualTo(2129920L)
assertThat(grid.totalBugs()).isEqualTo(2)
}
@Test
fun testRecursive() {
val input = """
....#
#..#.
#..##
..#..
#....
""".trimIndent()
val grid = readRecursiveGrid(input)
val reference = mutableMapOf<String, Coord>()
for (y in 0 until 5) {
for (x in 0 until 5) {
val coord = Coord(x, y, 1)
val pos = coord.pos(5)
val level1 = ('A' + pos - 1).toString()
reference[level1] = coord
val level0 = pos.toString()
reference[level0] = coord.copy(level = 0)
}
}
val cellE = Coord(4, 0, 1)
assertThat(reference["E"]).isEqualTo(cellE)
val surroundsE = grid.surrounds(cellE).toSet()
println("SurroundsE for $cellE = $surroundsE")
val expectedE = listOf("8", "D", "14", "J").map { reference[it]!! }.toSet()
println("Expected $expectedE")
assertThat(surroundsE).isEqualTo(expectedE)
val cell19 = reference["19"]!!
assertThat(cell19).isEqualTo(Coord(3, 3, 0))
val surrounds19 = grid.surrounds(cell19).toSet()
val expected19 = listOf("14", "18", "20", "24").map { reference[it]!! }.toSet()
println("Surrounds19 = $surrounds19")
assertThat(surrounds19).isEqualTo(expected19)
val cell14 = reference["14"]!!
assertThat(cell14).isEqualTo(Coord(3, 2, 0))
val surrounds14 = grid.surrounds(cell14).toSet()
println("Surrounds14 = $surrounds14")
val expected14 = listOf("9", "E", "J", "O", "T", "Y", "15", "19").map { reference[it]!! }.toSet()
assertThat(surrounds14).isEqualTo(expected14)
println(grid.printToString())
repeat(10) {
grid.stepLife()
}
for (level in grid.levels()) {
if (grid.countBugs(level) > 0) {
println("Depth=$level")
println(grid.printToString(level))
}
}
assertThat(grid.countBugs(-5)).isEqualTo(7)
assertThat(grid.countBugs(-4)).isEqualTo(6)
assertThat(grid.countBugs(-3)).isEqualTo(6)
assertThat(grid.countBugs(-2)).isEqualTo(10)
assertThat(grid.countBugs(-1)).isEqualTo(10)
assertThat(grid.countBugs(0)).isEqualTo(5)
assertThat(grid.countBugs(1)).isEqualTo(15)
assertThat(grid.countBugs(2)).isEqualTo(12)
assertThat(grid.countBugs(3)).isEqualTo(7)
assertThat(grid.countBugs(4)).isEqualTo(9)
assertThat(grid.countBugs(5)).isEqualTo(12)
assertThat(grid.totalBugs()).isEqualTo(99)
}
}Day 25: kotlin
Cryostasis
Part 1
I built a little program around intcode where I could enter commands like I did with "The Hobbit" on my ZX Spectrum in 1983. The I added code to parse the output and navigate the ship and eventually to drop random items when the pressure plate thinks the droid is too heavy or or collect one random item when it is too light.
Solution Source
package com.github.corneil.aoc2019.day25
import com.github.corneil.aoc2019.day25.CollectionStrategy.ALL
import com.github.corneil.aoc2019.day25.CollectionStrategy.NONE
import com.github.corneil.aoc2019.day25.CollectionStrategy.ONE
import com.github.corneil.aoc2019.intcode.Program
import com.github.corneil.aoc2019.intcode.ProgramState
import com.github.corneil.aoc2019.intcode.readProgram
import org.jgrapht.alg.shortestpath.JohnsonShortestPaths
import org.jgrapht.graph.DefaultDirectedGraph
import org.jgrapht.graph.DefaultEdge
import java.io.File
import kotlin.random.Random
fun makeInput(input: String): List<Long> {
val lines = input.trim().split('\n')
return lines.map { it.trim().map { it.toLong() } + 10L }.flatten()
}
fun printOutput(output: List<Long>): String {
return output.map { if (it.toInt() < 256) it.toChar().toString() else it.toString() }.joinToString("")
}
enum class CollectionStrategy {
NONE,
ONE,
ALL
}
data class Robot(
var location: String = "",
var move: String = "",
var lastObject: String = "",
var collectionStrategy: CollectionStrategy = ALL,
val tried: MutableMap<String, MutableList<String>> = mutableMapOf(),
val commands: MutableList<String> = mutableListOf(),
val movements: MutableList<Pair<String, String>> = mutableListOf(),
val objects: MutableSet<String> = mutableSetOf()
) {
fun addObject(obj: String) {
lastObject = obj
objects.add(obj)
}
}
fun findLocation(input: String): String {
if (input.contains("== ")) {
val sub = input.substringAfter("== ")
return sub.substringBefore(" ==")
}
return ""
}
fun parseList(input: String, start: String): List<String> {
if (input.contains(start)) {
val output = mutableListOf<String>()
val lines = input.substringAfter(start).trim().split('\n')
for (line in lines) {
if (line.startsWith("- ")) {
output.add(line.substringAfter("- "))
} else {
break
}
}
return output
}
return emptyList()
}
fun findItems(input: String): List<String> = parseList(input, "Items here:")
fun findDirections(input: String) = parseList(input, "Doors here lead:")
fun findInventory(input: String) = parseList(input, "Items in your inventory:")
fun execute(state: ProgramState, cmd: String): String {
val output = if (cmd.isNotBlank()) {
println("Executing:$cmd")
val input = makeInput(cmd)
state.executeUntilInput(input)
printOutput(state.extractOutput())
} else {
println("Waiting for output")
printOutput(state.executeUntilOutput(emptyList()))
}
println(output)
if (output.contains("Unrecognized")) {
error("Command:[$cmd]")
}
return output
}
val directions = setOf("north", "south", "east", "west")
class World(code: List<Long>, val ignoreItems: Set<String>) {
var program = Program(code).createProgram(emptyList())
val graph = DefaultDirectedGraph<String, DefaultEdge>(DefaultEdge::class.java)
val links = mutableMapOf<Pair<String, String>, String>()
val locations = mutableMapOf<String, Set<String>>()
val locationItems = mutableMapOf<String, MutableSet<String>>()
val locationEntries = mutableMapOf<String, MutableList<String>>()
val allItems = mutableSetOf<String>()
fun processCommands(robot: Robot, commands: MutableList<String>): String {
var output = ""
while (commands.isNotEmpty()) {
val command = commands.removeAt(0)
if (directions.contains(command)) {
robot.move = command
robot.movements.add(Pair(robot.location, command))
val triedOptions = robot.tried[robot.location] ?: mutableListOf()
triedOptions.add(command)
robot.tried[robot.location] = triedOptions
println("${robot.location} -> ${command}")
}
output = execute(program, command)
if (output.contains("You don't see that item here")) {
println("Reset the items for ${robot.location}")
locationItems[robot.location] = mutableSetOf()
}
if (output.contains("You take the")) {
val item = output.substringAfter("You take the").substringBefore(".").trim()
require(allItems.contains(item)) { "Expected $item to be in $allItems" }
robot.addObject(item)
}
if (output.contains("You drop the")) {
val item = output.substringAfter("You drop the").substringBefore(".").trim()
require(allItems.contains(item)) { "Expected $item to be in $allItems" }
robot.objects.remove(item)
}
val loc = findLocation(output)
if (loc.isNotBlank()) {
println("Location:$loc")
val directions = findDirections(output)
if (directions.isNotEmpty()) {
println("Directions:$directions")
locations[loc] = directions.toSet()
}
if (robot.location.isNotBlank()) {
if (!graph.containsVertex(loc)) {
graph.addVertex(loc)
}
if (!graph.containsVertex(robot.location)) {
graph.addVertex(robot.location)
}
if (graph.getEdge(robot.location, loc) == null) {
graph.addEdge(robot.location, loc)
}
}
links[Pair(robot.location, loc)] = robot.move
robot.location = loc
val entries = locationEntries[loc] ?: mutableListOf()
if (robot.move.isNotBlank()) {
entries.add(robot.move)
}
locationEntries[loc] = entries
}
val items = findItems(output)
if (items.isNotEmpty()) {
println("Items=$items")
val locItems = locationItems[loc] ?: mutableSetOf()
locItems.addAll(items)
locationItems[loc] = locItems
allItems.addAll(items)
}
val inventory = findInventory(output)
if (inventory.isNotEmpty()) {
robot.objects.clear()
robot.objects.addAll(inventory)
}
}
return output
}
}
fun findUntried(location: String, move: String, world: World, tried: MutableMap<String, MutableList<String>>): String {
val movementOptions = world.locations[location] ?: mutableSetOf()
if (movementOptions.isNotEmpty()) {
val triedOptions = tried[location]?.toList() ?: emptyList()
val untriedOptions = movementOptions - triedOptions.toSet()
if (untriedOptions.isNotEmpty()) {
val attempt = when {
move.isNotBlank() && untriedOptions.contains(move) -> move
untriedOptions.size == 1 -> untriedOptions.first()
else -> {
untriedOptions.toList().get(Random(System.currentTimeMillis()).nextInt(untriedOptions.size))
}
}
if (attempt.isNotBlank()) {
return attempt
}
}
}
return ""
}
fun opposite(direction: String): String {
return when (direction) {
"south" -> "north"
"north" -> "south"
"east" -> "west"
"west" -> "east"
else -> error("Invalid direction:$direction")
}
}
fun findOpposites(entry: Set<String>): Set<String> {
return entry.map { opposite(it) }.toSet()
}
fun findRoute(start: String, end: String, world: World, robot: Robot): Pair<String, List<String>> {
val jsp = JohnsonShortestPaths(world.graph)
val path = jsp.getPath(start, end)
val route = mutableListOf<String>()
if (path != null && path.vertexList.isNotEmpty()) {
val links = mutableListOf<Pair<String, String>>()
val startIndex = if (path.vertexList.first() == start) {
1
} else {
0
}
var prev = start
for (i in startIndex until path.vertexList.size) {
val current = path.vertexList[i]
val link = world.links[Pair(prev, current)]
if (link != null) {
route.add(link)
} else {
route.clear()
break
}
prev = current
}
}
if (route.isEmpty()) {
val firstMove = robot.movements.find { it.first == start }
if (firstMove != null) {
val remainList = robot.movements.subList(robot.movements.indexOf(firstMove), robot.movements.lastIndex)
val lastMove = remainList.find { it.first == end }
if (lastMove != null) {
val lastIndex = remainList.indexOf(lastMove)
for (i in 0 until lastIndex) {
route.add(remainList[i].second)
}
}
}
}
return Pair(end, route)
}
fun findPassword(code: List<Long>): String {
var password = ""
val ignoreItems = mutableSetOf<String>("infinite loop")
do {
var commands = mutableListOf<String>("inv")
var lastTake = ""
val dropped = mutableSetOf<String>()
var world = World(code, emptySet())
val robot = Robot()
try {
do {
if (robot.commands.isNotEmpty()) {
val movement = robot.commands.removeAt(0)
commands.add(movement)
}
val output = world.processCommands(robot, commands)
if (robot.commands.isNotEmpty()) {
continue
}
if (output.contains("Analysis complete!")) {
password = output.substringAfter("get in by typing ").substringBefore(' ').trim()
continue
}
if (output.contains("ejected")) {
val loc = findLocation(output.substringAfter("ejected"))
if (loc.isNotBlank()) {
robot.location = loc
}
}
if (output.contains("Alert! Droids on this ship are lighter than the detected value!")) {
println("All Items:${world.allItems},Robot:${robot.objects}")
println("Ignored:$ignoreItems")
if ((robot.objects - dropped).isEmpty()) {
println("Clearing Dropped:$dropped")
dropped.clear()
}
val dropList = (robot.objects - dropped).toList()
val drop = dropList.get(Random(System.currentTimeMillis()).nextInt(dropList.size))
println("Dropping $drop")
robot.collectionStrategy = NONE
commands.add("drop $drop")
dropped.add(drop)
commands.add("inv")
} else if (output.contains("Alert!")) {
println("All Items:${world.allItems},Robot:${robot.objects}")
println("Ignored:$ignoreItems")
commands.add("inv")
commands.add(robot.move)
robot.collectionStrategy = ONE
}
val items = world.locationItems[robot.location]?.toSet() ?: emptySet()
if (items.isNotEmpty()) {
val taken = when (robot.collectionStrategy) {
ONE -> {
val take = items.toList().get(Random(System.currentTimeMillis()).nextInt(items.size))
commands.add("take $take")
lastTake = take
true
}
ALL -> {
var result = false
for (item in items) {
if (!ignoreItems.contains(item) && !robot.objects.contains(item)) {
commands.add("take $item")
lastTake = item
result = true
}
}
result
}
NONE -> {
false
}
}
if (taken) {
continue
}
}
val movement = findUntried(robot.location, robot.move, world, robot.tried)
if (movement.isNotBlank()) {
println("Location:${robot.location}:Untried move:$movement")
commands.add(movement)
continue
}
val untriedMovements = world.locations.entries.map {
it.key to (it.value - (robot.tried[it.key]?.toSet() ?: emptySet()))
}.filter {
it.second.isNotEmpty()
}
val movements = untriedMovements.map { findRoute(robot.location, it.first, world, robot) }
.filter { it.second.isNotEmpty() }
println("Other Untried:$movements")
if (movements.isNotEmpty()) {
val route =
if (Random(System.currentTimeMillis()).nextBoolean()) movements.first() else movements.last()
println("Route:$route")
commands.addAll(route.second)
continue
}
if (untriedMovements.isNotEmpty()) {
error("Could not find routes!! $untriedMovements")
}
val routeToDoor = findRoute(robot.location, "Pressure-Sensitive Floor", world, robot)
if (routeToDoor.second.isNotEmpty()) {
commands.addAll(routeToDoor.second)
continue
}
val routeToSecurity = findRoute(robot.location, "Security Checkpoint", world, robot)
if (routeToSecurity.second.isNotEmpty()) {
commands.addAll(routeToSecurity.second)
commands.add("south")
continue
} else {
println("Cannot find Security Checkpoint!!")
}
println("Tried:$robot.tried")
println("Robot=$robot")
println(":")
val str = System.console().readLine().trim()
if (str.isNotBlank()) {
when {
str.startsWith("take") -> {
val item = str.substringAfter(' ')
println("Taking $item")
}
str.startsWith("drop") -> {
val item = str.substringAfter(' ')
robot.objects.remove(item)
}
str == "inv" -> {
println("Robot=$robot")
}
directions.contains(str) -> {
println("Move=$str")
}
else -> {
println("Invalid $str")
}
}
commands.add(str.trim())
}
} while (password.isBlank() && !world.program.isHalted())
} catch (x: Throwable) {
x.printStackTrace()
}
if (password.isBlank()) {
println("Locations:${world.locations}")
println("Locations Items:${world.locationItems}")
println("Tried:${robot.tried}")
print("Untried:")
println(world.locations.entries.map {
it.key to (it.value - (robot.tried[it.key]?.toSet() ?: emptySet()))
}.filter {
it.second.isNotEmpty()
})
println("Robot:$robot")
println("==IGNORING:$lastTake")
ignoreItems.add(lastTake)
} else {
println("Robot is at ${robot.location} carrying: ${robot.objects}")
}
} while (password.isBlank())
return password
}
fun main() {
val code = readProgram(File("input.txt"))
val password = findPassword(code)
println("Password=$password")
}