James Williams
LinkedInMastodonGithub

What I Read - American Sherlock

American Sherlock cover

American Sherlock: Murder, Forensics, and the Birth of American CSI by Kate Winkler Dawson

Edward Oscar Heinrich was a complicated figure. On one hand, he perfected many of the techniques used in forensic science today and was such a great autodidact that he passed his state's pharmacy board exam without a high school degree. On the other hand, his reputation, built by his work on high profile cases, lent credibility to the pseudoscience handwriting analysis cases that formed a bulk of his caseload.

In a time where not only do most people not carry pens nor regularly write, it's easy to think it's absurd that you can determine someone's mood, personality or intent from their handwriting. But we still have contested science in today's forensics, in the branch of arson investigation commonly called fire science. Lots of "conventional knowledge" that's been long disproven is still presented as fact with little recourse for the accused.

Another contemporary view I had upon reading the book is how we still confer reverence on folks that have great success on an unrelated area. Being a SuperBowl winning quarterback doesn't make you an automatic expert on vaccine science. We need to be able to honor their accomplishments in one area without fast-tracking them to credibility in another where they haven't earned it.

Nonetheless the book was an interesting time capsule into what was cutting edge 100 years ago.

Permalink

What I Read - Forget the Alamo

Forget The Alamo cover

Forget the Alamo: The Rise and Fall of an American Myth by Bryan Burrough, Chris Tomlinson, and Jason Stanford

It's very weird to learn that everything you were taught about the inception of Texas, its larger than life reputation, and "Don't Mess With Texas" was built upon a well-constructed lie. They say "history is written by the victors." More important is what they choose not to write. For example, the mythos of Texas omits that a lot of the conflict boils down to Mexico's displeasure with slavery in the Tejas. Also not noted is illegal immigration into Mexico with slaves (ironic in today's climate) or US intervention in the conflict.

The well sourced book also chronicled Hollywood's role in remaking the Alamo church, a site that was unimportant in the battle, into hallowed ground. The actual site of most fighting, the longhouse, was willfully destroyed in the efforts to preserve the complex because it didn't fit the funder's plans for "America's ruins."

There are many more little tidbits like this in the book. I highly recommend.

Permalink

Trying the Google Project Management Certificate

Project board with stickie notes affixed - Photo by Daria Nepriakhina @epicantus on Unsplash

Most folks know about the marquee Google perks like the food and buses. One of my favorites that doesn't get mentioned much are educational services. Education is something you can take with you. It also goes well with my job in Developer Relations. To do this job well, I think you should be constantly learning things in and outside your field of study. The Project Management Professional Certificate is kind of work adjacent so that's an extra plus.

A way into tech without a degree

Google Career Certificates are training programs meant to give people a means to break into tech possibly without a degree. Beyond Project Management, there are certificates in Digital Marketing/E-commerce, IT Support, Data Analytics, and UX Design with other areas in development.

In addition to the career certificates themselves, Google set up an employer consortium that will factor completion of the certificates into their hiring decisions for new candidates or to use them to "reskill" their current employers.

What are the courses? How are they?

Courses:

  • Foundations of Project Management
  • Project Initiation: Starting a Successful Project
  • Project Planning: Putting It All Together
  • Project Execution: Running the Project
  • Agile Project Management
  • Capstone: Applying Project Management in the Real World

The first course starts with an overview of what a project manager does. Each of the next four courses have you working on small tasks somewhat in isolation based on a brief/stems for a sample project. The capstone course presents a totally new project for which you must work through creating all the project documents.

How much does it cost?

To complete the program, you need a Coursera subscription. Either $39 USD per month for a single professional certification or Coursera Plus that gives you access to all the programs. At the time of writing, it was $59 per month or $399 USD for a yearly subscription. Full disclosure, I paid no fee for the course as it is covered in my educational benefits. The Grow with Google team didn't see or approve this write-up before hand.

How long did it take to complete?

