29.09.2016

Häufigkeiten von Würfelsummen - kleines Rätsel

Ich bin ein typischer Informatiker - wenn irgendwo ein Rätsel, Denksportaufgabe o.ä. abgedruckt ist, muss ich es probieren. Zuerst denke ich kurz darüber nach, ob es eine offensichtliche Lösung gibt, und da ich sehr ungeduldig bin, geht das nicht lange gut ;)

Danach denke ich darüber nach, wie ich die Aufgabe mit dem Rechner lösen kann - auch das Nachdenken über eine algorithmische Lösung ist schließlich Denksport ;)

Kürzlich fragte die "Spektrum der Wissenschaft" nach der Häufigkeitsverteilung beim Würfeln mit drei Würfeln. Das ist ein nettes Beispiel für eine Anfängeraufgabe, und natürlich versuchte ich mich damit, das "Problem" in perl zu lösen. Ich liebe perl, perl ist cool, genauso wie Fliegen cool sind ;)

Also zurück zur Aufgabe: welche Würfelsumme ist beim Würfeln mit drei Würfeln am häufigsten?

Der offensichtliche Ansatz ist eine dreifach geschachtelte Schleife, d.h. dreimal von 1 bis 6 zählen, Summe bilden und diese Summe (die zwischen 3 und 18 liegen kann) als Index verwenden, um in einem Array einen Zähler für diese Summe zu erhöhen.

Bei dieser Aufgabe kann man einige coole Features von perl gut zum Einsatz bringen, nämlich Arrays und einige sehr bequeme Funktionen und Operatoren, um mit Arrays umzugehen.

Natürlich will ich das kleine perl-Programm nicht einfach so hier in's Blog werfen, sondern ein paar der Besonderheiten von perl  ausführlicher kommentieren.

Zunächst verwende ich für das Zählen der Häufigkeiten ein assoziatives Array %sum, bei dem die Indizes beliebige Strings sein können, und kein Array mit numerischen Indizes. Das mag zunächst unnötig umständlich wirken, aber es erspart mir später einige Fallunterscheidungen, weil ich mir vorgenommen habe, Funktionen zu verwenden, die wenig bekannt sind. Aber natürlich gilt wie immer der perl-Leitsatz "there's more than one way to do it", und man kann die Aufgabe auch lösen, wenn man ein Array @sum verwendet.

Das Progrämmchen besteht aus drei Teilen: Variablendeklaration, Berechnung und Ausgabe. Die Kommentare unten markieren diese drei Teile. Ganz unten ist der vollständige Code zu finden, und hier im Text jeder Teil einzeln.

# Variablendeklaration
my %sum;


Wie schon beschrieben, wird bei der Berechnung einfach die Summe der drei ineinander geschachtelten Laufvariablen (i1, i2, i3) berechnet und als Index in das Array verwendet. Der auch aus C bekannte "++"-Operator addiert eins zum adressierten Array-Element. Die Schreibweise für die Schleifen finde ich besonders elegant: der perl-Operator ".." erzeugt eine Liste (oder auch Array genannt) von .. bis. Das funktioniert übrigens nur sauber in der Aufwärts-Richtung, es gibt grenzwertige Situationen, in denen man überrascht wird, wenn das bis kleiner ist als das von, also obacht hier!

# Berechnung
foreach my $i1 (1..6) {
    foreach my $i2 (1..6) {
        foreach my $i3 (1..6) {
            ++$sum{$i1+$i2+$i3};
        }
    }
}


Bei der Lösung solcher Aufgaben sollte man sich vorher überlegen, ob man den "brute force"-Ansatz wählt und einfach alle Varianten durchprobiert oder ob es Optimierungsmöglichkeiten gibt, mit denen man die Komplexität reduzieren kann. Bei drei Schleifen von 1 bis 6, mithin also 216 Schleifendurchläufen, ist das Programm selbst auf einem C-64 noch zu meinen Lebzeiten beendet ;)

# Ausgabe
print join("\n",
           map { sprintf("% 3d",$_) . " => $sum{$_}" }

               sort { $sum{$b} <=> $sum{$a} }
                    keys(%sum)
      ),"\n";


