tiz_jegyu_kulonbozo_szamu_oszto_szamparok_szamossaga.pl

#! /usr/bin/perl

=pod
    Hany olyan a, b szampar van amelyikre igaz?
    - a es b tizjegyu,
    - minden szamjegybol pontosan egyet tartalmazo szam,
    - es b/a > 1 egesz. Vagyis a osztoja b-nek.

    Pl.: 9 876 543 120 / 1 234 567 890 = 8
    a) 1 - 10 db
    b) 11 - 100 db
    c) 101 - 1 000 db
    d) 1 001 - 10 000 db
    e) >10 000 db
=cut

# 1: kigyujtes
# 2: ellenorzes
# kicsit memoria igenyes. 1.2GB RAM nem art hozza.
# ha optimalizaljuk 1-5 -el kezdodo szamokra, eleg 580 MB is.

my $debug_level = 0;

my %list = [];
my $db;
my $limit = 9876543210;
my $sum = 0;
foreach (0 .. 9) { $sum += $_; };

# fuggveny: ellenorizi, hogy a bemeneti szam szamjegyei mind kulonbozoek-e
sub haveDifferentNumbers($)
{
  my @a = (split('', $_[0]));
  for (my $x = 0; $x <= $#a; $x++)
  {
    for (my $y = $x + 1; $y <= $#a; $y++)
    {
      return 0 if $a[$x] == $a[$y];
    }
  }
  return 1;
}

#===== kulonbozo szamokbol allo, 10 szamjegyu szamok legyartasa =====
#
# mennyi valtozo kell majd?
# 0123456789
# abcdefghij

# azert eleg 4-ig menni, mert 498... *2 a legnagyobb szam, amit beleszamithatunk a feladatba
my $opt_max = 4;
foreach my $a (1 .. $opt_max)
{
  foreach my $b (0 .. 9)
  {
    next if ($b == $a);
    foreach my $c (0 .. 9)
    {
      next if ($c == $a || $c == $b);
      foreach my $d (0 .. 9)
      {
        next if ($d == $a || $d == $b || $d == $c);
        foreach my $e (0 .. 9)
        {
          next if ($e == $a || $e == $b || $e == $c || $e == $d);
          foreach my $f (0 .. 9)
          {
            next if ($f == $a || $f == $b || $f == $c || $f == $d || $f == $e);
            foreach my $g (0 .. 9)
            {
              next if ($g == $a || $g == $b || $g == $c || $g == $d || $g == $e || $g == $f );
              foreach my $h (0 .. 9)
              {
                next if ($h == $a || $h == $b || $h == $c || $h == $d || $h == $e || $h == $f || $h == $g);
                foreach my $i (0 .. 9)
                {
                  next if ($i == $a || $i == $b || $i == $c || $i == $d || $i == $e || $i == $f || $i == $g || $i == $h);
                  foreach my $i (0 .. 9)
                  {
                    next if ($i == $a || $i == $b || $i == $c || $i == $d || $i == $e || $i == $f || $i == $g || $i == $h);

                    foreach my $j (0 .. 9)
                    {
                      next if ($j == $a || $j == $b || $j == $c || $j == $d || $j == $e || $j == $f || $j == $g || $j == $h || $j == $i);

                      # szamok redundanci mentes tarolasa asszociativ tomb kulcskent
                      $list{$a.$b.$c.$d.$e.$f.$g.$h.$i.$j} = '' if $a+$b+$c+$d+$e+$f+$g+$h+$i+$j == $sum;

                      if ($debug_level > 1)
                      {
                        print $a.$b.$c.$d.$e.$f.$g.$h.$i.$j."\n" unless $#list > 10;
                      }
                    }
                  }
                }
              }
            }
          }
        }
      }
    }
  }
}

print "Legfeljebb $opt_max-vel kezdodo 10 jegyu szamok osszessege: ". scalar(keys(%list)) . "\n";

my %res = [];
$db = 0;

# szorzando $n
foreach my $a (sort(keys(%list)))
{
  # szorzo tenyezo $mul
  # 2es a legkisebb szorzo tenyezo
  # 9esnel nincs ertelme nagyobbanak, mert b = mul * n hosszabb lesz, mint 10 szamjegy.

  foreach my $mul (2 .. 9)
  {
    # a szorzat $a * $mul = $b (lasd feladat leirasban 'a' es 'b' szamok)
    my $b = $a * $mul;

    # 10 szamjegyunel nagyobb szorzatok kihagyasa
    last if (length($b) != 10);

    # nem kulonbozo szamjegyuek kihagyasa
    next unless (haveDifferentNumbers($b));

    # eredmeny redundancia-mentes tarolasa
    $res{"$a * $mul = $b"} = '';

    # szamlalo novelese
    $db ++;

    if ($debug_level > 0)
    {
      print "-->$a * $mul = ".($b)."\n" if $db < 20; # debug miatt jo
      if ($debug_level > 1)
      {
        print "$db\n" if ($db % 1000 == 0);
      }
    }

    # ha egy szamot csak egyszer szamolunk bele es nem nezzuk mas tenyezokkel valo szorzatat, akkor a kov. sor uncomment!
    # next;
  }
}

# print "ennyi szampart talaltam: $db\n";
print "ennyi szampart talaltam: ". scalar(keys(%res)) . "\n";

if ($debug_level > 0)
{
  my $max = 10;
  foreach (sort(keys(%res)))
  {
    print "$_\n";
    last unless (--$max);
  }
}

# free memory
%list = undef;
%res = undef;

=pod
    Kimenet:

    Legfeljebb 4-vel kezdodo 10 jegyu szamok osszessege: 1451521
    ennyi szampart talaltam: 244424
=cut