Grow with Google quotes about 3 to 6 months of time if one works on the credential for 10 hours per week. We tended to say the same thing at Udacity and it can be variable. We had seen folks take a year or zoom through things in under 3 months to minimize costs. I had the benefit of not paying for the content so I didn't have to rush. I took big breaks with several clear crunch times where I got a lot done. Being able to watch videos on double speed also helps. The final course revisits a lot of the concepts from the other courses so taking your time there will help you in the end. Big caveat and disclaimer that I have a lot of experience making and beta testing content like this. It was about 2 months of actual work time spread over about 15 months.

What kind of assessments are there? How many ? What are they like?

There are three types of assessments: practice quizzes, graded quizzes, and peer graded assignments. Most of the practice quizzes can skipped and don't factor into your grade until you reach the last course. It uses them as prep steps for the peer graded assignments.

There were 25 graded quizzes and 13 peer graded assignments throught the six courses. The tasks range from making project charters and stating RACI (Responsible, Accountable, Consulted, Informed) tables to planning tasks for a sprint to writing persuasive emails to stake holders to get consensus.

Was it worth it?

Yes. I have no goal to become a project manager but have found myself often in a position where I didn't have one and needed to take on some of those responsibilities to move a project forward or I had a project idea and the lack of a project manager was used as a cudgel against me. In those cases, being about to think through the project to entice a project manager to take on the project was helpful.

Beyond those wanting to break into project management, I think small dev teams could benefit from the content perhaps splitting the responsibilities among them. If this existed back when I was in college or if I knew what project management was then, I might have referred it to the folks who hit the wall in Computer Science when the curriculum ramps up in difficulty and they dropped it thinking Computer Science isn't for them. Being a developer isn't the only way to work in tech.

Learn more or enroll in the program here.

Permalink

The Southwest Debacle

I've worked for an airline before...when multiple hurricanes hit Florida in a short span. I was told I was ruining their weddings/vacations/etc. People straight up lied to me when I had all the evidence to prove it and then cussed me out when I had to call out their lies. I think I've earned a small soapbox to rant about the recent events. Here are the things I think contributed to the catastrophic failure at Southwest:

Problem 1: Point to point flying.

A point to point system relies on the system being generally healthy because you have aircraft coming from wherever going to wherever. So instead of weather(WX) at origin and destination, as a passenger I have to think about WX at every other city that flight has visited before me. This makes for a bad customer experience because "why is my flight delayed or CXLD but not this flight that leaves later?" is a thing. Hub/Spoke do suffer greatly when there is bad WX at a major hub, but it's usually contained somewhat and there is a prioritization of which flights will get takeoff slots (usually international, then hub to hub).

Problem 2: Seating.

Being a decently tall dude, seat anxiety made me stay away from Southwest. The boarding group + number helps a bit but the problem for me is the fact that on Southwest, your boarding pass is a not really a guaranteed seat. They don't by policy overbook (as in intentionally sell more seats than are available) but in the case of a cancellation, reduced capacity/positive space employees, you can end up in an oversold situation (incidentally more passengers than seats). There's a nuance of difference but it's hard for the passenger to understand not unlike the difference between non-stop and direct. The point isn't to hate on open seating but it feels less like I have a guaranteed seat and more like I have a claim ticket to redeem for a seat...maybe that's just me.

Problem 3: Lack of capacity.

Back in the day, I could easily travel non-revenue to Europe with only a small worry of having to kill 4-5 hours at ATL or JFK. Capacity was tight pre-COVID and it still is. Lack of extra capacity means it's harder for the system to absorb passengers from CXLD flights.

Problem 4: Lone wolf mentality.

One little known fact is that while it is not encouraged and nigh impossible to do easily, most airlines can book segments on other airlines. This is beyond what airlines they may codeshare with. These interline agreements allow an airline to handle check-in and carriage of the passenger / baggage. Handoff of baggage usually is seamless. For boarding passes, each airline might reprint the BP in their format but that's a minor inconvenience. This is important in irregular operations(IROP) because airlines with an interline agreement have some capacity to book on other carriers that aren't affected by the same issue.

Southwest by policy doesn't interline with anyone and its capacity isn't even viewable/bookable on the major booking systems. I understand the initial allure when the internet was slow to get folks to come to your site and book. People are more savvy, price check easily and...multiple tabs are a thing.

Problem 5: Lack of tools/That cop

