#!/usr/bin/env perl6

use v6.c;

# Solution for Project Euler problem 104 https://projecteuler.net/problem=104

sub MAIN(Int $digits where 1..9 = 9, Bool :v(:$verbose) = False)
{
    # Store all permutations of 1..$digits in a set for easy checking
    say "Creating set of permutations of 1..$digits ..." if $verbose;
    my $pan = set (1..$digits).permutations.map(+*.join);

    say "Starting..." if $verbose;
    my $mod = 10**$digits;          # For checking right-pandigital
    my $max = 10**($digits+5);      # For left-pandigital (5 extra for rounding)
    my $lfibo = 0;                  # Left digits of Fibonacci sequence
    my $lfibo-next = 1;
    my $rfibo = 0;                  # Right digits of Fibonacci sequence
    my $rfibo-next = 1;
    my $extra-digits = 0;           # Remember how many digits we cut off
    for 1..* -> $k {
        # Iterate left fibonacci Sequence.  Divide both numbers by 10
        # when the get too big. (Keep 5 digits extra to prevent rounding issues.)
        ($lfibo, $lfibo-next) = ($lfibo-next, $lfibo+$lfibo-next);
        if $lfibo > $max {
            $lfibo = ($lfibo + 5) div 10;
            $lfibo-next = ($lfibo-next + 5) div 10;
            $extra-digits++;
        }

        # Iterate right Fibonacci sequence.  This one can simply use modulo.
        ($rfibo, $rfibo-next) = ($rfibo-next, ($rfibo+$rfibo-next) % $mod);

        # First, check if right-pandigital
        if $rfibo ∈ $pan {
            say "$k: right-pandigital" if $verbose;

            # Then, check if left-pandigital
            if +$lfibo.substr(0,$digits) ∈ $pan {
                # We have a winner!
                say '' if $verbose;
                say "$lfibo...$rfibo" if $verbose;
                say '' if $verbose;
                say "Fibonacci number {$k} (length {$lfibo.chars+$extra-digits}) ",
                    "is the first that is left and right {$digits}-pandigital.";
                last;
            }
        }
    }
}