Retour sur la 17e édition de la Battle Dev

Battledev juin 2021

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

Présentation

Cette année, le sujet était centré autour des aventures de "Tommy Pasqua" dans l’espace.

Comme chaque année, les exercices étaient classés par difficulté croissante.

  • Les exercices 1 et 2 ne sont que des échauffements.
  • Les exercices 3 et 4 sont faisables sans trop de difficulté par des développeurs pros, mais demandent déjà plus de maturité.
  • Les deux derniers exercices (et en particulier le 6) sont plus adressés à des développeurs habitués des questions algorithmiques, voire de la programmation compétitive.

Pour ma part, j’ai fait 5 exercices en 1h23, ce qui m’a placé 40ème. A la seule lecture de l’exercice 6, j’ai su que je n’aurais pas le temps de le faire dans le temps restants, alors je me suis arrêté là (et, de fait, sur plus de 3000 inscrits, seulement deux personnes ont réussi à aller au bout du 6).

Exo 1

Un exercice très simple, pour s’échauffer. Il s’agit de déterminer la quantité de carburant nécessaire pour le voyage, sachant

  • D la quantité consommée au décollage
  • L la distance parcourue

L’énoncé donne que la fusée consomme 5kg de carburant par unité de distance.

D = int(input())
L = int(input())

print(D + 5 * L)

Exo 2

On nous donne une liste de boutons du cockpit, il faut trouver lequel apparaît exactement deux fois.

Les boutons sont représentés par des chaînes de caractères.

Le sujet nous garantit que seule l’une d’entre elles apparaît exactement deux fois. Les autres peuvent n’apparaître qu’une fois, ou trois fois …

N = int(input())
words = [input() for _ in range(N)]

print(next(word for word in words if words.count(word) == 2))

Remarques:

  • La fonction next renvoie, commne son nom l’indique, le premier élément de la séquence. Comme on utilise un générateur, l’évaluation s’arrêtera dès qu’elle aura trouvé le bon mot. Je trouve ça plus élégant que de former toute la liste puis prendre le [0], mais il faut faire attention car s’il ne trouve aucun élément, next soulève une erreur StopIteration.

  • La syntaxe for _ in est ce qu’on appelle une itération anonyme. Pour Python il n’y a aucune différence avec un nom de variable plus classique, car _ est un nom de variable tout aussi valide que les autres, mais il s’agit d’une convention indiquant qu’on n’a pas l’intention d’utiliser le contenu de cette variable.

  • Enfin, du point de vue complexité, l’algo utilisé ici est en O(n2) alors qu’il aurait été possible de faire mieux, typiquement avec des Counter. Mais ce n’est que l’exo 2, on ne nous enverra que des cas gentils, pas besoin de s’embêter si tôt avec ce genre de questions.

Exo 3

Ca commence à devenir plus complexe. Cet exo 3 était encore assez facile conceptuellement, mais arriver à coder une solution correcte dans tous les cas et rapidement peut poser plus de problèmes. D’ailleurs, je pense que beaucoup de gens (à commencer par moi) ont passé plus de temps sur celui-ci que sur le 4.

Pour palier l’ennui, notre astronaute joue à Tetris. Il s’agit de détecter les situations où on peut faire disparaître 4 lignes d’un coup, en faisant tomber une barre verticale (sans changer de colonne en cours de route).

Exemple de grille invalide, tiré du sujet :

..........
..........
..........
..........
..........
...###....
.....#...#
.....#.#..
.#...###..
#....#.##.
###.######
###.######
###.######
###.######
#####.####
#####.####
#####.####
#####.####
#.##.#.###
####.##.#.

Quand c’est possible, il faut renvoyer BOOM <col>, où <col> est le numéro de la première colonne où insérer la barre. Quand ce n’est pas possible, il faut renvoyer NOPE.

La grille fait toujours 20 × 10.

grid = [input() for _ in range(20)]

for col in range(10):
    lower = 0
    while lower < 20 and grid[lower][col] == '.':
        lower += 1

    if lower < 4:
        continue

    if all(
        row.count('#') == 9
        for row in grid[lower - 4: lower]
    ):
        print(f'BOOM {col + 1}')
        break
else:  # TODO
    print('NOPE')

Remarque

Il y a beaucoup de façons différentes de faire ça. Notamment il est possible de manipuler le tableau initial pour limiter le nombre de cas particuliers:

  • ajouter une ligne de ‘#’ en bas pour éviter une condition sur la taille (On assure le fait de terminer le while).
  • ajouter 3 lignes vides au dessus, pour éliminer le if lower < 4
  • ajouter des colonnes de ‘#’ à droite et gauche pour chercher un patern '#'*n + '.' + '#'*m (si on a pas pensé à la fonction str.count() ou qu’on aime les regexp).

Je pense que dans ce genre de concours, où le temps est un facteur déterminant, le plus important est de coder une solution avec laquelle on est à l’aise, et qu’on pense pouvoir débugger rapidement le cas échéant, plutôt qu’une solution particulièrement élégante mais inextricable.

Exo 4

Ca commence à se corser. Il faut réflechir un peu pour trouver comment aborder l’exercice et, comme on va le voir, le temps devient un problème. La solution "naïve" ne suffit plus.

Nous sommes aux abords d’une planète, avec des débris gravitant autour. On dispose de deux robots ramasseurs, qu’on peut lancer sur une même orbite. Il faut compter les façons de découper une orbite en deux parts contenant les mêmes débris.

Exemple

L’orbite est représentée par une str de taille paire, par exemple ABBA (en gardant en tête que le dernier caractère est "relié" au premier, notre orbite est circulaire). Ici, il y a précisément deux endroits valides où couper la chaîne : en 0 et en 2.

Approche

