%%bash
cat << EOF
AA AA AA AA AA AA B                    ;
AA AA AA AA AA AA B                    ;
EOF > /tmp/test_nongreedy_optimal.txt

cat /tmp/test_nongreedy_optimal.txt

%%bash
cat << EOF
AA AA AA AA AA AA B AA AA AA AA AA AA ;
B                                     ;
EOF > test_greedy_suboptimal.txt

cat /tmp/test_greedy_suboptimal.txt

"""
Explanation: <h1>Table de matières<span class="tocSkip"></span></h1>
<div class="toc"><ul class="toc-item"><li><span><a href="#Un-exercice-d'algorithmique---mise-en-page-de-paragraphe,-résolutions-gourmande-et-dynamique" data-toc-modified-id="Un-exercice-d'algorithmique---mise-en-page-de-paragraphe,-résolutions-gourmande-et-dynamique-1"><span class="toc-item-num">1&nbsp;&nbsp;</span>Un exercice d'algorithmique - mise en page de paragraphe, résolutions gourmande et dynamique</a></span><ul class="toc-item"><li><span><a href="#Question-1." data-toc-modified-id="Question-1.-1.1"><span class="toc-item-num">1.1&nbsp;&nbsp;</span>Question 1.</a></span><ul class="toc-item"><li><span><a href="#Réponse-:-non-!" data-toc-modified-id="Réponse-:-non-!-1.1.1"><span class="toc-item-num">1.1.1&nbsp;&nbsp;</span>Réponse : non !</a></span></li><li><span><a href="#Contre-exemple-de-taille-fixée" data-toc-modified-id="Contre-exemple-de-taille-fixée-1.1.2"><span class="toc-item-num">1.1.2&nbsp;&nbsp;</span>Contre exemple de taille fixée</a></span></li><li><span><a href="#Faire-croître-la-différence-entre-les-deux-coûts-vers-l'infini" data-toc-modified-id="Faire-croître-la-différence-entre-les-deux-coûts-vers-l'infini-1.1.3"><span class="toc-item-num">1.1.3&nbsp;&nbsp;</span>Faire croître la différence entre les deux coûts vers l'infini</a></span></li><li><span><a href="#Bonus-:-faire-croître-le-rapport-vers-l'infini-?" data-toc-modified-id="Bonus-:-faire-croître-le-rapport-vers-l'infini-?-1.1.4"><span class="toc-item-num">1.1.4&nbsp;&nbsp;</span>Bonus : faire croître le <em>rapport</em> vers l'infini ?</a></span></li><li><span><a href="#Code-Python-pour-la-méthode-gloutonne" data-toc-modified-id="Code-Python-pour-la-méthode-gloutonne-1.1.5"><span class="toc-item-num">1.1.5&nbsp;&nbsp;</span>Code Python pour la méthode gloutonne</a></span></li><li><span><a href="#Exemples" data-toc-modified-id="Exemples-1.1.6"><span class="toc-item-num">1.1.6&nbsp;&nbsp;</span>Exemples</a></span></li></ul></li><li><span><a href="#Question-2." data-toc-modified-id="Question-2.-1.2"><span class="toc-item-num">1.2&nbsp;&nbsp;</span>Question 2.</a></span><ul class="toc-item"><li><span><a href="#Problème-d'optimisation-à-résoudre" data-toc-modified-id="Problème-d'optimisation-à-résoudre-1.2.1"><span class="toc-item-num">1.2.1&nbsp;&nbsp;</span>Problème d'optimisation à résoudre</a></span></li><li><span><a href="#Relation-de-récurrence" data-toc-modified-id="Relation-de-récurrence-1.2.2"><span class="toc-item-num">1.2.2&nbsp;&nbsp;</span>Relation de récurrence</a></span></li><li><span><a href="#Implémentation-naïve-par-mémoïsation" data-toc-modified-id="Implémentation-naïve-par-mémoïsation-1.2.3"><span class="toc-item-num">1.2.3&nbsp;&nbsp;</span>Implémentation naïve par mémoïsation</a></span></li><li><span><a href="#Exemples" data-toc-modified-id="Exemples-1.2.4"><span class="toc-item-num">1.2.4&nbsp;&nbsp;</span>Exemples</a></span></li></ul></li><li><span><a href="#Question-3." data-toc-modified-id="Question-3.-1.3"><span class="toc-item-num">1.3&nbsp;&nbsp;</span>Question 3.</a></span></li><li><span><a href="#Question-4.-Pourquoi-un-coût-cubique-et-pas-linéaire-?" data-toc-modified-id="Question-4.-Pourquoi-un-coût-cubique-et-pas-linéaire-?-1.4"><span class="toc-item-num">1.4&nbsp;&nbsp;</span>Question 4. Pourquoi un coût cubique et pas linéaire ?</a></span></li><li><span><a href="#Conclusion" data-toc-modified-id="Conclusion-1.5"><span class="toc-item-num">1.5&nbsp;&nbsp;</span>Conclusion</a></span></li></ul></li></ul></div>

Un exercice d'algorithmique - mise en page de paragraphe, résolutions gourmande et dynamique

Source : http://lacl.fr/~lpellissier/Algo1/TD3.pdf, auteur : Luc Pélissier (2020-21).

Le problème étudié est l’impression équilibrée d’un paragraphe sur une imprimante.
Le texte d’entrée est modélisé comme une séquence de $n$ mots de longueurs $l_1,l_2, \dots, l_n$ (mesurées en caractères, que l'on suppose tous de même largeur - c'est le cas par exemple avec une police dite à chasse fixe).
On souhaite imprimer ce paragraphe de manière équilibrée sur un certain nombre de lignes qui contiennent un maximum de $M\geq1$ caractères chacune.
Le critère d’équilibre est le suivant :
Si une ligne donnée contient les mots $i$ à $j$ (avec $i \leq j$) et qu’on laisse exactement une espace entre deux mots, le nombre de caractères d’espacements supplémentaires à la fin de la ligne est $f(M - j+i - \sum\limits_{k=i}^j l_k)$, qui doit être positif ou nul pour que les mots tiennent sur la ligne.
L’objectif est de minimiser la somme, sur toutes les lignes hormis la dernière, des cubes des nombres de caractères d’espacement présents à la fin de chaque ligne : cela correspond à $f(s) = s^3$.

Auteur: Lilian Besson
Date : jeudi 04/02/2021
Licence : MIT
Lien : https://github.com/Naereen/notebooks/tree/master/agreg/

Remarque : pour bien visualiser ces espaces en fin de fichier, je termine chaque ligne par ;.

Question 1.
1. Est-ce que l’algorithme glouton consistant à remplir les lignes une à une en mettant à chaque fois le maximum de mots possibles sur la ligne en cours, fournit l’optimum ?
Réponse : non !
Contre exemple de taille fixée
Comme le coût est la somme des cubes d'espaces en fin de ligne, on peut penser à un contre-exemple qui va exploiter le fait que $(2x)^3 >> 2 x^3$, et produire un texte qui aura deux lignes identiques (avec $k$ espaces en fin de lignes) lorsqu'on le met en page optimalement, et une ligne quasi complète mais une deuxième ligne quasi vide :
End of explanation
"""


%%bash
clear
for file in /tmp/test_*txt; do
    echo $file
    hr
    cat $file
    hr
    n=0
    echo $n
    for line in $(cat $file | grep -o ' *;' | sed s/';'/''/g | tr ' ' 'X'); do
        echo $line; i=$(echo $line | wc -c)
        i=$((i-1))
        echo "n = $n, i = $i"; n=$((n + i*i*i))
        echo "=> n = $n, i = $i"
    done
done

"""
Explanation: Pour l'instant, j'ai codé ça vite fait en Bash pour calculer le coût des deux fichiers :
End of explanation
"""


from typing import Tuple, List

def longueur_ligne(ligne: List[str]) -> int:
    return sum(len(mot) for mot in ligne)

def mise_en_page_paragraphe_gloutonne(longueur_max:int, mots: List[str]) -> List[List[str]]:
    print(f"Longueur maximum de la ligne = {longueur_max}")
    print(f"Longueur des mots = {longueurs_mots}")
    
    assert all(
        1 <= len(mot) <= longueur_max
        for mot in mots
    )
    
    mots = list(mots)[::-1]  # on les lit de la fin

    paragraphes = []
    ligne_actuelle = []
    longueur_ligne_actuelle = 0

    while mots:
        # print(f"mots = {mots}")
        mot_a_placer = mots.pop()
        # print(f"  mot_a_placer = {mot_a_placer}")
        # print(f"  ligne_actuelle = {ligne_actuelle}")
        
        if longueur_ligne(ligne_actuelle) + len(mot_a_placer) <= longueur_max:
            ligne_actuelle += [mot_a_placer]
            longueur_ligne_actuelle += len(mot_a_placer)
            if longueur_ligne_actuelle < longueur_max:
                ligne_actuelle += [" "]
                longueur_ligne_actuelle += 1

        # 1 + car on ajoute l'espace
        if longueur_ligne_actuelle + 1 >= longueur_max:
            paragraphes.append(ligne_actuelle)
            ligne_actuelle = []
            longueur_ligne_actuelle = 0

        # print(f"  ligne_actuelle = {ligne_actuelle}")
        # print(f"  paragraphes = {paragraphes}")
    
    # dernière ligne si pas encore ajoutée
    if ligne_actuelle:
        paragraphes.append(ligne_actuelle)

    # puis on complète avec des espaces en fin de lignes
    for ligne in paragraphes:
        espaces_fin_paragraphe = longueur_max - longueur_ligne(ligne)
        ligne += [" "] * espaces_fin_paragraphe
    
    assert all(
        longueur_ligne(ligne) == longueur_max
        for ligne in paragraphes
    )
    return paragraphes

def print_paragraphes(paragraphes: List[List[str]]):
    print(f"\n# Mise en page finale d'un texte de {len(paragraphes)} lignes ")
    for ligne in paragraphes:
        print("".join(ligne) + ";")

from typing import Callable

def cout_paragraphes(paragraphes: List[List[str]], cout: Callable[[int], int]) -> int:
    lignes = [ "".join(ligne) for ligne in paragraphes ]
    espaces_de_fin = [
        len(ligne) - len(ligne.rstrip())
        for ligne in lignes
    ]
    return sum(cout(es) for es in espaces_de_fin)

def print_couts(paragraphes):
    print("- Nombre d'espaces en fin de lignes =", cout_paragraphes(paragraphes, cout= lambda i: i))
    print("- Somme des carrés des nombres d'espaces en fin de lignes =", cout_paragraphes(paragraphes, cout= lambda i: i**2))
    print("- Somme des cubes des nombres d'espaces en fin de lignes =", cout_paragraphes(paragraphes, cout= lambda i: i**3))

"""
Explanation: On voit que la solution gourmande a un coût de 54873 alors que la solution non gourmande (optimale) a un coût de 16000.
Faire croître la différence entre les deux coûts vers l'infini
On peut juste produire $n$ fois ces deux lignes, et le coût de la solution gourmande sera $54873 n$ et le coût optimal sera $16000 n$.
Cela montre que la différence entre les deux coûts n'est pas bornée.
Bonus : faire croître le rapport vers l'infini ?
On devrait pouvoir aussi faire croître le rapport des deux coûts vers l'infini : plutôt que de générer ces $n$ lignes identiques, on a juste à augmenter la longueur de ces lignes (et n'en avoir que deux, mais très longues).
Comme le coût est cubique en le nombre d'espaces, on aura bien un rapport non borné entre le coût gourmand (sous optimal) et le coût optimal.
Corollaire : cela montre que la solution gourmande n'est pas un k-approximation du problème étudié.
Code Python pour la méthode gloutonne
Même si elle n'est pas efficace, on va commencer par écrire cette méthode gloutonne :
End of explanation
"""


