Kata

Un classique : compter les points au bowling

Pour commencer, un classique le Kata Bowling en Haskell.

  • D’une part c’est l’occasion pour des débutants en Haskell (dont je fais partie) de revoir un problème déjà bien balisé.
  • D’autre part, malgré les apparences, il reste des simplifications à explorer dans l’exercice posé.

Je rappelle le sujet du Kata. On souhaite écrire un programme qui à partir de la liste des coups joués (nombres de quilles tombées à chaque boule lancée) annonce le score réalisé. On le retrouve dans quantités de livres ou de sites consacrés au TDD, dans différents languages de programmation.

J’avoue avoir été un peu déçu par les solutions que j’ai vu à droite ou à gauche, un peu comme voir un judoka qui gagne un combat en force, sans utiliser la force de l’adversaire. Trève de discussion, voici ma version.

Le calcul du score de bowling classique est décidément trop compliqué, alors pourquoi pas résoudre un problème plus simple. Disons un Bowling à un seul tour de jeu ou l’on se contenterait d’essayer d’abattre seulement dix quilles, avec éventuellement une boule ou deux de bonus en cas de spare ou de strike.

Disons qu’on joue plutôt mal et que les deux boules finissent dans la rigole. Cela donne le test suivant:

module Main
where
import Test.HUnit
import Bowling

main = do runTestTT tests
tests = TestList [ test1TourAucuneQuilleTombe]

test1TourAucuneQuilleTombe =     0   ~=? score 1 [0,0]

La fonction score calcule le score du Bowling, le 1 apparaissant comme premier paramètre de la fonction score indique qu’il s’agit de la variante à un tour de jeu. Le second paramètre indique le nombre de quilles abattues à chaque boule. Le code permettant au test de passer est très simple:

module Bowling
where
score _ _ = 0

On compile et on teste (en l’occurence sous Linux) par

ghc --make TestBowling.hs Bowling.hs && ./TestBowling

Jouons encore au bowling à un tour. Cette fois on fait tomber quelques quilles pour lever le fake.

test1TourAucuneQuilleTombe =     0   ~=? score 1 [0,0]
test1Tour7QuillesTombent   =     7   ~=? score 1 [3,4]

Le programme le plus simple qui nous vienne à l’esprit pour faire passer les tests est celui-ci:

module Bowling
where
score _ s = sum s

Quel va être le troisième test ? Un strike ? Un spare ? En fait une rapide réflexion sur le fonctionnement du Bowling à un tour suffit à nous convaincre que ces cas sont déjà pris en compte par le code. En fait le calcul de score pour le Bowling à 1 coup est entièrement traité. Pour avoir un nouveau test qui échoue il faut donc passer au Bowling à deux coups. Il faut de plus impérativement introduire le cas d’un strike ou d’un spare au premier coup, sinon la encore le test passerait immédiatement.

Disons donc que nous réussissons un spare au premier coup :

test1TourAucuneQuilleTombe =     0   ~=? score 1 [0,0]
test1Tour7QuillesTombent   =     7   ~=? score 1 [3,4]
test2ToursSpare            = (11+1)  ~=? score 2 [6,4,1,0]

Un fake suffit à faire passer le nouveau test

module Bowling
where

score 1 s = sum s
score 2 _ = 12

Cette fois nous pouvons introduire une partie sans Bonus au Bowling à deux tours. Le programme différentie Bowling à un et deux tours et ne fonctionne plus immédiatement. Quatres boules dans la rigole suffisent à lever le fake

test1TourAucuneQuilleTombe =     0   ~=? score 1 [0,0]
test1Tour7QuillesTombent   =     7   ~=? score 1 [3,4]
test2ToursSpare            = (11+1)  ~=? score 2 [6,4,1,0]
test2ToursNul              = (0+ 0)  ~=? score 2 [0,0,0,0]

et le code pour faire passer le test

score 1 s = sum s
score 2 (x1:x2:xs)
    | x1 + x2 == 10 = x1 + x2 + (head xs) + score 1 xs
    | otherwise     = x1 + x2            + score 1 xs

Cette fois la méthode qui semble la plus simple pour tombr dans un cas non traité consiste à introduire un strike.

test1TourAucuneQuilleTombe =     0   ~=? score 1 [0,0]
test1Tour7QuillesTombent   =     7   ~=? score 1 [3,4]
test2ToursSpare            = (11+1)  ~=? score 2 [6,4,1,0]
test2ToursNul              = (0+ 0)  ~=? score 2 [0,0,0,0]
test2ToursStrike           = (17+7)  ~=? score 2 [10,3,4]

