Battle dev blogpost

Retour de Jonathan sur la Battle Dev de Novembre 2020

La Battle dev est une compétition de code ou le but est de résoudre dans l’ordre 6 exercices d’algorithmie en 2h. Jonathan développeur chez Budget Insight partage son expérience de la 16e Battle Dev et ses conseils pour vous préparer à la prochaine édition. Prêt à relever le challenge ?

« La difficulté est croissante et couvre un très large spectre :

  • Exo 1 et 2 : Assez simple, dont le but est de proposer quand même un petit challenge à ceux qui sont débutants en programmation.
  • Exo 3 et 4 : Plus compliqué, où la majorité des participants finissent. Il faut connaître assez bien la programmation pour y arriver rapidement. La difficulté est ici souvent de trouver un algo efficace car le temps de calcul est limité. Bien souvent votre première idée marchera en théorie, mais pourra ne pas satisfaire à cette contrainte de temps pour tous les jeux de données (et ils sont prévus justement pour vous forcer à trouver une astuce d’optimisation).
  • Exo 5 (et parfois 4) : Là on a souvent affaire à de la programmation dynamique et de la théorie des graphs. Avoir une culture générale des algorithmes “classiques” sera un vrai plus, car certains exo sont souvent des variantes d’algo bien connus.
  • Exo 6 : Réalisable dans les temps que par une vingtaine de personnes qui font de très nombreuses compétitions de ce genre, autant dire irréaliste pour le commun des mortels.

Vous pouvez rejouer les exercices de cette 16ème battle dev (et les autres) sur le site d’isograd. Je vous invite à le faire avant de voir la discussion des solutions qui suivent si vous voulez voir quel est votre niveau (vous avez 2h !).

Sur la plateforme Isograd, je vous conseille vivement d’utiliser le zip avec les inputs/outputs d’exemples disponibles à chaque exercice. Cela permet un développement offline simple et efficace. Un test comme python3 exo3.py < data/input1.txt && echo « attendu: » && cat data/output1.txt vous fera gagner pas mal de temps en vous permettant un debug plus facile.

Explications

Je vais seulement expliquer les exos 3, 4 et 5 car ce sont ceux sur lesquels une majorité de gens reste bloquée. Les deux premiers exo sont assez simples et le dernier, j’ai tout juste lu le sujet. Pour ceux qui voudraient quand même se pencher dessus, regardez du côté des jeux de Nim. 🙂

Je vais simplifier un peu les énoncés lors de mes explications et ne discuterai pas de tous les détails d’implémentation pour alléger les explications.

Exercice 3 : Hiérarchie pyramidale

Les données

On nous donne une suite de N liens de subordination sous forme de deux entiers. 4 7 signifie “l’agent 7 est le supérieur de l’agent 4”. L’agent 0 étant le grand patron au sommet de la pyramide.

Le but

Reformer la pyramide de la hiérarchie et donner pour chaque niveau le nombre d’agents ayant ce grade.

Résolution

Ici on doit clairement créer un graph puis le parcourir par niveau. Les principales manières de représenter simplement un graph sont :

  • par un tableau 2D (Matrice d’adjacence), indiquant à la cellule (i, j) si i est relié à j. Utile lorsque l’on doit faire évoluer les liens car toutes les cases sont initialisées et (i, j) sont directement les index d’accès aux données.
  • un dictionnaire de liste ou pour chaque id de nœud on associe la liste des voisins. Plus simple et qui convient très bien à notre énoncé.

On va parcourir chaque niveau dans l’ordre, l’info utile par niveau est la liste des agents de ce niveau, peu importe s’ils ont le même supérieur. Il suffit donc à chaque niveau de concaténer la liste des subordonnés des agents pour avoir la liste des agents du niveau suivant.

