Advent of Code 2024 day 9

aoc09

#!/usr/bin/env raku
use v6.d;
$*OUT.out-buffer = False;   # Autoflush

# Advent of Code 2024 day 9 -- https://adventofcode.com/2024/day/9

class DiskMap
{
    has $.map;

    has @!blocks;

    submethod TWEAK
    {
        # Parse the map, fill the blocks
        my $is-empty = True;
        my $file-id = -1;
        my $block-ptr = 0;
        for $!map.comb(/\d/) -> $n {
            $is-empty = !$is-empty;
            if $is-empty {
                @!blocks[$block-ptr ..^ $block-ptr+$n] »=» '.';
            }
            else {
                $file-id++;
                @!blocks[$block-ptr ..^ $block-ptr+$n] »=» $file-id;
            }
            $block-ptr += $n;
        }
    }

    method compact
    {
        my $left = 0;
        my $right = @!blocks.end;
        loop {
            $left++ while @!blocks[$left] ne '.' && $left ≤ $right;
            $right-- while @!blocks[$right] eq '.' && $right ≥ $left;
            last unless $left < $right;
            @!blocks[$left,$right] = @!blocks[$right,$left];
        }
    }

    method checksum
    {
        return @!blocks.kv.map(-> $i, $b { $i × ($b eq '.' ?? 0 !! $b) }).sum;
    }
}

class DiskMap2
{
    has $.map;

    has @!files;
    has @!free;

    submethod TWEAK
    {
        # Parse the map, keep track of files and free space
        my $is-empty = True;
        my $file-id = -1;
        my $block-ptr = 0;
        for $!map.comb(/\d/) -> $n {
            $is-empty = !$is-empty;
            if $is-empty {
                @!free.push({ start=>$block-ptr, len=>$n }) if $n > 0;
            }
            else {
                $file-id++;
                @!files.push({ id=>$file-id, start=>$block-ptr, len=>$n });
            }
            $block-ptr += $n;
        }
    }

    method compact
    {
        FILE:
        for @!files.reverse -> $file {
            # Find the leftmost free space that could fit the file
            my ($i, $free) = @!free.first(*<len> ≥ $file<len>, :kv);
            next FILE unless $free && $free<start> < $file<start>;

            # Move the file
            my $old-start = $file<start>;
            $file<start> = $free<start>;

            # Shrink (or remove) the originally free space
            if $free<len> > $file<len> {
                $free<start> += $file<len>;
                $free<len> -= $file<len>;
            }
            else {
                @!free.splice($i, 1);
            }

            # We should really manage the freed-up space.  But this is
            # time-consuming, and not really needed for this
            # compactification algorithm.  So don't bother.
            next FILE;

            # Free the original space of the file
            @!free.push({ start=>$old-start, len=>$file<len> });
            @!free .= sort(*<start>);

            # Consolidate free space
            loop (my $j = 0; $j < @!free.end; $j++) {
                if @!free[$j]<start> + @!free[$j]<len> == @!free[$j+1]<start> {
                    @!free[$j]<len> += @!free[$j+1]<len>;
                    @!free.splice($j+1, 1);
                }
            }
        }
    }

    method checksum
    {
        return @!files.map(-> $f {
                $f<id> × ($f<start>×$f<len> + $f<len> × ($f<len>-1) div 2)
            }).sum;
    }
}

sub MAIN(IO() $inputfile where *.f = 'aoc09.input')
{
    my $disk = DiskMap.new(:map($inputfile.slurp));
    $disk.compact;
    say "Part 1: the filesystem checksum is ", $disk.checksum;

    my $disk2 = DiskMap2.new(:map($inputfile.slurp));
    $disk2.compact;
    say "Part 1: the filesystem checksum is ", $disk2.checksum;
}