• # Belle modélisation, rapide, efficace.

    Posté par (Mastodon) . En réponse au message Avent du Code, jour 24. Évalué à 4.

    Je suis fier de moi !
    Bon, j'ai pu démarrer très tard aujourd'hui, mais j'ai été efficace et j'ai fait du joli code, court et propre.
    Une bête erreur de préparation a flingué ma perfection, pour le calcule des 4 directions de mouvements, j'avais fait droite, gauche, bas, gauche... Et les données de test passent : ya jamais besoin d'aller en haut pour trouver la bonne solution, rhaaa !

    Bref, j'ai relu, j'ai trouvé, et j'ai passé à peine quelques minutes entre le 1 et le 2, le temps de mettre le code d'itération dans une fonction avec une position de départ et une d'arrivée, et de l'appeler trois fois d'affilé.

    Exécution en 1,5 secondes.
    Utilisation extensives des set(), union, intersection.
    J'ai aussi eu une flemme terrifiante de calculer un PPCM, alors il est mochement en dur dans le code, comme quoi tout n'est pas si beau ^

    from collections import deque
    class Position(tuple):
     def __add__(self, other):
     return Position((self[0] + other[0], self[1] + other[1]))
     def __contains__(self, other):
     return (
     0 <= other[0] < self[0] and
     0 <= other[1] < self[1])
     def moves(self, dimensions):
     return (
     _
     for _ in (self + (1, 0), self + (-1, 0), self + (0, 1), self + (0, -1))
     if _ in dimensions
     )
    def whirlwind(x, y, d, w, h, n):
     if d == ">":
     return [(_ % w, y) for _ in range(x, x + n)]
     if d == "<":
     return [(_ % w, y) for _ in range(x, x - n, -1)]
     if d == "^":
     return [(x, _ % h) for _ in range(y, y - n, -1)]
     if d == "v":
     return [(x, _ % h) for _ in range(y, y + n)]
    data = sys.stdin.read().strip().splitlines()
    dimensions = Position((len(data[0]) - 2, len(data) - 2)) # should be 120, 25
    ppcm = 12 if dimensions[0] == 6 else 600 # complete whirlwind board cycle length
    start = Position((data[0].index(".") - 1, -1)) # Should be (0, -1)
    startpos = start + (0, 1) # Should be (0, 0)
    end = Position((data[-1].index(".") - 1, dimensions[1])) # should be (6, 3) or (120, 24)
    # ending on the tile before the end, north of it, last move being unique, and unstoppable
    endpos = end + (0, -1) # Should be (5, 3) or (119, 24)
    board = deque((set(_) for _ in zip(*[
     whirlwind(x - 1, y - 1, c, dimensions[0], dimensions[1], ppcm)
     for y, line in enumerate(data)
     for x, c in enumerate(line)
     if c in "<>^v"
    ])), ppcm)
    def reach(start, end, board, dimensions):
     positions = {start}
     i = 0
     while end not in positions:
     positions = positions.union(
     p
     for _ in positions
     for p in _.moves(dimensions)
     ).difference(board[0])
     board.rotate(-1)
     i += 1
     return i
    r1 = reach(start, endpos, board, dimensions)
    r2 = reach(end, startpos, board, dimensions)
    r3 = reach(start, endpos, board, dimensions)
    print(f"Reaching destination in {r1} rounds")
    print(f"Returning to start in {r2} rounds")
    print(f"Reaching destination again in {r3} rounds")
    print(f"Total of {r1+r2+r3=} rounds")

    L'état du terrain avec ses tornades est cycliques en PPCM(largeur, hauteur), donc je calcule tous les états possibles au début et je me balade après en faisant tourner le deque.
    L'initialisation est presque plus longue que la solution...

    • Yth.