corneil

466422?v=4

corneil
Corneil du Plessis
Github: corneil
Twitter: @corneil
Mastodon: @corneil@hachyderm.io

About me

I am a Staff Software Engineer at VMware working on the Spring Cloud Data Flow team. I enjoyed AoC 2019 and decided to give it another go this year.

I love coding in Kotlin and I try write the code solving the puzzles in a way that someone else can understand the solution.

Day 00: kotlin

Hello World!

This is a simple Hello World program in Kotlin, if you want to experiment with Kotlin use the Kotlin Playground

My aim with Advent of Code is to write code solving the puzzles in a way that is understandable to a wide audience. Feel free to reach out with comments at the links above.

Day 01: kotlin

Calorie Counting

In order to follow these solutions you will need to login to Advent of Code and complete each day.

The day was lines representing the calories of food items carried by elves and separated by blank lines. Kotlin File has a readLines function that makes it easy to parse the input, calculate the calories for each elf and add to a list.

Parsing
  fun findCalories(input: List<String>): List<Int> {
    val elves = mutableListOf<Int>()
    var calories = 0
    for (line in input) {
      if (line.isBlank()) {
        elves.add(calories)
        calories = 0
      } else {
        calories += line.toInt()
      }
    }
    elves.add(calories)
    return elves
  }
Part 1

For part one the max value it the answer.

  fun findMaxCalories(input: List<String>): Int {
    val calories = findCalories(input)
    return calories.max()
  }
Part 2

For part two the result is the sum of the first three when sorted in descending order. Kotlin has the take method on collections which is very useful in this case.

  fun topThree(input: List<String>): Int {
    val calories = findCalories(input)
    return calories.sortedDescending().take(3).sum()
  }

Day 02: kotlin

Rock Paper Scissors

Part 1 meant we needed to parse input representing an opponent hand when playing RPS, and we had to assume the 2nd input was an answer we needed to provide while "cheating".

Part 2 came with a curveball in that the 2nd input should be treated as an outcome. This means we needed to find the correct hand for the outcome. The score calculation was a function of the outcome and the hand we selected.

Below is the final code and there are loaders for creating the rounds for part 1 and part 2.

enum class Rps(val identifiers: String, val shapeScore: Int) {
  ROCK("AX", 1),
  PAPER("BY", 2),
  SCISSORS("CZ", 3)
}

enum class Outcome(val identifier: String, val score: Int) {
  LOSE("X", 0),
  DRAW("Y", 3),
  WIN("Z", 6)
}

data class Hand(val them: Rps, val me: Rps)

object Rules {

  data class Rule(val loser: Rps, val winner: Rps)

  private val beats = mapOf(
    Rps.ROCK to Rule(Rps.SCISSORS, Rps.PAPER),
    Rps.PAPER to Rule(Rps.ROCK, Rps.SCISSORS),
    Rps.SCISSORS to Rule(Rps.PAPER, Rps.ROCK)
  )

  fun winner(shape: Rps): Rps {
    val winner = beats[shape] ?: error("Cannot find $shape")
    return winner.winner
  }

  fun loser(shape: Rps): Rps {
    val loser = beats[shape] ?: error("Cannot find $shape")
    return loser.loser
  }

  fun didIWin(round: Hand): Boolean {
    val shape = loser(round.me)
    return shape == round.them
  }

}

fun main() {

  fun toRps(hint: String): Rps {
    return Rps.values().find { it.identifiers.contains(hint) }
              ?: error("Invalid RPS $hint")
  }

  fun toOutcome(outcome: String): Outcome {
    return Outcome.values().find { it.identifier == outcome }
              ?: error("Invalid Outcome:$outcome")
  }

  fun readRounds(input: List<String>): List<Hand> {
    return input.map {
      val hints = it.split(" ")
      Hand(toRps(hints[0]), toRps(hints[1]))
    }
  }

  // choose a shape to match the outcome
  fun chooseShape(shape: Rps, outcome: Outcome): Rps {
    return when (outcome) {
      Outcome.DRAW -> shape
      Outcome.WIN -> Rules.winner(shape)
      Outcome.LOSE -> Rules.loser(shape)
    }
  }

  // convert 2nd to outcome and then find a shape to match outcome given 1st
  fun readRounds2(input: List<String>): List<Hand> {
    return input.map {
      val hints = it.split(" ")
      Pair(toRps(hints[0]), toOutcome(hints[1]))
    }.map {
      Hand(it.first, chooseShape(it.first, it.second))
    }
  }

  fun calcRound(round: Hand): Int {
    return when {
      round.them == round.me -> Outcome.DRAW.score
      Rules.didIWin(round) -> Outcome.WIN.score
      else -> Outcome.LOSE.score
    }
  }

  fun calcScore(round: Hand): Int {
    return round.me.shapeScore + calcRound(round)
  }

  fun calcTotal(rounds: List<Hand>): Int {
    return rounds.sumOf { calcScore(it) }
  }

  fun part1() {

    val testScore = calcTotal(readRounds(readInput("day02_test")))
    println("Test Total = $testScore")
    check(testScore == 15)

    val total = calcTotal(readRounds(readInput("day02")))
    println("Total = $total")

  }

  fun part2() {

    val testScore2 = calcTotal(readRounds2(readInput("day02_test")))
    println("Test Total 2 = $testScore2")
    check(testScore2 == 12)

    val total2 = calcTotal(readRounds2(readInput("day02")))
    println("Total 2 = $total2")
  }

  part1()
  part2()
}

Day 03: kotlin

Rucksack Reorganization

Today puzzle was about manipulating strings and calculating the values of characters according rules.

Calculating the priority
fun calcPriority(value: Char): Int = when (value) {
  in 'a'..'z' -> value - 'a' + 1
  in 'A'..'Z' -> value - 'A' + 27
  else -> error("Invalid input $value")
}
Part1
fun calcRucksacks(input: List<String>): Int =
  input.map {
      Pair(it.substring(0 until it.length / 2), it.substring(it.length / 2)) (1)
    }
    .map {
      it.first.toSet().intersect(it.second.toSet()).first() (2)
    }
    .sumOf { calcPriority(it) } (3)
1 Split string into equal parts to represent compartments
2 Determine common character by converting to set of characters and finding union
3 Calculate the sum of the priorities
Part 2
fun calcBadges(input: List<String>): Int =
  input.mapIndexed { index, s -> index / 3 to s }
    .groupBy({ it.first }, { it.second })           (1)
    .map { e ->
      e.value
        .map { it.toSet() }
        .reduce { a, b -> a.intersect(b) }
        .first()                                    (2)
    }
    .sumOf { calcPriority(it) }                     (3)
1 Group strings by 3.
2 Determine common character from all 3 strings.
3 Calculate the sum of the priorities
Takeaways

  • String.toSet gives to a Set of Char

  • reduce is a great way to determine the intersection on multiple sets.

  • groupBy can take two parameters and with the second parameter you can determine the type of the value.

Full source
fun main() {

  fun calcPriority(value: Char): Int = when (value) {
    in 'a'..'z' -> value - 'a' + 1
    in 'A'..'Z' -> value - 'A' + 27
    else -> error("Invalid input $value")
  }

  fun calcRucksacks(input: List<String>): Int =
    input.map {
        Pair(it.substring(0 until it.length / 2), it.substring(it.length / 2))
      }
      .map { it.first.toSet().intersect(it.second.toSet()).first() }
      .sumOf { calcPriority(it) }

  fun calcBadges(input: List<String>): Int =
    input.mapIndexed { index, s -> index / 3 to s }
      .groupBy({ it.first }, { it.second })
      .map { e -> e.value.map { it.toSet() }
          .reduce { a, b -> a.intersect(b) }
          .first()
      }
      .sumOf { calcPriority(it) }

  fun part1() {
    val testPriorities = calcRucksacks(readInput("day03_test"))
    println("Test Priorities = $testPriorities")
    check(testPriorities == 157)

    val priorities = calcRucksacks(readInput("day03"))
    println("Priorities = $priorities")
    check(priorities == 8123)
  }

  fun part2() {
    val testPriorities = calcBadges(readInput("day03_test"))
    println("Test Priorities = $testPriorities")
    check(testPriorities == 70)

    val priorities = calcBadges(readInput("day03"))
    println("Priorities = $priorities")
    check(priorities == 2620)
  }
  part1()
  part2()
}

Day 04: kotlin

Camp Cleanup

I wasted some time today because I misunderstood the fully contains applying to a pair of assignments. I was trying to check across assignments. Re-reading when I got the wrong answer meant some facepalms.

We needed to convert the input depicting 2 ranges into sets of sections representing by numbers. So that meant converting 2-4,6-8 to a Pair of IntRange and then to a Pair of Set<Int> which it as simple as:

fun convertRange(input: String): IntRange {
  val values = input.split("-")
  return values[0].toInt()..values[1].toInt()
}

fun convertRanges(input: List<String>): List<Pair<Set<Int>, Set<Int>>> =
  input.map { it.split(",") }
    .map { Pair(convertRange(it[0]).toSet(), convertRange(it[1]).toSet()) }
Part 1

Determining fully contains for part 1 was as simple as:

fun calcContains(ranges: List<Pair<Set<Int>, Set<Int>>>): Int {
  return ranges.count {
    it.first.containsAll(it.second) || it.second.containsAll(it.first)
  }
}
Part 2

And determining an overlap for part1 was as simple as:

fun calcOverlap(ranges: List<Pair<Set<Int>, Set<Int>>>): Int {
  return ranges.count { it.first.intersect(it.second).isNotEmpty() }
}
Takeaways

Re-read the problem because a lot of effort was made to explain with a complete example.

If you first answer is incorrect you may have misunderstood something.

Full source
fun main() {
  fun convertRange(input: String): IntRange {
    val values = input.split("-")
    return values[0].toInt()..values[1].toInt()
  }

  fun convertRanges(input: List<String>): List<Pair<Set<Int>, Set<Int>>> =
    input.map { it.split(",") }
      .map { Pair(convertRange(it[0]).toSet(), convertRange(it[1]).toSet()) }

  fun calcContains(ranges: List<Pair<Set<Int>, Set<Int>>>): Int {
    return ranges.count {
      it.first.containsAll(it.second) || it.second.containsAll(it.first)
    }
  }

  fun calcOverlap(ranges: List<Pair<Set<Int>, Set<Int>>>): Int {
    return ranges.count { it.first.intersect(it.second).isNotEmpty() }
  }

  fun part1() {
    val testInput = readInput("day04_test")
    val testCount = calcContains(convertRanges(testInput))
    println("Part 1 Test Count = $testCount")
    check(testCount == 2)

    val input = readInput("day04")
    val count = calcContains(convertRanges(input))
    println("Part 1 Count = $count")
    check(count == 524)
  }

  fun part2() {
    val testInput = readInput("day04_test")
    val testCount = calcOverlap(convertRanges(testInput))
    println("Part 2 Test Count = $testCount")
    check(testCount == 4)

    val input = readInput("day04")
    val count = calcOverlap(convertRanges(input))
    println("Part 2 Count = $count")
    check(count == 798)
  }
  part1()
  part2()
}

