Advent of code

◂ 24 décembre 2022 ▸

  Blizzard Basin : Déplacement avec des blizzards à éviter qui bougent

#.############################ … 

#><v><>..v<<vv^vvv><.^v<v>^>v< … 

#<<v<^v^<>^v><v>v^<><v^^^><>>< … 

1. code.py
2. codeParcoursEnLargeur.py

from functools import cache
from sys import setrecursionlimit
MAX_TIME = 1000
setrecursionlimit(MAX_TIME*2 + 10)

with open("input.txt", 'r', encoding='utf-8') as f:
    lines = [line[:-1] for line in f.readlines()]

lines = [line[1:-1] for line in lines] # supprimer les bords gauche et droite

START1 = (lines[0] .index('.'), -1)
END1   = (lines[-1].index('.'), len(lines) - 3) #  -1 à cause des bords haut et bas et qu'on s'arrête devant la sortie

START2 = (END1[0], END1[1] + 1)
END2   = (START1[0], 0)


lines = lines[1:-1]   # Supprimer les bords haut et bas
W = len(lines[0])
H = len(lines)

def biggestCommonDivisor(a, b):
    a, b = max([abs(a), abs(b)]), min([abs(a), abs(b)])
    while b != 0:
        a, b = b, a%b
    return a
def leastCommonMultiple(a, b):
    return a * b // biggestCommonDivisor(a, b)
CYCLE_LENGTH = leastCommonMultiple(W, H)


def addBlizzard(levels, x, y, dx, dy):
    for level in levels:
        level[y][x] += 1
        x = (x + dx) % W
        y = (y + dy) % H

DIRS = {'>':(1,0), '<':(-1,0), '^':(0,-1), 'v':(0,1)}
LEVELS = [[W*[0] for _ in range(H)] for _ in range(CYCLE_LENGTH)]
for y in range(0, H):
    for x in range(0, W):
        c = lines[y][x]
        if c != '.':
            addBlizzard(LEVELS, x, y, *DIRS[c])


MOVES = ((0,0), (0,1), (0,-1), (1,0), (-1,0))
@cache
def minNbMoves(x, y, goal, time):
    global MAX_TIME
    time += 1
    if (x, y) == goal:
        MAX_TIME = min(MAX_TIME, time)
        return time
    if time >= MAX_TIME:
        return None
    bestTime = None
    level = LEVELS[time%len(LEVELS)]
    if y in [-1, H]:    # on est à la case départ: il faut
        # Possibilité 1: rester sur place (comme MOVE=(0,0) mais sans vérif du bord)
        t = minNbMoves(x, y, goal, time)
        if t is not None and (bestTime is None or bestTime > t):
            bestTime = t

        # Possibilité 2: aller dans la seule direction possible, si permis (sans vérif du bord)
        ny = (H - 1 if y == H else 0)
        if level[ny][x] != 0:
            t = minNbMoves(x, ny, goal, time)
            if t is not None and (bestTime is None or bestTime > t):
                bestTime = t
    else:
        for (dx, dy) in MOVES:
            nx = x + dx
            ny = y + dy
            if nx < 0 or nx >= W or ny < 0 or ny >= H or level[ny][nx] != 0:
                continue
            t = minNbMoves(nx, ny, goal, time)
            if t is not None and (bestTime is None or bestTime > t):
                bestTime = t
    return bestTime

min1 = minNbMoves(*START1, END1, 0)
print("Réponse partie 1:", min1)

MAX_TIME = 1000
minNbMoves.cache_clear()   # anciennes valeurs pas utiles, donc gain de temps dans la recherche
min2 = minNbMoves(*START2, END2, min1)
#print("Temps intermédiaire:", min2)

MAX_TIME = 1000
minNbMoves.cache_clear()   # MAX_TIME remis à zéro
min3 = minNbMoves(*START1, END1, min2)
print("Réponse partie 2:", min3)


#print(minNbMoves.cache_info())