Puzzles algorithmes (1) - correction#

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é.

Produits scalaires#

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.

[1]:

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.

[2]:

from IPython.core.display import Image

Image("inter.png", width=500)

[2]:

../../_images/practice_tds-algo_puzzle_algo_1_correction_7_0.png

[3]:

# 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)]

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.

[4]:

from IPython.core.display import Image

Image("priso.png", width=450)

[4]:

../../_images/practice_tds-algo_puzzle_algo_1_correction_11_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.

[ ]:

Notebook on github