Welcome back to day number 7 of the 2022 Advent of Code, we’ll have worked our way through a whole week of challenges after finishing today’s puzzle!
Continuing with our theme of trying to write not over engineered, but also not terribly unclear “clever” code, we’ll be parsing the input into an actual tree structure. This’ll also give us a taste of using classes and protocols and give us some practice with working with types!
Parsing
Parsing today’s input isn’t as funky as day 5 was, but it’s still more involved than previous days where we could get away with a few splits and a map.
Per the usual, let’s build out the base containers for our tree. We’ve got both files and directories to represent and we know that directories have some children and a parent, while files are just a size and pathname. Technically, to solve the problem we only need to store the sizes and could represent this as a single type, but for the sake of making debugging easier, I’ve chosen to split directories and files apart and to store extra information such as the path.
class Directory {
let path: String
var size: Int { 0 } // TODO: Implement this
let parent: Directory?
var children: [Any] = [] // TODO: We'll need to figure out what this is
init(_ path: String, parent: Directory? = nil) {
self.path = path
self.parent = parent
}
}
class File: Node {
let path: String
let size: Int
init(_ path: String, _ size: Int) {
self.path = path
self.size = size
}
}
We have two problems, as our little // TODO comment’s points out. The first is that we need a way to calculate the size of a directory, and the second is that children can be both directories and files so how do we make an array that can hold both? We need to know how to store the children before we can worry about finding the size of a directory so let’s focus on that for now.
In order to store both files and directories in children we’ll need to have a common base that they both implement. We have two options here, we could either use a type union, or we could use a protocol. In swift, the equivalent of a type union is created using an enum with an associated value, like so:
enum Node {
case directory(Directory)
case file(File)
}
var children: [Node] = [
.directory(Directory("a")),
.file(File("b.txt", 14848514))
]
This’ll work dandy, but it duplicates information that is already encoded in the type of object: A directory is a directory and a file is a file.
We can do better with protocols and even gain some functionality while we’re at it. A protocol in swift is typically called an “interface” in other languages. It’s basically a way to tell swift “these two, separate types implement this subset of functionality, so I can use them interchangeably” and it looks a bit like this:
protocol Node {
var path: String { get }
var size: Int { get }
}
// Update these definitions to state that Directory and File implement our new protocol:
class Directory: Node {
var children: [Node] = []
// Same as before
}
class File: Node {
// Same as before
}
// Now we can do this:
var children: [Node] = [
Directory("a"),
File("b.txt", 14848514)
]
That’s not too different from the enum setup above, but now we don’t have to worry about duplicating information that is intrinsic to our system already. Using the protocol also lets us store both directories and files in our children array but it has an added benefit: we can specify functions and properties that all Nodes should implement and can call them without having to worry about any type casting. For example, to get an Array of the sizes of each child we can just map over them and call the protocols .size property:
children.map { $1.size }
Now that we’ve got our base containers set up, let’s get into parsing our input into our tree structure. Scanning through our input, we find 4 different formats:
$ cd /moves us up and down the tree$ lsmarks the start of several lines denoting the current node’s contentsdir atells us that there is a directoryawe need to add to our children array14848514 b.txttells us that there is a fileb.txtwe need to add to our children array
We can actually ignore $ ls lines completely since they’re just a marker in our input saying, “the next lines are a listing for the directory we just moved into.”
We can also ignore the first $ cd / since it’s telling us that we’re starting at the top, the root of the tree. We’ll take into account when we set up our parser which will remove the need to handle creating a root when we come across $ cd /, further simplifying the cases we need to deal with.
Swift’s iterator helpers makes it easy to ignore both the $ ls lines, and our first line ($ cd /) with dropFirst() and filter(where:). After that we just have to parse each line to build up our tree:
var currentParent = Directory("/")
func parseString(_ input: String) -> Directory {
let root = currentParent
var lines = input
.split(separator: "\n")
.dropFirst()
.filter { $0 != "$ ls" }
.forEach(parseLine)
return root
}
func parseLine(_ line: Substring) {}
We’ll use currentParent to handle inserting nodes into the correct child array and we’ll use $ cd <path> to change it. Since we want to operate on the root of the tree once we get to solving the challenge, I’ve kept a reference to the root node for convenience which lets us freely change where currentParent is pointing at.
With this we’ve narrowed our cases down to three and we can further investigate them for a pattern that’ll make it easy to determine which case each line falls into. If we split each line on spaces, we’ll get the following:
$ cd acan be split into["$", "cd", "a"]dir acan be split into["dir", "a"]14848514 b.txtcan be split into["14848514", "b.txt"]
In other words our pattern is:
- If the line starts with
$it’s a cd command and the third index is our directory to change into - If the line starts with
dirit’s a new directory command and the second index is the directory name - Otherwise it’s a new file command where the first index is the size and the second is file name
There’s one wrinkle we’ll have to address for cd commands specifically: $ cd ... This means we’ll need to navigate to the current directory’s parent, not a child directory.
func parseLine(_ line: Substring) {
let parts = String(line).split(separator: " ")
switch parts[0] {
case "$":
let dir = String(parts[2])
if dir == ".." {
currentParent = currentParent.parent!
return
}
guard let newParent = currentParent.children.first(where: { $0.path == dir }) as? Directory else {
fatalError("Can't find a directory for path \(dir) in \(currentParent)")
}
currentParent = newParent
case "dir":
let dir = String(parts[1])
let newDirectory = Directory(dir, parent: currentParent)
currentParent.children.append(newDirectory)
default:
let path = String(parts[1])
let size = Int(parts[0]) ?? 0
let newFile = File(path, size)
currentParent.children.append(newFile)
}
}
Here we get our first taste of guard statements this season as well:
guard let newParent = currentParent.children.first(where: { $0.path == dir }) as? Directory else {
fatalError("Can't find a directory for path \(dir) in \(currentParent.path)")
}
This is essentially a smart if statement that lets swift set the guarantee for any code after the guard that newParent will exist and be a Directory. Typically guard statements are a better way to go than the forced optional-unwrapping and forced casting that we’ve done on previous days but since we suspect that no file will be named the same as a directory and thus causing some issues, we could in theory shorten this to:
let newParent = currentParent.children.first(where: { $0.path == dir })! as! Directory
But those two ! forces make the code a bit uglier and are a smell to me.
There are a few other optional related gotchas: we’re assuming that we’ll never try to navigate to the roots parent, which would be nil and we could in theory get a file of size 0 if the int parsing fails. Both of those are fair assumptions we can make, however, since we know the format “shouldn’t” have either of those issues.
Finally we’ve got our input parsed into a tree structure and we can focus on solving this!
Part One
Find all of the directories with a total size of at most 100000. What is the sum of the total sizes of those directories?
In order to solve this, for each directory in our tree we need to get an array consisting of that directory’s size as well as the size of all the child directories. We’ll want to combine all of these into a single array which we can filter down to all sizes equal to or less than 100000 before finally summing them together. In order to do this, we’ll need to finish our calculation for the size of a directory first. Remember how we’ve got a computed property setup in our Directory?
var size: Int { 0 } // TODO: Implement this
This is where having size on the protocol, and having all our children using this protocol comes in handy. To get the size of a directory it’s simply a summation of all the sizes of its children:
var size: Int { children.reduce(0) { $0 + $1.size } }
Next up we need to build an array of directory sizes. We’ll use some swift pattern matching, specifically a for in where statement to iterate through our children array and only pull out the directories. I attached this function as an instance function for a Directory:
class Directory: Node {
// Existing code ...
func subSizes() -> [Int] {
var sizes: [Int] = [size]
for child in children where child is Directory {
// we can safely force cast this since we filtered
// it down to directories in the where clause above
let child = child as! Directory
sizes.append(contentsOf: child.subSizes())
}
return sizes
}
}
For every directory we’ll take its size and append the sizes, we get back from all of the children directories. For example, if we’ve got a tree that looks like this, where the sizes are in parentheses:
- / (13)
- a/ (2)
- b.txt (2)
- e/ (11)
- f/ (11)
- dodge.coin (6)
- hat.trick (5)
- We’ll start at
/andsizeswill be[13]. - Next we’ll loop over the child directories, so we’ll visit
afirst which will give us back[2]sinceaonly has a single file with size2in it - We’ll continue at the end of our for-loop and we’ll append the contents of
a’s[2]to our existing[13]in the root for[13, 2] - Then we’ll visit
ewhich takes us down intof - in
fwe’ll get[11] - returning back to
e, we’ll have the equivelent of[11].append(contentsOf: [11]) - finally back to the root where we have
[13, 2].append(contentsOf: [11, 11])
For a little more of a visual aid, this shows the nesting we’ll see while traversing from the root into f/:
┌────────────────────────────────────────────────┐
│ ┌─────────────────────────────┐ │
│ │ ┌────────────┐ │ │
│ / - [ 13, 2, │ e/ - [ 11, │ f/ - [11] │ ] │ ] │
│ │ └────────────┘ │ │
│ └─────────────────────────────┘ │
└────────────────────────────────────────────────┘
Since we’re using append(contentsOf:), which is implicitly flattening our arrays as we go, our final array that root.subSizes() returns is:
[13, 2, 11, 11]
From here we can do a filter where the element is less than or equal to 100000 and finally sum it up for our part on solution:
root.subSizes()
.filter { $0 <= 100000 }
.reduce(0, +)
Part Two
Find the smallest directory that, if deleted, would free up enough space on the file system to run the update. What is the total size of that directory?
We’ve got to first find out the minimum size of directory that we need to delete. We’ll start with finding how much space we have free which is the total space we have on the disk, 70000000 minus the size of our root directory. Then we find the amount of extra space required for the update, ie: the minimum amount of space we need to delete by taking the update size and subtracting the existing free space that we can use.
let totalSpace = 70000000
let usedSpace = root.size
let freeSpace = totalSpace - usedSpace
let requiredSpace = 30000000 - freeSpace
This gives us the number we need to filter our directories down with: any directory size equal to or more than the required space is a candidate for deletion. From that filtered down list of directory sizes, we’ll take the minimum and will have our solution:
root.subSizes()
.filter { $0 >= requiredSpace }
.min() ?? 0