You can hear birds chirping and raindrops hitting leaves as the expedition proceeds. Occasionally, you can even hear much louder sounds in the distance; how big do the animals get out here, anyway?
The device the Elves gave you has problems with more than just its communication system. You try to run a system update:
$ system-update --please --pretty-please-with-sugar-on-top
Error: No space left on device
Perhaps you can delete some files to make space for the update?
You browse around the filesystem to assess the situation and save the resulting terminal output (your 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
The filesystem consists of a tree of files (plain data) and directories (which can contain other directories or files). The outermost directory is called /. You can navigate around the filesystem, moving into or out of directories and listing the contents of the directory you're currently in.
Within the terminal output, lines that begin with $ are commands you executed, very much like some modern computers:
cd means change directory. This changes which directory is the current directory, but the specific result depends on the argument:cd x moves in one level: it looks in the current directory for the directory named x and makes it the current directory.cd .. moves out one level: it finds the directory that contains the current directory, then makes that directory the current directory.cd / switches the current directory to the outermost directory, /.ls means list. It prints out all of the files and directories immediately contained by the current directory:123 abc means that the current directory contains a file named abc with size 123.dir xyz means that the current directory contains a directory named xyz.Given the commands and output in the example above, you can determine that the filesystem looks visually like this:
- / (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)
Here, there are four directories: / (the outermost directory), a and d (which are in /), and e (which is in a). These directories also contain files of various sizes.
Since the disk is full, your first step should probably be to find directories that are good candidates for deletion. To do this, you need to determine the total size of each directory. The total size of a directory is the sum of the sizes of the files it contains, directly or indirectly. (Directories themselves do not count as having any intrinsic size.)
The total sizes of the directories above can be found as follows:
e is 584 because it contains a single file i of size 584 and no other directories.a has total size 94853 because it contains files f (size 29116), g (size 2557), and h.lst (size 62596), plus file i indirectly (a contains e which contains i).d has total size 24933642./ contains every file. Its total size is 48381165, the sum of the size of every file.To begin, find all of the directories with a total size of at most 100000, then calculate the sum of their total sizes. In the example above, these directories are a and e; the sum of their total sizes is 95437 (94853 + 584). (As in this example, this process can count files more than once!)
Find all of the directories with a total size of at most 100000. What is the sum of the total sizes of those directories?
# Python imports
from __future__ import annotations # required for self-typing within class, will be default in 3.11
from pathlib import Path
from typing import Optional
test = Path("data/day07_test.txt") # test data
data = Path("data/day07_data.txt") # puzzle data
class FSNode:
"""Represents a node (directory or file) in a Filesystem object"""
def __init__(self, name: str, parent: Optional[FSNode], ntype: str="file", size: int=0) -> None:
"""Instantiate an FSNode (directory or file)
:param name: human-readable name for the node
:param parent: parent node (None if root node)
:param ntype: type of node
:param size: size of node
"""
self.name = name # name of this node
self.parent = parent # parent directory
self.children = {} # holds all children, dirs and files, keyed by name
self.ntype = ntype # node type
self.size = size # size of this node (0 for directories)
def add_child(self, name: str, ntype: str="file", size: int=0) -> None:
"""Add child FSNode to current node
:param name: human-readable name of child node
:param ntype: type of child node
:param size: size of child node
"""
self.children[name] = FSNode(name, self, ntype, size) # add new node to children
def get_all_children(self) -> list[FSNode]:
"""Return all children of the current node"""
# Iterate over child nodes, and their children, and return as a list
nodes = []
for name, node in self.children.items():
nodes += [node] + node.get_all_children()
return nodes
@property
def tree(self) -> str:
"""Return subtree as prettified string"""
outstr = [f"- {self}"] # start at current location
for name, node in self.children.items(): # indent tree output for children by " "
outstr += [" " + _ for _ in node.tree.split("\n")]
return "\n".join(outstr) # return recompiled tree with indents
def __len__(self) -> int:
"""Report length of node contents"""
# file nodes don't have children, so this is equivalent to self.size
# dir nodes only have children, so this is the size of all nodes below current node
return self.size + sum([len(_) for _ in self.children.values()])
def __str__(self) -> str:
"""Return human-readable information"""
if self.ntype == "dir": # directories don't have a size...
return f"{self.name} ({self.ntype})"
else: # ...but files do
return f"{self.name} ({self.ntype}, size={self.size})"
def __repr__(self) -> str:
"""Return string describing FSNode object"""
return f"<FSNode {self.name} ({self.ntype}, size={self.size}, total_size={len(self)} at {id(self)}>"
class Filesystem:
"""Represents a filesystem containing FSNode files and directories"""
def __init__(self) -> None:
"""Initialise a filesystem object"""
self.root = FSNode("/", None, ntype="dir", size=0) # initialise filesystem with root node
@property
def total_size(self) -> int:
"""Return total size of filesystem"""
return len(self.root) # length/size of root node is the used space
@property
def dirs(self) -> list[FSNode]:
"""Return all directories in the filesystem"""
return [_ for _ in self.root.get_all_children() if _.ntype == "dir"]
@property
def dir_sizes(self) -> list[tuple[int, str]]:
"""Return list of tuples containing directory names and sizes"""
return [(len(_), _.name) for _ in self.dirs]
def __str__(self):
"""Return Filesystem tree as string"""
return self.root.tree # root tree is the filesystem tree
def __repr__(self) -> str:
"""Return string describing Filesystem"""
return f"<Filesystem object at {id(self)}>"
def parse_input(fpath: Path):
"""Parse puzzle input into a filesystem
:param fpath: path to puzzle input
"""
with fpath.open() as ifh:
filesystem = Filesystem() # initialise
cursor = None
state = "command"
for line in [_.strip() for _ in ifh.readlines()]:
if line.startswith("$"): # start to read command state
state = "command" # switch state
# In a command state, process the command
if state == "command":
command = line.split()[1:]
if command[0] == "cd": # change directory
if command[1] == "/": # go to filesystem root
cursor = filesystem.root
elif command[1] == "..": # go up a directory
cursor = cursor.parent
else: # descend into child directory
cursor = cursor.children[command[1]]
if command[0] == "ls": # start to receive node information
state = "nodeinfo" # switch state
# In a node information state, add the current directory/file
elif state == "nodeinfo":
nodeinfo = line.split()
if nodeinfo[0] == "dir": # add directory to current node
cursor.add_child(nodeinfo[1], ntype="dir")
else:
cursor.add_child(nodeinfo[1], size=int(nodeinfo[0]))
return filesystem
def part1(fpath: Path) -> int:
"""Solve the puzzle
:param fpath: path to puzzle input
"""
filesystem = parse_input(fpath)
small_dirs = [_ for _ in filesystem.root.get_all_children() \
if _.ntype == "dir" and len(_) < 100000]
return sum([len(_) for _ in small_dirs])
# Check that we can reproduce the filesystem pretty output
fs = parse_input(test)
print(fs)
- / (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)
part1(test)
95437
part1(data)
1423358
Now, you're ready to choose a directory to delete.
The total disk space available to the filesystem is 70000000. To run the update, you need unused space of at least 30000000. You need to find a directory you can delete that will free up enough space to run the update.
In the example above, the total size of the outermost directory (and thus the total amount of used space) is 48381165; this means that the size of the unused space must currently be 21618835, which isn't quite the 30000000 required by the update. Therefore, the update still requires a directory with total size of at least 8381165 to be deleted before it can run.
To achieve this, you have the following options:
e, which would increase unused space by 584.a, which would increase unused space by 94853.d, which would increase unused space by 24933642./, 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.
Find the smallest directory that, if deleted, would free up enough space on the filesystem to run the update. What is the total size of that directory?
def get_dir_for_deletion(filesystem: Filesystem, min_dirsize: int) -> FSNode:
"""Return smallest FSNode directory with size above min_dirsize, or root
:param filesystem: filesystem being searched
:param min_dirsize: lower limit on directory size to report
"""
curdir = filesystem.root # start by considering deletion of complete filesystem
for fsdir in sorted(filesystem.dir_sizes, reverse=True): # iterate from largest to smallest directory
if fsdir[0] > min_dirsize: # if the current directory size > threshold...
curdir = fsdir # ...this is the smallest directory that can be deleted
else: # no more directories could fulfil conditions...
return curdir # ...so return the last directory we found
def part2(fpath: Path) -> int:
"""Solve the puzzle
:param fpath: path to puzzle input
"""
total_space = 70000000 # total space available to filesystem
required_space = 30000000 # space required for update
filesystem = parse_input(fpath) # load in filesystem info
min_dirsize = required_space - (total_space - filesystem.total_size) # calculate minimum deletion size
return get_dir_for_deletion(filesystem, min_dirsize)[0] # size of directory to be deleted
part2(test)
24933642
part2(data)
545729