Day 05: kotlin

Supply Stacks

Today we had to implement a parser to read the state of stacks of containers and instructions for moving the containers. The result was a list of the top container labels. I decided to create a data structure for the instructions and a simple Stack.

Data Structures
data class Instruction(val count: Int, val from: Int, val to: Int)

class Stack<T>(private val elements: MutableList<T> = mutableListOf<T>()) {
  fun empty(): Boolean = elements.isEmpty()
  fun peek(): T = elements[elements.lastIndex]
  fun pop(): T = elements.removeAt(elements.lastIndex)
  fun push(value: T) {
    elements.add(value)
  }

  fun items() = elements.toList()
  fun size() = elements.size
}
Parsing
fun readStack(lines: List<String>, stack: Int): Stack<Char> {
  val result = mutableListOf<Char>()
  val offset = stack * 4 + 1
  for (line in lines) {
    if (line.length > offset) {
      val crate = line[offset]
      if (crate in 'A'..'Z') {
        result.add(crate)
      }
    }
  }
  result.reverse()
  println("Stack[${stack + 1}]=${result.joinToString("")}")
  return Stack(result)
}

fun loadStacks(input: List<String>): List<Stack<Char>> {
  val lines = input.toMutableList()
  val numbers = lines.last()
        .split(" ")
        .filter { it.isNotEmpty() }
        .map { it.toInt() }
  lines.removeAt(lines.lastIndex)
  val stacks = mutableListOf<Stack<Char>>()
  for (stack in numbers.indices) {
    stacks.add(readStack(lines, stack))
  }
  return stacks.toList()
}

fun loadInstructions(input: List<String>): List<Instruction> {
  val regex = """move (\d+) from (\d+) to (\d+)""".toRegex()
  return input.mapNotNull { line ->
    regex.find(line)?.let {
      val (count, from, to) = it.destructured
      Instruction(count.toInt(), from.toInt(), to.toInt())
    }
  }
}
Part 1

Perform all the instructions and provide the list of top level crates:

fun perform(stacks: List<Stack<Char>>, instruction: Instruction) {
  for (i in 1..instruction.count) {
    val crate = stacks[instruction.from - 1].pop()
    stacks[instruction.to - 1].push(crate)
  }
}
fun performAndFindTops(
  stacks: List<Stack<Char>>,
  instructions: List<Instruction>
): String {
  instructions.forEach {
    perform(stacks, it)
  }
  return stacks.joinToString("") { it.peek().toString() }
}
Part 2

The crane can now move multiple containers at the same time retaining their order. I decided to use a local stack to pop all the container and then push them again which will retain the order. The alternative would have been to adjust the Stack to remove multiple items at once.

fun perform9001(stacks: List<Stack<Char>>, instruction: Instruction) {
  println(instruction)
  val tmp = Stack<Char>()
  for (i in 1..instruction.count) {
    val crate = stacks[instruction.from - 1].pop()
    tmp.push(crate)
  }
  while (!tmp.empty()) {
    stacks[instruction.to - 1].push(tmp.pop())
  }
}
fun performAndFindTops9001(
    stacks: List<Stack<Char>>,
    instructions: List<Instruction>
): String {
  instructions.forEach {
    perform9001(stacks, it)
  }
  return stacks.joinToString("") { it.peek().toString() }
}
Takeaways

Sometimes a requirement change can impact your data structures in huge ways. Using a stack to represent the piles of crates was fine until we needed to move multiple crates at a time. In a real system the performance differences of moving multiple crates at the same time will be huge if it is a core part of the system.

Full source
data class Instruction(val count: Int, val from: Int, val to: Int)
class Stack<T>(private val elements: MutableList<T> = mutableListOf<T>()) {
  fun empty(): Boolean = elements.isEmpty()
  fun peek(): T = elements[elements.lastIndex]
  fun pop(): T = elements.removeAt(elements.lastIndex)
  fun push(value: T) {
    elements.add(value)
  }

  fun items() = elements.toList()
  fun size() = elements.size
}

fun main() {

  fun readStack(lines: List<String>, stack: Int): Stack<Char> {
    val result = mutableListOf<Char>()
    val offset = stack * 4 + 1
    for (line in lines) {
      if (line.length > offset) {
        val crate = line[offset]
        if (crate in 'A'..'Z') {
          result.add(crate)
        }
      }
    }
    result.reverse()
    println("Stack[${stack + 1}]=${result.joinToString("")}")
    return Stack(result)
  }

  fun loadStacks(input: List<String>): List<Stack<Char>> {
    val lines = input.toMutableList()
    val numbers = lines.last().split(" ").mapNotNull { if(it.isNotBlank()) it.toInt() else null }
    lines.removeAt(lines.lastIndex)
    val stacks = mutableListOf<Stack<Char>>()
    for (stack in numbers.indices) {
      stacks.add(readStack(lines, stack))
    }
    return stacks.toList()
  }

  fun loadInstructions(input: List<String>): List<Instruction> {
    val regex = """move (\d+) from (\d+) to (\d+)""".toRegex()
    return input.mapNotNull { line ->
      regex.find(line)?.let {
        val (count, from, to) = it.destructured
        Instruction(count.toInt(), from.toInt(), to.toInt())
      }
    }
  }

  fun perform(stacks: List<Stack<Char>>, instruction: Instruction) {
    for (i in 1..instruction.count) {
      val crate = stacks[instruction.from - 1].pop()
      stacks[instruction.to - 1].push(crate)
    }
  }

  fun perform9001(stacks: List<Stack<Char>>, instruction: Instruction) {
    val tmp = Stack<Char>()
    for (i in 1..instruction.count) {
      val crate = stacks[instruction.from - 1].pop()
      tmp.push(crate)
    }
    while (!tmp.empty()) {
      stacks[instruction.to - 1].push(tmp.pop())
    }
  }

  fun performAndFindTops(stacks: List<Stack<Char>>, instructions: List<Instruction>): String {
    instructions.forEach {
      perform(stacks, it)
    }
    stacks.forEach { stack -> println("[${stack.items().joinToString("")}]") }
    return stacks.joinToString("") { it.peek().toString() }
  }

  fun performAndFindTops9001(stacks: List<Stack<Char>>, instructions: List<Instruction>): String {
    instructions.forEach {
      perform9001(stacks, it)
    }
    stacks.forEach { stack -> println("[${stack.items().joinToString("")}]") }
    return stacks.joinToString("") { it.peek().toString() }
  }

  val test = """    [D]
[N] [C]
[Z] [M] [P]
 1   2   3

move 1 from 2 to 1
move 3 from 1 to 3
move 2 from 2 to 1
move 1 from 1 to 2
"""

  val testInputs = test.split("\n\n").map { readText(it) }
  val input = readFileGroup("day05")
  fun part1() {
    val testTops = performAndFindTops(loadStacks(testInputs[0]), loadInstructions(testInputs[1]))
    println("Part 1 Test Tops = $testTops")
    check(testTops == "CMZ")
    val tops = performAndFindTops(loadStacks(input[0]), loadInstructions(input[1]))
    println("Part 1 Tops = $tops")
    check(tops == "PTWLTDSJV")
  }

  fun part2() {
    val testTops = performAndFindTops9001(loadStacks(testInputs[0]), loadInstructions(testInputs[1]))
    println("Part 2 Test Tops = $testTops")
    check(testTops == "MCD")
    val tops = performAndFindTops9001(loadStacks(input[0]), loadInstructions(input[1]))
    println("Part 2 Tops = $tops")
    check(tops == "WZMFVGGZP")
  }

  part1()
  part2()

}

Day 06: kotlin

Tuning Trouble

Today was probably the easiest one so far from my perspective. We had to write a simple parser to find the first unique sequence of characters with a given length and report the number of characters read.

The Kotlin collections method windowed provides a way to create a window over an Iterable and provides a simple way to solve this. Checking that the content of the window as a unique set is the same size as the window.

Solution
fun findUniquePacketEnd(input: String, packetSize: Int): Int {
  return input.toList()
    .windowed(packetSize)
    .indexOfFirst { it.toSet().size == packetSize } + packetSize
}
Full source
fun main() {
  fun findUniquePacketEnd(input: String, packetSize: Int): Int {
    return input.toList()
      .windowed(packetSize)
      .indexOfFirst { it.toSet().size == packetSize } + packetSize
  }

  val input = readFileToString("day06")

  fun part1() {
    val testStart = findUniquePacketEnd("nznrnfrfntjfmvfwmzdfjlvtqnbhcprsg", 4)
    println("Part1 Test Start = $testStart")
    check(testStart == 10)
    val start = findUniquePacketEnd(input, 4)
    println("Part1 Start = $start")
    check(start == 1965)
  }

  fun part2() {
    val testStart = findUniquePacketEnd("nznrnfrfntjfmvfwmzdfjlvtqnbhcprsg", 14)
    println("Part 2 Test Message = $testStart")
    check(testStart == 29)
    val start = findUniquePacketEnd(input, 14)
    println("Part 2 Start = $start")
    check(start == 2773)
  }
  part1()
  part2()
}

Day 07: kotlin

No Space Left On Device

We had to parse a series of commands and output representing changing to and listing directories as in the example below.

$ cd /
$ ls
dir a
14848514 b.txt
8504156 c.dat
dir d
$ cd a
$ ls
dir e
29116 f
2557 g
62596 h.lst
$ cd e
$ ls
584 i
$ cd ..
$ cd ..
$ cd d
$ ls
4060174 j
8033020 d.log
5626152 d.ext
7214296 k

The aim was to determine directory sizes. In the first case the challenge was to find directories with a total size including children of below a threshold and the second problem was to find the smallest directory above a certain size.

Data Model
  data class FileInfo(val name: String, val size: Int)

  class Directory(val name: String) {
    private val files = mutableMapOf<String, FileInfo>()
    private val directories = mutableMapOf<String, Directory>()
    fun listDirectories() = directories.values.toList()
    fun hasDir(dirname: String): Boolean = directories.containsKey(dirname)
    fun getDir(dirname: String) = directories[dirname]
    fun addDir(dirname: String): Directory = directories.getOrPut(dirname) { Directory(dirname) }
    fun addFile(name: String, size: Int): FileInfo {
      val file = FileInfo(name, size)
      files[name] = file
      return file
    }
    fun listFiles(): List<FileInfo> = files.values.toList()
    fun fileSizes(): Int = files.values.sumOf { it.size }
    fun totalSize(): Int = fileSizes() + directories.values.sumOf { it.totalSize() }

    override fun toString(): String {
      return "Directory(name='$name'," +
                "directories=${directories.values.map { it.name }.toList()}," +
                "files=${files.values.map { "${it.name}:${it.size}" }}" +
              ")"
    }
    override fun equals(other: Any?): Boolean {
      if (this === other) return true
      if (javaClass != other?.javaClass) return false

      other as Directory

      if (name != other.name) return false

      return true
    }
    override fun hashCode(): Int {
      return name.hashCode()
    }
}
Parsing

