Advent of Code 2022: Day 7
A TypeScript solution for the Advent of Code 2022, Day 7 puzzle: simulating an imaginary file system by inspecting terminal input & ouput.
Today’s puzzle asks us to inspect the input and output of cd
and ls
commands in a made-up terminal session in order to calculate the directory structure and sizes of an imaginary file system.
The puzzle input looks something like this.
$ 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
To calculate the size of a directory, including the sizes of all its children, we can define a helper function called ancestors()
. It takes a path string as an argument and returns an array of ancestor paths leading up to that path.1 To do this, we split the path into segments using split()
, then remove the first and last segments with slice()
.2 We then use reduce()
to create an array of paths by calling pathJoin()
(which we will implement next) on each directory name and the previous path.
// Returns ancestor paths of a given file or directory path. const ancestors = (path: string) => path .split('/') .slice(1, -1) .reduce( (acc, curr) => [...acc, pathJoin(acc[acc.length - 1], curr)], ['/'] );
For example, calling the ancestors()
function with the path "/one/two/three"
would return the following array of ancestor paths:
["/", "/one", "/one/two"]
For joining multiple paths into a single path, we implement the pathJoin()
utility function. It takes a variable number of paths as arguments and joins them together. We use map()
to remove any trailing /
characters from the paths and join()
to combine them into a single string with /
as the separator.
// Joins the given path segments // and removes trailing slashes from each segment. const pathJoin = (...paths: string[]) => paths .map(path => path?.replace(/\/$/, '') ?? '') .join('/');
Now we’re ready to parse. We split the puzzle input into lines and reduce()
over them with the following rules:
- Terminal Input: if the line starts with
$
Split the line on the space character to extract the commandcmd
and its argumentarg
. If the command is “cd”, update the current working directorycwd
based on thearg
, with special handling for “..” and “/”. If the command is something other than “cd”, leave thecwd
unchanged. In either case, then return an object containing the updatedcwd
and the originaldirSizeMap
. - Terminal Output: if the line does not start with
$
Split the line on the space character to extract theleft
andright
segments. Ifleft
is a size (i.e. the line is not a directory), find all of the ancestors of the path using theancestors()
function, then update those ancestor paths indirSizeMap
by adding the file size to each of them. Finally, return an object containing the unchangedcwd
and the updateddirSizeMap
.
// This code processes a string containing a sequence of // commands and files/directories, and returns an array // of sizes for each directory in the file system. const { dirSizeMap } = puzzleInput.split('\n').reduce( ({ cwd, dirSizeMap }, line) => { if (line.startsWith("$")) { // Terminal Input const [,cmd,arg] = line.split(' '); return { cwd: cmd === 'cd' ? arg === '/' ? '/' : arg === '..' ? ancestors(cwd).slice(-1)[0] : pathJoin(cwd, arg) : cwd, dirSizeMap } } else { // Terminal Output const [left, right] = line.split(' '); const size = left !== 'dir' ? parseInt(left) : undefined; const path = pathJoin(cwd, right); return { cwd, dirSizeMap: !!size ? ancestors(path) .map(path => [path, size] as const) .reduce( (map, [path, size]) => map.set(path, (map.get(path) ?? 0) + size), dirSizeMap ) : dirSizeMap } } }, { cwd: '', dirSizeMap: new Map<string, number>() } ); const dirSizes = [...dirSizeMap.values()];
At the end, we convert dirSizeMap
into an array of numbers using the Map.prototype.values()
method and the spread operator ...
, and assign the result to the dirSizes
variable. We do this because the directory path information is no longer relevant to our final answers.
For the part 1 solution, we filter the dirSizes
array and keep only the sizes that are less than or equal to 100,000. We then reduce()
to sum up the remaining sizes.
const part1 = dirSizes .filter(s => s <= 100_000) .reduce((s, x) => s + x, 0);
For part 2, we first define some constants that are used in the calculation of the answer:
totalDiskSpace
represents the total disk space on the computer,usedDiskSpace
represents the amount of disk space used by the directories in the input,unusedDiskSpace
represents the amount of disk space that is unused,requiredDiskSpace
represents the total amount of disk space that is required for the new software,- and
diskSpaceToFree
represents the amount of disk space that must be freed up in order to install the new software.
This time we filter()
the dirSizes
array and keep only the sizes that are greater than or equal to the diskSpaceToFree
. We then find the minimum value in this list using Math.min()
, which is the smallest directory that satisfies the diskSpaceToFree
.
const totalDiskSpace = 70_000_000; const usedDiskSpace = dirSizeMap.get('/'); const unusedDiskSpace = totalDiskSpace - usedDiskSpace; const requiredDiskSpace = 30_000_000; const diskSpaceToFree = requiredDiskSpace - unusedDiskSpace; const part2 = Math.min( ...dirSizes.filter(s => s >= diskSpaceToFree) );
Final Solution
// Returns ancestor paths of a given file or directory path. const ancestors = (path: string) => path .split('/') .slice(1, -1) .reduce( (acc, curr) => [...acc, pathJoin(acc[acc.length - 1], curr)], ['/'] ); // Joins the given path segments // and removes trailing slashes from each segment. const pathJoin = (...paths: string[]) => paths .map(path => path?.replace(/\/$/, '') ?? '') .join('/'); // This code processes a string containing a sequence of // commands and files/directories, and returns an array // of sizes for each directory in the file system. const { dirSizeMap } = puzzleInput.split('\n').reduce( ({ cwd, dirSizeMap }, line) => { if (line.startsWith("$")) { // Terminal Input const [,cmd,arg] = line.split(' '); return { cwd: cmd === 'cd' ? arg === '/' ? '/' : arg === '..' ? ancestors(cwd).slice(-1)[0] : pathJoin(cwd, arg) : cwd, dirSizeMap } } else { // Terminal Output const [left, right] = line.split(' '); const size = left !== 'dir' ? parseInt(left) : undefined; const path = pathJoin(cwd, right); return { cwd, dirSizeMap: !!size ? ancestors(path) .map(path => [path, size] as const) .reduce( (map, [path, size]) => map.set(path, (map.get(path) ?? 0) + size), dirSizeMap ) : dirSizeMap } } }, { cwd: '', dirSizeMap: new Map<string, number>() } ); const dirSizes = [...dirSizeMap.values()]; const part1 = dirSizes .filter(s => s <= 100_000) .reduce((s, x) => s + x, 0); const totalDiskSpace = 70_000_000; const usedDiskSpace = dirSizeMap.get('/'); const unusedDiskSpace = totalDiskSpace - usedDiskSpace; const requiredDiskSpace = 30_000_000; const diskSpaceToFree = requiredDiskSpace - unusedDiskSpace; const part2 = Math.min( ...dirSizes.filter(s => s >= diskSpaceToFree) ); console.log("Part 1:", part1); console.log("Part 2:", part2);
Part 1: 1915606 Part 2: 5025657
Footnotes:
Note that the ancestors()
function only returns ancestor paths up to but not including the current directory. The current directory is not considered an ancestor because it is not “above” the current path in the file system hierarchy.
This is because the first segment is always the root directory /
and the last segment is the current directory, which is not an ancestor.