Advent of Code 2022 — Day 7

This is the seventh article in the series where I share my solutions to the puzzles from the Advent of Code 2022. This year I am using PHP and created a platform for comfortable development. You can find more details about the platform here and feel free to use it.

<Day 6 | Day 8>

File system

Before you start reading, I encourage you to try to solve the puzzle by yourself.

No Space Left On Device

Surrounded by the wild nature the expedition continues towards its goal. However, the problems with the Elves' device don't seem to be over. We tried to update the system:

$ system-update --please --pretty-please-with-sugar-on-top
Error: No space left on device

The disk is full and we have to determine which files to delete. Today’s input is the series of commands and their results:

$ cd /
$ ls
dir a
14848514 b.txt
8504156 c.dat
dir d
$ cd a
$ ls
dir e
29116 f
2557 g
62596 h.lst
...

The cd and ls commands work the same as in the standard Linux terminal. The output of the ls command contains types of lines. Those starting with dir represent directories and the others files where the first number is the size of the file.

Our goal is to calculate the sum of the directories smaller than 100000. The size of the directory is equal to the sum of the files plus the size of the nested directories.

To represent the directory we will create a class:

class Directory
{
    private int $size = 0;
    private string $name;
    private array $subDirs;

    public function __construct(string $name, ?Directory $parent)
    {
        $this->name = $name;
        $this->subDirs['..'] = $parent;
    }

    public function addFile(int $size): void
    {
       $this->size += $size;
       $this->subDirs['..']?->addFile($size);
    }

    public function addDir(Directory $dir): void
    {
        $this->subDirs[$dir->getName()] = $dir;
    }

    // Getters ...
}

There shouldn’t be anything surprising except:

$this->subDirs['..']?->addFile($size);

This line accomplishes that the parent directories will contain the files of the child directory. That’s what we in terms of the sizes of directories want.

Another class we will create is the wrapper around the whole file system. It will later simplify the execution of the commands.

class FileSystem
{
    private Directory $root;
    private Directory $context;

    public function __construct()
    {
        $root = new Directory('/', null);
        $this->root = $this->context = $root;
    }

    public function createDirectory(string $name): void
    {
        $this->context->addDir(new Directory($name, $this->context));
    }

    public function changeDirectory(string $name): void
    {
        $this->context = $name === '/'
            ? $this->root
            : $this->context->getSubDirs()[$name];
    }

    // Getters ...
}

The class maintains the current dir we are switched in and the pointer to the root. Since the dirs contain their parent directories the change mechanism is pretty simple.

Now we can start to think about how to process the input. First of all, we have to detect whether the line is the command.

protected function isCommand(string $line): bool
{
    return $line[0] === '$';
}

Also, a helper function to parse the command could be useful.

protected function parseCommand(string $cmd): array
{
    $parts = explode(' ', $cmd);
    array_shift($parts);
    return [
        'name' => array_shift($parts),
        'args' => $parts,
    ];
}

Processing of commands can be written as:

protected function processCommand($line, FileSystem $fileSystem): FileSystem
{
    $cmd = $this->parseCommand($line);

    if ($cmd['name'] === 'cd')
        $fileSystem->changeDirectory($cmd['args'][0]);

    return $fileSystem;
}

Here, we ignore the ls command because it doesn’t do anything useful for us. Processing of the output of the ls have to do two things. Create a new directory if the line starts with dir or add the file to the existing directory. We expect that the input is correct so we can omit the test for the directory existence.

protected function processLsOutput($line, FileSystem $fileSystem): FileSystem
{
    $parts = explode(' ', $line);
    if ($parts[0] === 'dir')
        $fileSystem->createDirectory($parts[1]);
    else
        $fileSystem->getCurrentDir()->addFile(intval($parts[0]));

    return $fileSystem;
}

That’s all we need to create the file system from the input. To make it happen we write a simple reduce function.

$fileSystem = array_reduce($input, function (FileSystem $fileSystem, $line) {
    return $this->isCommand($line)
        ? $this->processCommand($line, $fileSystem)
        : $this->processLsOutput($line, $fileSystem);
}, new FileSystem());

