[QUIZ#15] Enumerator (Perl)


Enumerator

Mitglied Kamel
#1
50 Zeilen BruteForce: Beim Schreiben und in der Ausführung.. :p

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:

Perl:
#!/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
 

Anhänge

Enumerator

Mitglied Kamel
#2
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:
Code:
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:
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
 

Anhänge

Zuletzt bearbeitet: