[QUIZ#15] Enumerator (Perl)

[Enumerator]

50 Zeilen BruteForce: Beim Schreiben und in der Ausführung..

Das Skript probiert einfach alle möglichen Kombinationen aus - 2 "hoch" der-Anzahl-der-Sweeties-die-nicht-schon-allein-über-das-Maximum-hinaus-schießen ergibt die Anzahl der möglichen Kombinationen - diese werden in einer Schleife abgezählt. In jeder Iteration repräsentiert das Bitmuster der Zahl die aktuelle Kombi zum Testen, ein wenig Shiften und schon kann man mit den Werten arbeiten:

#!/usr/bin/perl -w
use strict;

sub usage {
    print STDERR <<'EOT;';
Na, da stimmt wohl was mit der Eingabe nicht! Schau mal hier:
tutorials.de/forum/diskussion/357969-quiz-15-lisas-osternest.html
EOT;
    exit -1;
}

my($max, @sweeties, %best, $i, $j, $k) = ();

# Input
$max = int <STDIN> or &usage;
while(1) {
    my $name = <STDIN>;
    last unless $name;
    chomp $name;
    last if $name =~ /^\s*$/ and @sweeties;
    &usage unless $name =~ s/^\s*(.+?)\s*$/$1/;
    my $data = <STDIN>;
    &usage unless $data =~ /^\s*([0-9]+)\s+([0-9]+)\s$/;
    next if $1 > $max;
    push @sweeties, { name => $name, g => $1, kcal => $2 };
}
&usage unless @sweeties;

# Process
%best = (%{ $sweeties[0] }, no => 1 );
CANDIDATE:
for($i = 2; $i != 2 ** @sweeties; ++$i) {
    my($g, $kcal) = (0, 0);
    for(($j, $k) = ($i, 0); 0 != $j; $j >>= 1, ++$k) {
        next unless $j & 1;
        next CANDIDATE if ($g + $sweeties[$k]{g}) > $max;
        $g += $sweeties[$k]{g};
        $kcal += $sweeties[$k]{kcal};
    }
    %best = ( no => $i, g => $g, kcal => $kcal )
        if $kcal > $best{kcal} or ($kcal == $best{kcal} and $g < $best{g});
}

# Output
print "Optimale Auswahl: ";
for(($j, $k) = ($best{no}, 0); 0 != $j; $j >>= 1, ++$k) {
    print $sweeties[$k]{name}, 1 == $j? "\n": ", " if $j & 1;
}
print "Masse: ", $best{g}, " g\n",
      "Nährwert: ", $best{kcal}, " kcal\n";

Mal schauen ob ich noch Zeit und Muße finde, mir schwirren da schon ein paar Optimierungen durch den Kopf...
Bis dahin -

Gruß
Enum

 

[Enumerator]

Soo, nachdem ich durch die in der Diskussion genannten Zeiten angespornt wurde hab' ich die angekündigten Optimierungen vorgenommen - eigentlich hab' ich nicht viel von der alten Version übrig gelassen...
Anstelle jede mögliche Kombination abzuarbeiten, nutze ich jetzt die Ergebnisse vorheriger Berechnungen. Ob das nun generische Programmierung ist oder nicht weiß ich nicht, aber es funktioniert und ist halbwegs performant:

lenny:~/oster-quiz$ time ./lisa.pl < 100leckereien.txt; echo 
Optimale Auswahl: Vollmilch-Eierlikör-Schokohase, Joghurt-Trüffel-Krokant-Goldhase, Trüffel-Butter-Eierlikör-Ostereier
Gewicht: 494
Nährwert: 3393 kcal

real    0m42.242s
user    0m39.786s
sys     0m0.660s

lenny:~/oster-quiz$ time ./lisa.pl < 50leckereien.txt; echo 
Optimale Auswahl: Waffel-Joghurthase, Marzipan-Vollmilch-Goldeier, Vollmilch-Krokant-Waffelhase
Gewicht: 494
Nährwert: 3392 kcal

real    0m2.379s
user    0m2.332s
sys     0m0.036s

lenny:~/oster-quiz$

Hier die überarbeitete Version in Perl:

#!/usr/bin/perl -w
no warnings "recursion";
use strict;

my($MAX, @BEST, @SWEETIES, @RESULT) = (
    (int <STDIN> or &usage), { n => ["dummy"], g => 0, c => 0, x => 0 }
);

sub usage {
    print STDERR <<'EOT;';
Na, da stimmt wohl was mit der Eingabe nicht! Schau mal hier:
tutorials.de/forum/diskussion/357969-quiz-15-lisas-osternest.html
EOT;
    exit -1;
}

sub candidate {
    if($BEST[0]{c} < $_[0]{c}) {
        @BEST = @_;
    } elsif($BEST[0]{c} == $_[0]{c}) {
#       if($BEST[0]{g} > $_[0]{g}) {
#           @BEST = @_;
#       } elsif($BEST[0]{g} == $_[0]{g}) {
            push @BEST, @_;
#       }
    }
}

sub calculate {
    my($first, @result, $g, @combis) = ();
    if($first = shift(@_)) {
        for(@combis = calculate(@_)) {
            if(($g = $_->{g} + $first->{g}) <= $MAX) {
                push @result,
                     {
                         x => [ @{$first->{x}}, @{$_->{x}} ],
                         g => $g,
                         c => $first->{c} + $_->{c}
                     };
            }
        }
        push @result, $first, @combis;
    }
    return @result;
}

while(<>) {
    s/\s*$//; # chomp is nich weil CR/LF. blöd.
    <> =~ /^([0-9]+)\s+([0-9]+)/;
    next if $1 > $MAX;
    push @SWEETIES,
    {
        n => $_,
        g => $1,
        c => $2,
        x => [scalar @SWEETIES]
    };
}
usage unless 1 < @SWEETIES;
for(calculate(@SWEETIES)) {
    candidate $_;
}
print "Optimale Auswahl: ", $SWEETIES[shift @{$BEST[0]{x}}]{n};
while($_ = shift @{$BEST[0]{x}}) {
    print ", ", $SWEETIES[$_]{n};
}
print "\nGewicht: ", $BEST[0]{g}, "\nNährwert: ", $BEST[0]{c}, " kcal\n";

__END__

Da mich die Zeiten von OnlyFoo allerdings sehr beeindruckt hatten, hab' ich den Code noch in C übersetzt...

Gruß
Enum