The parsing meant keeping track of the directory tree and the current directory. I used the Stack from Day 05 to maintain the parent directories.

fun parseCommandsAndOutput(lines: List<String>): Directory {
  val root = Directory("/")
  val dirs = Stack<Directory>()
  dirs.push(root)
  var current = root
  for(line in lines) {
    val data = line.split(" ")
    when {
      data[0] == "$" && data[1] == "cd" && data[2] == "/" -> { dirs.clear(); dirs.push(root) }
      data[0] == "$" && data[1] == "cd" && data[2] == ".." -> { dirs.pop(); current = dirs.peek()}
      data[0] == "$" && data[1] == "cd" -> { dirs.push(current.addDir(data[2])); current = dirs.peek() }
      data[0] == "$" && data[1] == "ls" -> println("listing ${dirs.items().joinToString("/") { it.name }}")
      data[0] == "dir" -> current.addDir(data[1])
      else -> {
        val file = current.addFile(data[1], data[0].toInt())
        println("file=dir:${current.name} + ${file.name}:${file.size}")
      }
    }
  }
  return root
}
Solutions

Both solutions need to obtain a list of all directories.

Shared
fun listAllDirectories(directories: Directory): List<Directory> {
  val result = mutableListOf<Directory>()
  directories.listDirectories().forEach {
    result.add(it)
    result.addAll(listAllDirectories(it))
  }
  return result
}
Part 1

Find the directory sizes at most 100000 and calculate the total.

fun calcDirectoriesBelow(input: List<String>, maxValue: Int): Int {
  val root = parseCommandsAndOutput(input)
  val directories = listAllDirectories(root)
  return directories.map { it.totalSize() }.filter { it <= maxValue }.sum()
}
Part 2

Find the small of the directories large enough to delete in order to free up enough space so that at least 30000000 of 70000000 is unused.

fun calcDirectoriesToFree(input: List<String>, diskSize: Int, freeSpace: Int): Int {
  val root = parseCommandsAndOutput(input)
  val directories = listAllDirectories(root)
  val unused = diskSize - root.totalSize()
  val requiredDelete = freeSpace - unused
  return directories.map { it.totalSize() }.filter { it > requiredDelete }.min()
}
Full source
fun main() {
  val test = readFile("day07_test")
  val input = readFile("day07")

  data class FileInfo(val name: String, val size: Int)
  class Directory(val name: String) {
    private val files = mutableMapOf<String, FileInfo>()
    private val directories = mutableMapOf<String, Directory>()
    fun listDirectories() = directories.values.toList()

    fun hasDir(dirname: String): Boolean =
            directories.containsKey(dirname)
    fun getDir(dirname: String) = directories[dirname]
    fun addDir(dirname: String): Directory =
            directories.getOrPut(dirname) { Directory(dirname) }
    fun addFile(name: String, size: Int): FileInfo {
      val file = FileInfo(name, size)
      files[name] = file
      return file
    }

    fun listFiles(): List<FileInfo> = files.values.toList()
    fun fileSizes(): Int = files.values.sumOf { it.size }
    fun totalSize(): Int =
            fileSizes() + directories.values.sumOf { it.totalSize() }
    override fun toString(): String {
      return "Directory(name='$name',directories=${
        directories.values.map { it.name }.toList()
      },files=${files.values.map { "${it.name}:${it.size}" }})"
    }

    override fun equals(other: Any?): Boolean {
      if (this === other) return true
      if (javaClass != other?.javaClass) return false

      other as Directory

      if (name != other.name) return false

      return true
    }

    override fun hashCode(): Int {
      return name.hashCode()
    }

    private fun printTree(dir: Directory, depth: Int) {
      println("- ${dir.name} (dir)")
      val prefix = 0 until depth
      dir.listDirectories().forEach {
        prefix.forEach { _ -> print(' ') }
        printTree(it, depth + 2)
      }
      dir.listFiles().forEach {
        prefix.forEach { _ -> print(' ') }
        println("- ${it.name} (file, size = ${it.size})")
      }
    }

    fun printTree() = printTree(this, 0)
  }

  fun listAllDirectories(directories: Directory): List<Directory> {
    val result = mutableListOf<Directory>()
    directories.listDirectories().forEach {
      result.add(it)
      result.addAll(listAllDirectories(it))
    }
    return result
  }

  fun parseCommandsAndOutput(input: List<String>): Directory {
    val root = Directory("/")
    val dirs = Stack<Directory>()
    dirs.push(root)
    var current = root
    input.forEach { line ->
      val data = line.split(" ")
      when {
        data[0] == "$" && data[1] == "cd" && data[2] == "/" -> { dirs.clear(); dirs.push(root) }
        data[0] == "$" && data[1] == "cd" && data[2] == ".." -> { dirs.pop(); current = dirs.peek()}
        data[0] == "$" && data[1] == "cd" -> { dirs.push(current.addDir(data[2])); current = dirs.peek() }
        data[0] == "$" && data[1] == "ls" -> println("listing ${dirs.items().joinToString("/") { it.name }}")
        data[0] == "dir" -> current.addDir(data[1])
        else -> {
          val file = current.addFile(data[1], data[0].toInt())
          println("file=dir:${current.name} + ${file.name}:${file.size}")
        }
      }
    }
    return root
  }


  fun calcDirectoriesBelow(input: List<String>, maxValue: Int): Int {
    val root = parseCommandsAndOutput(input)
    root.printTree()
    val directories = listAllDirectories(root)
    return directories.map { it.totalSize() }.filter { it <= maxValue }.sum()
  }

  fun calcDirectoriesToFree(input: List<String>, diskSize: Int, freeSpace: Int): Int {
    val root = parseCommandsAndOutput(input)
    val directories = listAllDirectories(root)
    val unused = diskSize - root.totalSize()
    val requiredDelete = freeSpace - unused
    return directories.map { it.totalSize() }.filter { it > requiredDelete }.min()
  }


  fun part1() {
    val testResult = calcDirectoriesBelow(test, 100000)
    println("Part 1 Answer = $testResult")
    check(testResult == 95437)
    separator()
    val result = calcDirectoriesBelow(input, 100000)
    check(result == 1792222)
    println("Part 1 Answer = $result")
    separator()
  }

  fun part2() {
    val testResult = calcDirectoriesToFree(test, 70000000, 30000000)
    println("Part 2 Answer = $testResult")
    check(testResult == 24933642)
    separator()
    val result = calcDirectoriesToFree(input, 70000000, 30000000)
    println("Part 2 Answer = $result")
    check(result == 1112963)
    separator()
  }
  println("Day - 07")
  part1()
  part2()
}

Day 08: kotlin

Treetop Tree House

Today’s puzzle was all about creating a grid and determining the state of coordinates given certain conditions.

Model

I decided to create a class to represent the grid as an array of int array.

class Grid(val lines: Array<IntArray>) {
    fun width() = lines[0].size
    fun height() = lines.size
    fun get(x: Int, y: Int) = lines[x][y]
}
Parsing

The data was presents as lines of digits, each digits represented a tree and the value was the height of the tree.

30373
25512
65332
33549
35390

Parsing meant converting each line to an array of int by converting each character to it’s integer representation.

fun parseGrid(input: List<String>): Grid {
  return Grid(input.map { line ->
            line.toList()
              .map { it - '0' }
              .toIntArray()
          }.toTypedArray())
}
Part 1

We had to determine how many trees are visible considering it is invisible it there is a tree of similar or greater height above or below, to the left or right.

I added a visible method to Grid

fun visible(x: Int, y: Int): Boolean {
  val treeHeight = get(x, y)
  var bottom = true
  var top = true
  var left = true
  var right = true
  for (i in 0 until x) {
    val tree = get(i, y)
    if (tree >= treeHeight) {
      top = false
      break
    }
  }
  for (i in x + 1 until height()) {
   if (get(i, y) >= treeHeight) {
      bottom = false
      break
    }
  }
 for (i in y + 1 until width()) {
   if (get(x, i) >= treeHeight) {
      right = false
      break
    }
  }
  for (i in 0 until y) {
    if (get(x, i) >= treeHeight) {
      left = false
      break
    }
  }
  return top || bottom || left || right
}

fun calcVisible(grid: Grid): Int {
  val height = grid.height()
  val width = grid.width()
  var result = (height * 2) + (width * 2) - 4
  for (x in 1 until height - 1) {
    for (y in 1 until width - 1) {
      if (grid.visible(x, y)) {
        result += 1
      }
    }
  }
  return result
}
Part 2

We had to calculate a scenic value for each tree and determine the answer was maximum scenic. The scenic value was determined by how many trees were visible from a given tree.

I added a scenic method to Grid.

fun scenic(x: Int, y: Int): Int {
  val treeHeight = get(x, y)
  var bottom = 0
  var top = 0
  var left = 0
  var right = 0
  for (i in x + 1 until height()) {
    bottom += 1
    if (get(i, y) >= treeHeight) {
      break
    }
  }
  for (i in x - 1 downTo  0 ) {
    top += 1
    if (get(i, y) >= treeHeight) {
      break
    }
  }
  for (i in y + 1 until width()) {
    right += 1
    if (get(x, i) >= treeHeight) {
      break
    }
  }
  for (i in y - 1 downTo  0 ) {
    left += 1
    if (get(x, i) >= treeHeight) {
      break
    }
  }
  return bottom * left * right * top
}

fun calcMaxScenic(grid: Grid): Int {
  val height = grid.height()
  val width = grid.width()
  var result = 0
  for (x in 1 until height - 1) {
    for (y in 1 until width - 1) {
      result = max(result, grid.scenic(x, y))
    }
  }
  return result
}
Full source
import kotlin.math.max

