#!/usr/bin/perl

use strict;
use warnings;

use feature         qw(say);

my @input = map { chomp; split // } <>;

# Read in disk
my @disk;

my $id = 0;
while (@input) {
    my $size = shift @input;
    my $gap  = shift @input;

    push( @disk, {id => $id++, size => int $size} );
    push( @disk, {id => -1,    size => int $gap } )   if ($gap);
}

# Defragment disk
my $idx = $#disk;
for (my $file_id = $id - 1; $file_id > 0; $file_id--) {
    $idx--  while ($disk[$idx]{id} != $file_id);

    my $span = 0;
    $span++ while ($span < $idx and ($disk[$span]{id} != -1
                                    or $disk[$span]{size} < $disk[$idx]{size}));

    next if ($span >= $idx);

    # get amount of span still not used:
    my $unused_size = $disk[$span]{size} - $disk[$idx]{size};

    # move data:
    $disk[$span]->%* = $disk[$idx]->%*;
    $disk[$idx]{id}  = -1;

    splice( @disk, $span + 1, 0, {size => $unused_size, id => -1} ) if ($unused_size);
}

# Calculate checksum
my $part2 = 0;
my $pos = 0;
foreach my $b (@disk) {
    if ($b->{id} != -1 and $b->{size} > 0) {
        for (my $i = 0; $i < $b->{size}; $i++) {
            $part2 += $b->{id} * ($pos + $i);
        }
    }
    $pos += $b->{size};
}
say "Part 2: $part2";