Voir le flux RSS

Func' programming - un blog homéopathique

Poker time!

Noter ce billet
par , 27/03/2015 à 13h04 (911 Affichages)
Une question de cartes
Dans son billet Misères de l’analyse objet, un cas pratique, François (j’ai décidé une bonne fois pour toute de l’appeler par son prénom) montre les travers d’une approche objet naïve qui tenterait de refléter le réel dans les classes du programme. Elle mène à un code difficile à factoriser et difficile à maintenir. Le billet montre comment raffiner le concept initial, de façon itérative, jusqu’à arriver à la représentation adaptée au meilleur algorithme. François en conclut que le véritable apport de l’approche OO est l’encapsulation, qui permet d’expérimenter à l’abri d’une interface.

Dans un autre billet, je montrerai comment des langages fonctionnels gèrent la question de l’encapsulation –et peut-être aussi que certains langages objet ne font aucun cas de l’encapsulation. Dans celui-ci, je voudrais surtout montrer ce qu’est une approche fonctionnelle et comment elle se distingue d’une approche objet.

De haut en bas, de bas en haut
L’approche fonctionnelle est parfois qualifiée de "bottom-up", de bas en haut, parce que son moteur est de partir de fonctions simples, faciles à tester et assez générales pour être réutilisées dans d’autres contextes, pour construire la solution au problème. Il s’agit donc de partir de fonctions primitives ou standard et de n’y ajouter que le strict nécessaire de fonctions nouvelles, elles-mêmes aussi orthogonales que possible aux fonctions existantes.

Cette approche a de nombreux avantages : les fonctions utilisées ont déjà été optimisées et testées, et les fonctions nouvelles à chaque programme s’ajoutent progressivement au vocabulaire du développeur pour lui faciliter la vie. Comme il les réutilise, il a un intérêt réel à les optimiser et à les tester.

Le problème à traiter
Nous reprendrons dans ce billet le problème posé par François : comment comparer deux mains au poker ? Je suppose que tout le monde ici sait jouer au poker et sera d’accord avec la remarque suivante : toutes les figures reposent sur le nombre des cartes qui, dans la main, sont identiques –par le rang ou la couleur- ou se succèdent, ou les deux (la quinte flush).

Deux conséquences découlent de cette remarque : la première est qu’il nous faut une représentation des cartes qui permette de les comparer par rang et par couleur, et rien de plus. Donc une paire d’entiers fera parfaitement l’affaire. La deuxième est que la fonction split-if-not (définie dans le précédent billet) permettra de détecter la présence de toutes les figures.

Où sont passés les domestiques ?
Pour avancer dans notre programme, nous allons d’abord définir quelques petites fonctions facultatives qui nous permettront de tester au fur et à mesure nos avancées :

Code LISP : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
(defun card()
  (cons (random 13) (random 4))) ; ; random renvoie un entier entre 0 (inclus) et l’argument (exclu)
 
