use strict;
use warnings;

my $digits = 5;
my %cache;

# Keep digits in a shift map - 3 places per digit.
my @digitmap;
$digitmap[$_] = 1 << ($_ * 3) for (0..9);

my @starter;
my $min = 1 . (0 x ($digits-1));
my $max = 9 x $digits;
for (0..8) {
   $starter[($_+1) % 9] = $min + $_;
}

# Cache all the digit combinations we will need.
init_cache(0);
init_cache(2);
init_cache(3);
init_cache(5);
init_cache(6);
init_cache(8);

find_vampires(0,0);
find_vampires(2,2);
find_vampires(3,6);
find_vampires(5,8);
find_vampires(6,3);
find_vampires(8,5);

sub init_cache {
  my $i = shift;
  my ($a, $a_digits);
  for ($a = $starter[$i]; $a <= $max; $a += 9) {
     $a_digits = 0;
     $a_digits += $digitmap[$_] for (split //,$a);
     $cache{$a} = $a_digits;
  }
}

sub find_vampires {
   my ($i, $j) = @_;
   my ($a, $b, $a_digits, $b_digits, $prod_digits);
   for ($a = $starter[$i]; $a <= $max; $a += 9) {
      $a_digits =  $cache{$a};
      for ($b = $starter[$j]; $b <= $a; $b += 9) {
	  $b_digits =  $cache{$b};

          my $prod = $a * $b;
          $prod_digits = 0;
          $prod_digits += $digitmap[$_] for (split //,$prod);
          if ($prod_digits == ($a_digits + $b_digits)) {
              print "$a * $b = $prod\n";
          }
      }
   }
}