Hung-Yi's LogoHung-Yi’s Journal

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:

  1. Terminal Input: if the line starts with $
    Split the line on the space character to extract the command cmd and its argument arg. If the command is “cd”, update the current working directory cwd based on the arg, with special handling for “..” and “/”. If the command is something other than “cd”, leave the cwd unchanged. In either case, then return an object containing the updated cwd and the original dirSizeMap.
  2. Terminal Output: if the line does not start with $
    Split the line on the space character to extract the left and right segments. If left is a size (i.e. the line is not a directory), find all of the ancestors of the path using the ancestors() function, then update those ancestor paths in dirSizeMap by adding the file size to each of them. Finally, return an object containing the unchanged cwd and the updated dirSizeMap.
// 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:

1

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.

2

This is because the first segment is always the root directory / and the last segment is the current directory, which is not an ancestor.