To find the size the puzzle is asking for we have to traverse the file system now. It may be overkill for a puzzle like this, but for educational purposes, I will implement an iterator for the FileSystem class.

class FileSystemIterator implements \Iterator
{
    private Directory $root;
    private ?Directory $context;
    private \SplStack $stack;


    public function __construct(Directory $root)
    {
        $this->root = $this->context = $root;
        $this->stack = new \SplStack();
    }

    // Other required functions 
}

The iterator will receive the root directory to easy rewind and will contain the stack of the directories we are nested in.

public function rewind(): void
{
    $this->context = $this->root;
    $this->stack->push($this->getIterableDirs($this->root->getSubDirs()));
}

The getIterbleDirs will filter out the parent directories. In the case of the root directory, we have to check for the null because it hasn’t any parent.

private function getIterableDirs(array $dirs): array
{
    return array_filter(
        $dirs,
        fn($dir, $name) => !is_null($dir) && $name != '..',
        ARRAY_FILTER_USE_BOTH
    );
}

Context property is the current directory we will use for the implementation of three functions.

public function current(): int
{
    return $this->context->getSize();
}

public function key(): string
{
    return $this->context->getName();
}

public function valid(): bool
{
    return !is_null($this->context);
}

current and key are self-explaining. At the moment we run out of directories to iterate over we set context to null and that’s the signal for the valid function to stop the iteration. The only missing piece is the most complex next function.

public function next(): void
{
    if ($this->stack->isEmpty()) {
        $this->context = null;
        return;
    }

    $cur = $this->stack->pop();
    $item = array_shift($cur);
    $subDirs = $this->getIterableDirs($item->getSubDirs());

    if (!empty($cur))
        $this->stack->push($cur);

    if (!empty($subDirs))
        $this->stack->push($subDirs);

    $this->context = $item;
}

The first if is the functionality I wrote about higher. It’s here to stop the iteration. Then we pop one directory from the stack shift the first subdirectory and set it as the current context. In between, we fetch subdirectories of the selected item and in case they are not empty we push them on the stack. Also, we push back the original subdirectories.

The iterator is done. We can add it to our filesystem.

class FileSystem implements \IteratorAggregate
{
    // Functions we saw earlier 

    public function getIterator(): Traversable
    {
        return new FileSystemIterator($this->root);
    }
}

Because as you may notice in the previous chapters of this series I like to use functions like array_map or array_reduce. The sad story is that those functions work only with arrays and not with iterables. To fix this issue here is a helper function that can.

function reduce(iterable $iterator, callable $callback, $initial = null) {
    foreach ($iterator as $item) {
        $initial = $callback($initial, $item);
    }
   return $initial;
}

After a long preparation here is the fast solution to the puzzle:

protected function calculateSize(FileSystem $fileSystem): mixed
{
    return reduce(
        $fileSystem,
        fn($sum, $dir) => $sum + ($dir <= 100000 ? $dir : 0),
        0
    );
}

Part two

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.

Well, we have to find the smallest directory we can delete to have enough space. The preparation once again pays off and we can solve the second part by modifying one function.

protected function calculateSize(FileSystem $fileSystem): mixed
{
    $rootSize = $fileSystem->getRootDir()->getSize();
    $requiredSpace = $rootSize - 40000000;
    return reduce(
        $fileSystem,
        function ($minToDelete, $dir) use ($requiredSpace) {
            return $dir >= $requiredSpace 
                ? min($minToDelete, $dir) 
                : $minToDelete;
        },
        $rootSize
    );
}

Conclusion

This puzzle wasn’t algorithmically hard, but we had to find a way to interpret the commands and their output. We created a replica of the filesystem and implement the iterator of that recursive structure. That allowed us to easily solve both parts of the puzzle.

The complete source code of today’s solution can be found on my GitHub.

Do you want to know how I solve the other days? Please follow me here on Medium and don’t miss the following articles.

<Day 6 | Day 8>