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)}\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