Advent Of Code Setup and Day 1

Dec 02, 2022

Advent Of Code Setup and Day 1

It's that time of year again where nerds all around the globe wait for the clock to strike 12AM EST each night in December so that they can earn stars for solving the day's scenarios.

Advent of Code is a bit special for me because it was what I prepped with for my Google interview. Compared to a more rote interview prep site like Leetcode, I enjoy the scenarios the problems present. For some reason, I would freeze if you ask me directly to make some advanced structure but come alive when I have an engaging prompt. I've never completed all stars for a year but last year I got through half of the advent calendar (27 out of 50 possible stars.)

My Setup

Since 2020, my main competition language has been Kotlin and I have a Gradle based setup I've adapted over the years from various sources. Understanding how your infrastructure reads streams of data is extra important. Advent of Code is 70% understanding the problem and 30% understanding how to parse in the data.

The keystone class of my setup is AdventOfCode. It handles initializing the file input, provides overrideable functions for part 1 and 2, and finally adds utility and convenience functions for benchmarking and MD5 hashes. Hashes don't come up frequently but I noticed during my all years prep in 2022 that there were more than a few MD5 related problems.

package adventofcode

import java.io.BufferedInputStream
import java.math.BigInteger
import java.security.MessageDigest
import java.util.*
import kotlin.system.measureTimeMillis

abstract class DayOf2015(day:Int) : AdventOfCode(2015, day)
abstract class DayOf2016(day:Int) : AdventOfCode(2016, day)
abstract class DayOf2017(day:Int) : AdventOfCode(2017, day)
abstract class DayOf2018(day:Int) : AdventOfCode(2018, day)
abstract class DayOf2019(day:Int) : AdventOfCode(2019, day)
abstract class DayOf2020(day:Int) : AdventOfCode(2020, day)
abstract class DayOf2021(day:Int) : AdventOfCode(2021, day)
abstract class DayOf2022(day:Int) : AdventOfCode(2022, day)

open class AdventOfCode(val year: Int, val day:Int) {
    var DEBUG = false
    var scanner:Scanner = Util.initScanner("$year/day${String.format("%02d", day)}.in")
    var testScanner:Scanner = Util.initScanner("$year/day${String.format("%02d", day)}.test")

    open fun part01(): Any? = null
    open fun part02(): Any? = null

    companion object {
        fun mainify(codeDay: AdventOfCode) {
            with(codeDay) {
                println("Year $year, day $day")
                measureTimeMillis {
                    println("Part 1: ${part01()}")
                }.run {
                    println("Part 1 Time: ${this}ms")
                }
                println("-----------")
                measureTimeMillis {
                    println("Part 2: ${part02()}")
                }.run {
                    println("Part 2 Time: ${this}ms")
                }
            }
        }
    }
}

object Util {
    var scanner: Scanner? = null
    fun initScanner(filename:String):Scanner {
        val inputStream = ClassLoader.getSystemClassLoader()
                .getResourceAsStream(filename)
        return Scanner(BufferedInputStream(inputStream))
    }

    fun computeMD5Hash(input:String): String {
        val md = MessageDigest.getInstance("MD5")
        val messageDigest = md.digest("$input".toByteArray())
        val no = BigInteger(1, messageDigest)
        // Convert message digest into hex value
        var hashtext = no.toString(16)
        while (hashtext.length < 32) {
            hashtext = "0$hashtext"
        }
        return hashtext
    }
}

I was running a relatively old version of Kotlin last year so bumping to current uncovered a bunch of warnings and errors from language changes.

Day 1 - Part I

Advent of Code Day 1 is meant to be an easy on-ramp and usually is some sort of simple arithmetic or comparison problem.

The theme for day 1 this year was calories and snacks. Elves are traveling to a magical forest and want to make sure they have enough calories to make the trip. In part 1, you needed to find the elf carrying the most calories (and thus who is more likely to have a surplus) and report how many calories they are carrying.

In the data file, the snacks each elf is carrying is a series of Ints each on its own line followed by a blank line or the end of file to indicate the end of the snacks the given elf is carrying. I went with the most naive solution by keeping a running sum, pushing it to an array on elf change and finding the maximum sum by running maxOrNull.

val elves = mutableListOf()

override fun part01(): Any? {
    var sum = 0
    while(scan.hasNextLine()) {
        val nextLine = scan.nextLine()
        if (nextLine.isEmpty()) {
            // save sum and clear it
            elves.add(sum)
            sum = 0
        } else {
            sum += nextLine.toInt()
        }
    }
    if (sum != 0) elves.add(sum)
    val max = elves.maxOrNull()
    return max
}

I call it naive because it uses O(n) space for storing the totals for each elf and a search time of O(n) for the maxOrNull call. I could have improved the space to O(1) and essentially get the max for free if I modified the code to keep a running count of the maximum so far and did that comparison instead of pusing to the array. However, the naive setup make it easy to tackle Part II.

Day 2 - Part II

For Part II, you need to identify the three elves carrying the most calories and find the sum. With the setup of storing each of the elves total in the array in Part I, all I had to do was sort the array and take the three elves' totals and sum them.

override fun part02(): Any? {
    elves.sortDescending()
    val top3 = elves.take(3)
    return top3.sum()
}

All and all, it was a fun day one problem and emblematic of how optimizing part one for speed and memory can make it necessary to refactor it a lot for Part II.