# AP3 — Défis ★

## Avant de commencer

Ce notebook est facultatif. Commencez par le tronc commun du cycle AP1–AP3,
puis choisissez un défi si vous souhaitez approfondir. Une recherche expliquée
et testée peut être jointe au rendu du 6 décembre 2026 pour un bonus ; elle
n'est pas nécessaire pour valider le minimum demandé.

Ces défis sont volontairement exigeants : énoncés brefs, pas de recette à
appliquer. Nous avons rencontré la récursion, les clauses et les guards ;
`Enum` sera approfondi en AP4. Il s'agit maintenant de chercher avec ces outils. Prenez-les dans le désordre si vous
voulez, sautez, revenez. Le dernier résiste à un très bon élève une bonne
heure, à finir chez soi s'il le faut.

Si vous séchez une heure, n'y voyez pas de la lenteur : c'est plutôt que ça
travaille. Les vérifications testent des **propriétés** : plusieurs cas, des
cas limites, des invariants, des allers-retours. On ne peut pas y coller une
valeur recopiée, il faut que la fonction soit *juste*.

Contrainte de jeu : vous pouvez utiliser les modules, `def`/`defp`, les clauses,
les guards `when`, la récursion
(avec ou sans accumulateur), ainsi que `Enum` et `Stream` si vous les connaissez.
Pour chaque défi, un outil vous est interdit : celui qui donnerait
la réponse directement. Ce qui
nous intéresse, c'est que vous sachiez écrire vous-même ce que cet outil
fait à votre place.

## Défi 1 — La racine numérique

La **racine numérique** d'un entier positif : on additionne ses chiffres, et
on recommence sur le résultat, jusqu'à obtenir un seul chiffre. Par
exemple `12345` donne `1+2+3+4+5 = 15`, puis `1+5 = 6`.

Écrivez `Racine.de/1` qui la calcule par récursion, pour tout entier
`n ≥ 0`. Interdit : convertir en chaîne (`Integer.digits`, `to_string`,
`String.*`). Vous n'avez que `div`, `rem` et la récursion.

```elixir
defmodule Racine do
  # À COMPLÉTER : de(n) renvoie la racine numérique de n (un chiffre 0..9).
  # Piste : une fonction pour SOMMER les chiffres (récursion sur div/rem),
  # puis de/1 qui se rappelle tant que le résultat a plus d'un chiffre.
  def de(n) do
    nil
  end
end
```

Vérification :

```elixir
if Code.ensure_loaded?(Racine) do
  # référence indépendante : la racine numérique a une formule fermée
  ref = fn
    0 -> 0
    n -> 1 + rem(n - 1, 9)
  end

  cas = [0, 1, 9, 10, 18, 99, 100, 12_345, 999_999, 2_024]

  for n <- cas do
    obtenu = Racine.de(n)

    if obtenu != ref.(n) do
      raise "Racine.de(#{n}) a renvoyé #{inspect(obtenu)}, attendu #{ref.(n)}"
    end

    # propriété : le résultat est TOUJOURS un seul chiffre
    if obtenu < 0 or obtenu > 9 do
      raise "Racine.de(#{n}) = #{inspect(obtenu)} n'est pas un chiffre 0..9"
    end
  end

  # propriété d'idempotence : appliquer la racine à une racine ne change rien
  for n <- cas do
    r = Racine.de(n)

    if Racine.de(r) != r do
      raise "Racine.de est censée être idempotente sur un chiffre : de(#{r}) devrait valoir #{r}"
    end
  end

  IO.puts("✅ Racine numérique correcte, toujours un chiffre, et idempotente")
else
  IO.puts("ℹ️  Définissez d'abord le module Racine, puis réévaluez cette vérification.")
end
```

> En une phrase : votre `de/1` se rappelle elle-même. **Pourquoi s'arrête-t-elle
> toujours** ? (Indice : à chaque appel récursif, quelle quantité diminue
> strictement, et pourquoi ne peut-elle pas descendre indéfiniment ?)
>
> Votre réponse : …

## Défi 2 — Le minimum ET le maximum, en un seul passage

Trouver le minimum d'une liste demande un parcours, et le maximum un autre :
on parcourt donc naturellement la liste deux fois. Ici, on vous en demande un
seul.

Écrivez `Extremes.de/1` qui, pour une liste **non vide** d'entiers, renvoie
le tuple `{min, max}` en parcourant la liste une seule fois. Interdit :
`Enum.min`, `Enum.max`, `Enum.min_max`, et parcourir deux fois. Utilisez soit
la récursion avec un **accumulateur en tuple** `{min_courant, max_courant}`,
soit **un seul** `Enum.reduce/3` dont l'accumulateur est ce tuple.