I could be wrong but I've never noticed banks of phones in airports for Southwest to handle changes. At DL, those were called DL Direct and it rang through to me at a higher priority than elite members. I even had more power on those calls because I was deemed to be "at the airport." It was airport, reissues, Skymiles/Elite, General Sales IIRC.

These desks are usually PAST SECURITY. The advice to exit the secure area and talk to the check-in agents endangers the other flights leaving that day because you will have folks with a departing flight mixed in with those who are canceled and it's the worst customer service to have found someone a seat but have to let it go because there is no way they'll get through security in ATL before boarding or tell someone that you gave their seat away because they were in line and not checked in because someone told 200 people to get in line ahead of them. When I "protected" a passenger on a flight because they were likely to miss their connection, the boarding pass from the previous flight still scan. If the gate agent had extra time, they would print new boarding cards for the folks, otherwise during boarding, the existing boarding card would spit out a seat assignment ticket. IE STILL VALID IANAL so don't get arrested but staying inside the secure area is in your best interest most of the time.

How does Southwest recover?

It seems like they have been living in the mindset of "if that flight is CXLD, there will be another flight in an hour or two." Climate change affects everything. If that 100 year event becomes a 5, 10, or 20 year event and it's not in your modeling, that's a problem.

I hope the company invests in the tech side. They need to start thinking about themselves as a tech company. Given the other things I didn't touch on like the FAA fines if flight crew goes over their legal limit, perhaps this multi-day shutdown of the full system was the only way to reset things. I wouldn't want to explain this to the customer when all the other airlines are fine. If you are a Southwest passenger, be nice to the agent on the phone, they are trying their hardest to help you. Your salty attitude x 80 or 100 calls is what they've been dealing with on a daily basis. Don't get yourself put in the penalty box or accidentally dropped.

Permalink

Advent Of Code 2022 - Day 6 - Tuning Trouble

For day 6, you need to help the elves with their communication system. Their devices receive a series of characters, one at a time. The start of a usable data packet is indicated by some x characters that are unique.

If you are doing this problem in Kotlin, 95% of the work can be done for you using a pre-defined function in the collections library. I, however, didn't think of it until AFTER completing both stars.

Part I and II

I used much of the same logic for both parts as the only difference was the required number of unique characters. I iterated over the string from zero to string length minus the required size. On each iteration, I created a substring for the target size and tested it for uniqueness.

package adventofcode.y2022
import adventofcode.AdventOfCode
import adventofcode.DayOf2022
import java.util.*

class Day06 : DayOf2022(6) {
    var scan: Scanner

    init {
        //DEBUG = true
        scan = if(DEBUG)
            testScanner
        else scanner
    }

    lateinit var part2Line:String
    override fun part01(): Any? {
        val line = scan.nextLine()
        part2Line = line
        for (i in 0..line.length-4) {
            val x = line.substring(i..i+3).toCharArray().distinct()
            if (x.size == 4) {
                return i+4
            }
        }
        return super.part01()
    }

    override fun part02(): Any? {
        val line = part2Line
        for (i in 0..line.length-14) {
            val x = line.substring(i..i+13).toCharArray().distinct()
            if (x.size == 14) {
                return i+14
            }
        }

        return super.part02()
    }
}

fun main() = AdventOfCode.mainify(Day06())
 

If you are thinking that sounds a lot like windowed with the requirement for no partial windows. You are totally correct.

Permalink

Advent Of Code 2022 - Day 5 - Supply Stacks

