On se donne le type suivant pour représenter des expresssions régulières.
Voici quelques exemples d'expressions régulières, avec leur notation standard en commentaires, qui seront utilisés dans les tests :
Écrire une fonction comptant le nombre d'étoiles d'une expression régulière.
On se propose de calculer la longueur maximum d'un mot du langage associé à une expression régulière. Puisque cette longueur peut être indéfinie, on utilise le type suivant :
Donner le code de trois fonctions, calculant respectivement la somme de deux longueurs, le maximum de deux longueurs, et la longueur maximum d'un mot du langage associé à une expression régulière.
Écrire une fonction prenant une liste d'entiers en paramêtre et retournant la somme des entiers pairs de cette liste.
Nous définissons les types suivants pour représenter les prénoms :
Écrire une fonction qui prend en paramêtre une liste de prénoms, et retourne les chaînes de caractères pouvant faire office de prénoms féminins.
List.map applique une fonction à tous les éléments d'une liste. Soit $f$ une fonction à deux arguments. Écrire une fonction qui applique $f$ (donnée en paramêtre) à toutes les paires d'éléments apparaissant en même position dans deux listes (voir les exemples).
Si l'une des listes est plus longue que l'autre, les éléments excédentaires sont ignorés.
Utiliser la fonctionnelle map2 vue à la question précédente pour écrire une fonction retournant la liste des paires d'éléments consécutifs d'une liste, sans utiliser de récursion ni d'autre fonctionnelle.
2048 est le nom d'un jeu ayant récemment fait le buzz sur Internet. Il se présente sous la forme d'un damier de dimension 4x4 . Chaque case est vide, ou bien contient une seule tuile sur laquelle figure un entier. Le joueur choisit à chaque tour une des quatre directions (haut, bas, gauche, droite), et cela pousse au maximum toutes les tuiles dans cette direction. Les tuiles ne peuvent pas se superposer, mais lorsque deux tuiles de même valeur sont poussées l'une vers l'autre, elles fusionnent en une seule tuile de valeur double.
Il n'est pas utile de connaître le jeu pour résoudre les questions suivantes.
Nous représentons une position du jeu grâce aux types suivants :
L'exemple suivant nous servira à plusieurs reprises.
La première liste représente donc la ligne du haut, de gauche à droite, et ainsi de suite.
Voici le code de la fonction faisant tomber les tuiles d'une ligne vers la gauche :
Calculer le résultat de fall_line [ Some 4; None; Some 4; Some 8; None; Some 2 ], en procédant par substitutions successives.
Pour faire tomber tout le damier, il suffit de faire tomber chaque ligne indépendamment. En déduire la fonction qui prend un tableau et fait tomber les tuiles de chaque ligne vers la gauche.
Pour faire tomber les tuiles dans les autres directions, il suffit de savoir faire tourner le tableau de 90 degrés, pour se ramener à fall_leftward. Écrire une fonction effectuant une telle rotation (dans le sens horaire) du tableau.
Remarquez que la $k^\textrm{e}$ ligne après la rotation correspond à la $k^\textrm{e}$ colonne avant la rotation, en sens inverse.
Pour cette question, vous avez exceptionnellement le droit d'utiliser List.hd pour récupérer le premier élément d'une liste, et List.tl pour récupérer la queue d'une liste.
En déduire les fonctions pour faire tomber les tuiles dans les autres directions.
Seulement si vous avez fini toutes les autres questions !
Après chaque tour du joueur, une tuile est ajoutée dans une position vide choisie aléatoirement. La nouvelle tuile aura la valeur $2$ avec probabilité $0.9$, et $4$ avec probabilité $0.1$. Coder une fonction permettant l'ajout d'une tuile selon ce procédé.
