Advent of Code (in MiniScript), Day 7
Tags: miniscript, adventof, programm
Published: 2022-12-07 15:08:04

Continuing my [series](https://dev.to/search?q=JoeStrout%20%23adventofcode) showing [Advent of Code](https://adventofcode.com/) solutions in [MiniScript](https://miniscript.org), last night's challenge — [Day 7](https://adventofcode.com/2022/day/7) — was in interesting one.  We're given a terminal session showing a bunch of `cd` and `ls` commands, from which we need to reconstruct a file hierarchy, and then search that for some aggregate directory sizes.

More specifically: for Part A of the challenge, we needed to report the sum of all directories containing less than 100000 bytes.  And for Part B, we needed to report the size of the smallest directory that was at least big enough that, if deleted, it would provide a given amount of free space on the disk.

A file hierarchy is clearly a tree structure, but for some reason, I quickly abandoned making an actual tree of little node objects for a different approach.  But after completing the challenge and chatting with my spouse — who is doing these challenges [in Chapel](https://chapel-lang.org/blog/posts/aoc2022-day04-ranges/) — I couldn't shake the feeling that I had done it the hard way.

So today, I'll share both solutions!

## Solution #1: Directory Map

The data structure I actually chose last night was a **map** in which each key was a complete directory path, and the corresponding value was a list of [name, size] pairs.  In the case of a directory, the pair was actually [name, "dir"] instead.

As I read the input file, I kept track of the current directory path as a string, using Mini Micro's built-in [file](https://miniscript.org/wiki/File) module to find child and parent paths as needed.  Then to find the total size of a directory, I wrote a recursive `dirSize` function that added up all the sizes of its children (calling itself in the case of any entry with "dir" for a size).  A similar recursive function was used to find all the small directories.

The complete program — after a little morning-after cleanup — comes to 89 lines, including both parts of the challenge.

```
f = file.open("input.txt")
//f = file.open("example.txt")

contents = {} // key: path; value: list of [name, size]
curDir = "/"
curEntries = []
contents[curDir] = curEntries

while not f.atEnd
	line = f.readLine
	if line == null then break // end of file
	print line
	m = line.match("$ cd {subdir}")
	if m then
		if m.subdir == "/" then
			curDir = "/"
		else if m.subdir == ".." then
			curDir = file.parent(curDir)
		else
			newDir = file.child(curDir, m.subdir)
			curDir = newDir
		end if
		if contents.hasIndex(curDir) then
			curEntries = contents[curDir]
		else
			curEntries = []
			contents[curDir] = curEntries
		end if
	else if line == "$ ls" then
		continue
	else
		// file line
		sizeOrDir = line.split(" ")[0]
		name = line.split(" ")[1]
		if sizeOrDir == "dir" then
			curEntries.push [name, "dir"]
		else
			curEntries.push [name, sizeOrDir.val]
		end if
	end if
end while
f.close

dirSize = function(path)
	entries = contents[path]
	sum = 0
	for e in entries
		if e[1] == "dir" then
			sum = sum + dirSize(file.child(path, e[0]))
		else
			sum = sum + e[1]
		end if
	end for
	return sum
end function

resultA = []
findSmallDirs = function(path)
	for e in contents[path]
		if e[1] == "dir" then
			subpath = file.child(path, e[0])
			sz = dirSize(subpath)
			if sz <= 100000 then
				print "Small dir: " + subpath + " of size: " + sz
				resultA.push sz
			end if
			findSmallDirs subpath
		end if
	end for
end function

findSmallDirs "/"
print "final answer (part A): " + resultA.sum

diskSize = 70000000
spaceUsed = dirSize("/")
curFree = diskSize - spaceUsed
spaceRequired = 30000000
needed = spaceRequired - curFree
print "Need to find " + needed + " bytes"

// Now find smallest dir that's at least needed bytes
best = null
for d in contents.indexes
	sz = dirSize(d)
	if sz < needed then continue
	if best == null or sz < best then best = sz
end for
print "final answer (part B): " + best
```

It worked.  But it wasn't super fast to code; it took me 28 minutes, the longest time yet.  And my final rank was 1016, not quite reaching my goal of the top 1000.

## Solution #2: A Tree of Nodes

So this morning, I coded up the other approach, of making a proper tree.  I defined a Node class, which would be both the base class and the class instantiated for any file; and a DirNode subclass, which represents a directory.  DirNodes keep a map of their children (from name to Node).  We need to be able to get from a child to its parent, in order to process the `cd ..` commands in the input, so I gave `DirNode` an `addChild` method that would both add the child to its map, and set the child's `parent` to itself.

Finally, while a file Node would have a `size` member set to its own size, `DirNode.size` was assigned a function that added up the sizes of all its children.  (Notice that in MiniScript, it's perfectly fine for a subclass to override a simple value with a function, or vice versa.)

The code for reading and processing the input came out very similar.  The subsequent code was simpler, though.  Given any node, we can simply check its `.size`, and not worry about whether it's a file or a directory.  (However I did find I had no quick way to find all the directory nodes; so I ended up adding an `allDirs` list, and pushing each new DirNode onto that as it is made.)

The complete program comes to 87 lines — almost the same as last night's version.

```
f = file.open("input.txt")
//f = file.open("example.txt")

Node = {}
Node.name = ""
Node.size = 0

DirNode = new Node
DirNode.children = null // map from name to Node
DirNode.addChild = function(node)
	self.children[node.name] = node
	node.parent = self
end function
DirNode.size = function
	sum = 0
	for c in self.children.values
		sum = sum + c.size
	end for
	return sum
end function

root = new DirNode
root.name = ""
root.children = {}

curDir = root
allDirs = []

while not f.atEnd
	line = f.readLine
	if line == null then break // end of file
	print line
	m = line.match("$ cd {subdir}")
	if m then
		if m.subdir == "/" then
			curDir = root
		else if m.subdir == ".." then
			curDir = curDir.parent
		else
			curDir = curDir.children[m.subdir]
		end if
	else if line == "$ ls" then
		continue
	else
		// file line
		sizeOrDir = line.split(" ")[0]
		name = line.split(" ")[1]
		if sizeOrDir == "dir" then
			noob = new DirNode
			noob.children = {}
			allDirs.push noob
		else
			noob = new Node
			noob.size = sizeOrDir.val
		end if
		noob.name = name
		curDir.addChild noob
	end if
end while
f.close

// find sum of small dirs
resultA = []
for e in allDirs
	sz = e.size
	if sz <= 100000 then
		print "Small dir: " + e.name + " of size: " + sz
		resultA.push sz
	end if
end for
print "final answer (part A): " + resultA.sum

diskSize = 70000000
spaceUsed = root.size
curFree = diskSize - spaceUsed
spaceRequired = 30000000
needed = spaceRequired - curFree
print "Need to find " + needed + " bytes"

// Now find smallest dir that's at least needed bytes
best = null
for d in allDirs
	sz = d.size
	if sz < needed then continue
	if best == null or sz < best then best = sz
end for
print "final answer (part B): " + best
```

## Conclusion

In the end, the two approaches were of similar length and complexity.  The node approach _feels_ cleaner somehow, but when actually doing the challenge for time, all that matters is the fastest (not always the cleanest) path to an answer.  Would the tree approach have been faster?  Hard to say.

As always, I come away from one of these challenges thinking about what sort of library code could have made it faster.  Perhaps some methods for searching, filtering, and applying-methods-to trees?  With those in hand, the tree approach would certainly have been faster than my custom map-to-lists code.

Once again, the Advent of Code challenge was a fun and thought-provoking exercise.  I look forward to the days ahead!