```elixir
defmodule Extremes do
  # À COMPLÉTER : de(liste) -> {min, max}, UN seul parcours, liste non vide.
  # Piste : l'accumulateur porte à la fois le min et le max vus jusqu'ici.
  #   Bon point de départ : le premier élément est à la fois min et max.
  def de(liste) do
    nil
  end
end
```

Vérification :

```elixir
if Code.ensure_loaded?(Extremes) do
  cas = [
    [42],
    [3, 1, 4, 1, 5, 9, 2, 6],
    [-5, -1, -100, -3],
    [7, 7, 7, 7],
    [0, 1_000_000, -1_000_000, 500]
  ]

  for liste <- cas do
    obtenu = Extremes.de(liste)
    attendu = {Enum.min(liste), Enum.max(liste)}

    if obtenu != attendu do
      raise "Extremes.de(#{inspect(liste)}) a renvoyé #{inspect(obtenu)}, attendu #{inspect(attendu)}"
    end
  end

  # propriété : min <= max toujours, et les deux sont DANS la liste
  grande = Enum.to_list(1..1000) |> Enum.shuffle()
  {mn, mx} = Extremes.de(grande)

  cond do
    mn > mx -> raise "min (#{mn}) > max (#{mx}) — impossible"
    mn not in grande -> raise "le min renvoyé (#{mn}) n'appartient pas à la liste"
    mx not in grande -> raise "le max renvoyé (#{mx}) n'appartient pas à la liste"
    {mn, mx} != {1, 1000} -> raise "sur 1..1000 mélangé, attendu {1, 1000}, obtenu {#{mn}, #{mx}}"
    true -> :ok
  end

  IO.puts("✅ min et max corrects sur tous les cas, en un seul passage")
else
  IO.puts("ℹ️  Définissez d'abord le module Extremes, puis réévaluez cette vérification.")
end
```

> En une phrase : votre accumulateur `{min, max}` maintient un **invariant**
> pendant le parcours. Lequel — que garantit-il exactement sur la portion de
> liste **déjà lue**, et pourquoi cela suffit-il à conclure à la fin ?
>
> Votre réponse : …

## Défi 3 — Recoudre deux listes (votre propre `zip`)

`Enum.zip([1, 2, 3], [:a, :b, :c])` rend `[{1, :a}, {2, :b}, {3, :c}]` : il
apparie les éléments de même rang. Réimplémentez-le par récursion.

