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]:
[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 :
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]:
Découpage intelligent d’une base de données¶
Voir GroupKFold, découpage stratifié d’une base de données ou stratified sampling.
[ ]: