Advertisement
mscha

Project Euler 104

Jan 16th, 2017
540
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Perl 6 1.98 KB | None | 0 0
  1. #!/usr/bin/env perl6
  2.  
  3. use v6.c;
  4.  
  5. # Solution for Project Euler problem 104 https://projecteuler.net/problem=104
  6.  
  7. sub MAIN(Int $digits where 1..9 = 9, Bool :v(:$verbose) = False)
  8. {
  9.     # Store all permutations of 1..$digits in a set for easy checking
  10.     say "Creating set of permutations of 1..$digits ..." if $verbose;
  11.     my $pan = set (1..$digits).permutations.map(+*.join);
  12.  
  13.     say "Starting..." if $verbose;
  14.     my $mod = 10**$digits;          # For checking right-pandigital
  15.     my $max = 10**($digits+5);      # For left-pandigital (5 extra for rounding)
  16.     my $lfibo = 0;                  # Left digits of Fibonacci sequence
  17.     my $lfibo-next = 1;
  18.     my $rfibo = 0;                  # Right digits of Fibonacci sequence
  19.     my $rfibo-next = 1;
  20.     my $extra-digits = 0;           # Remember how many digits we cut off
  21.     for 1..* -> $k {
  22.         # Iterate left fibonacci Sequence.  Divide both numbers by 10
  23.         # when the get too big. (Keep 5 digits extra to prevent rounding issues.)
  24.         ($lfibo, $lfibo-next) = ($lfibo-next, $lfibo+$lfibo-next);
  25.         if $lfibo > $max {
  26.             $lfibo = ($lfibo + 5) div 10;
  27.             $lfibo-next = ($lfibo-next + 5) div 10;
  28.             $extra-digits++;
  29.         }
  30.  
  31.         # Iterate right Fibonacci sequence.  This one can simply use modulo.
  32.         ($rfibo, $rfibo-next) = ($rfibo-next, ($rfibo+$rfibo-next) % $mod);
  33.  
  34.         # First, check if right-pandigital
  35.         if $rfibo$pan {
  36.             say "$k: right-pandigital" if $verbose;
  37.  
  38.             # Then, check if left-pandigital
  39.             if +$lfibo.substr(0,$digits)$pan {
  40.                 # We have a winner!
  41.                 say '' if $verbose;
  42.                 say "$lfibo...$rfibo" if $verbose;
  43.                 say '' if $verbose;
  44.                 say "Fibonacci number {$k} (length {$lfibo.chars+$extra-digits}) ",
  45.                     "is the first that is left and right {$digits}-pandigital.";
  46.                 last;
  47.             }
  48.         }
  49.     }
  50. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement