Uncle Bob’s Bowling Game Kata

Vor zwei Tagen gab es auf ProgrammingPraxis.com die Aufgabe Uncle Bob’s Bowling Game Kata durchzuführen. Bei dieser Kata geht es darum, anhand von der umgefallenen Pins die Gesamtpunktzahl einer Bowling-Runde zu ermitteln. Die in Haskell angefertigte Lösung ist sehr elegant, weshalb ich sie hier präsentieren und verifizieren will. Aber davor müssen noch einige wichtige Begriffe und natürlich die Regeln erklärt werden (vgl. Bowlingregeln).

• Bowling-Runde: Die Bowling-Runde besteht aus 10 Frames.
• Frame: Ein Frame endet entweder nach zwei Würfen oder nach einem Strike.
• Strike: Alle 10 Pins wurden nach dem ersten Wurf getroffen. Zusätzlich zu den 10 Punkten werden die nächsten beiden Würfe addiert.
• Spare: Alle 10 Pins wurden nach dem zweiten Wurf getroffen. Zusätzlich zu den 10 Punkten wird der nächste Wurf addiert.
• Offener Frame: Es wurden mit den beiden Würfen weniger als 10 Pins getroffen.
• Miss: Es wurde kein Pin getroffen.
• Letzter Frame: Die Runde hat mindestens zwei und maximal drei Würfe deren Summe zum Ergebnis addiert wird. Der dritte Wurf wird genau dann gewährt, wenn ein Strike oder Spare geworfen wurde.
• Punktzahl: Die Anzahl der getroffenen Pins bei einem Wurf.

Die folgende Grafik zeigt einen beispielhaften Verlauf (entnommen von ProgrammingPraxis.com):

Ist ein Kästchen zur Hälfe ausgefüllt, so wurde ein Spare geworfen, d.h. es wurden 10 Punkte in dem Frame geworfen. Bei einem vollständig ausgefülltem Kästchen wurde ein Strike geworfen, d.h. mit einem Wurf wurden 10 Pins getroffen. In der obigen Darstellung steht in der unteren Zeile die Gesamtpunktzahl nach dem jeweiligen Frame, wobei die speziellen Regeln für Strikes, Spares und den letzten Frame bereits berücksichtigt wurden.

Meine Implementierung macht sich diese Regelunterscheidungen zunutze:

Die Erklärung des Codes erfolgt dabei direkt anhand der Verifikation der Korrektheit. Es wird der Einfachheit halber angenommen, dass die Würfe als Liste von Punktzahlen übergeben wird, d.h. Strikes, Spares oder Misses werden anhand der Punktzahlen ermittelt. Außerdem kann vorausgesetzt werden, dass die Eingabe korrekt ist. Eine wesentliche Eigenschaft zur Verifikation ist die Invariante, die besagt, dass bei einem Aufruf der Funktion pins genau ein Frame abgearbeitet wird.

Beginnen wir bei der Berechnung des letzten Frames: Der letzte Frame enthält entweder drei oder zwei Würfe. Hier wird lediglich die Gesamtpunktzahl des Frames ermittelt. Durch das Pattern-Matching werden nur die Fälle abgearbeitet, in denen die Liste zwei oder drei Punktzahlen, sodass die Regeln, wie definiert, nur im letzten Frame gilt. Die Regeln entsprechen offensichtlich dem, was in der Definition des letzten Frames angegeben wurde. Außerdem gilt die Invariante, da der letzte Frame in Gänze abgearbeitet wird.

Der andere Fall wird genau dann aufgerufen, wenn der letzte Frame noch nicht erreicht ist. Zuerst wird die Invariante gezeigt: Wurde ein Strike geworfen, hat der Frame nur einen Wurf, d.h. nur der Kopf der Liste (d.h. x) wird verarbeitet. In den restlichen Fällen werden die ersten beiden Elemente verarbeitet (d.h. x und y). Dies ist offensichtlich der Fall, da die jeweiligen Elemente in den nachfolgenden Aufrufen nicht mehr verarbeitet werden. Die Regeln werden regelkonform übernommen: Bei einem Strike werden die nächsten beiden (d.h. y und z), bei einem Spare nur die nächste (d.h. z) sowie bei einem offenen Frame keine weiteren Punktzahlen zur Gesamtpunktzahl des jeweiligen Frames addiert.

Da die Regeln jeweils korrekt übertragen wurden, wird die Gesamtpunktzahl jedes Frames korrekt berechnet. Es kann als bekannt vorausgesetzt werden, dass sich die Gesamtpunktzahl einer Bowling-Runde aus der Gesamtpunktzahl jedes einzelnen Frames ergibt. Da pins lt. Invariante jeweils einen Frame korrekt berechnet und diese Punktzahl anschließend auf Gesamtpunktzahl der restlichen Frames addiert wird, ist auch die Summe korrekt. Für das Verständnis exerziere ich die Funktionsweise am Beispiel der obigen Grafik durch:

Anhand dieses Beispiels kann man sehr gut erkennen, wie der Algorithmus arbeitet. Zuerst wird jeder einzelne Frame berechnet und anschließend dessen Summe gebildet. Zwar hat die Auswertungsreihenfolge lt. Church-Rosser-Theorem keinen Einfluss auf das Ergebnis, aber die obige Reihenfolge ist für das Verständnis sehr gut geeignet. Ein Vergleich mit den korrigierten Testfällen auf Tom Moertels Blog bekräftigt dieses Ergebnis.

Insgesamt bin ich sehr zufrieden mit meiner Lösung, da sie sehr kurz aber auch sehr präzise ist. Soweit ich weiß, sollten solche Code-Katas testgetrieben entwickelt werden, was in diesem Fall allerdings sehr wenig Sinn hat, denn sechs Zeilen Code sind schneller geschrieben als die Unit-Tests und man kann sich sehr leicht von der Korrektheit überzeugen. Wenn man beim Schreiben des Codes bereits plant, den Code zu verifzieren, macht man sich automatisch Gedanken darüber, wie man das Problem dekomponieren und die Teillösungen komponieren kann. In meinem Fall wurde die Gesamtpunktzahl der Bowling-Runde durch die Gesamtpunktzahl jedes Frames berechnet. Die Berechnung jedes Frames ist trivial und so mussten nur noch diese Teillösungen zur Gesamtlösung komponiert werden, d.h. die Summe der Frames musste berechnet werden. Diese Gedanken helfen beim Problemlösen enorm.

Kommentare