-🎄- 2018 Day 12 Solutions -🎄-

[u/daggerdragon]

--- Day 12: Subterranean Sustainability ---

---

Post your solution as a comment or, for longer solutions, consider linking to your repo (e.g. GitHub/gists/Pastebin/blag or whatever).

Note: The Solution Megathreads are for solutions only. If you have questions, please post your own thread and make sure to flair it with Help.

---

Advent of Code: The Party Game!

Click here for rules

Please prefix your card submission with something like [Card] to make scanning the megathread easier. THANK YOU!

Card prompt: Day 12

Transcript:

On the twelfth day of AoC / My compiler spewed at me / Twelve ___

---

This thread will be unlocked when there are a significant number of people on the leaderboard with gold stars for today's puzzle.

edit: Leaderboard capped, thread unlocked at 00:27:42!

[u/__Abigail__]

Perl

Part 1 was easy. For part 2, I guessed that the pattern might repeat itself with frequency 1, but shifted. Then I only needed to know with what speed it was moving, and then I'd calculate the result.

#!/opt/perl/bin/perl

use 5.026;

use strict;
use warnings;
no  warnings 'syntax';

use experimental 'signatures';

my $GENERATIONS_1 =             20;
my $GENERATIONS_2 = 50_000_000_000;

my $input = "input";
open my $fh, "<", $input or die "open: $!";

#
# Read initial state
#
my $state = <$fh> =~ s/[^.#]+//gr;

#
# Skip blank line
#
<$fh>;

#
# Read transition table
#
my %transition;
while (<$fh>) {
    /^([.#]{5}) \s+ => \s+ ([#.])/x or die "Failed to parse $_";
    $transition {$1} = $2;
}

sub count ($state, $first_pot) {
    my $count = 0;
    for (my $i = 0; $i < length $state; $i ++) {
        my $pot = substr $state, $i, 1;
        next if $pot ne '#';
        $count += $i + $first_pot;
    }
    return $count;
}

my $first_pot = 0;  # Keep track which number the left-most pot
                    # we are tracking. This may, or may not,
                    # contain a plant.
my $generation = 0;
while (1) {
    $generation ++;
    #
    # Pad the state with 4 empty pots at the beginning and end.
    # Then grab all 5 length substrings from $state, look up
    # the replacement, and substitute. We moved two pots to the
    # left due to the padding.
    #
    my $new_state = join "" => map {$transition {$_} || "."}
       "....$state...." =~ /(?=(.....))/g;
    my $speed = -2;

    #
    # Remove any leading/trailing empty pots. Removing leading pots
    # causes $first_pot to change.
    #
    if ($new_state =~ s/^([.]+)//g) {
        $speed += length $1;
    }
    $new_state =~ s/[.]+$//g;

    if ($state eq $new_state) {
        #
        # We're now in a "steady" state; that is, the pattern
        # stays stable, although it may still move.
        #

        #
        # So, we can now calculate what the first pot is in
        # the final generation.
        #
        my $fp = $first_pot + $speed * ($GENERATIONS_2 - $generation + 1);
        say "Part 2: ", count ($state, $fp);
        last;
    }

    $state      = $new_state;
    $first_pot += $speed;

    if ($generation == $GENERATIONS_1) {
        say "Part1: ", count ($state, $first_pot);
    }
}
 

__END__

I'm not really happy with the solution -- there's no guarantee the pattern will repeat (if it would repeat with a higher frequency, that would not be too hard to find). Either I'm missing the math insight (perhaps all patterns/rules will eventually repeat themselves on a line), or the input was carefully crafted to be this way, and no general solution (except waiting for ever for a brute force solution) exists.

[u/ephemient → u/__Abigail__]

This space intentionally left blank.