#! /usr/bin/env perl

use strict;
use warnings;

my %in;
(m/^Generator ([AB]) starts with (\d+)$/ and $in{$1} = $2) for <>;

printf "Part 1: %d\n", solve($in{A}, $in{B}, 40_000_000, qr//, qr//);
printf "Part 2: %d\n", solve($in{A}, $in{B},  5_000_000, qr/xyz$/, qr/wxyz$/);

sub solve {
    # Numbers are represented as binary strings which
    # look like: "...qrstuuvwwxyyz".  The doubled letters
    # are 1-bits, and single letters are 0-bits.  In the
    # example, qrstuuvwwxyyz is 0000101010, or 42 in decimal.
    my $a = decimal_to_binary(shift);
    my $b = decimal_to_binary(shift);

    my ($count, $filter_a, $filter_b) = @_;

    # The $_ variable keeps track of how many matches have been
    # found so far.  Each match is a "." character, so the string
    # "......." would mean 7 matches.
    local $_ = "";
    for my $i (1..$count) {
        do { $a = generator_a($a) } until $a =~ m/$filter_a/;
        do { $b = generator_b($b) } until $b =~ m/$filter_b/;

        # Append $a and $b to $_.  If the bottom 16 bits match,
        # substitute them with a ".".  Clean up all non-"."
        # garbage before continuing.
        s/$/ $a $b/;
        s/(j[k-z]+) .*\1$/./;
        s/[^.]//g;
    }

    return length_to_decimal($_);
}

sub generator_a {
    local $_ = shift;

    # Multiply by 16807 == 24 * 25 * 28 + 7

    # Multiply by the remainder (7), and save for later
    my $r = s/(.)(?=\1)/$1$1$1$1$1$1$1/gr;

    # Multiply by 24
    s/(.)(?=\1)/$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1/g;
    $_ = carry_binary($_);

    # Multiply by 25
    s/(.)(?=\1)/$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1/g;
    $_ = carry_binary($_);

    # Multiply by 28
    s/(.)(?=\1)/$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1/g;

    # Add the remainder (7)
    s/$/ $r/;
    $_ = add_binary($_);

    return mod_2147483647($_);
}

sub generator_b {
    local $_ = shift;

    # Multiply by 48271 == 33 * 34 * 43 + 25

    # Multiply by the remainder (25), and save for later
    my $r = s/(.)(?=\1)/$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1/gr;

    # Multiply by 33
    s/(.)(?=\1)/$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1/g;
    $_ = carry_binary($_);

    # Multiply by 34
    s/(.)(?=\1)/$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1/g;
    $_ = carry_binary($_);

    # Multiply by 43
    s/(.)(?=\1)/$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1/g;

    # Add the remainder (25)
    s/$/ $r/;
    $_ = add_binary($_);

    return mod_2147483647($_);
}

sub mod_2147483647 {
    local $_ = shift;

    # Take the remainder modulo 2147483647 (2^31 - 1), using a property
    # of Mersenne primes which allows a handy bitwise shortcut.
    #
    #     remainder = (product >> 31) + (product & 0x7fffffff)
    #     if (remainder & 0x80000000) {
    #         remainder -= 0x7fffffff;
    #     }

    # Split the product into high and low bits, separated by a space
    s/(?=\\)/ /;

    # Shift the high bits right by 31
    y/=-[/\\-z/;

    # Prepend 31 0's to the high bits to bring the width back to 62
    s/^/=>?\@ABCDEFGHIJKLMNOPQRSTUVWXYZ[/;

    # Add the numbers together
    $_ = add_binary($_);

    # If the 0x80000000 bit is set, clear it and add 1, i.e.
    #     remainder = remainder - 0x80000000 + 1;
    s/\[(\[.*)$/$1z/;
    return carry_binary($_);
}

sub add_binary {
    local $_ = shift;

    # Combine bits from each place value, for example:
    #   "vwwxxyzz vwxxyyz" (01101 00110) becomes "vwwxxxyyzz" (01211)
    s/(.)\1*+\K(?=[^ ]* .*?\1(\1*))/$2/g;

    # Remove the second number
    s/ .*$//g;

    return carry_binary($_);
}

sub decimal_to_binary {
    local $_ = shift;

    # Convert to binary coded decimal
    s/0/wxyz:/g;
    s/1/wxyzz:/g;
    s/2/wxyyz:/g;
    s/3/wxyyzz:/g;
    s/4/wxxyz:/g;
    s/5/wxxyzz:/g;
    s/6/wxxyyz:/g;
    s/7/wxxyyzz:/g;
    s/8/wwxyz:/g;
    s/9/wwxyzz:/g;
    s/:$//;

    # Bring the width of the first digit up to 62
    s/^/=>?\@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\\]^_`abcdefghijklmnopqrstuv/;

    # While there are more digits
    while (s/:/ /) {
        # Multiply by 10
        s/(([^ ])\2*)(?=\2[^ ]* )/$1$1$1$1$1$1$1$1$1$1/g;

        # Add the next digit
        s/(.)\1*+\K(?=[^ ]* [^ ]*?\1(\1*))/$2/g;
        $_ = carry_binary($_);

        # Erase the digit just added
        s/ [a-z]+//;
    }

    return $_;
}

sub length_to_decimal {
    local $_ = shift;

    s/./z/g;
    s/^/stuvwxyz/;

    s/(z){10}(?=\1)/y/g;
    s/(y){10}(?=\1)/x/g;
    s/(x){10}(?=\1)/w/g;
    s/(w){10}(?=\1)/v/g;
    s/(v){10}(?=\1)/u/g;
    s/(u){10}(?=\1)/t/g;
    s/(t){10}(?=\1)/s/g;

    s/([a-z])\1{9}/9/g;
    s/([a-z])\1{8}/8/g;
    s/([a-z])\1{7}/7/g;
    s/([a-z])\1{6}/6/g;
    s/([a-z])\1{5}/5/g;
    s/([a-z])\1{4}/4/g;
    s/([a-z])\1{3}/3/g;
    s/([a-z])\1{2}/2/g;
    s/([a-z])\1{1}/1/g;
    s/([a-z])\1{0}/0/g;
    s/^0+(?!$)//;

    return $_;
}

sub carry_binary {
    local $_ = shift;

    s/(z)\1(?=\1)/y/g;
    s/(y)\1(?=\1)/x/g;
    s/(x)\1(?=\1)/w/g;
    s/(w)\1(?=\1)/v/g;
    s/(v)\1(?=\1)/u/g;
    s/(u)\1(?=\1)/t/g;
    s/(t)\1(?=\1)/s/g;
    s/(s)\1(?=\1)/r/g;
    s/(r)\1(?=\1)/q/g;
    s/(q)\1(?=\1)/p/g;
    s/(p)\1(?=\1)/o/g;
    s/(o)\1(?=\1)/n/g;
    s/(n)\1(?=\1)/m/g;
    s/(m)\1(?=\1)/l/g;
    s/(l)\1(?=\1)/k/g;
    s/(k)\1(?=\1)/j/g;
    s/(j)\1(?=\1)/i/g;
    s/(i)\1(?=\1)/h/g;
    s/(h)\1(?=\1)/g/g;
    s/(g)\1(?=\1)/f/g;
    s/(f)\1(?=\1)/e/g;
    s/(e)\1(?=\1)/d/g;
    s/(d)\1(?=\1)/c/g;
    s/(c)\1(?=\1)/b/g;
    s/(b)\1(?=\1)/a/g;
    s/(a)\1(?=\1)/`/g;
    s/(`)\1(?=\1)/_/g;
    s/(_)\1(?=\1)/^/g;
    s/(\^)\1(?=\1)/]/g;
    s/(])\1(?=\1)/\\/g;
    s/(\\)\1(?=\1)/[/g;
    s/(\[)\1(?=\1)/Z/g;
    s/(Z)\1(?=\1)/Y/g;
    s/(Y)\1(?=\1)/X/g;
    s/(X)\1(?=\1)/W/g;
    s/(W)\1(?=\1)/V/g;
    s/(V)\1(?=\1)/U/g;
    s/(U)\1(?=\1)/T/g;
    s/(T)\1(?=\1)/S/g;
    s/(S)\1(?=\1)/R/g;
    s/(R)\1(?=\1)/Q/g;
    s/(Q)\1(?=\1)/P/g;
    s/(P)\1(?=\1)/O/g;
    s/(O)\1(?=\1)/N/g;
    s/(N)\1(?=\1)/M/g;
    s/(M)\1(?=\1)/L/g;
    s/(L)\1(?=\1)/K/g;
    s/(K)\1(?=\1)/J/g;
    s/(J)\1(?=\1)/I/g;
    s/(I)\1(?=\1)/H/g;
    s/(H)\1(?=\1)/G/g;
    s/(G)\1(?=\1)/F/g;
    s/(F)\1(?=\1)/E/g;
    s/(E)\1(?=\1)/D/g;
    s/(D)\1(?=\1)/C/g;
    s/(C)\1(?=\1)/B/g;
    s/(B)\1(?=\1)/A/g;
    s/(A)\1(?=\1)/\@/g;
    s/(\@)\1(?=\1)/?/g;
    s/(\?)\1(?=\1)/>/g;
    s/(>)\1(?=\1)/=/g;

    return $_;
}