Écrivez `Couture.zip/2` qui apparie deux listes en une liste de paires. Comme
`Enum.zip`, si les listes ont des longueurs différentes, on s'arrête à la
plus courte (les éléments en trop de l'autre sont ignorés). Interdit :
`Enum.zip`, `Enum.with_index`, `List.zip`. Récursion pure, en pattern-matchant
les têtes des deux listes à la fois.

```elixir
defmodule Couture do
  # À COMPLÉTER : zip(gauche, droite) -> liste de {g, d}.
  # Combien de cas de base ? Que se passe-t-il si UNE des deux listes est vide ?
  def zip(gauche, droite) do
    nil
  end
end
```

Vérification :

```elixir
if Code.ensure_loaded?(Couture) do
  cas = [
    {[1, 2, 3], [:a, :b, :c]},
    {[1, 2, 3], [:a, :b]},
    {[1, 2], [:a, :b, :c]},
    {[], [:a, :b]},
    {[1, 2, 3], []},
    {[], []},
    {[1], [:x]}
  ]

  for {g, d} <- cas do
    obtenu = Couture.zip(g, d)
    attendu = Enum.zip(g, d)

    if obtenu != attendu do
      raise "Couture.zip(#{inspect(g)}, #{inspect(d)}) a renvoyé #{inspect(obtenu)}, attendu #{inspect(attendu)}"
    end
  end

  # propriété de longueur : la sortie a la longueur de la plus courte entrée
  g = Enum.to_list(1..50)
  d = Enum.to_list(1..30)
  sortie = Couture.zip(g, d)

  if length(sortie) != 30 do
    raise "zip de listes de longueurs 50 et 30 devrait donner 30 paires, obtenu #{length(sortie)}"
  end

  # propriété : chaque paire respecte l'ordre {élément de gauche, élément de droite}
  if Enum.any?(sortie, fn {a, b} -> a > 30 or b > 30 end) do
    raise "une paire mélange les rangs — la couture n'apparie pas les mêmes positions"
  end

  IO.puts("✅ zip récursif correct, y compris sur les listes de longueurs inégales et vides")
else
  IO.puts("ℹ️  Définissez d'abord le module Couture, puis réévaluez cette vérification.")
end
```

> En une phrase : `zip` s'arrête « à la plus courte ». Combien de **cas de
> base** avez-vous dû écrire pour capturer cette règle, et pourquoi un seul ne
> suffit pas ?
>
> Votre réponse : …

## Défi 4 — Aplatir l'arbitrairement imbriqué

Une liste peut contenir des listes, qui contiennent des listes… à
n'importe quelle profondeur : `[1, [2, [3, 4], 5], [[6]]]`. Aplatissez-la
en `[1, 2, 3, 4, 5, 6]`.

Écrivez `Plat.aplatir/1`. Interdit : `List.flatten`, `List.wrap`. Vous
devez brancher sur la forme de la tête à chaque étape : est-ce une liste
(qu'il faut aplatir aussi) ou une valeur simple ? Les guards (`is_list/1`) et
plusieurs clauses sont vos amis.

```elixir
defmodule Plat do
  # À COMPLÉTER : aplatir(liste) -> liste à un seul niveau.
  # Réfléchissez à trois formes possibles pour la liste en cours :
  #   - vide ;
  #   - tête qui est ELLE-MÊME une liste ;
  #   - tête qui est une valeur simple.
  def aplatir(liste) do
    nil
  end
end
```

Vérification :

```elixir
if Code.ensure_loaded?(Plat) do
  cas = [
    {[], []},
    {[1, 2, 3], [1, 2, 3]},
    {[1, [2, 3], 4], [1, 2, 3, 4]},
    {[1, [2, [3, 4], 5], [[6]]], [1, 2, 3, 4, 5, 6]},
    {[[[[[7]]]]], [7]},
    {[[], [], [1], []], [1]},
    {[:a, [:b, [:c]], :d], [:a, :b, :c, :d]}
  ]

  for {entree, attendu} <- cas do
    obtenu = Plat.aplatir(entree)

    if obtenu != attendu do
      raise "Plat.aplatir(#{inspect(entree)}) a renvoyé #{inspect(obtenu)}, attendu #{inspect(attendu)}"
    end
  end

  # propriété : l'ordre est PRÉSERVÉ (de gauche à droite, profondeur d'abord)
  profond = [1, [2, [3, [4, [5, [6, [7, [8]]]]]]]]
  if Plat.aplatir(profond) != [1, 2, 3, 4, 5, 6, 7, 8] do
    raise "l'ordre n'est pas préservé sur une imbrication profonde : #{inspect(Plat.aplatir(profond))}"
  end

  # propriété : aplatir une liste DÉJÀ plate ne la change pas (idempotence en un sens)
  deja_plate = [9, 8, 7, 6]
  if Plat.aplatir(deja_plate) != deja_plate do
    raise "aplatir une liste déjà plate devrait la laisser telle quelle"
  end

  # propriété : le résultat ne contient plus AUCUNE liste
  if Enum.any?(Plat.aplatir([1, [2, [3]]]), &is_list/1) do
    raise "il reste une sous-liste dans le résultat — l'aplatissement est incomplet"
  end

  IO.puts("✅ Aplatissement correct à toute profondeur, ordre préservé, sans List.flatten")
else
  IO.puts("ℹ️  Définissez d'abord le module Plat, puis réévaluez cette vérification.")
end
```

> En une phrase : votre récursion descend dans des sous-listes **et** avance
> le long de la liste courante. Sur quel argument « plus petit » la récursion
> progresse-t-elle pour être sûre de **terminer**, alors que la profondeur
> d'imbrication, elle, n'est pas bornée à l'avance ?
>
> Votre réponse : …

## Défi 5 — Compresser, décompresser, et boucler la boucle (le gros morceau)

Le **run-length encoding** (RLE) compresse une liste en comptant les
répétitions consécutives : `[:a, :a, :a, :b, :c, :c]` devient
`[{:a, 3}, {:b, 1}, {:c, 2}]`. C'est réversible : de ces paires, on doit
pouvoir reconstruire la liste d'origine, à l'identique.

Écrivez deux fonctions dans `Rle` :

* `compresser/1` : d'une liste, rend la liste des paires `{valeur, compte}`, dans
  l'ordre, en fusionnant uniquement les répétitions consécutives (deux `:a`
  séparés par un `:b` font deux groupes, pas un) ;
* `decompresser/1` : de la liste des paires, rend la liste d'origine.

Interdit : `Enum.chunk_by`, `Enum.frequencies`, `Enum.dedup`,
`List.duplicate`, `Enum.group_by`. Récursion et/ou `Enum` de base uniquement.
Le vrai juge de paix n'est aucun de ces deux résultats pris isolément : c'est
que `decompresser(compresser(liste))` redonne `liste` pour *toute* liste,
c-à-d. un aller-retour parfait.

```elixir
defmodule Rle do
  # À COMPLÉTER (1) : compresser(liste) -> [{valeur, compte}, ...]
  #   Piste : en récursion, regarde la tête ET le sommet du groupe en cours.
  #   Que faites-vous quand la tête est égale au dernier élément vu ? Quand elle
  #   est différente ? Quand la liste est vide ?
  def compresser(liste) do
    nil
  end

  # À COMPLÉTER (2) : decompresser([{valeur, compte}, ...]) -> liste
  #   Piste : chaque paire {v, n} régénère n copies de v. Sans List.duplicate,
  #   comment fabriquez-vous n copies par récursion ?
  def decompresser(paires) do
    nil
  end
end
```

Vérification :

```elixir
if Code.ensure_loaded?(Rle) do
  # 1) compresser sur des cas connus
  cas_compresser = [
    {[], []},
    {[:a], [{:a, 1}]},
    {[:a, :a, :a], [{:a, 3}]},
    {[:a, :a, :b, :c, :c], [{:a, 2}, {:b, 1}, {:c, 2}]},
    # PIÈGE : deux groupes de :a séparés par :b -> surtout PAS {:a, 3}
    {[:a, :b, :a], [{:a, 1}, {:b, 1}, {:a, 1}]},
    {[1, 1, 2, 2, 2, 1], [{1, 2}, {2, 3}, {1, 1}]}
  ]

  for {entree, attendu} <- cas_compresser do
    obtenu = Rle.compresser(entree)

    if obtenu != attendu do
      raise "Rle.compresser(#{inspect(entree)}) a renvoyé #{inspect(obtenu)}, attendu #{inspect(attendu)}"
    end
  end

  # 2) decompresser sur des cas connus
  cas_decompresser = [
    {[], []},
    {[{:a, 3}], [:a, :a, :a]},
    {[{:a, 2}, {:b, 1}, {:c, 2}], [:a, :a, :b, :c, :c]},
    {[{:x, 1}, {:y, 1}], [:x, :y]}
  ]

  for {entree, attendu} <- cas_decompresser do
    obtenu = Rle.decompresser(entree)

    if obtenu != attendu do
      raise "Rle.decompresser(#{inspect(entree)}) a renvoyé #{inspect(obtenu)}, attendu #{inspect(attendu)}"
    end
  end

  # 3) LE juge de paix : l'aller-retour, sur des listes variées et générées
  listes_test = [
    [],
    [:seul],
    [:a, :a, :a, :a],
    [:a, :b, :a, :b, :a],
    [1, 1, 2, 3, 3, 3, 1, 1],
    Enum.map(1..200, fn i -> rem(div(i, 7), 3) end),
    Enum.map(1..500, fn _ -> Enum.random([:x, :y, :z]) end)
  ]

  for liste <- listes_test do
    retour = Rle.decompresser(Rle.compresser(liste))

    if retour != liste do
      raise """
      Aller-retour cassé : decompresser(compresser(l)) ≠ l.
      Sur l = #{inspect(Enum.take(liste, 12))}#{if length(liste) > 12, do: " (…tronqué)", else: ""}
      obtenu #{inspect(Enum.take(retour, 12))}#{if length(retour) > 12, do: " (…tronqué)", else: ""}.
      """
    end
  end

  # 4) propriété : aucun compte n'est nul ou négatif, et deux groupes voisins
  #    n'ont jamais la même valeur (sinon la compression est incomplète)
  compresse = Rle.compresser([:a, :a, :b, :b, :b, :a])

  if Enum.any?(compresse, fn {_v, n} -> n <= 0 end) do
    raise "un compte <= 0 est apparu dans la compression : #{inspect(compresse)}"
  end

  paires_voisines_identiques =
    compresse
    |> Enum.zip(Enum.drop(compresse, 1))
    |> Enum.any?(fn {{v1, _}, {v2, _}} -> v1 == v2 end)

  if paires_voisines_identiques do
    raise "deux groupes voisins ont la même valeur (#{inspect(compresse)}) — un groupe aurait dû être fusionné"
  end

  IO.puts("✅ RLE complet : compression, décompression, et aller-retour parfait sur toutes les listes")
else
  IO.puts("ℹ️  Définissez d'abord le module Rle (les deux fonctions), puis réévaluez cette vérification.")
end
```

> En une phrase : le seul test qui compte vraiment ici est
> `decompresser(compresser(l)) == l`. Pourquoi cet **aller-retour** est-il un
> juge bien plus sévère que de vérifier `compresser` et `decompresser`
> séparément sur quelques exemples ?
>
> Votre réponse : …