re: AoC Day 11: Chronal Charge VIEW POST

FULL DISCUSSION
 

Brute force was enough for part 1:

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

my $size = 3;
chomp( my $serial_number = <> );

my @grid;
my @squares;
my $max = [1, 1];
for my $x (1 .. 300) {
    for my $y (1 .. 300) {
        my $rack_id = $x + 10;
        my $level = ($rack_id * $y + $serial_number) * $rack_id;
        $level =~ s/^.*(.)..$/$1/ or $level = 0;
        $level -= 5;
        $grid[$x][$y] = $level;
        if ($x >= $size && $y >= $size) {
            for my $i (0 .. $size - 1) {
                for my $j (0 .. $size - 1) {
                    $squares[ $x - $size + 1 ][ $y - $size + 1 ]
                        += $grid[ $x - $i ][ $y - $j ];
                }
            }
            $max = [ $x - $size + 1, $y - $size + 1 ]
                if $squares[ $x - $size + 1 ][ $y - $size + 1 ]
                > $squares[ $max->[0] ][ $max->[1] ];
        }
    }
}

say join ',', @$max;

Part 2 was running for several hours, so I decided to optimize it. Using smaller squares and only adding the right and bottom edge reduced the time to 4m 10s which was good enough for me.

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

use List::Util qw{ sum };

chomp( my $serial_number = <> );

my @grid;
my @squares;
my $max;
for my $size (1 .. 300) {
    for my $x (1 .. 300 - $size + 1) {
        for my $y (1 .. 300 - $size + 1) {
            if (1 == $size) {
                my $rack_id = $x + 10;
                my $level = ($rack_id * $y + $serial_number) * $rack_id;
                $level =~ s/^.*(.)..$/$1/ or $level = 0;
                $level -= 5;
                $grid[$x][$y] = $squares[$x][$y] = $level;
                $max = [$x, $y, 1, $level] if ! defined $max
                                           || $level > $max->[3];
            } else {
                my $level = sum(
                    $squares[$x][$y],
                    @{ $grid[ $x + $size - 1 ] }[ $y .. $y + $size - 2 ],
                    $grid[ $x + $size - 1 ][ $y + $size - 1 ],
                    map $_->[ $y + $size - 1 ], @grid[ $x .. $x + $size - 2 ] );
                $squares[$x][$y] = $level;
                $max = [$x, $y, $size, $level] if $level > $max->[3];
            }
        }
    }
    warn "@$max";
}

say join ',', @$max[0 .. 2];
code of conduct - report abuse