.. _td2acorrectionsession6Arst: ============================================== 2A.algo - Puzzles algorithmes (1) - correction ============================================== .. only:: html **Links:** :download:`notebook `, :downloadlink:`html `, :download:`python `, :downloadlink:`slides `, :githublink:`GitHub|_doc/notebooks/td2a_algo/td2a_correction_session_6A.ipynb|*` 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é. .. code:: ipython3 from jyquickhelper import add_notebook_menu add_notebook_menu() .. contents:: :local: Produits scalaires ------------------ Le problème est tiré de `Google Jam 2008, round 1A `__. On considère deux tableaux :math:`v=(v_1,..., v_n)` et :math:`w=(w_1,...,w_n)`. On souhaite le minimum : :math:`\min_{\sigma,\sigma'} \sum_{i=1}^{n} v_{\sigma(i)} w_{\sigma'(i)}` où :math:`\sigma,\sigma'` sont deux permutations de l’ensemble :math:`[[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 :math:`[[0,n]]`, on passe en revue tous les intervalles qui inclut 0. On construit deux tableaux : - :math:`entier[i]` : conserve le nombre minimum d’intervalles pour couvrir tous les entiers de :math:`0` à :math:`i` - :math:`pred[i]` : conserver le dernier intervalle utilisé pour recouvrir :math:`i` On commence par initialiser :math:`entier[0]` en passant en revue tous les intervalles qui inclut 0. Pour trouver :math:`entier[i+1]`, on passe en revue tous les intervalles :math:`[a,b]`, et on affirme que: :math:`entier[n+1] = \min \{ entier[a] + 1 \; si \; a \leqslant n+1 \leqslant b \}` Le tableau :math:`pred[n+1]` conserve l’intervalle qui minimise le problème de minimisation précédent. Une fois les tableaux :math:`entier` et :math:`pred` renseigné, on utilise le tableaux :math:`pred` pour retrouver la solution. .. code:: ipython3 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)) .. parsed-literal:: sol= [(0, 1)] Seconde solution ~~~~~~~~~~~~~~~~ Ce programme améliore la solution précédente. .. code:: ipython3 from IPython.core.display import Image Image("inter.png", width=500) .. image:: td2a_correction_session_6A_8_0.png :width: 500px .. code:: ipython3 # 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)) .. parsed-literal:: 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 :math:`P` cellules et strictement moins de :math:`Q` prisonniers. On peut alors r´esoudre notre problème par : .. math:: \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. .. code:: ipython3 from IPython.core.display import Image Image("priso.png", width=450) .. image:: td2a_correction_session_6A_13_0.png :width: 450px Découpage intelligent d’une base de données ------------------------------------------- Voir `GroupKFold `__, découpage stratifié d’une base de données ou `stratified sampling `__.