AoC 2022/7 - ENOSPC - no space left on device

TL;DR

On with Advent of Code puzzle 7 from 2022: finding space in a disk.

There’s definitely a parsing flair in this year’s puzzles, within a rich bouquet of themes and a strong note of three.

This time we’re given the (hypotetical) recording of a shell session, from where we have to calculate a few things about directory sizes and what to get rid of.

The input is 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 parse it, I’m sticking to my Perl origins:

sub get-inputs ($filename) {
   my (@cwd, $cwd, %fs);
   %fs</> = { name => '/' };
   for $filename.IO.lines -> $line {
      if $line ~~ /^ \$ \s+ cd \s+ (.*) / {
         my $dir = $/[0].Str;
         $dir = '' if $dir eq '/';
         if $dir eq '..' { @cwd.pop }
         else            { @cwd.push: $dir }
         $cwd = (@cwd.Slip, '').join('/');
      }
      elsif $line ~~ /^ \$ \s+ ls / {
         %fs{$cwd} = { name => @cwd[*-1], size => 0, children => [] };
      }
      elsif $line ~~ /^ dir \s+ (.*) / {
         %fs{$cwd}<children>.push: $/[0].Str ~ '/';
      }
      else {
         $line ~~ /^ (\d+) \s+ (.*) /;
         %fs{$cwd}<children>.push: $/[1].Str;
         %fs{$cwd ~ $/[1].Str} = {size => $/[0].Int};
      }
   }
   update-sizes(%fs, '/');
   return %fs;
}

The return value is a Hash representing the filesystem (each key points to either a “file” or a “directory”.

The update-sizes at the end does the visit on the tree to update the overall size of each node:

sub update-sizes (%fs, $path) {
   return %fs{$path}<size> unless %fs{$path}<children>:exists;
   my $size = 0;
   for %fs{$path}<children>.Slip -> $child {
      $size += update-sizes(%fs, $path ~ $child);
   }
   %fs{$path}<size> = $size;
   return $size;
}

Plain old recursion is good.

At this point, I found it best to address both puzzle halves in a single function:

sub solve ($filename) {
   my $highlight = "\e[1;97;45m";
   my $reset     = "\e[0m";

   my %filesystem = get-inputs($filename);
   my ($start, $elapsed);

   $start = now;
   my $sum = 0;
   my $needed = 30000000 - (70000000 - %filesystem</><size>);
   my ($best, $best_size);
   for %filesystem.keys -> $path {
      next unless $path ~~ / \/$ /;
      my $size = %filesystem{$path}<size>;
      $sum += $size if $size <= 100000;
      if $size > $needed {
         if defined($best) {
            ($best, $best_size) = $path, $size
               if $best_size > $size;
         }
         else {
            ($best, $best_size) = $path, $size;
         }
      }
   }
   $elapsed = now - $start;

   put "part1 ($elapsed) $highlight$sum$reset";
   put "part2 ($elapsed) $highlight$best_size$reset";

   return 0;
}

Our %filesystem has all the info we need, so it’s just a matter of looking for the needed data.

Full solution.

This is it, cheers!


Comments? Octodon, Twitter, GitHub, Reddit, or drop me a line!