• # La solution la plus courte à écrire, la plus longue à expliquer.

    Posté par (Mastodon) . En réponse au message Advent of Code, jour 18. Évalué à 2.

    Hier encore, j'ai sévèrement lutté pour coder : repas d'entreprise en montagne (dur la vie...), donc j'ai eu rien de temps pour coder, à moitié sur PC, à moitié sur téléphone.
    En pratique, j'ai honte un peu, j'ai fini de coder en voiture (au volant oui, oui), avec un algo sous-optimisé qui a mit un bon quart d'heure à s'exécuter, et m'a sorti le bon résultat.
    Le même code prend 70s sur mon petit PC.

    Mais j'ai eu le temps de réfléchir à une autre approche, que je n'avais pas eu le temps de coder, mais que j'ai validé le soir.
    Et là c'est magique, une fonction de 12 lignes, 3 lignes pour les deux jeux de données, et 2 structures constantes, allez 22 lignes avec le she-bang python3.
    Le résultat sort en rien de temps, O(n).

    L'idée c'est de considérer une unique zone rectangulaire qu'on va agrandir ou rétrécir au fur et à mesure de l'exploration des sommets, en notant ce qu'on a tranché, ou rajouté.
    Voilà les données de test et quelques itérations :

    ####### 0# 1####### 2####### 3#####__ 4##### 5#####** 8##
#+++++# ####### #####__ ##### #####** ##
###+++# ####### #####__ ##### #####** ##
..#+++# ####### #####__ ##### #####** ##
..#+++# ####### #####__ ##### #####** ##
###+### ####### #####__ ##### #####** ##
#+++#.. ##### #####** ##
##++### ##### ####### ##
.#++++# .*
.###### .*

    Étape 0 j'ai la zone (0, 0) -> (0, 0), facile.
    Étape 1 j'étends vers la droite de 6 cases, rien à faire, ma zone fini en (6, 0), je prends tout.
    Étape 2, pas mieux, j'étends vers le bas jusque (6, 5), je prends encore tout (je ne sais pas encore ce qui se passe à la fin, on enlèvera plus tard, sommet par sommet).
    Étape 3, je réduis vers la gauche vers (4, 5) ! Là je perd une zone, indiquée avec des _, elle fait 12 cases, donc je la supprime du problème mais je note une superficie de 12.
    Étape 4, j'étends vers le bas, rien à dire, ma zone se termine en (4, 7).
    Étape 5, j'étends vers la droite encore, jusque (6, 7), et là on voit bien qu'on a agrandit dans une zone de vide, les *, il faut les retirer, mais attention, les # en bas sont l'épaisseur du trait, on les garde ! Donc on note que notre superficie est de 14 trop grand maintenant, notre superficie de côté est donc 12-14 = -2, ce qui correspond bien aux deux . à droite du résultat cherché.
    Je saute, étape 6 on descends vers (6, 9) rien à faire, étape 7 on va vers la droite jusque (1, 9) donc on ajoute à notre superficie stockée 50 cases, on est à 48.
    Étape 8, on remonte vers (1, 7) ! On doit considérer l'épaisseur du trait qui va disparaître, ici 2, mais le reste était en dehors de notre résultat, donc la superficie augmente simplement de 2 pour arriver à 50.

    On a vu les 4 règles, on termine les 14 étapes ainsi :
    Étape 9 : gauche de 1 vers (0, 7) superficie + 8 = 58
    Étape 10 : haut de 2 vers (0, 5) superficie + 2 = 60
    Étape 11 : droite de 2 vers (2, 5) superficie - 10 = 50
    Étape 12 : haut de 3 vers (2, 2) superficie + 3 = 53
    Étape 13 : gauche de 2 vers (0, 2) superficie + 6 = 59
    Étape 14 : haut de 2 vers (0, 0) superficie + 2 = 61
    Et enfin, il nous reste la zone qui se termine en (0, 0) et qui fait donc # et a une superficie de 1.
    J'ajoute 1 : 62, youpi.

    Cet algo est pensé sur un départ à gauche et en bas, avec le (0, 0) qui est dans le coin.
    Pour valider que ça marche un peu partout, surtout en débordant à gauche ou en haut, on peut constater que les instructions peuvent cycler, on peut commencer à la seconde instruction et reboucler jusque la 1ère, etc.
    Donc j'ai validé avec toutes les positions de départ : 62 tout le temps, on est bons.
    Ok, bah plus qu'à tester en grand et sur données réelles : ça marche, bingo.

    Le code :

    from sys import stdin
import re
data = re.findall(r"([UDLR]) (\d+) [(]#([0-9abcdef]+)[)]", stdin.read().strip())
DIR = [(1, 0), (0, 1), (-1, 0), (0, -1)]
Dir = {"R": DIR[0], "D": DIR[1], "L": DIR[2], "U": DIR[3]}
data1 = [(int(b), Dir[a]) for a, b, _ in data]
data2 = [(int(d[:-1], 16), DIR[int(d[-1])]) for *_, d in data]
def run(d):
 x = y = s = 0
 for n, (a, b) in d:
 x1, y1 = x + n * a, y + n * b
 if a == -1:
 s += (y + 1) * (x - x1)
 elif a == 1:
 s -= y * (x1 - x)
 elif b == -1:
 s += y - y1
 x, y = x1, y1
 return s + 1
ex1 = run(data1)
ex2 = run(data2)

    Voilà, voilà, sans théorème, sans connaissances particulières, sans module externe, juste des méninges torturées pendant des heures à ne pas pouvoir coder les algos qui tournent dans la tête.
    Inutile de dire que le temps d'exécution c'est l'overhead python, et c'est tout.

    Par contre difficile de bien coder ça en vrac, dehors, dans la neige et le froid, avec un téléphone, on est mieux sur un bureau, avec un papier, et un clavier.

    • Yth.