longueur_max = len("AA AA ")  # sans le ;
mots = ["AA", "AA", "AA", "B"]

paragraphes = mise_en_page_paragraphe_gloutonne(longueur_max, mots)

print_paragraphes(paragraphes)
print_couts(paragraphes)

"""
Explanation: Exemples
Un premier exemple simple :
End of explanation
"""


cat /tmp/test_greedy_suboptimal.txt

longueur_max = len("AA AA AA AA AA AA AA AA AA AA AA AA AA ")  # sans le ;
mots = ["AA"]*13 + ["B"]*1

"""
Explanation: Peut-on retrouver la solution suivante, qui avait été calculée à la main ?
End of explanation
"""


paragraphes = mise_en_page_paragraphe_gloutonne(longueur_max, mots)

print_paragraphes(paragraphes)
print_couts(paragraphes)

"""
Explanation: Vérifions cela :
End of explanation
"""


from typing import List, Tuple

from functools import lru_cache as memoize

couts = {
    "lineaire": lambda i: i,
    "quadratique": lambda i: i**2,
    "cubique": lambda i: i**3,
}

@memoize(maxsize=None)
def mise_en_page_paragraphe(
        longueur_max:int,
        mots: Tuple[str],
        choix_cout: str="cubique",
    ) -> List[List[str]]:
    print(f"Longueur maximum de la ligne = {longueur_max}")
    mots = list(mots)
    print(f"Longueur des mots = {mots}")
    
    assert len(mots) > 0
    if len(mots) == 1:
        return [ [mots[0]] ]
    
    else:
        cout = couts[choix_cout]
        
        # première possibilité, on regroupe les deux premiers mots ensemble
        mots1 = [mots[0] + " " + mots[1]] + mots[2:]
        cout1 = float('+inf')
        if len(mots1[0]) <= longueur_max:
            solution1 = mise_en_page_paragraphe(longueur_max, tuple(mots1))
            cout1 = cout_paragraphes(solution1, cout)
        
        # deuxième possibilité, on place mots[0] tout seul, et on résoud les autres mots
        sous_solution2 = mise_en_page_paragraphe(longueur_max, tuple(mots[1:]))
        morceau_gauche2 = [ mots[0] ] + [" "] * (longueur_max - len(mots[0]))
        solution2 = [ morceau_gauche2 ] + sous_solution2
        cout2 = cout_paragraphes(solution2, cout)

        if cout1 < cout2:
            recombinaison_1 = []
            for ligne in solution1:
                mots_ici = "".join(ligne).split(" ")
                ligne_ici = [ mots_ici[0] ]
                for mot in mots_ici[1:]:
                    if mot:
                        ligne_ici += [" ", mot] 
                ligne_ici += [" "] * (longueur_max - longueur_ligne(ligne_ici))
                recombinaison_1.append(ligne_ici)
            return recombinaison_1
        else:
            recombinaison_2 = solution2
            return recombinaison_2

