No Space Left On Device
Question
This was a fun day! we finally got something challenging.
We got a device from the elves when trying to update that device we got an error that notifies us that there isn't enough memory on our device
$ system-update --please --pretty-please-with-sugar-on-top
Error: No space left on the device
To determine what's going on we start exploring the device file system and record the output (our puzzle input)
For example
$ cd /
$ ls
dir a
14848514 b.txt
8504156 c.dat
dir d
$ cd a
$ ls
dir e
29116 f
2557 g
62596 h.lst
$ cd e
$ ls
584 i
$ cd ..
$ cd ..
$ cd d
$ ls
4060174 j
8033020 d.log
5626152 d.ext
7214296 k
represent the following structure
- / (dir)
- a (dir)
- e (dir)
- i (file, size=584)
- f (file, size=29116)
- g (file, size=2557)
- h.lst (file, size=62596)
- b.txt (file, size=14848514)
- c.dat (file, size=8504156)
- d (dir)
- j (file, size=4060174)
- d.log (file, size=8033020)
- d.ext (file, size=5626152)
- k (file, size=7214296)
When I first solved it I iterated over all commands and didn't create any kind of structure and just kept track of the current dir and update its parent size once we are done with it.
I thought about trying something a bit more interesting for this post, let's create a file system representation from our input and use it later to answer today's puzzle
First, we need to make sense of each line of our input, for that we are going to create a tokenizer!
our tokens
// token/token.go
package token
type TokenType string
const (
Cd TokenType = "Cd"
Ls TokenType = "Ls"
File TokenType = "File"
Dir TokenType = "Dir"
)
type Token struct {
Type TokenType
Literal string
}
We have 4 types of tokens, one for each type of output line.
In addition, we also save the raw data in literal so we can make use of it later on.
Now let's write our tokenizer, its responsibility is to get our input and transform it into a list of meaningful tokens
// token/tokenizer.go
package token
import "strings"
func newToken(tokenType TokenType, literal string) Token {
return Token{
Type: tokenType,
Literal: literal,
}
}
func Tokenize(raw string) []Token {
lines := strings.Split(string(raw), "\n")
tokens := []Token{}
for _, l := range lines {
parts := strings.Split(l, " ")
// process commands
if parts[0] == "$" {
if parts[1] == "ls" {
tokens = append(tokens, newToken(Ls, l))
} else {
tokens = append(tokens, newToken(Cd, l))
}
// process ls output
} else {
if parts[0] == "dir" {
tokens = append(tokens, newToken(Dir, l))
} else {
tokens = append(tokens, newToken(File, l))
}
}
}
return tokens
}
Create a struct to represent our file system
type FileSystem struct {
root *FileSystemNode
}
type FileSystemNode struct {
Size int
Parent *FileSystemNode
Token token.Token
Name string
Dirs map[string]*FileSystemNode
}
Now to the fun part, going over our tokens and constructing a tree like structure based on that
func newFileSystemNode(name string, token token.Token, parent *FileSystemNode) *FileSystemNode {
return &FileSystemNode{Name: name, Parent: parent, Token: token, Dirs: map[string]*FileSystemNode{}}
}
func NewFileSystem(tokens []token.Token) *FileSystem {
root := newFileSystemNode("/", token.Token{Type: token.Dir, Literal: "/"}, nil)
fileSystem := &FileSystem{root}
current := root
for _, t := range tokens {
switch t.Type {
case token.File:
current.Size += CreateFileNode(t.Literal).Size
case token.Dir:
node := CreateDirNode(t.Literal)
current.Dirs[node.Name] = newFileSystemNode(node.Name, t, current)
case token.Ls:
continue
case token.Cd:
cdNode := CreateCdNode(t.Literal)
if cdNode.To == ".." {
current.Parent.Size += current.Size
current = current.Parent
} else {
_, ok := current.Dirs[cdNode.To]
if ok {
current = current.Dirs[cdNode.To]
}
}
default:
fmt.Println("Unexpected token!", t)
}
}
// In case we are not ending at the root node
for current != root {
current.Parent.Size += current.Size
current = current.Parent
}
return fileSystem
}
We iterate over our tokens and perform some operations depending on the type of token we got
- file token: add the file size to the current dir
- dir token: create a new directory in the current dir and name it based on the token literal (the dir name)
- ls token: we don't care about it and just continue our loop
- cd token:
- ".." literal: we change
currentto becurrent.parentand add the size of the current dir to the parent - else, its some dir that we have seen before using
lsand we change the current dir to becurrent.Dirs[dirName]
- ".." literal: we change
type CdNode struct {
To string
}
func CreateCdNode(str string) CdNode {
parts := strings.Split(str, " ")
return CdNode{
To: parts[2],
}
}
At the end of the function we backtrack to our root directory and add each directory size in that path to its parent, this is because our output does not contain .. commands back to the top.
Now that we have got our file system creation process all dialed in we can start implementing the first part solution
Part 1
We are tasked to find all directories with size <= 100,000
To do that we need to have a way to walk over each directory in our file system structure. Let's add methods to support that capability
func (tree *FileSystem) Walk(visitor func(t *FileSystemNode)) {
tree.root.Walk(visitor)
}
func (node *FileSystemNode) Walk(visitor func(t *FileSystemNode)) {
visitor(node)
for _, t := range node.Dirs {
t.Walk(visitor)
}
}
Both FileSystem and FileSystemNode get a
Walkmethod
We pass in a function that will be called on each node in our file system.
Using the above method our solution is now as simple as
func Part1(raw string) int {
fs := parse(raw)
sum := 0
fs.Walk(func(node *fileSystem.FileSystemNode) {
if node.Size <= 100000 {
sum += t.Size
}
})
return sum
}
Part 2
In part 2 we are tasked with increasing the amount of free space to at least 3,000,000 we also know that the total memory on our device is 7,000,000
We need to find the smallest directory that we can delete that will increase the amount of free memory >= 3,000,000
In our example, we have the following options:
- Delete directory e, which would increase unused space by 584.
- Delete directory a, which would increase unused space by 94853.
- Delete directory d, which would increase unused space by 24933642.
- Delete directory /, which would increase unused space by 48381165.
Directories e and a are both too small; deleting them would not free up enough space. However, directories d and / are both big enough! Between these, choose the smallest: d, increasing unused space by 24933642.
The logic to solve part 2 is also fairly straightforward but we do need to expose the size of our fileSystem first
func (tree *FileSystem) Size() int {
return tree.root.Size
}
Part 2 solution
func Part2(raw string) int {
fs := parse(raw)
const OS_MEM = 70000000
const THRESHOLD = 30000000
unusedSpace := OS_MEM - fs.Size()
min := OS_MEM
fs.Walk(func(node *fileSystem.FileSystemNode) {
if unusedSpace+node.Size > THRESHOLD {
if min > node.Size {
min = node.Size
}
}
})
return min
}
For each directory, we check if by deleting it we have enough free memory unusedSpace+t.Size > THRESHOLD if it does we check to see if it's less than our current smallest directory.
Pheww...That's it for day 7!
I know this approach is a bit too structured for an AoC problem and initially, I solved it without building the entire structure, tokens etc...
For the sake of this blog post, I thought I'll make things a bit more structured and interesting
You can find the complete code here
Thanks for reading!
Top comments (0)