Code de la solution

	from collections import defaultdict
	from copy import copy
 
	# On crée le graph
	graph = defaultdict(list)
	n = int(input())
	for _ in range(n-1):
		a, b = map(int, input().split())
		graph[b].append(a)
 
	result = [] # Contiendra le compte de chaque niveau
 
	current_level = [0] # On part du big boss 0, tout seul à son niveau
	for _ in range(10): # On doit donner notre réponse pour 10 niveaux (même vide)
		result.append(len(current_level))
		next_level = []
		for agent in current_level:
			next_level += graph[agent]
 
		# Important! sans copy() current_level et next_level pointerais sur la même donnée
		current_level = copy(next_level)
 
	print(' '.join(str(nb) for nb in result))

Exercice 4 : Chiffrement xor

Les données

On nous donne :

  • une suite de N entiers (entre 0 et 255 compris), la clé.
  • M ligne de deux entiers (L, R) représentant un octet à déchiffrer.

Le but

Pour déchiffrer une ligne (L, R) il faut effectuer le xor binaire des entiers de la clé entre les positions L et R.

Le format de sortie : pour chaque valeur de 0 à 255, on doit indiquer le nombre de fois où le résultat d’une ligne a été cette valeur.

Résolution

On nous prévient qu’il faut un algo efficace. On peut donc oublier l’approche naïve qui consiste seulement à faire le xor des valeurs à chaque fois dans l’ordre car cela sera bien trop long.

Ici on a une donnée fixe, la clé, qui va être réutilisée maintes et maintes fois. Pour avoir un algo efficace, une bonne approche va donc être de précalculer des valeurs de manière à limiter les calculs. En posant un cas simple sur le papier :

clé: 1 2 3 4 5 6 7 8 9 10

ligne 1: (2, 7) res = 2 ^ 3 ^ 4 ^ 5 ^ 6 ^ 7

ligne 2: (4, 9) res = 4 ^ 5 ^ 6 ^ 7 ^ 8 ^ 9

 

On peut remarquer que l’on peut gagner quelques calculs car le morceau (4 ^ 5 ^ 6 ^ 7) est réutilisé. C’est un début, mais on ne va pas précalculer les valeurs pour tous les couples, cela nous donnerait encore plus de travail que l’implémentation naïve. L’idée est donc de n’avoir qu’un faible nombre de valeurs précalculées.

Avec un peu de réflexion (environ une demie-heure d’essais divers pour ma part), la solution est ici de précalculer les couples (0, i) pour tout i. Cela nous donne une clé cumulative :

cumul : 1 (1^2) (1^2^3) … (1^2^…^9)

Maintenant pour calculer (4, 9) il me suffit de faire une seule opération (1^2^…^8^9) ^ (1^2^3) car les deux parenthèses sont déjà calculées et disponibles dans ma clé cumulative. La partie (1^2^3) va s’annuler et j’aurai le bon résultat (4^5^6^7^8^9).

Si cela n’est pas assez clair, vous pouvez raisonner en termes d’addition pour comprendre la logique : la somme de 4 à 9 inclus est (1+2+…+8+9) – (1+2+3). La seule différence est que l’inverse de + est – tandis que l’inverse de xor est xor.

