Die Rache des Biermanns (Linux-Magazin, Oktober 1999)

Weil's so schön war -- noch eine mathematische Spielerei, die sich mit einem Perl-Skript knacken läßt.

Mein Biermann um die Ecke ist ein ehemaliger Software-Ingenieur, der seinen Job hingeschmissen und einen Liquor-Store eröffnet hat ([1]). Als ich neulich Bier kaufte und, wie es in Amerika so Sitte ist, mit ihm ein Schwätzchen hielt, erzählte ich ihm die Aufgabe mit den Ziegen ([2]). Daraufhin revanchierte er sich mit einer Aufgabe aus seinem Repertoire:

In einem Laden steht eine Balkenwaage mit vier Gewichten, mit denen sich tatsächlich Waren von 1, 2, 3, ... 40 Gramm aufs Gramm genau abwiegen lassen. Wie sind die Gewichte beschaffen? Hätte man zum Beispiel zwei Gewichte von je einem Gramm und zwei weitere von je drei Gramm, könnte man damit Waren von 1, 2, 3, 4, 5, 6, 7 und 8 Gramm abwiegen, denn man kann die Gewichte auf beiden Seiten der Waage zusammen mit der Ware plazieren. Eine zwei Gramm schwere Ware kann man dann zum Beispiel abwiegen, indem man auf der einen Seite der Balkenwage ein 3-er Gewicht legt und auf die andere Seite die Ware mitsamt dem 1-er Gewicht. Wiegt die Ware genau 2 Gramm, pendelt sich die Balkenwaage in der Mitte ein. Nun die Frage -- welche vier Gewichte braucht's, damit man nicht nur von 1 bis 8 Gramm, sondern von 1 bis 40 Gramm alles abwiegen kann?

Schwierige Sache

Schwierige Sache. Wie wär's mit einem Perlskript, das alle Möglichkeiten durchprobiert? Wir fangen einfach mit vier Einer-Gewichten an, sehen, wie die sich kombinieren lassen, dann geht's weiter mit drei Einern und einem Zweier, und so weiter, bis wir vier Vierziger-Gewichte haben und damit garantiert weit übers Ziel hinausgeschossen und am Ende aller Möglichkeiten sind:

    1, 1, 1, 1
    1, 1, 1, 2
   ...
    1, 1,40, 1 
   ...
    1,40, 1, 1
   ...
   40,40,40,40

Auf der Suche nach einem Algorithmus, um diese Folge zu erzeugen, hilft folgende Darstellung:

    0 0 0
    0 0 1
    0 1 0
    0 1 1
    1 0 0
    1 0 1
    1 1 0
    1 1 1

Das sind die Zahlen von 0 bis 7 im Binärsystem, deren Ziffern alle Kombinationen von Nullen und Einsen durchprobieren. Die Kombination für die Gewichte oben läßt sich also ganz einfach erzeugen, indem man im 40er-Zahlen-System von 0 bis 404-1 zählt -- 2.560.000 verschiedene Kombinationen.

Objektorientierte Kombinationen

Listing weights.pl zeigt ab Zeile 40 die Implementierung der Combine-Klasse, deren Konstruktor zwei Werte erwartet: $n, die Zahl der unterschiedlichen Zeichen im gewählten Zahlensystem (z.B. 2 im Binärsystem) und $k, die Anzahl der Stellen, also die Länge der Ergebnistupel. Kombinatorisch gesehen ist $n die Anzahl verschiedener Kugeln in einer Urne, und $k die Anzahl der Kugeln, die man pro Durchgang mit (!) Zurücklegen zieht. Die Ergebnistupel zeigen alle verschiedenen Möglichkeiten an, wie das Experiment ausgehen kann. Die next-Methode eines Objekts der Klasse Combine liefert mit jedem neuen Aufruf einen anderen Ergebnistupel -- bis sie alle durchgetrieben wurden. Alle dreistelligen Zahlen im 2-er-System, wie oben angegeben, gibt also folgender Perl-Code aus:

    my $comb = Combine->new(2, 3);
    while(@tuple = $comb->next()) {
        print "@tuple\n";
    }

weights.pl definiert in den Zeilen 3-5 die Konstanten für die Anzahl der erlaubten Gewichte ($NOF_WEIGHTS), die Anzahl der Gewichtsunterschiede ($NOF_DIFFS), die durch Kombinieren der Gewichte erzeugt werden sollen und schließlich mit $MAX_WEIGHT die größte erlaubte Masse eines einzelnen Gewichtes. Zeile 7 erzeugt das Kombinations-Objekt und die while-Schleife ab Zeile 10 iteriert über alle Kombinationen. Der Kombinationsalgorithmus liefert Tupel von 0,0,0,0 bis 39,39,39,39, aber da 1,1,1,1 bis 40,40,40,40 für Gewichte realistischer ist, zählt Zeile 11 zu jedem Tupel-Element flugs Eins dazu. Die in Zeile 12 aufgerufene Funktion calc_diffs errechnet die Anzahl der mit einem gegebenen Tupel erreichbaren Gewichtsverteilungen. Wenn die Zahl 40 zurückkommt, ist das Ziel erreicht, alle Gewichte von 1 bis 40 können simuliert werden und Zeile 17 bricht die Schleife und damit das Skript ab. In der Variablen $best steht immer der bis dato beste erreichte Wert. Jedesmal, wenn sich etwas verbessert, gibt Zeile 14 den untersuchten Tupel und die Anzahl der möglichen Kombinationen aus.

