re: AoC Day 9: Marble Mania VIEW POST

FULL DISCUSSION
 

For the part 1, I used the naive solution with an array. It took about 0.55s.

#!/usr/bin/perl
use warnings;
use strict;
use feature qw{ say };

use List::Util qw{ max };

my $input = <>;
my ($players, $points) = $input =~ /(\d+)/g;

my $player = 1;
my $marble = 0;
my $current = 0;
my @circle = ($marble);
my %score;
while ($marble != $points) {
    ++$marble;

    if ($marble % 23) {
        my $pos = ($current + 2) % @circle;
        splice @circle, $pos, 0, $marble;
        $current = $pos;

    } else {
        $score{$player} += $marble;
        my $remove = $current - 7;
        $remove += @circle if $remove < 0;
        $remove %= @circle;
        $score{$player} += (splice @circle, $remove, 1)[0];
        $current = $remove;
    }

    ++$player;
    $player %= $players;
}

say max(values %score);

For part 2, it took 2h 47m, so I decided to switch to linked lists. Using POSIX::_exit I skipped the final global destruction, which saved me almost 1 second, so the program finished in 8s.

#!/usr/bin/perl
use warnings;
use strict;
use feature qw{ say };
use POSIX qw{ _exit };

use List::Util qw{ max };

use constant { PREV  => 0,
               NEXT  => 1,
               VALUE => 2 };

my $input = <>;
my ($players, $points) = $input =~ /(\d+)/g;
$points *= 100;

my $player = 1;
my $marble = 0;
my $current = [];
$current->[PREV]  = $current;
$current->[NEXT]  = $current;
$current->[VALUE] = 0;

my %score;
while ($marble != $points) {
    ++$marble;

    if ($marble % 23) {
        my $before = $current->[NEXT];
        my $after  = $before->[NEXT];
        my $insert = [$before, $after, $marble];
        $before->[NEXT] = $insert;
        $after->[PREV] = $insert;
        $current = $insert;

    } else {
        my $remove = $current;
        $remove = $remove->[PREV] for 1 .. 7;
        $score{$player} += $marble + $remove->[VALUE];
        my ($before, $after) = @$remove[PREV, NEXT];
        $before->[NEXT] = $after;
        $after->[PREV]  = $before;
        $current = $after;
    }

    ++$player;
    $player %= $players;
}

say max(values %score);
_exit(0);

code of conduct - report abuse