On pourrait être tenté de faire directement des comparaisons de chaînes, par exemple avec du slicing (et, pour être transparent, c’est comme ça que j’ai fait en premier lieu haha). Mais alors la solution est en O(n2). Or le sujet précise bien que les chaînes qu’on nous envoie peuvent être de taille 500000.

Donc, en faisant ainsi, on ferait de l’ordre de 1012 opérations. Sur un ordinateur récent, ça correspond à un temps d’execution de l’ordre de l’heure. Ca pourrait être acceptable dans certains contextes, mais dans le cas d’une battledev, les exos doivent avoir un temps d’execution de l’ordre de la seconde. Il faut donc raisonner autrement.

Il faut alors réaliser que, d’un découpage à l’autre, les chaînes ne diffèrent que de deux caractères (celui du début, qu’on enlève, et celui qu’on rajoute à la fin).

On va donc utiliser ça pour ne pas recompter tous les éléments à chaque étape.

from collections import Counter

N = int(input())
debris = input()

c1 = Counter(debris[: N // 2])
c2 = Counter(debris[N // 2:])

solutions_nb = 0
for i in range(N // 2):
    c1[debris[i]] -= 1
    c2[debris[i]] += 1

    c1[debris[i + N // 2]] += 1
    c2[debris[i + N // 2]] -= 1

    solutions_nb += int(c1 == c2)

print(2 * solutions_nb)

Remarques

  • Pour stocker le compte des éléments, on pourrait utiliser un dict, ou une list, mais il se trouve que la librairie standard a une classe parfaitement adaptée : Counter. Ici, le seul gain par rapport à un dict est à l’initialisation, mais il est bon de connaître cette classe, qui a des fonctions spécifiques parfois bien utiles.

  • int(c1 == c2) est un petit raccourci malin pour 1 if c1 == c2 else 0, reposant sur le fait que int(True) == 1, et int(False) == 0.

Exo 5

A partir d’ici, il faut se poser sérieusement des questions avant de se lancer. Vu la taille des entrées, toute approche ressemblant de près ou de loin à du "brute force" est vouée à tourner encore après la mort de notre univers.

Notre fusée s’apprête à traverser un champs d’astéroïdes, pendant un nombre n de secondes. On sait à l’avance, pour chaque instant t, combien d’astéroïdes percuteront la fusée si on n’active pas le bouclier. On pourrait vouloir le garder activé tout du long, mais ce bouclier n’a qu’une durée d’activation a limitée, et doit ensuite être rechargé pendant une durée c. Le problème est de déterminer combien d’astéroïdes percuteront le vaisseau si on utilise la stratégie optimale.

Approche

Il fallait reconnaître ici un problème caractéristique de la programmation dynamique. En général ces situations sont repérables à leur aspect récursif.

Ici, on va écrire pour notre récursion une fonction min_cost(t), qui renvoie le nombre minimal de dégats qu’on prendrait si on commençait à l’instant t avec le bouclier activable.
A l’instant t, on a deux choix.

  • Si on n’active pas le bouclier, alors on prend les dégats de ce tour, et on passe à l’instant t + 1 avec le bouclier activable. Le plus petit nombre de dégats encaissés dans ce cas est donc degats[t] + min_cost(t + 1)
  • Si on active le bouclier, on évite les dégats entre les tours t et t + a (exclu), mais on prend forcément tous les dégats ensuite entre les tours t + a et t + a + c (exclu). Le bouclier sera de nouveau activable à partir du tour t + a + c.

Une fois que notre fonction est correcte, il ne nous reste (presque) plus qu’à appeler min_cost(0) pour obtenir le nombre minimal de dégats en partant de t = 0 et avec le bouclier activable, comme dans l’énoncé.

from functools import lru_cache

n, a, c = map(int, input().split())
costs = list(map(int, input().split()))

cumulated = [costs[0]]
for cost in costs[1:]:
    cumulated.append(cumulated[-1] + cost)

def compute_cost_between(start, end):
    end = min(end, n) - 1
    if start >= n:
        return 0
    if start == 0:
        return cumulated[end]
    return cumulated[end] - cumulated[start - 1]

@lru_cache(None)
def min_cost(t):
    if t >= n:
        return 0

    cost_if_activated = compute_cost_between(t + a, t + a + c)
    cost_if_not = costs[t]

    return min(
        cost_if_activated + min_cost(t + a + c),
        cost_if_not + min_cost(t + 1)
    )

for start in range(n, -1, -1):
    min_cost(start)

print(min_cost(0))

Remarques

  • Pour éviter de calculer de très nombreuses sommes, j’ai commencé par calculer le tableau des sommes cumulées.

  • Ici j’ai utilisé le décorateur lru_cache, qui permet de mémoïser (mettre en cache) les résultats déjà calculés d’une fonction. C’est important, car sinon on calculerait plusieurs fois les mêmes valeurs.

  • Mais la seule mémoïsation ne suffit pas, car en partant de 0, puisque pour tout t on s’appelle récursivement sur t + 1, on aurait une profondeur de récursion égale à la taille de la chaîne. Or la stack est limitée. L’astuce est alors de faire des appels "depuis la fin". Les résultats étant mis en cache, et puisqu’on aurait de toute façon du faire ces appels au moins une fois pour notre calcul de min_cost(0), ça ne change rien à la complexité, qui reste du O(n).

Conclusion

En conclusion, des exercices assez orientés "algo", mais toujours amusants. Par rapport à certaines autres éditions, j’ai trouvé que la progression de la difficulté avait été assez bien gérée (sauf éventuellement entre le 2 et le 3, où le gap était assez important.)

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

Pour ma part j’ai eu droit aux goodies de la battledev mais aussi à quelques bons pour des pintes, de quoi fêter ça dignement ! 🎉