"""
Explanation: Question 2.
2. Donner un algorithme de programmation dynamique résolvant le problème. Analyser sa complexité en temps et en espace. Et implémenter le dans le langage de votre choix. Vérifier qu'il donne la réponse optimale sur l'exemple trouvé en question 1. (ou en tous cas, une meilleure réponse).
On va déjà écrire le problème d'optimisation à résoudre, puis une relation de récurrence.
En écrivant un algorithme récursif naïf mais avec mémoïsation, on obtiendra un algorithme de programmation dynamique.
Problème d'optimisation à résoudre
On se donne $M\in\mathbb{N}^$ la taille de ligne, et un nombre $N\in\mathbb{N}^$ objets, de longueurs $l_k \in [1,\dots,M]$.
On souhaite minimiser le coût suivant, qui dépend de :

$L$ nombre de ligne,
$\forall x \in{1,\dots,L-1}, \ell_x$ indique l'indice de fin des mots présents en ligne $x$. Avec $\ell_0 = 0$ pour indiquer une ligne 0 vide.

$$
    \min_{
            L\in{1,\dots,M}, \
            \ell_1,\dots,\ell_{L-1}\in{1,\dots,N},\
            \forall x\in{1,\dots,L-1}, \ell_{x+1} \geq \ell_x + 1,
        }
        \sum_{x=1}^{L-1}
        (M - \ell_{x+1} + \ell_x - \sum_{k=\ell_x}^{\ell_{x+1}} l_k)^3
$$

On ne compte pas les espaces de la dernière ligne, d'où le L-1 dans la somme.

Relation de récurrence
Initialisation :
S'il n'y a qu'un seul mot, la solution est triviale : on le place sur la première ligne, et on a terminé.
Hérédité :
On considère le premier mot $l_1$ et le deuxième mot $l_2$.
Le coût de la solution optimale est le minimum des coûts des deux solutions optimales aux sous-problèmes suivants (de taille strictement plus petite) :

on place les deux premiers mots ensemble, et on remplace donc $l_1,l_2$ par $l_1' := l_1 + l_2 + 1$, et la suite des mots est juste décalée : $l_k' := l_{k+1}$. Ce cas a $N-1$ mots ;
on place le premier mot sur sa propre ligne (cas de base), et on résound avec les mots restants : $l_k' := l_{k+1}$. Ce cas a aussi $1$ et $N-1$ mots sur les deux sous-problèmes.

TODO
Implémentation naïve par mémoïsation
End of explanation
"""


longueur_max = len("AA AA AA")

mots = ["AA", "AA", "AA", "B"]
mots = tuple(mots)  # pour le rendre Hashable pour le @memoize

"""
Explanation: Exemples
End of explanation
"""


paragraphes = mise_en_page_paragraphe(longueur_max, mots)

print_paragraphes(paragraphes)
print_couts(paragraphes)

"""
Explanation: Vérifions cela :
End of explanation
"""


cat /tmp/test_nongreedy_optimal.txt

longueur_max = len("AA AA AA AA AA AA B                   ")

mots = (["AA"]*6 + ["B"]*1) * 2
mots = tuple(mots)  # pour le rendre Hashable pour le @memoize

"""
Explanation: Peut-on retrouver la solution suivante, qui avait été calculée à la main ?
End of explanation
"""


paragraphes = mise_en_page_paragraphe_gloutonne(longueur_max, mots)

print_paragraphes(paragraphes)
print_couts(paragraphes)

"""
Explanation: Vérifions cela :
End of explanation
"""


paragraphes = mise_en_page_paragraphe(longueur_max, mots)

print_paragraphes(paragraphes)
print_couts(paragraphes)

"""
Explanation: Et pour la solution dynamique :
End of explanation
"""


paragraphes = mise_en_page_paragraphe(longueur_max, mots, choix_cout="quadratique")

print_paragraphes(paragraphes)
print_couts(paragraphes)

"""
Explanation: Question 3.
3. Supposons que pour la fonction de coût à minimiser, on ait simplement choisi la somme des nombres de caractères d’espacement présents à la fin de chaque ligne. Est-ce que l’on peut faire mieux en complexité que pour la question ?
Oui la solution gourmande, qui est donc au plus linéaire en temps et demande une mémoire de travail supplémentaire constante (ou bornée par la taille du plus long mot, selon de savoir si len(mot) est en $O(1)$ ou en $O(|\text{mot}|)$), sera optimale.

Question 4. Pourquoi un coût cubique et pas linéaire ?
4. (Plus informel) Qu’est-ce qui à votre avis peut justifier le choix de prendre les cubes plutôt quesimplement les nombres de caractères d’espacement en fin de ligne ?
Si le coût est linéaire, alors la solution gourmande sera optimale (ou en tous cas une approximation à facteur constant).
Mais c'est aussi que l'affichage ne fera pas de différence entre les deux exemples ci dessous, alors que l'on est clairement plus satisfait du rendu visuel du deuxième, qui équilibre mieux les deux lignes.
(je ne suis pas trop sûr de tout ça)
TODO mieux expliquer !
On peut vérifier la solution trouvée avec un coût carré et pas cubique :
End of explanation
"""