Zahlenwerte in der N-Welt

Wie errechnet man nun die verschiedenen Wäge-Kombinationen aus einem Gewichte-Tupel? Für jedes Element eines Tupels, also für jedes Gewicht, gibt es drei Möglichkeiten: Es bleibt entweder außen vor oder steht entweder links oder rechts auf der Waage. Wenn man diese drei Zustände als 0 , 1 und 2 markiert, gibt es die folgenden Möglichkeiten, die Gewichte über die Waage zu verteilen und so Gewichtsdifferenzen zu erzeugen, die man zum abwiegen der Waren nutzen kann:

    0 0 0 0
    0 0 0 1
    0 0 0 2
    0 0 1 0
    ...
    2 2 2 2

Die Folge beginnt mit dem Null-Tupel (kein Gewicht auf der Waage), beim zweiten Tupel liegt das vierte Gewicht auf der linken Seite der Waage, beim dritten auf der rechten. Beim vierten liegt das dritte Gewicht auf der linken Seite, und so weiter, bis schließlich im letzten Tupel alle Gewichte auf der rechten Seite der Waage liegen.

Die mit jeder Kombination erreichte Gewichtsdifferenz zwischen linker und rechter Seite der Waage errechnet sich einfach aus der mit 0 , -1 oder 1 gewichteten Summe der Einzelgewichte, je nachdem ob das jeweilige Gewicht der Waage fernblieb, oder auf der linken oder der rechten Seite der Waage zu liegen kam. Die ab Zeile 20 definierte Funktion calc_diff nimmt einen Gewichtstupel als Array mit vier Elementen entgegen und erzeugt das oben erläuterte Wägeraster -- natürlich wieder mit einem Objekt vom Typ Combine, diesmal mit einem Wert von 3 für $n (drei Zustände: nicht auf der Waage, links oder rechts) und 4 für $k (weil's 4er-Tupel sind).

Die while-Schleife ab Zeile 26 iteriert dann über die Wägeverteilungen und die foreach-Schleife ab Zeile 29 errechnet für jede Gewichtekombination die Wägedifferenz in $diff.

Der Hash %diffs in Zeile 34 erhält für jede geschaffene Gewichtsdifferenz einen neuen Eintrag, die abs-Funktion sorgt dafür, daß positive und negative Differenzen nur je einmal zählen, schließlich spielt es keine Rolle, ob die Balkenwaage nach links oder rechts ausschlägt, allein das Differenzgewicht zählt, das man zum Abwiegen von Waren nutzen kann.

Zeile 36 gibt die Anzahl der Einträge im Hash zurück -- die Anzahl der mit der aktuellen Gewichteauswahl und -verteilung erreichbaren Wiegedifferenzen.

Von Zahlen und Tupeln

Die Klasse Combine, deren next-Methode alle möglichen Verteilungen der Reihe nach hervorzaubert, ist ab Zeile 40 definiert. So wie bei einer Dezimalzahl die rechteste Ziffer mit 1, die zweitrechteste mit 10, die drittrechteste mit 100 usw. gewichtet ist, sodaß 123 = 1*102 + 2*101 + 3*100, also 1*100 + 2*10 + 3*1 ist, läßt sich eine dreistellige Zahl abc im n-System als a*n2 + b*n1 + c*n0 darstellen.

Für die acht Zahlen 0 bis 7 im Zweiersystem mit dreiziffrigen Zahlen gilt beispielsweise:

                          Gewicht:   4 2 1
    
    0 = 0*4 + 0*2 + 0*1              0 0 0
    1 = 0*4 + 0*2 + 1*1              0 0 1
    2 = 0*4 + 1*2 + 0*1              0 1 0
    ...                              ...
    7 = 1*4 + 1*2 + 1*1              1 1 1

Nach diesem System ermittelt der Konstruktor der Combine-Klasse einen Array mit Faktoren, um die einzelnen Stellen der Zahlen im n-System zu multiplizieren: Der map-Befehl in Zeile 49 transformiert den Array mit den Zahlen von 0 bis $k-1 in (1, ..., $n$k-2, $n$k-1), was für $n=2 und $k=3 als (1,2,4) herauskommt. Die reverse-Funktion dreht den Array um, macht also (4,2,1) daraus. Zeile 48 legt eine Referenz auf diesen Array in der Instanzvariable weights des Combine-Objekts ab. Zwei weitere Instanzvariablen führt ein Combine-Objekt: total, die Anzahl der insgesamt möglichen Kombinationen, und count, einen Zähler, der bei 0 startet und bei jedem Aufruf der next-Methode um eins erhöht wird. Jeder Stand von count wird in eine Zahl im n-System verwandelt.

Falls die next-Methode in Zeile 60 feststellt, daß der Zählerstand bereits gleich der maximal möglichen Anzahl von Kombinationen ist, liefert sie statt einem neuen n-Tupel einfach einen leeren Array zurück und signalisiert so dem Aufrufer, daß keine weiteren Kombinationen mehr nachkommen.

Die foreach-Schleife ab Zeile 62 iteriert über den Array der Gewichtungen und findet den Wert jeder einzelnen Ziffer von count im n-System heraus, indem es $count jeweils durch das Gewicht an der entsprechenden Stelle ($weight) teilt und das Ergebnis mit der int-Funktion auf ganze Zahlen abrundet. Zeile 64 hängt die ermittelte Ziffer an den @result-Array an und Zeile 65 präpariert den verbleibenden Wert der darzustellenden Zahl.

Zeile 68 zählt den internen Zähler count für den nächsten Aufruf der next-Methode um eins hoch, bevor Zeile 70 die Ergebniszahl im n-System als Array an den Aufrufer der next-Methode zurückgibt.

Vorsicht, Spoiler, das Ergebnis!

Nachdem ich mich schon darauf eingestellt hatte, den Rechner über Nacht laufen zu lassen, war ich nicht schlecht erstaunt, als das Skript schon nach 38 Sekunden mit dem Ergebnis abbrach -- der Spannung halber wird's hier nicht abgedruckt, wer will, kann es auf http://perlmeister.com/weights.html nachlesen. Nur soviel: Man kommt sich ganz schön doof vor, weil man nicht gleich draufgekommen ist. Der Biermann staunte jedenfalls nicht schlecht.

Listing weights.pl

    01 #!/usr/bin/perl -w
    02 
    03 my $NOF_WEIGHTS =  4;
    04 my $NOF_DIFFS   = 40;
    05 my $MAX_WEIGHT  = 40;
    06 
    07 my $comb = Combine->new($MAX_WEIGHT, $NOF_WEIGHTS);
    08 my $best = 0;
    09 
    10 while(my @onecomb = $comb->next()) {
    11     @onecomb = map { $_ + 1 } @onecomb;
    12     my $diffs = calc_diffs(@onecomb);
    13     if($diffs > $best) {
    14         print join(',', @onecomb), " ($diffs)\n";
    15         $best = $diffs;
    16     }
    17     last if $diffs == $NOF_DIFFS;
    18 }
    19 
    20 sub calc_diffs {
    21     my @weights = @_;
    22     my %diffs   = ();
    23 
    24     my $scalecomb = Combine->new(3, $NOF_WEIGHTS);
    25 
    26     while(my @scale = $scalecomb->next()) {
    27         my $diff = 0;
    28         my $i    = 0;
    29         foreach my $scaleloc (@scale) {
    30             $diff += $weights[$i] if $scaleloc == 1;
    31             $diff -= $weights[$i] if $scaleloc == 2;
    32             $i++;
    33         }
    34         $diffs{abs($diff)}++ if $diff; 
    35     }
    36     return scalar keys %diffs;
    37 }
    38 
    39 
    40 package Combine;
    41 
    42 sub new {
    43     my ($class, $n, $k) = @_;
    44 
    45     my $self = { count => 0,
    46                  total => $n ** $k };
    47 
    48     $self->{weights} = 
    49                [reverse map { $n**$_ } (0..$k-1)];
    50 
    51     bless $self, shift;
    52 }
    53 
    54 sub next {
    55     my $self   = shift;
    56 
    57     my $count  = $self->{count};
    58     my @result = ();
    59 
    60     return () if $count == $self->{total};
    61 
    62     foreach my $weight (@{$self->{weights}}) {
    63         my $val = int $count/$weight;
    64         push @result, $val;
    65         $count -= $val * $weight;
    66     }
    67 
    68     $self->{count}++;
    69 
    70     @result;
    71 }

Referenzen

[1]
Der Laden des Biermanns (in San Francisco bei mir um die Ecke): http://www.urbancellars.com

[2]
Monty Hall und andere Probleme, Linux-Magazin, September 1999, http://www.linux-magazin.de/xxx/xxx.html

[3]
Ein noch schwierigeres Rätsel, das mit Perl und einem Mathematik-Genie gelöst wurde: http://www.perlmeister.com/devel/puzzle.html

Michael Schilli

arbeitet als Software-Engineer bei Yahoo! in Sunnyvale, Kalifornien. Er hat "Goto Perl 5" (deutsch) und "Perl Power" (englisch) für Addison-Wesley geschrieben und ist unter mschilli@perlmeister.com zu erreichen. Seine Homepage: http://perlmeister.com.