Extremum

Un petit exo sympa pour manier des itérateurs un peu avancés. Il était donné en 1A à l’Ensimag du temps où l’on faisait de l’Ada.

On dispose en entrée d’un vecteur d’entiers. On cherche à renvoyer en sortie un vecteur contenant tous les extremums locaux c’est à dire les min ou max locaux. Pour les mins locaux par exemple il s’agit de toutes les valeurs inférieurs à leurs valeurs précédentes et suivantes.

Par exemple, pour une entrée 1, 2, 3, 4, 3, 4, 2, 1, 0 on espère récupérer en sortie: 1, 4, 3, 4, 0. Là où les choses se compliquent c’est que l’on va également éliminer les répétitions. Par exemple pour 1, 2, 3, 3, 3, 3, 2, 1, 1, 3, 3 on souhaite récupérer 1, 3, 1, 3.

Je vous file un petit bout de code à compléter ici. Une fois la fonction complétée, cargo test vous permettra de savoir si votre solution est correcte.

Ce petit exo nécessite une bonne connaissance des itérateurs et quelques méthodes du trait Itertools de la crate du même nom.

Arriverez-vous à le faire sans utiliser un seul point virgule ?

Solution

Bon, voici le code de ma solution :

fn extremum(valeurs: &[u32]) -> Vec<u32> {
    valeurs
        .first()
        .into_iter()
        .chain(
            valeurs
                .iter()
                .dedup()
                .tuple_windows()
                .filter(|(a, b, c)| a.cmp(b) != b.cmp(c))
                .map(|(_, b, _)| b),
        )
        .chain(valeurs.last())
        .dedup()
        .copied()
        .collect()
}

Ça mérite sans doute quelques explications. On va commencer par la partie du milieu. La première et la dernière valeur du vecteur d’entrée sont un peu particulières, on va donc commencer par gérer toutes les autres valeurs.

            valeurs
                .iter()

On boucle sur toutes les valeurs.

                .dedup()

La méthode dedup d’itertools nous permet d’éliminer toutes les répétitions. Par exemple si notre entrée est [1, 2, 2, 2, 3, 3, 1] on va boucler uniquement sur 1, 2, 3, 1.

                .tuple_windows()
                .filter(|(a, b, c)| a.cmp(b) != b.cmp(c))
                .map(|(_, b, _)| b),

Bon, les choses se compliquent maintenant. tuple_windows est une fonction magique d’itertools. Elle permet de d’avoir une fenètre glissante de k-uplets sur tous les éléments itérés. Toujours sur notre exemple, pour k=3 on bouclerait alors sur (1, 2, 3) puis (2, 3, 1). Le truc magique c’est que la valeur de k n’est pas donnée explicitement. Elle est déduite par l’inférence de type. En effet on peut remarquer que la closure donnée au filter prend en entrée un triplet. La seule solution pour que ça fonctionne est donc k=3.

Le filtre sélectionne tous les extremums locaux d’une manière astucieuse. On termine avec le map pour ne garder que l’extremum lui même au lieu du triplet. À noter qu’un filter_map aurait très bien fait l’affaire.

C’est maintenant presque terminé, il reste à rajouter la première et la dernière valeur qui sont toujours des extremums locaux. Il y a néanmoins plusieurs cas spéciaux à gérer.

si l’entrée est vide ;
si il n’y a qu’un seul élément ;
si tous les éléments sont égaux.

    valeurs
        .first()
        .into_iter()

On commence par récupérer une Option sur la première valeur, que l’on transforme immédiatement en itérateur. Celui-ci fera donc un tour de boucle si le vecteur d’entrée n’est pas vide et 0 sinon.

        .chain(
            valeurs
                .iter()
                .dedup()
                .tuple_windows()
                .filter(|(a, b, c)| a.cmp(b) != b.cmp(c))
                .map(|(_, b, _)| b),
        )
        .chain(valeurs.last())

On chaine ensuite avec l’itérateur sur les extremums médians puis sur l’Option sur la dernière valeur (chain accepte IntoIterator).

        .dedup()

On appelle encore une fois dedup pour éviter le dernier cas pathologique: le cas où l’entrée ne contient qu’une seule valeur répétée dans tout le vecteur.

        .copied()
        .collect()

Il ne reste maintenant plus qu’à transformer les références en entiers et à collecter dans un vecteur.

Je trouve ce code très beau et très rustien. Aucune conditionnelle en vue. L’exo initial en Ada était un cauchemard rempli de conditions dans tous les sens.

Si vous avez quelque chose de proche, félicitations. Ça me parait déjà d’un niveau avancé.