fun main() {
  val test = readLines(
    """30373
25512
65332
33549
35390"""
  )
  val input = readFile("day08")

  class Grid(val lines: Array<IntArray>) {
    fun width() = lines[0].size
    fun height() = lines.size
    fun get(x: Int, y: Int) = lines[x][y]
    fun visible(x: Int, y: Int): Boolean {
      val treeHeight = get(x, y)
      var bottom = true
      var top = true
      var left = true
      var right = true
      for (i in 0 until x) {
        val tree = get(i, y)
        if (tree >= treeHeight) {
          top = false
          break
        }
      }
      for (i in x + 1 until height()) {
        if (get(i, y) >= treeHeight) {
          bottom = false
          break
        }
      }
      for (i in y + 1 until width()) {
        if (get(x, i) >= treeHeight) {
          right = false
          break
        }
      }
      for (i in 0 until y) {
        if (get(x, i) >= treeHeight) {
          left = false
          break
        }
      }
      return top || bottom || left || right
    }

    fun scenic(x: Int, y: Int): Int {
      val treeHeight = get(x, y)
      var bottom = 0
      var top = 0
      var left = 0
      var right = 0
      for (i in x + 1 until height()) {
        bottom += 1
        if (get(i, y) >= treeHeight) {
          break
        }
      }
      for (i in x - 1 downTo  0 ) {
        top += 1
        if (get(i, y) >= treeHeight) {
          break
        }
      }
      for (i in y + 1 until width()) {
        right += 1
        if (get(x, i) >= treeHeight) {
          break
        }
      }
      for (i in y - 1 downTo  0 ) {
        left += 1
        if (get(x, i) >= treeHeight) {
          break
        }
      }
      return bottom * left * right * top
    }
  }

  fun parseGrid(input: List<String>): Grid {
    return Grid(input.map { line ->
                 line.toList()
                   .map { it - '0' }
                   .toIntArray()
             }.toTypedArray()
     )
  }

  fun calcVisible(grid: Grid): Int {
    val height = grid.height()
    val width = grid.width()
    var result = (height * 2) + (width * 2) - 4
    for (x in 1 until height - 1) {
      for (y in 1 until width - 1) {
        if (grid.visible(x, y)) {
          result += 1
        }
      }
    }
    return result
  }

  fun calcMaxScenic(grid: Grid): Int {
    val height = grid.height()
    val width = grid.width()
    var result = 0
    for (x in 1 until height - 1) {
      for (y in 1 until width - 1) {
        result = max(result, grid.scenic(x, y))
      }
    }
    return result
  }

  fun part1() {
    val testResult = calcVisible(parseGrid(test))
    println("Part 1 Answer = $testResult")
    check(testResult == 21)
    val result = calcVisible(parseGrid(input))
    println("Part 1 Answer = $result")
    check(result == 1851)
  }

  fun part2() {
    val testResult = calcMaxScenic(parseGrid(test))
    println("Part 2 Answer = $testResult")
    check(testResult == 8)
    val result = calcMaxScenic(parseGrid(input))
    println("Part 1 Answer = $result")
    check(result == 574080)
  }
  println("Day - 08")
  separator()
  part1()
  separator()
  part2()
}

Day 09: kotlin

Rope Bridge

Today’s puzzle was about simulating the movement of a rope or chain. The knots / links follow each other when the head is pulled in a direction. The simulation had to implement rules for the movement and record the movement of the tail and reporting the number of unique positions visited by the tail.

In part 1 the rope has 2 knots and in part 2 the rope had 10 knots.

Model

I decided to model the Rope as an array of Position

data class Position(val row: Int, val col: Int) {
  fun left() = Position(row, col - 1)
  fun right() = Position(row, col + 1)
  fun above() = Position(row - 1, col)
  fun below() = Position(row + 1, col)
  fun distance(pos: Position): Int = max(abs(pos.row - row), abs(pos.col - col))
  operator fun minus(pos: Position) = Position(row - pos.row, col - pos.col)
  operator fun plus(pos: Position) = Position(row + pos.row, col + pos.col)
  fun sign(): Position = Position(row.sign,col.sign)
  fun move(direction: Char): Position {
    return when (direction) {
      'U' -> above()
      'D' -> below()
      'L' -> left()
      'R' -> right()
      else -> error("Expected one of U,D,L,R not ${direction}")
    }
  }
  override fun toString(): String {
    return "(col=$col, row=$row)"
  }
}

class Rope(val knots: Array<Position>) {
  val head: Position
    get() = knots[0]
  val tail: Position
    get() = knots[knots.lastIndex]

  operator fun set(index: Int, pos: Position) { knots[index] = pos }

  operator fun get(index: Int) = knots[index]
  fun indexOf(pos: Position) = knots.indexOf(pos)
  override fun toString() = knots.contentToString()
}
Parsing

The input was a list of steps with the direction as one of U,D,L,R and a number for the distance moved.

data class Step(val direction: Char, val distance: Int)

fun parseSteps(input: List<String>): List<Step> {
  return input.map {
    val words = it.split(" ")
    Step(words[0][0], words[1].toInt())
  }
}
Simulating the rope

After when I got to part 2 I had a situation where my answer to the provided data was correct but AOC report my answer with the input as low. I tried to find a case where I wasn’t handling the tail correctly. All this back and forth lead me to simplifying the calculation to the point where I calculated the difference between the knots and the movement was then a step in the direction of the first knot and it could be diagonally if the difference had values in both axis.

This worked and was a lot simpler. When I looked at some other submissions in the Kotlin community I discovered Int.sign() which returns 0,1 or -1 depending in the value. I added operators to Position for - and + and a sign method. This reduced the final expression to a very simple one.

for (index in 1 until knots) {
  val prev = rope[index - 1]                      (1)
  val next = rope[index]                          (2)
  if (prev != next && prev.distance(next) > 1) {  (3)
    val diff = prev - next                        (4)
    rope[index] = next + diff.sign()              (5)
  }
}
1 The previous knot
2 The knot we want to move
3 If they aren’t in same location and the Chebyshev distance is more than 1.
4 Determine the difference between the positions
5 Add the sign of the difference to the knot we want to move 
fun calcVisits(steps: List<Step>, knots: Int, printStep: Boolean): Int {
  val rope = Rope(Array(knots) { Position(0, 0) })
  val start = rope.head
  val visited = mutableSetOf<Position>()
  visited.add(rope.tail)
  steps.forEach { step ->
    for (i in 0 until step.distance) {
      rope[0] = rope.head.move(step.direction)
      for (index in 1 until knots) {
        val prev = rope[index - 1]
        val next = rope[index]
        if (prev != next && prev.distance(next) > 1) {
          val diff = prev - next
          rope[index] = next + diff.sign()
        }
      }
      visited.add(rope.tail)
      if (printStep) {
        println()
        print(steps, visited, start, rope, knots, false)
      }
    }
  }
  println()
  print(steps, visited, start, rope, knots, true)
  return visited.size
}
Full source
import kotlin.math.abs
import kotlin.math.max
import kotlin.math.min
import kotlin.math.sign

fun main() {

  val test = """R 4
U 4
L 3
D 1
R 4
D 1
L 5
R 2"""
  val test2 = """R 5
U 8
L 8
D 3
R 17
D 10
L 25
U 20"""
  val input = readFile("day09")

  data class Step(val direction: Char, val distance: Int)
  data class Position(val row: Int, val col: Int) {
    fun left() = Position(row, col - 1)
    fun right() = Position(row, col + 1)
    fun above() = Position(row - 1, col)
    fun below() = Position(row + 1, col)
    fun distance(pos: Position): Int = max(abs(pos.row - row), abs(pos.col - col))
    operator fun minus(pos: Position) = Position(row - pos.row, col - pos.col)
    operator fun plus(pos: Position) = Position(row + pos.row, col + pos.col)
    fun sign(): Position = Position(row.sign,col.sign)
    fun move(direction: Char): Position {
      return when (direction) {
        'U' -> above()
        'D' -> below()
        'L' -> left()
        'R' -> right()
        else -> error("Expected one of U,D,L,R not ${direction}")
      }
    }

    override fun toString(): String {
      return "(col=$col, row=$row)"
    }
  }

  fun parseSteps(input: List<String>): List<Step> {
    return input.map {
      val words = it.split(" ")
      Step(words[0][0], words[1].toInt())
    }
  }

  class Rope(val knots: Array<Position>) {
    val head: Position
      get() = knots[0]
    val tail: Position
      get() = knots[knots.lastIndex]
    operator fun set(index: Int, pos: Position) { knots[index] = pos }
    operator fun get(index: Int) = knots[index]
    fun indexOf(pos: Position) = knots.indexOf(pos)
    override fun toString() = knots.contentToString()
  }

  fun print(
    steps: List<Step>,
    visited: Set<Position>,
    start: Position,
    rope: Rope,
    knots: Int,
    visitsOnly: Boolean = false
  ) {
    var maxRow = 0
    var minRow = 0
    var maxCol = 0
    var minCol = 0
    var dummy = Position(0, 0)
    steps.forEach { step ->
      repeat(step.distance) {
        dummy = dummy.move(step.direction)
        maxRow = max(maxRow, dummy.row)
        maxCol = max(maxCol, dummy.col)
        minRow = min(minRow, dummy.row)
        minCol = min(minCol, dummy.col)
      }
    }

    for (row in minRow..maxRow) {
      val covered = mutableSetOf<Int>()
      for (col in minCol..maxCol) {
        val pos = Position(row, col)
        if (visitsOnly) {
          if (pos == start) {
            print('s')
          } else {
            print(if (visited.contains(pos)) '#' else '.')
          }
        } else {
          val index = rope.indexOf(pos)
          when {
            index == 0 -> print('H')
            index > 0 -> print(if (knots == 2) 'T' else index.toString())
            pos == start -> print('s')
            else -> print(if (visited.contains(pos)) '#' else '.')
          }
          if(index >= 0 && covered.isEmpty()) {
            if(pos == start) {
              covered.add(rope.knots.size) // indicate 's'
            }
            covered.add(index)
            for (i in index..rope.knots.lastIndex) {
              if (pos == rope[i]) {
                covered.add(i)
              }
            }
            if(covered.size == 1) {
              covered.clear()
            }
          }
        }
      }
      if(covered.size > 1) {
        print("  (")
        val coveredKnots = covered.sorted()
        coveredKnots.forEachIndexed { index, knot ->
          if(index == 1) {
            print(" covers ")
          } else if(index > 1) {
            print(" ,")
          }
          when(knot) {
            0 -> print('H')
            rope.knots.lastIndex -> print('T')
            rope.knots.size -> print('s')
            else -> print("$knot")
          }
        }
        println(')')
      }
      println()
    }
  }

  fun calcVisits(steps: List<Step>, knots: Int, printStep: Boolean): Int {
    val rope = Rope(Array(knots) { Position(0, 0) })
    val start = rope.head
    val visited = mutableSetOf<Position>()
    visited.add(rope.tail)
    steps.forEach { step ->
      for (i in 0 until step.distance) {
        rope[0] = rope.head.move(step.direction)
        for (index in 1 until knots) {
          val prev = rope[index - 1]
          val next = rope[index]

          if (prev != next && prev.distance(next) > 1) {
            val diff = prev - next
            rope[index] = next + diff.sign()
          }
        }
        visited.add(rope.tail)
        if (printStep) {
          println()
          print(steps, visited, start, rope, knots, false)
        }
      }
    }
    println()
    print(steps, visited, start, rope, knots, true)
    return visited.size
  }

  fun part1() {
    val testResult = calcVisits(parseSteps(readLines(test)), 2, true)
    println("Part 1 Answer = $testResult")
    check(testResult == 13)
    val result = calcVisits(parseSteps(input), 2, false)
    println("Part 1 Answer = $result")
    check(result == 6503)
  }

  fun part2() {
    check(calcVisits(parseSteps(readLines(test)), 10, true) == 1)
    val testResult = calcVisits(parseSteps(readLines(test2)), 10, true)
    println("Part 2 Answer = $testResult")
    check(testResult == 36)
    val result = calcVisits(parseSteps(input), 10, false)
    println("Part 2 Answer = $result")
    check(result == 2724)
  }

  println("Day - 09")
  separator()
  part1()
  separator()
  part2()
}

Day 10: kotlin

Cathode-Ray Tube

Today’s puzzle was about simulating a computer and the cathode ray tube. So far we have only 2 instructions to simulate: noop and addx. It very important to carefully read the instructions describing the clock cycles. In this case noop has one cycle and addx has two cycle.

