Advent of Code 2022 - Day 7, in Kotlin - No Space Left On Device • Todd Ginsberg

Part of the design philosophy of UNIX is that Everything Is A File . In today’s solution, we’ll flip that on its head and declare that Nothing Is A File. I had fun with today’s puzzle because the solution I have below is very different from the one I originally stated with. I had tried to somewhat faithfully model “Everything Is A File” at first, and ended up with the opposite after a lot of refactoring.

If you’d rather just view code, the GitHub Repository is here .

Puzzle Input

Originally, I had a somewhat complicated structure to model files and directories, thinking that Part Two would ask different questions. But once I solved the problem and started to refactor it something hit me - We don’t care about the files, just their total size within a directory. We’re never asked questions about the files themselves (sorry, spoiler, I know), just about how much space they take up in a directory. So that’s all we’ll model. Nothing Is A File.

To do this, let’s define a Directory class to use.

// In Day07

class Directory(val name: String) {
    private val subDirs: MutableMap<String, Directory> = mutableMapOf()
    private var sizeOfFiles: Int = 0

    val size: Int
        get() = sizeOfFiles + subDirs.values.sumOf { it.size }

    fun addFile(size: Int) {
        sizeOfFiles += size
    }

    fun traverse(dir: String): Directory =
        subDirs.getOrPut(dir) { Directory(dir) }
}

Let’s go over what is in our Directory class. Each directory has a public name and a private Map<String,Director> to keep track of subDirs. Additionally, each Directory has a sizeOfFile var to keep track of the total size of all the files within that directory. We don’t store their names or anything about them.

Next we have a size property with a getter in order to properly calculate the size of the directory. We do it this way because in theory, the file system is a dynamic place and subdirectories can be added at any time, altering the size of the parent directory. To calculate the size of a directory we add the sizeOfFiles (files in this directory) to the sumOf all the subdirectoories. This is going to lead to a recursive call to all the subDirs.

We’ll add a function to addFile, only caring about its size. Because we never actually do anything with the files, we can leave off their names and any sort of individualized tracking.

Finally, we’ll add a traverse function. This lets us either add or retrieve a subDir. We’ll use this when building the file tree in a moment. When given the name of a dir, we either already have it (in which case we return it) or we need to create it, store it, and return it. Thankfully Kotlin’s getOrPut does the hard work for us.

Now we can parse our input, which is a List<String> today using a when expression and a stack.

// In Day07

private fun parseInput(input: List<String>): Directory {
    val callStack = ArrayDeque<Directory>().apply { add(Directory("/")) }
    input.forEach { item ->
        when {
            item == "$ ls" -> {}// Noop
            item.startsWith("dir") -> {} // Noop
            item == "$ cd /" -> callStack.removeIf { it.name != "/" }
            item == "$ cd .." -> callStack.removeFirst()
            item.startsWith("$ cd") -> {
                val name = item.substringAfterLast(" ")
                callStack.addFirst(callStack.first().traverse(name))
            }
            else -> {
                val size = item.substringBefore(" ").toInt()
                callStack.first().addFile(size)
            }
        }
    }
    return callStack.last()
}

First we stet up a callStack which we’ll seed with the root Directory ("/"). We use a stack here because as we traverse to new directories, we need to know our path for when we cd .. back up and out. We could have added a parent: Directory? to each Directory, but I feel the call stack more accurately captures what we want in this case. Besides, we don’t need to do any kind of parent-traversals outside of the parsing phase.

Next we go through each item of input and decode what to do about it. The ls case is the easiest - ignore it as there is no work to do. The same goes for when a file listing shows us a dir. Since we don’t really care about empty directories, we can leave defining them until we actually traverse into one later on in this process.

When we see $ cd /, we can throw away the callStack except for the root directory, and we do that via removeIf. When we see $ cd .. we know we need to go up one directory so we remove the topmost Directory from the callStack, leaving its parent as the new topmost Directory on the stack.

When we need to change directories by detecting $ cd <name>, we parse out the name using substringAfterLast and calling our traverse function on the Directory on the top of the stack. The traverse function returns the newly created (or found) Directory so to switch into it, we push it on to the top of the stack.

Finally, we handle adding files (the only case left) by figuring out its size via subStringBefore and converting the String to an Int via toInt. We take that and addFile to the current working directory (whichever one is on top of the callStack).

When that’s done, we return the last (root) item in the callStack. Why last? If the parsing process leaves us in a subdirectory, we want the root. Finding the bottom of the stack (via last) will always be the root directory.

We’ll define a rootDirectory in our Day07 class to hold the root of the filesystem for us.

class Day07(input: List<String>) {

    private val rootDirectory: Directory = parseInput(input)

}

⭐ Day 7, Part 1

The puzzle text can be found here.

Due to all the work in the parsing section, we’re almost done. The only thing we really need is a function to find directories that we care about. I called this function find because it reminded me of the kinds of operations we perform with the UNIX find command . We’ll go in and add this to Directory:

// In Day07.Directory

fun find(predicate: (Directory) -> Boolean): List<Directory> =
    subDirs.values.filter(predicate) +
        subDirs.values.flatMap { it.find(predicate) }

When we call find we’re given a predicate which lets us determine which Directory objects we care about (in our case, we only care about their size). I thought about going back and only allowing find by size but I figured this was a good opportunity to talk about High Order Functions. A High Order Function is a function that takes another function as an argument (in our case) or returns a function. In this case, the predicate is a function that determines if we care about a specific Directory.

We use the predicate initially to find all of the immediate subDirs that match the predicate. Then we ask all of those subDirs if they have any matches, and flatMap the results into a single List<Directory>. Why flatMap instead of map? If we were to map, we would end up with a List<List<Directory>>. Since we want a “flattened” view of this (flattening removes the intermediate collections), we call flatMap to get a List<Directory>. The flatMap function does all the work of condensing the inner List<Directory> into a single list.

All that’s left is to call our function:

// Day07

fun solvePart1(): Int =
    rootDirectory.find { it.size <= 100_000 }.sumOf { it.size }

Here you can see we define the predicate as it.size <= 100_000 to indicate we want to find directories whose size is no greater than 100,000. I like to put _ in where I can as it helps me read the numbers better. When we have all the Directory objects that past the predicate we sumOf their size to get the answer for Part One.

Star earned! Onward!

⭐ Day 7, Part 2

The puzzle text can be found here.

We can use the existing find function but with a different predicate to solve Part Two:

// Day07

fun solvePart2(): Int {
    val unusedSpace = 70_000_000 - rootDirectory.size
    val deficit = 30_000_000 - unusedSpace
    return rootDirectory.find { it.size >= deficit }.minBy { it.size }.size
}

Fist we calculate both the unusedSpace and the deficit we need to make up. Then we use our existing find function to find directories that are at least as large as the deficit and then take the size of the smallest one.

Star earned! See you tomorrow!

⭐ Day 7, Part 1

⭐ Day 7, Part 2

Further Reading