Une ligne de plus suffit dans le programme pour prendre en compte les strikes:

score 1 s = sum s
score 2 (x1:x2:xs)
    | x1      == 10 = x1 + x2 + (head xs) + score 1 (x2:xs)
    | x1 + x2 == 10 = x1 + x2 + (head xs) + score 1 xs
    | otherwise     = x1 + x2             + score 1 xs

Tous les tests passent, et ô surprise on se rend compte qu’on vient à nouveau de traiter entièrement le jeu à deux tours. Passons donc au jeu à 3 tours.

test1TourAucuneQuilleTombe =     0   ~=? score 1 [0,0]
test1Tour7QuillesTombent   =     7   ~=? score 1 [3,4]
test2ToursSpare            = (11+1)  ~=? score 2 [6,4,1,0]
test2ToursNul              = (0+ 0)  ~=? score 2 [0,0,0,0]
test2ToursStrike           = (17+7)  ~=? score 2 [10,3,4]
test3ToursNormaux          = (9+6+6) ~=? score 3 [4,5,3,3,4,2]

Une fois n’est pas coutume, laissons nous tenter par un copier/coller afin de faire rapidement passer le test:

module Bowling
where

score 1 s = sum s
score 2 (x1:x2:xs)
    | x1      == 10 = x1 + x2 + (head xs) + score 1 (x2:xs)
    | x1 + x2 == 10 = x1 + x2 + (head s) + score 1 xs
    | otherwise     = x1 + x2            + score 1 xs
score 3 (x1:x2:xs)
    | x1      == 10 = x1 + x2 + (head xs) + score 2 (x2:xs)
    | x1 + x2 == 10 = x1 + x2 + (head s) + score 2 xs
    | otherwise     = x1 + x2            + score 2 xs

Les tests passent mais un petit refactoring s’impose pour éliminer le code dupliqué:

module Bowling
where

score 1 s = sum s
score n (x1:x2:xs)
    | x1      == 10 = x1 + x2 + (head xs) + score (n-1) (x2:xs)
    | x1 + x2 == 10 = x1 + x2 + (head xs) + score (n-1) xs
    | otherwise     = x1 + x2            + score (n-1) xs

