7.md

Day 7 - No Space Left On Device - Code

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

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:

• The total size of directory e is 584 because it contains a single file i of size 584 and no other directories.
• The directory 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).
• Directory d has total size 24933642.
• As the outermost directory, / 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?

Solution

The interesting part of this solution was parsing the input into a filesystem. I created an Iterator that could be passed around to iterate more of the lines:

interface File {
  name: string;
  size: number;
}

interface FileSystem {
  path: string;
  files: File[];
  directories: FileSystem[];
}

interface Simulation {
  name: string;
  root: FileSystem;
  // filepath to flesystem
  map: Map<string, FileSystem>;
}

type ContentIterator = ReturnType<typeof contentIterator>;

function contentIterator(content: string[]) {
  let idx = 0;
  return {
    next(): string | undefined {
      // return first, and then increment.
      return content[idx++];
    },
    hasNext() {
      return idx < content.length;
    },
    peek(): string | undefined {
      return content[idx];
    },
    return() {
      idx = 0;
    },
  };
}

We'll iterate every line. When the command ls is reached, we'll pass the iterator over to a helper function that will use the same iterator to get all the files underneath the ls command.

Once the helper function is done, the outer function can go back to use the same iterator to go to the next command.

function getSimulations(): Simulation[] {
  return getRunsFromIniNewlineSep(input).map((sim) => {
    const root: FileSystem = {
      path: '/',
      files: [],
      directories: [],
    };
    const map = new Map([['/', root]]);
    let filepath = '/';
    const iterator = contentIterator(sim.content);
    while (iterator.hasNext()) {
      if (isCommand(iterator.peek()!)) {
        const [, command, args] = iterator.next()!.split(' ');
        switch (command) {
          case 'cd':
            filepath = path.join(
              filepath,
              assert(args, (a) => a.length > 0)
            );
            break;
          case 'ls':
            // addList will use the iterator to convert the subsequent
            // lines into files/directories.
            addList(iterator, filepath, map);
            break;
          default:
            throw new Error(`Unknown command ${command}`);
        }
      }
    }
    return {
      name: sim.name,
      root,
      map,
    };
  });
}

The addList command:

/**
 * @param cwd Current working directory.
 */
function addList(
  iterator: ContentIterator,
  cwd: string,
  addTo: Map<string, FileSystem>
) {
  if (!addTo.has(cwd)) {
    addTo.set(cwd, { path: cwd, files: [], directories: [] });
  }
  const system = addTo.get(cwd)!;
  while (iterator.hasNext() && !isCommand(iterator.peek()!)) {
    const line = iterator.next()!;
    let match: RegExpMatchArray | null = [''];
    if ((match = line.match(/^dir (\w+)$/))) {
      const [, dirname] = match!;
      const directory = {
        path: path.join(cwd, dirname),
        files: [],
        directories: [],
      };
      system.directories.push(directory);
      addTo.set(path.join(cwd, dirname), directory);
    } else if ((match = line.match(/^(\d+) ([^\s]+)$/))) {
      const [, size, filename] = match!;
      system.files.push({
        size: assert(Number(size), (s) => s >= 0),
        name: filename,
      });
    }
  }
}

function isCommand(line: string) {
  return line.slice(0, 2) === '$ ';
}