When I start a new problem, a lot of times I will look at the sample test data first to try and understand what I might need to do with the data. This test data for Day 5 had me perplexed for a bit.

    [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
 

The premise is that you are in the supply docks and have a crane moving around containers. You must move them in a prescribed order and report their final state.

Part I

After a while, I realized it was the combination of a stack/queue problem and a regular expression problem. I HATE doing regexes. Further, in the first section of the input, the last line had the ids of the stacks and I could use that index position to find all the crates in that stack. The lines were varying lengths so I needed to make sure to not throw an index error but that was easy to manage.

val stacks = mutableListOf()
while(scan.hasNextLine()) {
    val line = scan.nextLine()
    if (line.isEmpty()) {
        break
    } else {
        stacks.add(line)
    }
}

val lastLine = stacks[stacks.size - 1]
val stackIds = stacks[stacks.size - 1].split(" ").filter{ it.isNotEmpty()}

val indices = stackIds.map { lastLine.indexOf(""+it) }

queues = Array>(stackIds.size) {i -> ArrayDeque()}
for (i in 0..stacks.size-2) {
    stackIds.forEachIndexed { j, value ->
            val index = indices[j]
            if (stacks[i].length > index) {
                val c = stacks[i][index]
                println("value  c:" + c)
            }
            if (stacks[i].length > index && stacks[i][index] != null && stacks[i][index] != ' ') {
                queues[value.toInt()-1].add(stacks[i][index])
            }
        }
}
 

The sneaky bit was the regex. My first version worked perfectly on the sample data but wasn't even close with the real data set. It turns out I made a subtle error that only became apparent when I switched datasets. My original regex only worked on single digits.

Regex("""move(\d)+ from (\d)+ to (\d)+""")

should have been

Regex("""move (\d+) from (\d+) to (\d+)""")

The parentheses define the digits as a matchable group, so putting the plus (indicating one or more items) causes the part of the input to be matched and affecting the results. With that sorted I could move the proper quantity of crates from the right source to the right destination.

fun moveObjects(queues:Array>, quantity:Int, source:Int, destination:Int) {
    repeat(quantity) {
        // remove from old
        val valueToPop = queues[source-1].pollFirst()
        // push to new
        if (valueToPop != null)
            queues[destination-1].addFirst(valueToPop)
    }
}
 

Part II

In Part II, you were still moving crates but instead of one by one, you needed to move them as a set and preserve initial ordering. To do this, I opted for a double ended queue as temporary storage and added items into it using addLast. When adding to the destination, I added each item to the front of the destination with addFirst but with the source items being repeated calls to removeLast on the temporary storage location. you could have done it with another data structure like a simple array but I'll take readability over terseness and having to track multiple indices.

fun moveCrates(q:Array>, quantity: Int, source: Int, destination: Int) {
    if (quantity == 1) {
        moveObjects(q, 1, source, destination)
    } else {
        val tempQueue = ArrayDeque()
        repeat(quantity) {
            val valueToPop = q[source-1].pollFirst()
            if (valueToPop != null)
            tempQueue.addLast(valueToPop)
        }
        while(tempQueue.isNotEmpty()) {
            q[destination-1].addFirst(tempQueue.removeLast())
        }
    }
}

override fun part02(): Any? {
    queuesClone.forEach{println(it)}
    instructions.forEach {
        moveCrates(queuesClone, it.first, it.second, it.third)
    }

    var topCrates = ""
    queuesClone.forEach {
        val peek = it.peekFirst()
        if (peek != null) topCrates += peek
        else topCrates += " "
    }
    return topCrates
}
 
Permalink

Advent Of Code 2022 - Day 3 - Ruck Reorganization

For day 3, you had to identify objects that were in one or more compartments of a single rucksack or occur across multiple rucksack. A rucksack is a rugged backpack. Its typical usage is in military settings or hiking/backpacking and are usually packed to the brim with items.

Day 3's problem at the core was a string search problem. For Part I, each line of the input was treated as a rucksack with 2 equally sized compartments that you had identify yourself.

vJrwpWtwJgWrhcsFMMfFFhFp
jqHRNqRjqzjGDLGLrsFMfFZSrLrFZsSL
PmmdzqPrVvPwwTWBwg
wMqvLMZHhHMvwLHjbvcjnnSBnvTQFn
ttgJtRGJQctTZtZT
CrZsJsPPZsGzwwsLwLmpwMDw
 

In each compartment, you needed to find the character that appears in both and based on that characters id, determine a priority and sum up the priorities. The priorities are:

  • Lowercase item types a through z have priority values 1 to 26, and,
  • Uppercase item types A through Z have priority values 27 to 52.

Part I

I began by substringing the lines into two halves, incurring some off by one errors along the way and then did what amounted to a full random search (n^2 worst case) because the two halves weren't guaranteed to be in any sort of order beforehand.

After getting the matches, I ran through them and subtracted the appropriate constant per the ASCII chart to convert the character to the 1 - 52 range.

fun part1(): Any {
    val common = mutableListOf()

    while (scan.hasNextLine()) {
        val localMatches = mutableSetOf()
        val line = scan.nextLine()
        val len = line.length
        val part1 = line.substring(0, len / 2).toCharArray()
        val part2 = line.substring(len / 2).toCharArray()
        part1.forEach { if (part2.contains(it)) localMatches.add(it) }
        common.addAll(localMatches)
    }
    return common.sumOf {
        if (it.isLowerCase())
            it.toInt() - 96
        else (it.toInt() - 38)
    }
}
 

Part II

For Part II, the goal was now to identify the common item between groups of three rucksacks. That new requirement made the solution for Part I unsuitable for Part II. It already had a slow runtime but the n was small so it was manageable. n^3 time is hard to justify in any circumstance.

To speed things up, I altered the order of my transformations. First, the code to convert the item types into priority ids was spun out into its own function.

fun charToScaledInt(c: Char): Int {
    return if (c.isLowerCase())
        c.toInt() - 96
    else (c.toInt() - 38)
}
 

The next problem to solve was the variable ruck size. This would wreak havoc on the search code as you could easily throw ArrayIndexOutOfBoundsExceptions. The solution was to normalize the ruck strings into IntArrays. The code in processString is essentially the first part of Counting Sort

fun processString(input: String): IntArray {
    val array = IntArray(53)
    input.forEach {
        val index = charToScaledInt(it)
        array[index] += 1
    }
    return array
}
 

The sorted rucks can be searched in linear time with one pass versus n^3. Here's the full part II code:

override fun part02(): Any? {
    var sum = 0
    while (lines.isNotEmpty()) {
        val elf1 = processString(lines.removeFirst())
        val elf2 = processString(lines.removeFirst())
        val elf3 = processString(lines.removeFirst())

        for (i in 0..53) {
            if (elf1[i] > 0 && elf2[i] > 0 && elf3[i] > 0) {
                sum += i
                break
            }
        }
    }
    return sum
}
 
Permalink

Advent Of Code 2022 - Day 4 - Camp Cleanup

Titled Camp Cleanup, Day 4's problem is a genre of problem that shows up a lot for Advent of Code: the numeric range problem.

I had the misfortune of having to do this problem twice. I coded it, got my stars, and then went on a trip without saving the code to version control. So apologies if this entry seems too polished.

Numeric range problems can ask you to determine if ranges overlap, don't overlap, if one is fully contained in the other or what values to add or remove to optimize them somehow.

In Kotlin, you can lean on the IntRange type to assist with these problems.

Part I

For Part I, you need to determine if one range is fully contained in the other. It's a matter of calling contains on the range and checking if both the .first and .endInclusive are contained.

override fun part01(): Any? {
    var count = 0
    while (scan.hasNextLine()) {
        val parts = scan.nextLine().split(",")
        val r1 = parts[0].split("-").map { it.toInt() }
        val r2 = parts[1].split("-").map { it.toInt() }
        val range1 = IntRange(r1[0], r1[1])
        val range2 = IntRange(r2[0], r2[1])

        if (range1.contains(range2.first) &&
            range1.contains(range2.endInclusive) ||
            range2.contains(range1.first) &&
            range2.contains(range1.endInclusive)) {
                count++
        }
    }
    return count
}
 

Part II

For this star, you needed to determine overlap but not full containment. All contained ranges are by default overlapping so by quick mental map you could ballpark that the correct answer would be higher than that of part one.

The logic was largely similar with a loosening of conditions so either the first or end needed to be contained to be deemed overlapping.

override fun part02(): Any? {
    var count = 0
    // part 1 saved computed IntRanges into an array of Pair
    part2Cache.forEach {
        val range1 = it.first
        val range2 = it.second
        if (range1.contains(range2.first) || range1.contains(range2.endInclusive) ||
            range2.contains(range1.first) || range2.contains(range1.endInclusive)) {
                count++
        }
    }
    return count
}
 
Permalink

Advent Of Code 2022 - Day 2 - Rock, Paper, Scissors

Day 2 was the first real problem this month. The scenario was to simulate scoring based on the win conditions of a Rock, Paper, Scissors game.

Your score for each round was based on the sum of the outcome (win = 6pts, lose = 0pts, or draw = 3pts) and the hand shape you chose (Rock = 1pt, Paper = 2pts, Scissors = 3pts).

Part I

My first attempt at Part I seized on the fact that the indicators for Rock, Paper, Scissors were assigned to A, B, and C for the opponent and X, Y, and Z for the player.

I "scaled" the X,Y,Z to A, B, C by subtracting the difference between X and Z. I then did a simple comparison and accounted for the off by one error I'd introduced. It worked fine for the sample cases...

A Y
B X
C Z
 

What I noticed when trying the real data was that the test cases never test Rock vs Scissors. That's the one case where a simple greater than comparison fails. Anticipating that Part II would take some sort of turn and need a more robust solution, I went verbose and made an enum class for the hand shapes storing their possible ids and point values.

enum class Shape(val idOne: Char, val idTwo: Char, val value:Int) {
    ROCK('A', 'X', 1),
    PAPER('B', 'Y', 2),
    SCISSORS('C', 'Z', 3)
}

private fun findShape(i: Char): Shape {
    return Shape.values().first { it.idOne == i || it.idTwo == i }
}
 

Once the shapes are determined, they are passed to determineWinner where I listed out the five possible end states as a bunch of if-else statements.

private fun determineWinner(opponent: Shape, player:Shape): Int {
    val draw = 3
    val won = 6
    return if (opponent == player) {
        draw + player.value
    } else if (opponent == Shape.ROCK && player == Shape.PAPER) {
        won + player.value
    } else if (opponent == Shape.PAPER && player == Shape.SCISSORS) {
        won + player.value
    } else if (opponent == Shape.SCISSORS && player == Shape.ROCK) {
        won + player.value
    } else player.value
}


val lines = mutableListOf()  // for part two

override fun part01(): Any? {
    var sum = 0
    while(scan.hasNextLine()) {
        val line = scan.nextLine().toCharArray()
        lines.add(line)
        val opponent = findShape(line[0])
        val player = findShape(line[2])
        sum += determineWinner(opponent, player)
    }
    return sum
}
 

Part II

The Part II twist was that instead of the second character indicated what you played, it now indicated the outcome and you had to determine what to play to reach that outcome. The scoring algorithm from the first round stayed the same.

I created an enum class called Outcome to allow me to lookup the states. Totally not required but it made the code a bit more readable and pluggable into the Part I code. determinePlay took the opponent's play and the desired outcome to provide the right move. Like with the determineWinner function, it was a small list and easily enumeratable.

enum class Outcome(val id:Char) {LOSE('X'),DRAW('Y'), WIN('Z') }
private fun findOutcome(i: Char):Outcome { return Outcome.values().first { it.id == i }}

private fun determinePlay(opponent: Shape, outcome: Outcome): Shape {
    when (outcome) {
        Outcome.DRAW -> return opponent
        Outcome.WIN -> {
            return when(opponent) {
                Shape.ROCK -> Shape.PAPER
                Shape.PAPER -> Shape.SCISSORS
                Shape.SCISSORS -> Shape.ROCK
            }
        }
        Outcome.LOSE -> {
            return when(opponent) {
                Shape.ROCK -> Shape.SCISSORS
                Shape.PAPER -> Shape.ROCK
                Shape.SCISSORS -> Shape.PAPER
            }
        }
    }
}

override fun part02(): Any? {
    var sum = 0
    lines.forEach {
        val opponent = findShape(it[0])
        val outcome = findOutcome(it[2])
        val player = determinePlay(opponent, outcome)
        sum += determineWinner(opponent, player)
    }
    return sum
}
 

From there, I passed the opponent move and the derived player move into determineWinner from Part I to get the score.

On to Day 3...

Permalink

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.

1000
2000
3000

4000

5000
6000

7000
8000
9000

10000
 

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.

Permalink