La bonne surprise c’est que nous avons fini. Le programme sait désormais calculer les scores au Bowling classique pour peu qu’on lui passe 10 comme premier pramètre de score.

  • Les esthètes peuvent même cacher le paramètre en définissant scoreBowling:
  • Un second refactoring est aussi possible pour éviter de répliquer les appels récursifs à score (là c’est un peu affaire de goût, le code résultant est plus compact mais on ajoute une fonction et le listing s’allonge d’une ligne.
module Bowling
where

scoreBowling = score 10

lancer (x1:x2:xs)
    | x1      == 10 = (10 + x2 + (head xs) ,  x2:xs)
    | x1 + x2 == 10 = (10 +      (head xs) ,     xs)
    | otherwise     = (x1 + x2             ,     xs)

score 1 s = sum s
score n s = let (c, suite) = lancer s in c + (score (n-1) suite)
module Main
where
import Test.HUnit
import Bowling

main = do runTestTT tests
tests = TestList [ test1TourAucuneQuilleTombe
                 , test1Tour7QuillesTombent
                 , test2ToursSpare
                 , test2ToursNul
                 , test2ToursStrike
                 , test3ToursNormaux
                 , testRecetteParfait
                 , testRecettePresqueParfait
                 , testRecette
                 ]

test1TourAucuneQuilleTombe =     0   ~=? score 1 [0,0]
test1Tour7QuillesTombent   =     7   ~=? score 1 [3,4]
test2ToursSpare            = (11+1)  ~=? score 2 [6,4,1,0]
test2ToursNul              = (0+ 0)  ~=? score 2 [0,0,0,0]
test2ToursStrike           = (17+7)  ~=? score 2 [10,3,4]
test3ToursNormaux          = (9+6+6) ~=? score 3 [4,5,3,3,4,2]

testRecetteParfait         = (300)   ~=? scoreBowling [10,10,10,10,10,10,10,10,10,10,10,10]

testRecettePresqueParfait  = ((9+1+10) + (10+10+2) + (10+2+0) + (2+0) + (6*30))   ~=? scoreBowling [9,1,  10,  10,  2,0  ,10  ,10  ,10  ,10  ,10  ,10  ,10,10]

testRecette                =  ((10+7+2) + (7+2) + (3+7) + (0+10+10) + (10+10+9) + (10+9+1) + (9+1+1) + (1+9+10) + (10+8+2) + (8+2+3)) ~=? scoreBowling [10, 7, 2, 3, 7, 0, 10, 10, 10, 9, 1, 1, 9, 10, 8, 2, 3]

Quelques remarques a posteriori : l’étude du jeu de Bowling réduit à un nombre de tours précis nous a finalement simplifié la têche. C’est probablement un pattern à relever. Lorsque le problème semble complexe ne peut on pas le considérer comme un cas particulier d’un problème plus général (moins contraint en termes de données) dont les cas simples sont facile à traiter. Une approche similaire marche assez bien dans le cas du problème classique des huit reines (considérer qu’un échiquier n’est qu’une liste arbitraire de cases) et facilite l’étude. L’apparition d’une constante dans le code (comme 11 dans le cas du Bowling avec compteur) est un indice fort qu’il existe une généralisation de ce type.

On remarque aussi que certaines listes de coup de « Bowling 10 » et de « Bowling 9 » sont identiques par exemple [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,10,0,0].

S’agit t’il d’une partie de « Bowling9 » avec un strike en dernier coup ou d’une partie de « Bowling 10 » avec un strike en avant-dernier coup.

Ceci nous permet d’affirmer qu’il n’existe aucune méthode permettant de calculer le score du Bowling qui n’introduise pas une information nous permettant de svoir que la partie est finie, typiquement un compteur de coups.

Il est possible d’avoir recours à un marqueur spécifique d’absence de bonus, une « sentinelle », mais dans ce cas cela oblige à modifier les données en entrées. Le module de calcul de score lui-même ne peut pas déduire d’un contexte local s’il faut insérer ou non ce marqueur (sauf à calculer explicitement le nombre de coups pour savoir ou placer la sentinelle).

Exemple avec sentinelle, les strikes en fin sont détectés des strike en avant-dernier par la parité du nombre de coup restant, un strike en avant dernier sera suivi d’un nombre impair de boules:

 module Main
where
import Test.HUnit
import Bowling

main = do runTestTT tests
tests = TestList [ test1TourAucuneQuilleTombe
                 , test1Tour7QuillesTombent
                 , test2ToursSpare
                 , test2ToursNul
                 , test2ToursStrike
                 , test3ToursNormaux
                 , test3ToursSpareAlaFin
                 , testRecetteParfait
                 , testRecettePresqueParfait
                 ]

-- la fin du jeu est indiquée par un ou deux coups supplémentaires
-- correspondant aux bonus
-- à zéro pour un tour sans bonus
-- comme d'habitude pour un spare ou un strike
-- par chance le procédé marche pour un spare suivi d'une boule nulle

test1TourAucuneQuilleTombe =     0   ~=? score [0,0,0]
test1Tour7QuillesTombent   =     7   ~=? score [3,4,0]
test2ToursSpare            = (11+1)  ~=? score [6,4,1,0,0]
test2ToursNul              = (0+ 0)  ~=? score [0,0,0,0,0]
test2ToursStrike           = (17+7)  ~=? score [10,3,4,0]
test3ToursNormaux          = (9+6+6) ~=? score [4,5,3,3,4,2,0]
test3ToursSpareAlaFin      = (1+3)+(3+4) + (5+5+1) ~=? score [1,2,3,4,5,5,1]
testRecetteParfait         = (300)   ~=? score [10,10,10,10,10,10,10,10,10,10,10,10]
testRecettePresqueParfait  = ((9+1+10) + (10+10+2) + (10+2+0) + (2+0) + (6*30))   ~=? score [9,1,  10,  10,  2,0  ,10  ,10  ,10  ,10  ,10  ,10  ,10,10]

Et le code correspondant:

module Bowling
where

lancer (x1:x2:xs)
    | x1      == 10 = (10 + x2 + (head xs) ,  x2:xs)
    | x1 + x2 == 10 = (10 +      (head xs) ,     xs)
    | otherwise     = (x1 + x2             ,     xs)

score (x:[])             = x
score s@(10:_:_:[])      = sum s
score s = let (c, suite) = lancer s in c + (score suite)
Publicités

Laisser un commentaire

Entrez vos coordonnées ci-dessous ou cliquez sur une icône pour vous connecter:

Logo WordPress.com

Vous commentez à l'aide de votre compte WordPress.com. Déconnexion /  Changer )

Photo Google+

Vous commentez à l'aide de votre compte Google+. Déconnexion /  Changer )

Image Twitter

Vous commentez à l'aide de votre compte Twitter. Déconnexion /  Changer )

Photo Facebook

Vous commentez à l'aide de votre compte Facebook. Déconnexion /  Changer )

w

Connexion à %s