Input Model

I decided to model a instructions as a sealed class and the processor as a class to maintain the clock and register value with a lambda to be called on each tick.

sealed class OpCode(val prefix: String) {
  object NOOP: OpCode("noop")
  data class ADDX(val value: Int): OpCode("addx")
}
Parsing

Parsing will create the instances of the various inner classes of the sealed class.

fun parseInstructions(lines: List<String>): List<OpCode> {
  return lines.map { ins ->
    val words = ins.split(" ")
    when (words[0]) {
      "noop" -> OpCode.NOOP
      "addx" -> OpCode.ADDX(words[1].toInt())
      else -> error("Unknown instruction: $ins")
    }
  }
}
Processor Model
class Processor(val processing: Processor.() -> Unit) {
  var clock = 0
    private set
  var regX: Int = 1
    private set

  fun tick() {
    clock += 1
    processing(this) (1)
  }
  fun execute(instructions: List<OpCode>) {
    instructions.forEach { ins ->
      when (ins) {
        is OpCode.NOOP -> tick()
        is OpCode.ADDX -> addX(ins)
      }
    }
  }

  private fun addX(ins: OpCode.ADDX) {
    tick()
    val value = ins.value
    tick()
    regX += value
  }
}
1 processing lambda is called after each clock tick.
Part 1

The first part had to calculate signal string based on the value of regX and on the 20th tick and each 40th tick thereafter.

fun calcSignalStrength(instructions: List<OpCode>): Int {
  var signalValue = 0
  val cpu = Processor {               (1)
    if (clock % 40 == 20) {
      signalValue += regX * clock     (2)
    }
  }
  cpu.execute(instructions)
  return signalValue
}
1 The lambda declaration after the Processor will be invoked on each tick
2 The lambda cannot modify clock or regX
Part 2

The second part had to render the CRT of 40 characters wide. The CRT prints from left to right on each clock tick and will print a # if the 3 character sprite overlaps with the cursor position, otherwise it prints .. I had to print spaces instead of dots before I could read the character spelled out by part 2.

fun renderCrt(instructions: List<OpCode>): List<String> {
  val pixels = mutableListOf<Char>()
  val crt = mutableListOf<String>()
  val cpu = Processor {
    val sprite = regX - 1
    val cursor = (clock - 1) % 40
    if (cursor >= sprite && cursor <= sprite + 2) {
      pixels.add('#')
    } else {
      pixels.add('.')
    }
    if (cursor == 39) {
      crt.add(pixels.joinToString(""))
      pixels.clear()
    }
  }
  cpu.execute(instructions)
  return crt.toList()
}
Full source
import utils.*

sealed class OpCode(val prefix: String) {
  object NOOP: OpCode("noop")
  data class ADDX(val value: Int): OpCode("addx")
}

fun main() {
  val test = readFile("day10_test")
  val input = readFile("day10")

  fun parseInstructions(lines: List<String>): List<OpCode> {
    return lines.map { ins ->
      val words = ins.split(" ")
      when (words[0]) {
        "noop" -> OpCode.NOOP
        "addx" -> OpCode.ADDX(words[1].toInt())
        else -> error("Unknown instruction: $ins")
      }
    }
  }

  class Processor(val processing: Processor.() -> Unit) {
    var clock = 0
      private set

    fun tick() {
      clock += 1
      processing(this)
    }

    var regX: Int = 1
      private set

    fun execute(instructions: List<OpCode>) {
      instructions.forEach { ins ->
        when (ins) {
          is OpCode.NOOP -> tick()
          is OpCode.ADDX -> addX(ins)
        }
      }
    }

    private fun addX(ins: OpCode.ADDX) {
      tick()
      val value = ins.value
      tick()
      regX += value
    }
  }


  fun calcSignalStrength(instructions: List<OpCode>): Int {
    var signalValue = 0
    val cpu = Processor {
      if (clock % 40 == 20) {
        signalValue += regX * clock
      }
    }
    cpu.execute(instructions)
    return signalValue
  }

  fun renderCrt(instructions: List<OpCode>): List<String> {
    val pixels = mutableListOf<Char>()
    val crt = mutableListOf<String>()
    val cpu = Processor {
      val sprite = regX - 1
      val cursor = (clock - 1) % 40
      if (cursor >= sprite && cursor <= sprite + 2) {
        pixels.add('#')
      } else {
        pixels.add('.')
      }
      if (cursor == 39) {
        crt.add(pixels.joinToString(""))
        pixels.clear()
      }
    }
    cpu.execute(instructions)

    return crt.toList()
  }

  fun part1() {
    val testResult = calcSignalStrength(parseInstructions(test))
    println("Part 1 Answer = $testResult")
    check(testResult == 13140)
    val result = calcSignalStrength(parseInstructions(input))
    println("Part 1 Answer = $result")
  }

  val expectedTestCrt = readLines(
    """##..##..##..##..##..##..##..##..##..##..
###...###...###...###...###...###...###.
####....####....####....####....####....
#####.....#####.....#####.....#####.....
######......######......######......####
#######.......#######.......#######....."""
  )
  val expectedCrt = readLines(
    """####..##....##..##..###....##.###..####.
#....#..#....#.#..#.#..#....#.#..#.#....
###..#.......#.#..#.#..#....#.#..#.###..
#....#.......#.####.###.....#.###..#....
#....#..#.#..#.#..#.#....#..#.#.#..#....
#.....##...##..#..#.#.....##..#..#.####."""
  )

  fun part2() {
    val testCrt = renderCrt(parseInstructions(test))
    println("Part 2 Test")
    testCrt.forEach { println(it) }
    check(testCrt == expectedTestCrt)
    val crt = renderCrt(parseInstructions(input))
    println("Part 2")
    crt.forEach { println(it.replace('.',' ')) }
    check(crt == expectedCrt)
  }
  println("Day - 10")
  separator()
  part1()
  separator()
  part2()
}

Day 11: kotlin

Monkey in the Middle

Today’s puzzle require the parsing of rules describing monkeys that have some of your items. Each monkey will toss the item to another monkey based on the worried factor perceived by the monkey.

Model

The model represents all the rules as well as tracking the number of inspections performed by the monkey.

data class Monkey(
  val number: Int,
  val worriedLevel: Long,
  val items: MutableList<Long>,
  val boredTarget: Int,
  val worriedTarget: Int,
  val expression: (Long) -> Long,
) {
  var inspected: Int = 0
    private set
  fun inspect(value: Int) {
    inspected += value
  }
  fun findTarget(boredLevel: Long) =
      if (boredLevel % worriedLevel != 0L) worriedTarget else boredTarget
  override fun toString(): String {
    return "Monkey(number=$number, " +
        "inspected=$inspected, " +
        "worriedLevel=$worriedLevel, " +
        "boredTarget=$boredTarget, " +
        "worriedTarget=$worriedTarget, "+
        "items=$items)"
  }
}
Parsing

I decided to parse each monkey rules using a regular expression for each line.

val regexMonkey = listOf(
    "Monkey (\\d+):$",
    "  Starting items:\\s*((\\S+(,\\s)*)*)\$",
    "  Operation: new =\\s(\\S+)\\s(\\+|\\*)\\s(\\S+)\$",
    "  Test: divisible by (\\d+)$",
    "    If true: throw to monkey (\\d+)$",
    "    If false: throw to monkey (\\d+)$"
).map { it.toRegex() }
fun parseMonkey(lines: List<String>): Monkey {
  val result = regexMonkey.mapIndexed { index, regex ->
          regex.find(lines[index]) ?: error("Regex error for ${lines[index]}")
      }.toTypedArray()

  val items = result[1].groupValues[1].split(",")
        .map { it.trim().toLong() }
        .toMutableList()

  val words = result[2].groupValues.drop(1)
  check(words[0] == "old")
  val isAdd = words[1] == "+"
  val constant = words[2].toLongOrNull()
  val lambda: (Long) -> Long =
          if (isAdd)
            { old -> Math.addExact(old, constant ?: old) }
          else
            { old -> Math.multiplyExact(old, constant ?: old) } (1)

  return Monkey(
      result[0].groupValues[1].toInt(),
      result[3].groupValues[1].toLong(),
      items,
      result[4].groupValues[1].toInt(),
      result[5].groupValues[1].toInt(),
      lambda
  )
}
1 Math.addExact and Math.multiplyExact will result in an exception if there is an overflow
Processing

Each monkey must process their items in the sequence of the assigned number.

fun processItems(
    monkeys: Map<Int, Monkey>,
    rounds: Int,
    divisor: Long = 3L
): Map<Int, Monkey> {
  val divisors = monkeys.values
      .map { monkey -> monkey.worriedLevel }
      .reduce { acc, l -> acc * l * divisor } (1)
  val sorted = monkeys.values.sortedBy { it.number }
  repeat(rounds) {
    sorted.forEach { monkey ->
      monkey.items.forEach { item ->
        val level = monkey.expression(item)
        val bored = level / divisor
        val targetNumber = monkey.findTarget(bored)
        val targetMonkey = monkeys[targetNumber]
            ?: error("Cannot find target Monkey:$targetNumber")
        targetMonkey.items.add(bored % divisors) (2)
      }
      monkey.inspect(monkey.items.size)
      monkey.items.clear()
    }
  }
  return monkeys
}
1 multiplying all worriedLevel with each other and the required divisor provides a least common divisor.
2 mod with least common divisor to ensure the smallest valid value.
Part 1

Initially using Int values caused an overflow and I changed the worriedLevel and items to Long.

fun calcShenanigans1(input: List<String>): Int {
  val monkeys = input.chunked(7)
          .map { parseMonkey(it) }
          .associateBy { it.number }
  val result = processItems(monkeys, 20)
  return result.values
          .map { it.inspected }
          .sortedDescending()
          .take(2)
          .reduce { acc, i -> acc * i }
}
Part 2

When we had to increase the number of rounds to 10000 the worriedLevel overflowed. Using BigInteger doesn’t solve the problem because the calculations for BigInteger take too long as the multiplication ofr BigInteger takes exponentially longer as the numbers increase.

Using a smallest common divisor all the modulus and / operations will ensure that the overflow is prevented until the number of Monkeys become very large. 
fun calcShenanigans2(input: List<String>): Long {
  val monkeys = input.chunked(7)
          .map { parseMonkey(it) }
          .associateBy { it.number }
  val result = processItems(monkeys, 10000, 1)
  return result.values
          .map { it.inspected.toLong() }
          .sortedDescending()
          .take(2)
          .reduce { acc, i -> acc * i }
}
Full source
import utils.readFile
import utils.separator

