2A.algo - Puzzles algorithmes (1) - correction#

Links: notebook, html, python, slides, GitHub

Eléments de réponses pour des puzzles algorithmiques tirés de Google Code Jam et autres sites équivalents, produits scalaires, problèmes de recouvrements, soudoyer les prisonniers, découpage stratifié.

from jyquickhelper import add_notebook_menu
add_notebook_menu()

Produits scalaires#

Le problème est tiré de Google Jam 2008, round 1A.

On considère deux tableaux v=(v_1,..., v_n) et w=(w_1,...,w_n). On souhaite le minimum : \min_{\sigma,\sigma'} \sum_{i=1}^{n} v_{\sigma(i)} w_{\sigma'(i)} où \sigma,\sigma' sont deux permutations de l’ensemble [[1,...,n]].

Problème de recouvrement#

Première solution#

Elle est inspiré de la distance d’édition. Si on doit recouvrir l’ensemble des entiers [[0,n]], on passe en revue tous les intervalles qui inclut 0. On construit deux tableaux :

  • entier[i] : conserve le nombre minimum d’intervalles pour couvrir tous les entiers de 0 à i

  • pred[i] : conserver le dernier intervalle utilisé pour recouvrir i

On commence par initialiser entier[0] en passant en revue tous les intervalles qui inclut 0. Pour trouver entier[i+1], on passe en revue tous les intervalles [a,b], et on affirme que:

entier[n+1] = \min \{ entier[a] + 1 \; si \; a \leqslant n+1 \leqslant b \}

Le tableau pred[n+1] conserve l’intervalle qui minimise le problème de minimisation précédent.

Une fois les tableaux entier et pred renseigné, on utilise le tableaux pred pour retrouver la solution.

def recouvrement(B, intervalles) :
    # initialisation
    entier = {}
    pred   = {}
    for a,b in intervalles:
        if 0 <= a <= B :
            for k in range(0,b+1):
                entier[k] = 1
                pred [k] = (a,b)

    # programmation dynamique
    i = 0
    while i <= B:
        mini = None
        best = None
        for a,b in intervalles:
            if a <= i <= b:
                a = max(0,a)
                for l in range(a, b+1):
                    if l in entier:
                        d = entier[l] + 1
                        if mini is None or d < mini:
                            mini = d
                            best = (a,b)
        entier[i] = d
        pred[i] = best
        i += 1

    # on retourne la solution
    if B in entier:
        sol = []
        while B > 0:
            p = pred[B]
            m = max(0,p[0])
            sol.append ( p )
            B = p[0]
        sol.reverse()
        return sol
    else:
        # la solution n'existe pas
        return None

b = 1
intervalles = [ (-1, 0), (0,1), (0,0) ]
print("sol=",recouvrement(b, intervalles))

sol= [(0, 1)]

Seconde solution#

Ce programme améliore la solution précédente.

from IPython.core.display import Image
Image("inter.png", width=500)
../_images/td2a_correction_session_6A_8_0.png 
# solution par Benjamin DONNOT
def solve(B, intervalles):
    res = []
    upper = 0
    while True:
        aux = []
        for x in intervalles :
            if x[0] <= upper:
                aux.append ( x )

        new_intervalles = []
        for x in intervalles :
            new_intervalles.append ( x )
        intervalles = new_intervalles

        if (aux ==[]) :
            return '0\n'

        mymax = max(aux,key=lambda x: x[1])
        res.append(mymax)
        upper = mymax[1]
        if(upper >= B):
            break

    return res

b = 1
intervalles = [ (-1, 0), (0,1), (0,0) ]
print("sol=",solve(b, intervalles))

sol= [(0, 1)]

Vous pouvez observer le déroulement de ces deux solutions sur PythonTutor.

Soudoyer les prisonniers#

Problem C. Bribe the Prisoners

Approche par programmation dynamique#

Une observation fondamentale à faire pour ce problème est la suivante. Imaginons qu’un oracle nous donne le nombre de pièces d’or minimum à dépenser pour toutes les prisons contenant strictement moins de P cellules et strictement moins de Q prisonniers. On peut alors r´esoudre notre problème par :

\min_{q \in Q} \left[ G(1,q-1) + G(q+1, P) + P - 1 \right]

On va donc utiliser cette observation pour calculer la quantité cherchée récursivement. D’autre part, afin d’éviter de refaire les calculs plusieurs fois, on va mémoriser les réponses.

from IPython.core.display import Image
Image("priso.png", width=450)
../_images/td2a_correction_session_6A_13_0.png

Découpage intelligent d’une base de données#

Voir GroupKFold, découpage stratifié d’une base de données ou stratified sampling.