L’exercice FizzBuzz est un petit exercice très simple, à tester par exemple lorsque vous recrutez un programmeur (H/F). Il s’avère que beaucoup de développeurs ne sont pas capables de le résoudre simplement sans l’aide d’Internet/StackOverflow ou autre. Ou d’autres vont y passer plus de 10 minutes, sur le langage qu’ils utilisent pourtant tous les jours…
L’exercice original apparaît en 2007 sur le blog d’Imran Gory, et a été aussi repris sur le blog de Jeff Atwood. Je crois que j’en ai entendu parler pour la première fois lors des sélections de CodeStory pour Devoxx France 2012, avec David Gageot et Jean-Laurent de Morlhon.
Le principe est simple :
Write a program that prints the numbers from 1 to 100. But for multiples of three print “Fizz” instead of the number and for the multiples of five print “Buzz”. For numbers which are multiples of both three and five print “FizzBuzz”.
Imran Gory https://imranontech.com/2007/01/24/using-fizzbuzz-to-find-developers-who-grok-coding/
Enoncé simple. Utilisez le langage de votre choix, l’IDE de votre choix, et expliquez votre démarche.
Exemple de résultat :
1 2 Fizz 4 Buzz Fizz 7 8 Fizz Buzz 11 Fizz 13 14 FizzBuzz 16 17 Fizz 19 Buzz
Stop ! Mettez en pause la lecture de ce blog et essayez de le faire !
Vous avez terminé ?
Faisons très simple et en Java « classique » avant de chercher une solution plus moderne.
// Version 1
public class FizzBuzz {
public static void main(String[] args) {
for(int i=1 ; i <= 100 ; i++){
if(i % 15 == 0){
System.out.println("FizzBuzz");
continue;
}
if(i % 3 == 0) {
System.out.println("Fizz");
continue;
}
if(i % 5 == 0){
System.out.println("Buzz");
continue;
}
System.out.println(i);
}
}
}
Si vous utilisez IntelliJ, avec Java 8 minimum, vous verrez que l’IDE propose d’utiliser IntStream, afin de générer un stream de Int. Voyons ce que cela donne :
// Version 2 - Java 1.8 minimum
public class FizzBuzz {
public static void main(String[] args) {
IntStream.rangeClosed(1, 100).forEach(i -> {
if (i % 15 == 0) {
System.out.println("FizzBuzz");
return;
}
if (i % 3 == 0) {
System.out.println("Fizz");
return;
}
if (i % 5 == 0) {
System.out.println("Buzz");
return;
}
System.out.println(i);
});
}
}
Du coup, je me suis dis qu’une version plus fonctionnelle serait plus lisible. Et elle permet aussi de tester éventuellement la fonction mapToMessage (ce nom de méthode n’est pas top, je suis d’accord)
// Version 3 - Java 1.8 minimum
public class FizzBuzz {
public static String mapToMessage(Integer i) {
if (i % 15 == 0) {
return "FizzBuzz";
}
if (i % 3 == 0) {
return "Fizz";
}
if (i % 5 == 0) {
return "Buzz";
}
return i.toString();
}
public static void main(String[] args) {
IntStream.rangeClosed(1, 100)
.mapToObj(FizzBuzz::mapToMessage)
.forEach(System.out::println);
}
}
Et on peut aussi aller jusqu’à une version « in-liner » qui pour moi, n’est pas forcément la plus lisible :
IntStream.rangeClosed(1, 100)
.mapToObj(i -> i % 5 == 0 ? (i % 3 == 0 ? "FizzBuzz" : "Fizz") : (i % 3 == 0 ? "Buzz" : i))
.forEach(System.out::println);
Et Scala dans tout cela ?
La première version que j’ai écrite est pas forcément la plus fonctionnelle, mais elle va nous permettre de vous parler de 2 trucs sympathiques en Scala.
Voyons d’abord le code :
package exercises.trash
import scala.annotation.tailrec
object BuzzMe {
type Buzz = String // (1)
def generate(counter: Int): List[Buzz] = {
@tailrec // (2)
def subGenerate(subCount: Int, accum: List[Buzz]): List[Buzz] = subCount match {
case 1 => "1" :: accum // (5)
case x if x % 15 == 0 => subGenerate(subCount - 1, "FizzBuzz" :: accum)
case x if x % 3 == 0 => subGenerate(subCount - 1, "Fizz" :: accum)
case x if x % 5 == 0 => subGenerate(subCount - 1, "Buzz" :: accum)
case other => subGenerate(subCount - 1, other.toString :: accum) // (3) dernier appel est un appel recursif
}
subGenerate(counter, List.empty[Buzz]) // (4)
}
def main(args: Array[String]): Unit = {
BuzzMe.generate(100).foreach(println(_))
}
}
Plusieurs petits trucs intéressants à noter ici.
(1) => Scala permet de déclarer des alias de type afin de faciliter la lecture. En général on s’en sert pour masquer la complexité d’un type. Par exemple « type Row = List[Int] ». Cela ne renforce pas spécialement le typage car le compilateur va remplacer Buzz par String à la compilation (voir plus de détails dans la doc Scala 2.12 type-erasure).
(2) Deuxième truc intéressant, c’est l’annotation @tailrec. Vous notez que le dernier appel de la fonction subGenerate (indice (3)) est récursif. Elle prend son sens lorsque l’on regarde le fonctionnement de la fonction generate(). Scala permet de déclarer des fonctions « dans » des fonctions, ce que l’on fait ici avec subGenerate. La fonction generate prend en argument un compteur et retourne une List de Buzz.
(4) Le premier appel à subGenerate démarre avec le compteur passé en paramètre et List.empty[Buzz]. Regardez comment fonctionne la fonction subGenerate : elle fait du pattern-matching. J’ai fait exprès de changer les noms des paramètres pour que les lecteurs qui ne connaissent pas Scala puisse bien suivre.
Selon la valeur de subCount, nous rappellerons de façon récursive la même fonction subCount, en ayant simplement ajouté soit « Fizz », soit « Buzz », soit « FizzBuzz », soit le compteur en début de liste. La liste retournée est un accumulateur. On part de 100 jusqu’à 1, en ajoutant à chaque fois un élément en début de liste. C’est assez efficace en Scala car la création d’une nouvelle liste en plaçant la nouvelle valeur en tête, est une opération très rapide de l’ordre de O(1).
La notation « Fizz » :: accum crée une nouvelle liste constituée de « Fizz » comme premier élément et ensuite « accum » comme étant le reste de la liste. L’opérateur :: (cons) est une fonction de la liste « accum ». Nous pourrions écrire aussi accum.::(« Fizz ») mais les développeurs Scala ont l’habitude de cette notation.
En programmation fonctionnelle on ne cherche pas à « remplir » une liste, mais à créer petit à petit des objets (comme des Legos) jusqu’à obtenir la structure recherchée. C’est évidemment contre-intuitif lorsque l’on vient du monde de la programmation impérative.
L’annotation @tailrec est là pour indiquer au compilateur de surveiller notre code, et de nous avertir si notre fonction subCount n’est plus tail-recursive.
Alors c’est quoi une fonction tail-rec ?
Prenez la fonction factorial suivante :
// Cette implémentation n'est pas correcte, ne copiez pas betement ce code. // Utilise ton brain comme dirai JCVD (t'a la ref ?) def factorial(n: Int): Int = if (n == 0) 1 else n * factorial(n - 1)
Comment va-t-elle se résoudre ?
factorial(4) if (4 == 0) 1 else 4 * factorial(4 - 1) 4 * factorial(3) 4 * (3 * factorial(2)) 4 * (3 * (2 * factorial(1))) 4 * (3 * (2 * (1 * factorial(0))) 4 * (3 * (2 * (1 * 1))) 24
Nous voyons bien que chaque itération de notre code ne converge pas avant la fin. Cela va s’accumuler sur la pile, pour ne converger qu’à la toute fin.
Essayez de lancer factorial de 100 000 : StackOverflowError. L’accumulation en attendant la résolution va exploser la pile. C’est lié uniquement à la « mauvaise » implémentation de la fonction.
Alors ok, sur ce petit exemple très mignon de FizzBuzz de 1 à 100 : on est laaaaarrrggee 🙂
Mais c’est un peu comme de se laver les dents après un repas : tu vois une fonction qui semble tailRec ? Pense à l’annoter avec @tailrec !
Cela ne vous enlève pas alors la responsabilité d’implémenter correctement une fonction Tail-Rec, qui s’exécutera sur une taille de pile constante. IntelliJ sur ce point est assez malin pour valider votre code, en plus de l’utilisation de l’annotation.
La version « tailrec » de la fonction factorial est la suivante :
// Vas-y lache toi : copier-coller. Note l'utilisation des BigInt...
def factorial(n: Int): BigInt = {
@tailrec
def iter(x: BigInt, result: BigInt): BigInt =
if (x == 0) result
else iter(x - 1, result * x)
iter(n,1)
}
L’annotation @tailrec en Scala est donc une annotation qui assure que la fonction annotée est bien Tail-Rec.
// version avec pattern matching
def factorial(n: Int): BigInt = {
@tailrec
def iter(x: BigInt, result: BigInt): BigInt = x match {
case x if x == 0 => result
case _ => iter(x - 1, result * x)
}
iter(n,1)
}
Si ce sujet vous intéresse, je vous recommande la formation FP-Tower par Julien TRUFFAUT. Il explique cela très bien dans le chapitre « Parrallel data processing » / « Recursion ». La formation est très accessible pour les personnes ayant un petit niveau en Scala. Elle ne coûte qu’environ 340 euros, et sincèrement, elle est excellente. Vous pouvez y consacrer quelques heures par ci par là, et vous pourrez vraiment progresser en programmation fonctionnelle.
Lunatech est partenaire de FP Tower, je remercie donc mon employeur, grâce à qui j’ai pu en profiter.
Il est (pas assez/trop) compliqué ton code Scala
Il existe des tonnes de façon de résoudre l’exercice. J’en ai deux autres à vous proposer, et lâchez dans les commentaires si vous voulez aussi participer.
La première c’est un peu la version « one-liner » de Scala, en utilisant Range pour générer notre séquence :
object BuzzBuzz {
def main(args: Array[String]): Unit = {
Range(1, 101).foreach {
case i if i % 15 == 0 => println("FizzBuzz")
case i if i % 5 == 0 => println("Buzz")
case i if i % 3 == 0 => println("Fizz")
case other => println(other)
}
}
}
J’aime bien cette version. Simple, aussi facile à lire que la version Java.
Et enfin une version un peu plus originale (et très bête). Je vous montre le code et on se reparle après :
object BuzzBuzz {
def main(args: Array[String]): Unit = {
Range(1,101).map(x => (x, x.toString))
.appendedAll(Range(3,101,3).map(x => (x,"Fizz")))
.appendedAll(Range(5,101,5).map(x => (x,"Buzz")))
.appendedAll(Range(15,101,15).map(x => (x,"FizzBuzz")))
.toMap
.toSeq
.sortBy(_._1)
.foreach(println)
}
}
Bien bien bien…
Je vais créer 4 listes :
- une liste de 1 à 100
- une liste de 3 à 100 en itérant de 3 en 3
- une liste de 5 à 100 en itérant de 5 en 5
- une liste de 15 à 100 en itérant de 15 en 15
Ensuite je merge ces 4 listes dans une Map. Comme l’ordre d’insertion s’applique en mappant chaque collection, je vais écraser les multiples de 5 et de 3 par les multiples de 15. Coup de bol, faut le savoir.
Ensuite je remets le tout sous la forme d’une séquence, je trie sur les indices et cela va fonctionne.
Le résultat n’est pas la consigne demandée, il manque un map, mais bon, je voulais ne pas vous perdre avec l’indice :
(1,1)
(2,2)
(3,Fizz)
(4,4)
(5,Buzz)
(6,Fizz)
(7,7)
(8,8)
(9,Fizz)
(10,Buzz)
(11,11)
(12,Fizz)
(13,13)
(14,14)
(15,FizzBuzz)
(16,16)
(17,17)
(18,Fizz)
(19,19)
(20,Buzz)
Voilà, je me suis pas mal amusé et il existe des variantes complémentaires si vous voulez « corser » un peu l’exercice.
Je vous laisse une nouvelle consigne :
« Afficher Fizz si un nombre est multiple de 3 ou s’il se termine par le chiffre 3 comme 23 »
Bonne journée !
1 comment