fun main() {

  val test = readFile("day11_test")
  val input = readFile("day11")

  data class Monkey(
    val number: Int,
    val worriedLevel: Long,
    val items: MutableList<Long>,
    val boredTarget: Int,
    val worriedTarget: Int,
    val expression: (Long) -> Long,
  ) {
    var inspected: Int = 0
      private set
    fun inspect(value: Int) {
      inspected += value
    }
    fun findTarget(boredLevel: Long) = if (boredLevel % worriedLevel != 0L) worriedTarget else boredTarget
    override fun toString(): String {
      return "Monkey(number=$number, inspected=$inspected, worriedLevel=$worriedLevel, boredTarget=$boredTarget, worriedTarget=$worriedTarget, items=$items)"
    }
  }

  val regexMonkey = listOf(
    "Monkey (\\d+):$",
    "  Starting items:\\s*((\\S+(,\\s)*)*)\$",
    "  Operation: new =\\s(\\S+)\\s(\\+|\\*)\\s(\\S+)\$",
    "  Test: divisible by (\\d+)$",
    "    If true: throw to monkey (\\d+)$",
    "    If false: throw to monkey (\\d+)$"
  ).map { it.toRegex() }
  fun parseMonkey(lines: List<String>): Monkey {
    val result = regexMonkey.mapIndexed { index, regex ->
              regex.find(lines[index]) ?: error("Regex error for ${lines[index]}")
        }.toTypedArray()

    val items = result[1].groupValues[1].split(",")
      .map { it.trim().toLong() }
      .toMutableList()

    val words = result[2].groupValues.drop(1)
    check(words[0] == "old")
    val isAdd = words[1] == "+"
    val constant = words[2].toLongOrNull()
    val lambda: (Long) -> Long =
        if (isAdd)
          { old -> old + (constant ?: old) }
        else
          { old -> old * (constant ?: old) }

    return Monkey(
      result[0].groupValues[1].toInt(),
      result[3].groupValues[1].toLong(),
      items,
      result[4].groupValues[1].toInt(),
      result[5].groupValues[1].toInt(),
      lambda
    )
  }

  fun processItems(
    monkeys: Map<Int, Monkey>,
    rounds: Int,
    divisor: Long = 3L
  ): Map<Int, Monkey> {
    // The mod of the total of worriedLevels overcomes the Long overflow
    // using all divisors ensure that it is the smallest value that will
    // still satisfy all the requirements when using a large number of rounds
    val divisors = monkeys.values
          .map { monkey -> monkey.worriedLevel }
          .reduce { acc, l -> acc * l * divisor }
    val sorted = monkeys.values.sortedBy { it.number }
    repeat(rounds) {
      sorted.forEach { monkey ->
        monkey.items.forEach { item ->
          val level = monkey.expression(item)
          val bored = level / divisor
          val targetNumber = monkey.findTarget(bored)
          val targetMonkey = monkeys[targetNumber]
                  ?: error("Cannot find target Monkey:$targetNumber")
          targetMonkey.items.add(bored % divisors) // mod to ensure smallest valid value
        }
        monkey.inspect(monkey.items.size)
        monkey.items.clear()
      }
    }
    return monkeys
  }

  fun calcShenanigans1(input: List<String>): Int {
    val monkeys = input.chunked(7)
            .map { parseMonkey(it) }
            .associateBy { it.number }
    println("Before: ====")
    monkeys.values.forEach { println(it.toString()) }
    val result = processItems(monkeys, 20)
    println("After: ====")
    result.values.forEach { println(it.toString()) }
    return result.values
            .map { it.inspected }
            .sortedDescending()
            .take(2)
            .reduce { acc, i -> acc * i }
  }

  fun calcShenanigans2(input: List<String>): Long {
    val monkeys = input.chunked(7)
            .map { parseMonkey(it) }
            .associateBy { it.number }
    println("Before: ====")
    monkeys.values.forEach { println(it.toString()) }
    val result = processItems(monkeys, 10000, 1)
    println("After: ====")
    result.values.forEach { println(it.toString()) }
    return result.values
            .map { it.inspected.toLong() }
            .sortedDescending()
            .take(2)
            .reduce { acc, i -> acc * i }
  }

  fun part1() {
    val testResult = calcShenanigans1(test)
    println("Part 1 Answer = $testResult")
    check(testResult == 10605)
    val result = calcShenanigans1(input)
    println("Part 1 Answer = $result")
    check(result == 151312)
  }

  fun part2() {
    val testResult = calcShenanigans2(test)
    println("Part 2 Answer = $testResult")
    check(testResult == 2713310158L)
    val result = calcShenanigans2(input)
    println("Part 2 Answer = $result")
    check(result == 51382025916L)
  }
  println("Day - 11")
  separator()
  part1()
  separator()
  part2()
}

Day 12: kotlin

Hill Climbing Algorithm

Today’s puzzle required graph traversal. I decided to use utilities I created during the 2019 edition of Aoc.

The problem used a grid of letter to describe a map. Each letter describes an elevation starting at a as the lowest and z the highest. The user may only navigate horizontally or vertically and only to one step higher, the same level, or lower by any amount. (You may jump off a cliff!)

Sabqponm
abcryxxl
accszExk
acctuvwj
abdefghi
Model

The Graph requires a list of Edges. Each of the edges must contain two Comparable items that are linked with a distance. In our case the distance is always one and since you can go from low to only one step higher but jump off a cliff the graph will be directed and the distance between cells will always be 1.

The Graph uses the Dijkstra algorithm to find the shortest path between nodes.

Class Diagram 
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
  }
  override fun equals(other: Any?): Boolean {
    if (this === other) return true
    other as Cell
    if (c != other.c) return false
    if (pos != other.pos) return false
    return true
  }
  override fun hashCode(): Int {
    return pos.hashCode() * c.hashCode()
  }
  fun actual(): Char = when (c) {
    'S' -> 'a'
    'E' -> 'z'
    else -> c
  }
  override fun toString(): String {
    return "Cell($c, $pos)"
  }
}
Parsing

The parsing of the grid and creating of Cells and Edges will be in one function.

fun createGrid(input: List<String>): List<Edge<Cell>> {
  val edges = mutableListOf<Edge<Cell>>()
  val cells = input.mapIndexed { y, line ->
    line.mapIndexed { x, c ->
      Cell(c, Coord(x, input.lastIndex - y))
    }
  }.flatMap { row -> row.map { it } }.associateBy { it.pos }
  cells.values.forEach { cell ->
    cell.pos.surrounds().forEach { coord ->
      val neighbour = cells[coord]
      if (neighbour != null) {  (1)
        val height = neighbour.actual() - cell.actual()
        if (height <= 1) { (2)
          edges.add(Edge(cell, neighbour))
        }
      }
    }
  }
  return edges
}
1 If there is no neighbour at the surrounding coordinates it will be skipped. This will happen for the cells on the edges of the grid.
2 We are interested in cells that are 1 step higher or lower.
Processing
fun calculateSteps(
  edges: List<Edge<Cell>>,
  start: Cell,
  end: Cell
): Int? {
  val graph = Graph(edges, true)
  val path = graph.findPath(start, end)
  return if (path.isEmpty()) null else path.size - 1 (1)
}
1 The path includes the start and end node and we will subtract 1 from the path length to obtain the number of steps. Null is returned for an empty path.
Part 1

In part 1 we had to find the shortest path between S (which is the same as a) and E (which is the same elevation as z).

fun calcSolution1(input: List<String>): Int {
  val edges = createGrid(input)
  val end = edges.map { edge -> edge.c2 }
    .find { it.c == 'E' } ?: error("Cannot find E")
  val start = edges.map { edge -> edge.c1 }
    .find { it.c == 'S' } ?: error("Cannot find S")
  return calculateSteps(edges, start, end)
    ?: error("Cannot find solution from $start to $end")
}
Part 2

In part 2 we had to find the shortest paths for all cells labelled a and report the shortest of those.

fun calcSolution2(input: List<String>): Int {
  val edges = createGrid(input)
  val end = edges.map { edge -> edge.c2 }
    .find { it.c == 'E' } ?: error("Cannot find E")
  return edges.map { edge -> edge.c1 }
    .filter { it.actual() == 'a' }
    .mapNotNull { start -> calculateSteps(edges, start, end) }
    .min()
}
Full source
package day12

import main.utils.Edge
import main.utils.Graph
import main.utils.measureAndPrint
import utils.Coord
import utils.readFile
import utils.readLines

fun main() {

  val test = readLines(
    """Sabqponm
abcryxxl
accszExk
acctuvwj
abdefghi"""
  )
  val input = readFile("day12")

  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
    }

    override fun equals(other: Any?): Boolean {
      if (this === other) return true
      other as Cell
      if (c != other.c) return false
      if (pos != other.pos) return false


      return true
    }

    override fun hashCode(): Int {
      return pos.hashCode() * c.hashCode()
    }

    fun actual(): Char = when (c) {
      'S' -> 'a'
      'E' -> 'z'
      else -> c
    }

    override fun toString(): String {
      return "Cell($c, $pos)"
    }

  }

  fun createGrid(input: List<String>): List<Edge<Cell>> {
    val edges = mutableListOf<Edge<Cell>>()
    val cells = input.mapIndexed { y, line ->
      line.mapIndexed { x, c ->
        Cell(c, Coord(x, input.lastIndex - y))
      }
    }.flatMap { row -> row.map { it } }.associateBy { it.pos }
    cells.values.forEach { cell ->
      cell.pos.surrounds().forEach { coord ->
        val neighbour = cells[coord]
        if (neighbour != null) {
          val height = neighbour.actual() - cell.actual()
          if (height <= 1) {
            edges.add(Edge(cell, neighbour))
          }
        }
      }
    }
    return edges
  }

  fun calculateSteps(
    edges: List<Edge<Cell>>,
    start: Cell,
    end: Cell
  ): Int? {
    val graph = Graph(edges, true)
    val path = graph.findPath(start, end)
    return if (path.isEmpty()) null else path.size - 1
  }

  fun calcSolution1(input: List<String>): Int {
    val edges = createGrid(input)
    val end = edges.map { edge -> edge.c2 }
      .find { it.c == 'E' } ?: error("Cannot find E")
    val start = edges.map { edge -> edge.c1 }
      .find { it.c == 'S' } ?: error("Cannot find S")
    return calculateSteps(edges, start, end)
      ?: error("Cannot find solution from $start to $end")
  }

  fun calcSolution2(input: List<String>): Int {
    val edges = createGrid(input)
    val end = edges.map { edge -> edge.c2 }
      .find { it.c == 'E' } ?: error("Cannot find E")
    return edges.map { edge -> edge.c1 }
      .filter { it.actual() == 'a' }
      .mapNotNull { start -> calculateSteps(edges, start, end) }
      .min()
  }

  fun part1() {
    val testResult = measureAndPrint("Part 1 Test Time: ") {
      calcSolution1(test)
    }
    println("Part 1 Answer = $testResult")
    check(testResult == 31)
    val result = measureAndPrint("Part 1 Time: ") {
      calcSolution1(input)
    }
    println("Part 1 Answer = $result")
    check(result == 339)
  }

  fun part2() {
    val testResult = measureAndPrint("Part 2 Test Time: ") {
      calcSolution2(test)
    }
    println("Part 2 Answer = $testResult")
    check(testResult == 29)
    val result = measureAndPrint("Part 2 Time: ") {
      calcSolution2(input)
    }
    println("Part 2 Answer = $result")
    check(result == 332)
  }
  println("Day - 12")
  part1()
  part2()
}