(defun card-names () '(2 3 4 5 6 7 8 9 10 V D R 1))
(defun color-names () '(Coeur Pique Carreau Trefle))
 
(defun name (card)
  (cons (nth (car card) (card-names)) ; ; (nth n liste) renvoie le énième argument de la liste
	(nth (cdr card) (color-names)))) ; ; cons peut être appelé avec 2 atomes –regardez le résultat par vous-mêmes
 
(defun hand() ; ; je vous l’ai dit, LISP n’est pas fonctionnel ; en voici un exemple :
  (let ((h nil))
    (dotimes (x 5) ; ; faire 5 fois (x prend les valeurs 0, 1 … 4)
      (push (card) h)) ; ; insère (card) au début de h
    h))
 
(defun ranks (hand)
  (mapcar #'car hand))
(defun colors (hand)
  (mapcar #'cdr hand))
Voilà, les domestiques sont arrivés, passons à la suite.

Déterminer les figures

Commençons par le gros morceau : comment détecter la présence d’un carré, d’un full, etc.
Tirons d’abord une main :

CL-USER> (setf h (hand))
((7 . 0) (9 . 1) (3 . 3) (0 . 1) (3 . 0))
CL-USER> (mapcar #'name h)
((9 . COEUR) (V . PIQUE) (5 . TREFLE) (2 . PIQUE) (5 . COEUR))

Nous n’aurons besoin que des rangs, de toute façon :

CL-USER> (setf r (ranks h))
(7 9 3 0 3)

Trions notre main :

CL-USER> (setf sr (sort r #'<))
(0 3 3 7 9)

Puis regroupons les cartes identiques :

CL-USER> (setf gsr (split-if-not #'= sr))
((0) (3 3) (7) (9))

Enfin nous retrions ce résultat pour savoir quelle est la figure la plus importante :

CL-USER> (setf sgsr (sort gsr (lambda (x y) (> (length x) (length y)))))
((3 3) (0) (7) (9))

Pour récapituler :
NB : :key précède un argument facultatif et nommé de sort, appliqué aux éléments avant d’appliquer la fonction de comparaison. (sort liste #’> :key #’length) = (sort liste (lambda (x y) (> (length x) (length y))))
Code LISP : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
(defun process-same-ranks (hand)
  (sort (split-if-not #'= (sort (ranks hand) #'<)) #'> :key #'length))

Pour détecter une couleur, le principe est le même :
Code LISP : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
(defun process-same-colors (hand)
  (sort (split-if-not #'= (sort (colors hand) #'<)) #'> :key #'length))

Et pour détecter une suite, ce n’est pas bien différent !
Code LISP : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
(defun process-succ-ranks (hand)
  (sort (split-if-not (lambda (x y) (= (1+ x) y)) (sort (ranks hand) #'<)) #'> :key #'length))

Il est donc très facile de factoriser :
Code LISP : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
(defun process-hand (split-pred rank-or-color hand)
  (sort (split-if-not split-pred (sort (funcall rank-or-color hand) #'<)) #'> :key #'length))

Pas encore tiré d’affaire
Il reste encore à comparer les deux mains, même si nous avons beaucoup avancé. Nous allons devoir calculer un score synthétique et comparable, de quelque façon que la main ait été traitée.

Pour les figures reposant sur des cartes de rang identique, la longueur de la figure la plus longue dans la main ne suffit pas à déterminer le score. Dans le cas présent (une paire), il pourrait également y avoir une seconde paire dans la main. Il faut donc également tenir compte de la longueur totale de la liste : si la première figure est une paire et que la liste des figures compte 4 éléments, il ne peut pas y avoir de deuxième paire. Pour avoir un score croissant qui corresponde à l’ordre des mains au poker, on peut multiplier la longueur de la première figure par (longueur maximale de la liste – longueur de la liste). Dans notre exemple, le score de la figure est 2 * (5 – 4) = 2.
Pour l’ensemble des figures, on a : paire = 2, double paire = 4, brelan = 6, full = 9, carré = 12 avec :

Code LISP : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
(defun score-id-ranks-figure (phand)
  (* (length (car phand)) (- 5 (length phand))))

Il suffit maintenant d’intercaler la quinte et la couleur (7 et 8 respectivement) et d’ajouter la quinte-flush (15). Vous devriez pouvoir maintenant comprendre le code suivant :
Code LISP : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
(defun synthetic-score (hand)
  (let ((id-ranks (process-hand #'= #'ranks hand))
	(succ-ranks (process-hand (lambda (x y) (= (1+ x) y)) #'ranks hand))
	(id-colors (process-hand #'= #'colors hand)))
    (let ((color (if (= 1 (length id-colors)) 8 0))
	  (straight (if (= 1 (length succ-ranks)) 7 0))
	  (other-figures (* (length (car id-ranks)) (- 5 (length id-ranks)))))
      (max (+ color straight) other-figures))))

Sommes-nous vraiment tirés d’affaire ?
Malheureusement, deux mains peuvent avoir un score identique, et il faut les départager. Heureusement, il ne nous reste presque plus rien à faire. Il suffit de donner, à côté du score synthétique, la main classée par rangs identiques. Comparer ces deux listes pour départager ne pose pas de problème :

NB: cond ressemble au switch d'autres langages. Il prend en argument un nombre variable de listes, dont le premier élément est une condition, le deuxième une expression à évaluer si la condition est vraie
Code LISP : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
(defun disambiguate (a b)
  (cond 
    ((null a) 'even)
    ((< (caar a) (caar b)) T)
    ((< (caar b) (caar a)) Nil)
    (T (disambiguate (cdr a) (cdr b)))))

Conclusion
Le billet est long mais le code est court : nous avons créé quatre fonctions non-standard : process-hand et synthetic-score, spécifiques au problème, split-if-not qui pourra nous resservir telle quelle, et disambiguate, qui aurait dû être généralisée : une fonction lexicographic-order-compare devrait être disponible dans notre arsenal de fonctions de base.

Exercices :
- écrire la fonction lexicographic-order-compare
- faites une recherche sur les différents types d’argument des fonctions de LISP (optionnels, à mot-clé, etc.)
- comment auriez-vous écrit ce programme dans votre langage favori ?
- proposez une amélioration des fonctions de ce billet

Envoyer le billet « Poker time! » dans le blog Viadeo Envoyer le billet « Poker time! » dans le blog Twitter Envoyer le billet « Poker time! » dans le blog Google Envoyer le billet « Poker time! » dans le blog Facebook Envoyer le billet « Poker time! » dans le blog Digg Envoyer le billet « Poker time! » dans le blog Delicious Envoyer le billet « Poker time! » dans le blog MySpace Envoyer le billet « Poker time! » dans le blog Yahoo

Mis à jour 31/03/2015 à 15h10 par stendhal666

Catégories
Programmation

Commentaires

  1. Avatar de kolodz
    • |
    • permalink
    Est-il possible d'avoir un lien sur le billet " Misères de l’analyse objet, un cas pratique" de ce "François" ?

    J'avoue ne pas trop comprendre la problématique traité dans le billet.

    Le Bottom-Up n'est pas spécifique à la programmation fonctionnelle et la programmation fonctionnelle n'est pas limité au Bottom-Up.

    Il est certains certains que la programmation objet pourrai commencer l'écriture d'un code équivalent en Up-Bottom de cette façon :

    Code Java : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    public class Hand{
     
        public static void main(String[] args) {
            Hand hand = new Hand();
            System.out.println(hand.getScore());
        }
    }

    Mais il est totalement possible de faire du Bottom-Up :

    Code Java : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    public class Hand{
        private Color color;
        private Rank rank;
     
        public boolean hasColor();
        public boolean hasSuccRank();
    }

    De même qu'il est possible de débuter votre raisonnement en commençant par la fonction synthetic-score.
    Cela ne distingue aucunement le type langage, mais l'approche utilisé sur le problème.

    De même, votre exemple présent une découpe fine en sous-fonction, qui n'est encore une fois spécifique au Bottom-Up (ou à la programmation fonctionnelle). D'ailleurs, c'est un approche qui a vite tendance à s'inverser quand on se rend compte qu'on ne maitrise pas les cas métier.

    En suite, il y a la problématique que l'optimisation et du test.

    Pour ce qui est du test :
    Beaucoup vous diront qu'il est impératif de savoir le retour attendu d'une fonction avant de la coder. Certains vous diront même qu'il est nécessaire d'écrire les cas de test de cette fonction avant de la coder. Cette approche n'a donc pas d’influence sur le fait qu'une sera testé ou non.

    Pour ce qui est de l'optimisation :
    Il faut bien comprendre que l'approche Bottom-Up est basiquement inadapté pour réaliser une bonne optimisation. Même si l'ensemble des fonctions sont optimisés. Il est n'est pas rare de voir des optimisations ou des simplifications dans un traitement dû à un contexte plus général. D'ailleurs, il est déconseillé de réaliser des optimisations autres qu'algorithmique pendant une phase de développement. Celles-ci doivent se faire avec une fonction/application stable, afin de pouvoir mesurer l'impacte globale de cette "optimisation".

    En somme, votre billet présent un belle exemple de programmation LISP, utilisant de nombreuse bonne pratique de programmation (Sous fonction, commentaire, etc...). Mais le propos de fond de l'article me laisse perplexe.

    Cordialement,
    Patrick Kolodziejczyk.
  2. Avatar de stendhal666
    • |
    • permalink
    Bonjour Kolodz,

    Tout d'abord, merci pour ce premier commentaire du blog, qui soulève des points importants que je suis content de pouvoir préciser.

    J'ai édité le post pour insérer un lien vers le billet de François comme vous aviez raison de le demander, puisque je lui réponds.

    Je suis d'accord pour dire que les généralités sur la programmation fonctionnelle -ou aussi bien la programmation objet- sont rarement justifiées et je ne veux pas affirmer d' équations comme: programmation fonctionnelle = bottom-up ou programmation objet = up-bottom.
    Je suis encore plus d'accord pour dire que le choix d'un langage ne définit pas le choix d'une approche (au contraire, même, et j'essaierai dans ce blog de montrer les aspects fonctionnels de C++ 11 / 14 ou de Python).

    Néanmoins, l'un des apports les plus intéressants de la programmation fonctionnelle est un certain type de modularité: la possibilité de composer des fonctions avec d'autres fonctions, qui pousse à une approche de type bottom-up. Inversement, dans la programmation objet, la modularité est orientée vers la réutilisation d'objets (que ce soit par héritage ou par composition); cela n'exclut pas des éléments bottom-up dans l'approche mais pousse tout de même à réfléchir d'abord à l'interface et ensuite à l'algorithme. Je ne dis pas pour autant qu'un programmeur objet expérimenté tombera dans les travers dénoncés par François.

    Sur les questions de l'optimisation et des tests, que vous soulevez très justement:
    - sur les tests, je n'affirme bien sûr pas que la programmation bottom-up est la seule qui permette des tests. Je dis simplement qu'il y a une plus forte incitation à tester des fonctions que l'on réutilise fréquemment, et une plus forte probabilité qu'elles aient déjà été écrites, testées et optimisées lorsqu'elles sont plus générales.
    - sur l'optimisation, pour tout vous dire, j'en suis presque un adversaire. Je considère que la généralité et la compréhension du code sont en général plus importantes (mais je ne programme pas le logiciel d'avions de chasse ou de moteurs de fusée). Les optimisations figent trop souvent le code. Cela étant, le code de ce billet pourrait être facilement amélioré, mais je voulais en faire l'objet d'un prochain billet, dans un langage plus fonctionnel que LISP...