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 collections import deque

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))
def minNbMoves(x, y, goal, time):
    aFaire = deque([(x,y,time)])
    dejaFaits = set()

    while aFaire:
        x,y,time = aFaire.popleft()
        if (x,y,time) in dejaFaits:
            continue
        dejaFaits.add((x,y,time))

        time += 1
        if (x, y) == goal:
            return time
        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)
            aFaire.append((x,y,time))

            # 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:
                aFaire.append((x, ny, time))
        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
                aFaire.append((nx, ny, time))
    return None


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

min2 = minNbMoves(*START2, END2, min1)
#print("Temps intermédiaire:", min2)

min3 = minNbMoves(*START1, END1, min2)
print("Réponse partie 2:", min3)