Day 13: kotlin

Distress Signal

Today’s puzzle required parsing a data structure with nested elements. My brain fell apart initially.

I decided to try a List<Object> where the entry can be an Int or List<Object> Once this worked I refactored to use an abstract class to represent any packet item, packet value and packet list.

Implementing the determination of the order provided some problems until I understood that the packet order is determined once two items aren’t equal.

Sample Input
[1,1,3,1,1]
[1,1,5,1,1]

[[1],[2,3,4]]
[[1],4]

[9]
[[8,7,6]]

[[4,4],4,4]
[[4,4],4,4,4]

[7,7,7,7]
[7,7,7]

[]
[3]

[[[]]]
[[]]

[1,[2,[3,[4,[5,6,7]]]],8,9]
[1,[2,[3,[4,[5,6,0]]]],8,9]
Model

The model for Item, Value and Packet below

abstract class Item
data class Value(val value: Int) : Item() {
  fun compareTo(right: Value): Int {
    return value.compareTo(right.value)
  }
  override fun toString(): String {
    return value.toString()
  }
}

data class Packet(val items: List<Item>) : Item(), List<Item> by items {
  constructor(value: Item) : this(listOf(value)) {
  }
}
Parsing
fun parsePacket(input: String): Packet {
  val value = StringBuilder()
  var list: MutableList<Item> = mutableListOf()

  fun checkAdd() {
    if (value.isNotBlank()) {
      list.add(Value(value.toString().toInt()))
    }
    value.clear()
  }
  val lists = Stack<List<Item>>()
  var index = 1 // skip first [
  while (index < input.lastIndex) {
    when (val c = input[index]) {
      ',', ' ' -> checkAdd()
      '[' -> {
        lists.push(list)
        list = mutableListOf()
      }
      ']' -> {
        checkAdd()
        val v = list
        list = lists.pop().toMutableList()
        list.add(Packet(v))
      }
      '-' -> value.append('-')
      '+' -> value.append('+')
      else -> {
        if (c.isDigit()) {
          value.append(c)
        } else {
          error("Unexpected $c")
        }
      }
    }
    index += 1
  }
  checkAdd()
  return Packet(list.toList())
}
Processing

We needed comparison functions for the Packet and one for generic Item. The isOrdered function couldn’t be part of Item because it references Packet and Value.

fun Packet.compareTo(right: Packet): Int {
  var result = 0
  for (index in indices) {
    val item = this[index]
    val rightItem = right.getOrNull(index)
    result = when {
      rightItem == null -> 1
      item is Value && rightItem is Value -> item.compareTo(rightItem)
      item is Packet && rightItem is Value -> item.compareTo(Packet(rightItem))
      item is Packet && rightItem is Packet -> item.compareTo(rightItem)
      item is Value && rightItem is Packet -> Packet(item).compareTo(rightItem)
      else -> 1
    }
    if (result != 0) {
      break
    }
  }
  if (result == 0 && size < right.size) {
    result = -1
  }
  return result
}

fun Item.isOrdered(right: Item?): Int {
  return when {
    right == null -> 1
    this is Value && right is Value -> compareTo(right)
    this is Packet && right is Packet -> this.compareTo(right)
    this is Packet && right is Value -> this.compareTo(Packet(right))
    this is Value && right is Packet -> Packet(this).compareTo(right)
    else -> 1
  }
}

fun isIndexOrdered(index: Int, input: List<String>): Boolean {
  check(input.size == 2)
  val (left, right) = input.map { parsePacket(it) }
  var result = 0
  for (index in left.indices) {
    val item = left[index]
    val rightItem = if (index <= right.lastIndex) right[index]
        else null
    result = item.isOrdered(rightItem)
    if (result != 0) {
      break
    }
  }
  return result <= 0
}
Part 1

In part 1 we had check every 2 pairs to determine if they are in the right order and then report the sum of the indexes of those pairs.

fun calcSolution1(input: List<List<String>>): Int {
  return input.mapIndexedNotNull { index, inputs ->
    if (isIndexOrdered(index, inputs)) index + 1 else null
  }.sum()
}
Part 2

In part 2 we had to treat all the packets as one list and add 2 more with the values:

"[[2]]"
"[[6]]"

Then we had to sort the packets using the ordering rules from part 1. We need to find the indexes of the 2 additional packets and print the product.

fun calcSolution2(input: List<String>): Int {
  val extra1 = "[[2]]"
  val extra2 = "[[6]]"
  val packets = input.filter { it.isNotBlank() }.toMutableList()
  packets.add(extra1)
  packets.add(extra2)
  val sorted = packets.map { it to parsePacket(it) }
    .sortedWith { o1, o2 -> o1.second.compareTo(o2.second) }
    .map { it.first }
  val index1 = sorted.indexOf(extra1) + 1
  val index2 = sorted.indexOf(extra2) + 1
  return index1 * index2
}
Full source
package day13

import utils.groupLines
import utils.readFile
import utils.readLines
import utils.separator
import java.util.*

fun main() {
  val test = readLines(
    """[1,1,3,1,1]
       [1,1,5,1,1]

       [[1],[2,3,4]]
       [[1],4]

       [9]
       [[8,7,6]]

       [[4,4],4,4]
       [[4,4],4,4,4]

       [7,7,7,7]
       [7,7,7]

       []
       [3]

       [[[]]]
       [[]]

       [1,[2,[3,[4,[5,6,7]]]],8,9]
       [1,[2,[3,[4,[5,6,0]]]],8,9]
       """.trimIndent()
  )
  val input = readFile("day13")

  abstract class Item
  data class Value(val value: Int) : Item() {
    fun compareTo(right: Value): Int {
      return value.compareTo(right.value)
    }

    override fun toString(): String {
      return value.toString()
    }
  }

  data class Packet(val items: List<Item>) : Item(), List<Item> by items {
    constructor(value: Item) : this(listOf(value)) {}
  }

  fun parsePacket(input: String): Packet {
    val value = StringBuilder()
    var list: MutableList<Item> = mutableListOf()

    fun checkAdd() {
      if (value.isNotBlank()) {
        list.add(Value(value.toString().toInt()))
      }
      value.clear()
    }

    val lists = Stack<List<Item>>()
    var index = 1 // skip first [
    while (index < input.lastIndex) {
      when (val c = input[index]) {
        ',', ' ' -> checkAdd()
        '[' -> {
          lists.push(list)
          list = mutableListOf()
        }

        ']' -> {
          checkAdd()
          val v = list
          list = lists.pop().toMutableList()
          list.add(Packet(v))
        }

        '-' -> value.append('-')
        '+' -> value.append('+')
        else -> {
          if (c.isDigit()) {
            value.append(c)
          } else {
            error("Unexpected $c")
          }
        }
      }
      index += 1
    }
    checkAdd()
    return Packet(list.toList())
  }


  fun Packet.compareTo(right: Packet): Int {
    var result = 0
    for (index in indices) {
      val item = this[index]
      val rightItem = right.getOrNull(index)
      result = when {
        rightItem == null -> 1
        item is Value && rightItem is Value -> item.compareTo(rightItem)
        item is Packet && rightItem is Value -> item.compareTo(Packet(rightItem))
        item is Packet && rightItem is Packet -> item.compareTo(rightItem)
        item is Value && rightItem is Packet -> Packet(item).compareTo(rightItem)
        else -> 1
      }
      if (result != 0) {
        break
      }
    }
    if (result == 0 && size < right.size) {
      result = -1
    }
    return result
  }

  fun Item.isOrdered(right: Item?): Int {
    return when {
      right == null -> 1
      this is Value && right is Value -> compareTo(right)
      this is Packet && right is Packet -> this.compareTo(right)
      this is Packet && right is Value -> this.compareTo(Packet(right))
      this is Value && right is Packet -> Packet(this).compareTo(right)
      else -> 1
    }
  }

  fun isIndexOrdered(index: Int, input: List<String>): Boolean {
    check(input.size == 2)
    val (left, right) = input.map { parsePacket(it) }
    var result = 0
    for (index in left.indices) {
      val item = left[index]
      val rightItem = if (index <= right.lastIndex)
        right[index] else null
      result = item.isOrdered(rightItem)
      if (result != 0) {
        break
      }
    }
    val ordered = result <= 0
    if (result == 0) {
      println("Pair $index: was the same")
    } else if (result < 0) {
      println("Pair $index: left was lower")
    }
    return ordered
  }

  fun calcSolution1(input: List<List<String>>): Int {
    return input.mapIndexedNotNull { index, inputs ->
      if (isIndexOrdered(index, inputs)) index + 1 else null
    }.sum()
  }

  fun calcSolution2(input: List<String>): Int {
    val extra1 = "[[2]]"
    val extra2 = "[[6]]"
    val packets = input.filter { it.isNotBlank() }.toMutableList()
    packets.add(extra1)
    packets.add(extra2)
    val sorted = packets.map { it to parsePacket(it) }
      .sortedWith { o1, o2 -> o1.second.compareTo(o2.second) }
      .map { it.first }
    val index1 = sorted.indexOf(extra1) + 1
    val index2 = sorted.indexOf(extra2) + 1
    return index1 * index2
  }

  fun part1() {
    val testResult = calcSolution1(groupLines(test))
    println("Part 1 Test Answer = $testResult")
    check(testResult == 13)
    separator()
    val result = calcSolution1(groupLines(input))
    println("Part 1 Answer = $result")
    check(result == 4643)
  }

  fun part2() {
    val testResult = calcSolution2(test)
    println("Part 2 Test Answer = $testResult")
    check(testResult == 140)
    separator()
    val result = calcSolution2(input)
    println("Part 2 Answer = $result")
    check(result == 21614)
  }
  println("Day - 13")
  part1()
  separator()
  part2()
}

Day 14: kotlin

Regolith Reservoir

Today we had to use the input data to represent a cave system and model sand falling into the cave.

In the first part there is a point where the sand falls over the edge and it means all the sand falls down that abyss. So you needed to detect and out of boundary condition.

Sample Input
498,4 -> 498,6 -> 496,6
503,4 -> 502,4 -> 502,9 -> 494,9
Model

The model of the cave is a grid with a map of coordinates and the substance found their, like rock, sand or air.