Code de la solution

	N, M = map(int, input().split())
	keys = map(int, input().split())
 
	# on crée la clé cumulative
	cumul = [0]
	for k in keys:
		cumul.append(cumul[-1] ^ k)
 
	# on initialise notre tableau de compteur
	result = [0] * 256
 
	for i in range(M):
		l, r = map(int, input().split())
		decipher = cumul[l] ^ cumul[r + 1]
		result[decipher] += 1
 
	print( ' '.join(str(nb) for nb in result)

Exercice 5 : Hash collision

Il y a beaucoup de choses à dire sur cet exercice, je vais vous expliquer 3 solutions différentes, démontrant chacune une approche sous un angle différent.

Les données

On nous donne :

  • une chaîne de caractère
  • une fonction de hachage de string :
    hash(S) = (S_0 * 31^(N-1) + S_1 * 31^(N-2) + … + S_N-2 * 31 + S_N-1) % 4294967296

Cette fonction sera partagée par les solutions suivantes. Voici son équivalent en code :

    def myhash(s):
    total = 0
    for c in s:
        total *= 31
        total += ord(c)
    return total % 2**32

On peut remarquer que 4294967296 est 2 puissance 32 mais cela ne nous donne aucune indication pour la résolution.

Le but

Trouver une autre chaine de caractère qui a le même hash que la chaîne donnée. Nous avons aussi la contrainte de trouver une chaine de caractère ‘printable’, c’est à dire que chaque caractère doit être dans l’intervalle [33, 126] de la table ascii.

Le piège

On remarquera vite que la fonction de hachage permet de simples opérations sur une chaîne, tout en conservant le hash : faire -1 à l’indice i et +31 à l’indice i+1 (ou respectivement +1/-31) suffit. J’ai moi-même passé environ une heure à essayer ce genre d’opérations, mais la contrainte des valeurs entre 33 et 126 rend cette approche difficile à mon avis.

Si on essaye de l’utiliser on arrive à devoir propager les calculs sur plusieurs lettres quand l’opération nous donne des valeurs hors intervalle et cela ne passe pas les données composées uniquement de ‘!’ (33), ou de ‘~’ (126) car on ne peut pas faire une seule opération sans ‘déborder’…

La solution attendue

La solution attendue par les organisateurs pour cet exercice était l’utilisation d’un meet in the middle. Le code est disponible en solution sur la page de l’exercice (il faut être en langage python puis cliquer sur ‘solution’).

L’idée est que l’on peut découper le problème :

myhash(‘abcdef’) = myhash(‘a’)* 31**5 + myhash(‘bcdef’)

On peut ainsi concaténer des chaînes, leurs hash s’additionne à un facteur 31 puissance le décalage prêt.

Une fois cette constatation faite, en découpant notre chaîne en deux, le problème devient un bruteforce de l’ordre de 2**16 au lieu de 2**32. Un gain d’un facteur 65536 qui rend alors le temps du bruteforce acceptable.

Nous allons pour cela devoir générer un dictionnaire d’environ 2**16 hash de chaîne de caractère aléatoire qui seront nos premières moitiés potentielles. Ensuite, avec une nouvelle chaîne aléatoire, notre seconde moitié, nous chercherons s’il existe dans notre dictionnaire un hash d’une première moitié qui correspond à :

needed_hash = (myhash(chaine_donnée) – myhash(seconde_moitié)*31**n) % 2**32

n étant la longueur des moitiés, la solution utilise 5. Je ne saurais pas trop justifier comment choisir ce nombre si ce n’est en essayant. L’important est qu’il soit suffisamment grand. Trop grand n’a pas de trop fort impact car le calcul du hash n’est pas si complexe, j’ai essayé 15 et cela passe encore.

En quelques répétitions, nous sommes statistiquement certains que needed_hash se trouve dans notre dictionnaire précalculé. Il suffit alors de concaténer la chaîne correspondante à notre deuxième moitié.

Je vous laisse aller consulter le code de la solution pour l’implémentation complète.

Note : la solution utilise 100 000 entrée dans le dictionnaire entrée qui est un arrondi des 2**16 que j’indique (65 536). Cela n’a pas grande importance sur une solution probabiliste comme celle-ci, l’important est d’être dans le bon ordre de grandeur. Si on calcule trop peu de chaîne, on aura peu de chance de trouver un match. Si on en calcule trop, on va finir par tomber souvent sur des valeurs déjà calculées, si tel est le cas, c’est du calcul inutile et cela veut aussi dire que l’on est à un point où trouver un match est très facile (probabilité d’un match pour la deuxième moitié = probabilité de tomber sur un hasch existant pour l’addition d’une première moitié).

La solution la plus simple

D’après h25, qui ont participé à l’organisation de la Battle dev, la méthode la plus élégante se basait sur le principe suivant :

On part d’une chaîne ‘!!!!!!!!’, dont l’indice des caractères est 33, la plus petite valeur acceptable. On calcule le reste r = (myhash(chaine_donnée) – myhash(‘!!!!!!!!’))%2**32 que l’on doit ajouter à notre hash pour avoir la collision. On convertit ce reste en base 31, et on ajoute à chaque ‘!’ (en partant de la droite) les offsets donnés par cette représentation en base 31.

On aura par construction le bon hash, et les valeurs seront toujours entre 33 (notre point de départ) et 63 (33 + 30 qui est le max en base 31) garantissant ainsi la contrainte.

Code de la solution

	def b31(n):
		# converti n en base 31
		result = []
		while n:
			n, r = divmod(n, 31)
			result.append(r)
		return result
 
	def conv(n):
		s = '!!!!!!!!!!'
		r = (n - myhash(s)) % 2**32
		offsets = b31(r)
		res = [ord(c) for c in s]
		
		# le premier offset à gauche correspond à la dernier lettre de s
		for i, offset in enumerate(offsets, start=1):
			res[-i] += offset
		return ''.join(chr(k) for k in res)
 
 
	print(conv(myhash(input())))

Ma solution

Je vous propose encore une solution, la mienne, qui en comparaison me semble plus simple à trouver par soi-même. Le meet in the middle demande de bien connaître ce genre de technique (je ne la connaissais pas pour ma part) et la solution simple demande d’avoir un réel éclair de génie.

Ma solution part du hash de la donné reçu en entrée et cherche à reconstruire une chaîne caractère par caractère à partir de là. Il est possible de reconstruire la chaîne progressivement pour la même raison évoquée plus haut : concaténer des chaînes revient à faire un simple calcul sur les hash.

Le déroulement de l’algo se fait de cette manière:

  • pour un hash donné, on pose q, r = divmod(hash, 31). r nous permet de trouver un nombre de caractères possible limité (car on peut additionner 31 en diminuant q de 1).
  • Et on recommence avec q.

Cela va nous faire parcourir un arbre de possibilités et dès que l’on trouve une solution valide on termine.

Comme cela est un peu abstrait, voici un exemple: on part de ‘abc’, hash=96354.

96354%31 = 6, on a donc comme valeur possible pour le dernier caractère 6 + k*31 soit :

  • 96354 = 6 + 31*3108 # éliminé car 6 < 33
  • 96354 = 37 + 31* 3107
  • 96354 = 68 + 31*3106
  • 96354 = 99 + 31*3105
  • 96354 = 130 + 31*3104 # éliminé car 130 > 126

On continue en prenant le premier cas valide : 37 (’%’) et on recommence donc avec 3107 :

  • 3107 = 7 + 31*100 # éliminé
  • 3107 = 38 + 31* 99
  • 3107 = 69 + 31*98
  • 3107 = 100 + 31*97
  • 3107 = 131 + 31*96 # éliminé

On prend 38 (’&’) et on recommence avec 99.

On se rend compte que 99 (‘c’) est bien entre 33 et 126 et on peut s’arrêter là.

On vient donc de trouver une solution ‘c&%’ qui a le même hash que ‘abc’ !

Il peut arriver que l’on ne trouve aucune chaine valide. Ceci est dû au modulo 2**32. On effectue alors l’algo sur hash + i * 2**32 en augmentant i jusqu’à trouver une solution.

Code de la solution

	from collections import deque
 
	def conv(total, original_input):
		i = 0
		while True:
			q = deque([(total + i * (2**32), [])])
			while q:
				n, acc = q.popleft()
				if n < 33:
					continue
				if n <= 126:
					result = [n] + acc
					if result != original_input:
						# vérifie que la solution est différente de l'input
						return result
				r = n % 31
				possible_values = [
					r + j * 31
					for j in range(5)
					if 33 <= r + j * 31 <= 126 ] for p in possible_values: # append -> bfs, appendleft -> dfs. Les deux fonctionnent ici.
					q.append(((n - p) // 31, [p] + acc))
			i += 1
 
 
	data = input()
	print(''.join(chr(c) for c in conv(myhash(data), [ord(c) for c in data])))

Je n’ai malheureusement pas réussi à coder cette solution correctement dans les temps, je n’en ai eu l’idée qu’à 10 minutes de la fin…

Ce genre d’algorithme de ‘réduction’ progressive est assez courant en competitive programming. Je considère que cette solution est plus classique que les précédentes. Comprendre sa logique vous sera peut être utile pour la prochaine Battle dev ! »

Si toi aussi tu aimes ce genre de challenge, en individuel ou en équipe, on recrute chez Budget Insight 🙂 👉 ICI