Bei der Ausgabe der Ergebnisse habe ich tief in die Trickkiste gegriffen und alles in einen einzigen "print"-Befehl gepackt. Dieser Befehl bekommt als Parameter das Ergebnis des "join"-Kommandos und hintendran wird noch ein einzelnes "\n", also ein Zeilenumbruch gehängt. Die Einrückungen habe ich so gewählt, dass man genau sieht, was zusammengehört.

print join("\n",
           map { sprintf("% 3d",$_) . " => $sum{$_}" }
               sort { $sum{$b} <=> $sum{$a} }
                    keys(%sum)
      ),"\n";


Der "join"-Befehl selbst nimmt zwei Parameter: das Verbindungszeichen "\n" und ein Array von Strings (man kann in perl alles als String verwenden, selbst Zahlen - es gibt keine strikte Unterscheidung, wie man ein "skalares Element" verwenden darf).

map { sprintf("% 3d",$_) . " => $sum{$_}" }
   
sort { $sum{$b} <=> $sum{$a} }
         keys(%sum)


Das "Array von Strings", das "join" bekommt, wird von einem "map"-Befehl dynamisch erzeugt. "map" ist eigentlich ein versteckter Schleifenoperator und erzeugt aus einer Funktion und einem Array als Parameter wiederum ein Array. Dies ist eines der faszinierenden Features von perl, die ich oben erwähnt hatte: "map" nimmt als Parameter eine namenlose Funktion, die man in {} schreibt.

In dieser Funktion, genau wie im folgenden Befehl "sort" gibt es Pseudo-Variablen, die nur innerhalb dieser Funktion benutzbar sind. Bei "map" ist es die Variable "$_", die das aktuell bearbeitete Array-Element beinhaltet. Dieses Element ist der Index des Arrays und bedeutet hier eine spezielle Würfelsumme. Mit "sprintf" formatiere ich diese Zahl rechtsbündig, dahinter hänge ich mit dem Stringoperator "." noch ein bißchen Schmuck als Trennzeichen an und danach noch die tatsächliche Anzahl an Möglichkeiten, diese Würfelsumme zu werfen.

sort { $sum{$b} <=> $sum{$a} } keys(%sum)

Jetzt kommt noch ein weiteres cooles Feature von perl: es gibt einen eingebauten Befehl zum Sortieren von Arrays, und diesem Befehl kann ich wiederum in einer namenlosen Funktion mitgeben, wie ich die Sortierung wünsche. Da ich beim Sortieren immer zwei Elemente vergleichen muss, liefert mir perl bequemerweise zwei Pseudovariablen, die mit "$a" und "$b" bezeichnet werden. Diese Variablen sind nur innerhalb dieses "sort"-Befehls bekannt und beeinflussen eventuell "außerhalb" deklarierte Variablen "$a" und "$b" nicht!

Sortiert wird absteigend nach der Häufigkeit, mit der dieser Würfelwurf vorkommen kann, also nach dem Inhalt des Arrays an dieser Stelle, und der "<=>"-Operator erzählt mir, welcher der beiden Werte kleiner bzw. größer ist. Dies ist ein sogenannter "ternärer" Operator, der mir je nach Vergleichsergebnis -1, 0 oder 1 liefert (also drei mögliche Ergebnisse, deshalb "ternär").

Solche verketteten Ausdrücke in perl muss man also von hinten nach vorne lesen, damit man den Sinn versteht.

Nochmal aus dieser Sichtweise betrachtet: ich sortiere das Array nach der Häufigkeit und übergebe das sortierte Array an "map", um dort die einzelnen Array-Elemente hübsch lesbar zu machen. Mit "join" verknote ich alle diese aufgehübschten Array-Elemente, so dass "print" einen einzelnen String ausgeben kann.

Und dies ist das gesamte Skript ohne Erklärungen dazwischen:

#!/usr/bin/perl -w


# Variablendeklaration

my %sum;

# Berechnung

foreach my $i1 (1..6) {
    foreach my $i2 (1..6) {
        foreach my $i3 (1..6) {
            ++$sum{$i1+$i2+$i3};
        }
    }
}
 

# Ausgabe
print join("\n",
           map { sprintf("% 3d",$_) . " => $sum{$_}" }
               sort { $sum{$b} <=> $sum{$a} }
                    keys(%sum)
      ),"\n";



[Update 20160930: Schleife von for auf foreach geändert, Einrückungen bei print zur Verdeutlichung]