open class Grid(
val cells: MutableMap<Coord, Substance> = mutableMapOf()
): MutableMap<Coord, Substance> by cells {
  open val maxX: Int get() = cells.keys.maxOf { it.x }
  open val minX: Int get() = cells.keys.minOf { it.x }
  open val maxY: Int get() = cells.keys.maxOf { it.y }
  open val minY: Int = 0
  fun countSand() = cells.values.count { it == Substance.SAND }
  open fun isInGrid(pos: Coord): Boolean = pos.x in minX..maxX
        && pos.y in minY..maxY

  fun getSubStance(pos: Coord) = getOrDefault(pos, Substance.AIR)
  fun isAir(pos: Coord) = getSubStance(pos) == Substance.AIR
  fun isTarget(pos: Coord) = isInGrid(pos) && isAir(pos)
  fun canDrop(pos: Coord): Pair<Coord, Direction> {
    if (!isInGrid(pos.left()) || !isInGrid(pos.right())) {
      return Pair(pos, Direction.ABYSS)
    }
    if (isInGrid(pos.bottom())) {
      if (isTarget(pos.bottom())) {
        return canDrop(pos.bottom())
      } else {
        if (isTarget(pos.bottom().left())) {
          return canDrop(pos.bottom().left())
        } else if (isTarget(pos.bottom().right())) {
          return canDrop(pos.bottom().right())
        }
        if (isTarget(pos)) {
          return Pair(pos, Direction.DOWN)
        }
      }
    }
    return Pair(pos, Direction.STOP)
  }
}
Parsing
fun loadStructure(lines: List<String>): Grid {
  val grid = mutableMapOf<Coord, Substance>()
  lines.map {
    it.scanInts()
      .windowed(2, 2)
      .map { line -> Coord(line[0], line[1]) }
  }.forEach { scan ->
    scan.windowed(2)
      .forEach { pair ->
        val prev = pair[0]
        val curr = pair[1]
        val diff = curr - prev
        if (diff.y == 0) {
          for (x in min(curr.x, prev.x)..max(curr.x, prev.x)) {
            val pos = Coord(x, curr.y)
            if (!grid.containsKey(pos)) {
              grid[pos] = Substance.ROCK
            }
          }
        } else {
          for (y in min(curr.y, prev.y)..max(curr.y, prev.y)) {
            val pos = Coord(curr.x, y)
            if (!grid.containsKey(pos)) {
              grid[pos] = Substance.ROCK
            }
          }
        }
      }
  }
  return Grid(grid)
}
Processing
fun isStop(direction: Direction) = direction == Direction.STOP
    || direction == Direction.NONE
    || direction == Direction.ABYSS
fun dropSand(grid: Grid, entry: Coord): Pair<Coord, Boolean> {
  val drop = grid.canDrop(entry)
  if (drop.second == Direction.ABYSS) {
    return Pair(drop.first, false)
  }
  return Pair(drop.first, !isStop(drop.second))
}

fun simulateSand(grid: Grid, start: Coord, print: Boolean): Int {
  do {
    val result = dropSand(grid, start)
    if (result.second) {
      grid[result.first] = Substance.SAND
    }
  } while (result.second)
  return grid.countSand()
}
Part 1

Part 1 involved simulating the sand while determining the boundary.

fun calcSand(input: List<String>, print: Boolean): Int {
  val grid = loadStructure(input)
  val entry = Coord(500, 0)
  simulateSand(grid, entry, print)
  return grid.countSand()
}
Part 2

Part 2 provided for an infinite floor and I overloaded the grid to provide for a different boundary condition and the floor.

class InfiniteGird(
cells: MutableMap<Coord, Substance>,
val level: Int
) : Grid(cells) {
  override val maxY: Int get() = level
  override fun get(key: Coord): Substance? {
    if (key.y == level) {
      return Substance.ROCK
    }
    return super.get(key)
  }
  override fun getOrDefault(key: Coord, defaultValue: Substance): Substance {
    if (key.y == level) {
      return Substance.ROCK
    }
    return super.getOrDefault(key, defaultValue)
  }
  override fun isInGrid(pos: Coord): Boolean = pos.y <= level
}

fun calcInfiniteSand(input: List<String>, print: Boolean): Int {
  val grid = loadStructure(input)
  val entry = Coord(500, 0)
  val infiniteGrid = InfiniteGird(grid.toMutableMap(), grid.maxY + 2)
  if (print) {
    grid.print(entry)
  }
  infiniteGrid.stretch()
  val sand = simulateSand(infiniteGrid, entry, print)
  if (print) {
    infiniteGrid.print(null)
  }
  return sand
}
Full source
package day14

import main.utils.measureAndPrint
import main.utils.scanInts
import utils.Coord
import utils.readFile
import utils.readLines
import utils.separator
import kotlin.math.max
import kotlin.math.min

enum class Substance(val c: Char) {
  AIR('.'),
  ROCK('#'),
  SAND('o')
}

enum class Direction {
  STOP,
  NONE,
  DOWN,
  LEFT,
  RIGHT,
  ABYSS
}

object Depth {
  private val depth = ThreadLocal.withInitial { 0 }
  var maxDepth = 0
  fun enter() {
    depth.set(depth.get() + 1)
    maxDepth = max(maxDepth, depth.get())
  }

  fun exit() {
    depth.set(depth.get() - 1)
  }
}

fun main() {

  val test = readLines(
    """498,4 -> 498,6 -> 496,6
503,4 -> 502,4 -> 502,9 -> 494,9"""
  )
  val input = readFile("day14")

  open class Grid(val cells: MutableMap<Coord, Substance> = mutableMapOf()) : MutableMap<Coord, Substance> by cells {
    open val maxX: Int get() = cells.keys.maxOf { it.x }
    open val minX: Int get() = cells.keys.minOf { it.x }
    open val maxY: Int get() = cells.keys.maxOf { it.y }
    open val minY: Int = 0
    open fun stretch() {}
    fun countSand() = cells.values.count { it == Substance.SAND }
    open fun isInGrid(pos: Coord): Boolean = pos.x in minX..maxX
        && pos.y in minY..maxY

    fun getSubStance(pos: Coord) = getOrDefault(pos, Substance.AIR)
    fun isAir(pos: Coord) = getSubStance(pos) == Substance.AIR
    fun isTarget(pos: Coord) = isInGrid(pos) && isAir(pos)
    fun canDrop(pos: Coord): Pair<Coord, Direction> {
      Depth.enter()
      try {
        if (!isInGrid(pos.left()) || !isInGrid(pos.right())) {
          return Pair(pos, Direction.ABYSS)
        }
        if (isInGrid(pos.bottom())) {
          if (isTarget(pos.bottom())) {
            return canDrop(pos.bottom())
          } else {
            if (isTarget(pos.bottom().left())) {
              return canDrop(pos.bottom().left())
            } else if (isTarget(pos.bottom().right())) {
              return canDrop(pos.bottom().right())
            }
            if (isTarget(pos)) {
              return Pair(pos, Direction.DOWN)
            }
          }
        }
        return Pair(pos, Direction.STOP)
      } finally {
        Depth.exit()
      }
    }

    fun print(entry: Coord?) {
      val zX = maxX
      val aX = minX
      val zY = maxY
      val aY = minY
      for (y in aY..zY) {
        for (x in aX..zX) {
          val pos = Coord(x, y)
          if (entry != null && pos == entry) {
            print('+')
          } else {
            print(getOrDefault(pos, Substance.AIR).c)
          }
        }
        println()
      }
    }
  }

  class InfiniteGird(cells: MutableMap<Coord, Substance>, val level: Int) : Grid(cells) {
    override val maxY: Int get() = level
    override fun get(key: Coord): Substance? {
      if (key.y == level) {
        return Substance.ROCK
      }
      return super.get(key)
    }

    override fun getOrDefault(key: Coord, defaultValue: Substance): Substance {
      if (key.y == level) {
        return Substance.ROCK
      }
      return super.getOrDefault(key, defaultValue)
    }

    override fun isInGrid(pos: Coord): Boolean = pos.y <= level
    override fun stretch() {
      val zX = (cells.keys.filter { it.y < level }.maxOfOrNull { it.x } ?: maxX) + 1
      val aX = (cells.keys.filter { it.y < level }.minOfOrNull { it.x } ?: minX) - 1
      for (x in aX..zX) {
        val pos = Coord(x, level)
        if (!containsKey(pos)) {
          cells[pos] = Substance.ROCK
        }
      }
    }
  }

  fun loadStructure(lines: List<String>): Grid {
    val grid = mutableMapOf<Coord, Substance>()
    val scans = lines.map {
      it.scanInts()
        .windowed(2, 2)
        .map { line -> Coord(line[0], line[1]) }
    }
    scans.forEach { scan ->
      scan.windowed(2)
        .forEach { pair ->
          check(pair.size == 2)
          val prev = pair[0]
          val curr = pair[1]
          val diff = curr - prev
          check((diff.x == 0 && diff.y != 0) || (diff.x != 0 && diff.y == 0)) { "Expected one 0 in $diff" }
          if (diff.y == 0) {
            for (x in min(curr.x, prev.x)..max(curr.x, prev.x)) {
              val pos = Coord(x, curr.y)
              if (!grid.containsKey(pos)) {
                grid[pos] = Substance.ROCK
              }
            }
          } else {
            for (y in min(curr.y, prev.y)..max(curr.y, prev.y)) {
              val pos = Coord(curr.x, y)
              if (!grid.containsKey(pos)) {
                grid[pos] = Substance.ROCK
              }
            }
          }
        }
    }
    return Grid(grid)
  }

  fun isStop(direction: Direction) = direction == Direction.STOP
      || direction == Direction.NONE
      || direction == Direction.ABYSS

  fun dropSand(grid: Grid, entry: Coord): Pair<Coord, Boolean> {
    val drop = grid.canDrop(entry)
    if (drop.second == Direction.ABYSS) {
      return Pair(drop.first, false)
    }
    return Pair(drop.first, !isStop(drop.second))
  }

  fun simulateSand(grid: Grid, start: Coord, print: Boolean): Int {
    do {
      val result = dropSand(grid, start)
      if (result.second) {
        grid[result.first] = Substance.SAND
      }
    } while (result.second)
    return grid.countSand()
  }

  fun calcSand(input: List<String>, print: Boolean): Int {
    val grid = loadStructure(input)
    val entry = Coord(500, 0)
    if(print) {
      grid.print(entry)
    }
    simulateSand(grid, entry, print)
    if(print) {
      grid.print(entry)
    }
    return grid.countSand()
  }

  fun calcInfiniteSand(input: List<String>, print: Boolean): Int {
    val grid = loadStructure(input)
    val entry = Coord(500, 0)
    val infiniteGrid = InfiniteGird(grid.toMutableMap(), grid.maxY + 2)
    if (print) {
      grid.print(entry)
    }
    infiniteGrid.stretch()
    val sand = simulateSand(infiniteGrid, entry, print)
    if (print) {
      infiniteGrid.print(null)
    }
    return sand
  }

  fun part1() {
    val testResult = calcSand(test, false)
    println("Part 1 Test Answer = $testResult")
    check(testResult == 24) { "Expected 24 not $testResult" }
    val result = measureAndPrint("Test 1 Time: ") {
      calcSand(input, false)
    }
    println("Part 1 Answer = $result")
  }

  fun part2() {
    val testResult = calcInfiniteSand(test, false)
    println("Part 2 Test Answer = $testResult")
    check(testResult == 93) { "Expected 93 not $testResult" }
    val result = measureAndPrint("Test 2 Time: ") {
      calcInfiniteSand(input, false)
    }
    println("Part 2 Answer = $result")
    check(result == 22499) { "Expected 22499 not $result" }
  }
  println("Day - 14")
  part1()
  part2()
}