Advent of code

◂ 23 décembre 2022 ▸

  Unstable Diffusion : Déplacer des elfes sur la carte tant qu'ils ont des voisins

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

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

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

1. code.py

import re
f = open("input.txt", 'r')
lines = [line[:-1] for line in f.readlines()]


NB_ROUNDS = 10
MARGE = NB_ROUNDS + 1
H = len(lines) + 2*MARGE
W = len(lines[0]) + 2*MARGE


NB_ELFES = 0

minX = W
maxX = 0
maxY = minY = None


### lecture des données
grid = [W*[False] for _ in range(MARGE)]
y = MARGE-1
for line in lines:
    y += 1
    nbElfesLine = line.count('#')
    NB_ELFES += nbElfesLine
    if nbElfesLine > 0:
        minX = min(minX, MARGE + line. index('#'))
        maxX = max(maxX, MARGE + line.rindex('#'))
        maxY = y
        if minY == None:
            minY = y
    grid.append(MARGE*[False] + [c == '#' for c in line] + MARGE*[False])
grid.extend([W*[False] for _ in range(MARGE)])


### calculs des déplacements désirés
X = 0
Y = 1
DEPLACEMENT = 2
ZONES_CHOIX_DEPLACEMENT = (
        ((-1,0,+1),(-1,),(0,-1)),  # nord
        ((-1,0,+1),(+1,),(0,+1)),  # sud
        ((-1,),(-1,0,+1),(-1,0)),  # ouest
        ((+1,),(-1,0,+1),(+1,0)),  # st
        )

def positionDemandee(x,y):
    global grid, H, W, nbRounds
    nbElfes = sum(sum(grid[ny][x-1:x+2]) for ny in range(y-1,y+2))
    if nbElfes == 1:   # personne sinon soi
        return (x,y)
    for i in range(4):
        zone = ZONES_CHOIX_DEPLACEMENT[(i + nbRounds - 1) % len(ZONES_CHOIX_DEPLACEMENT)]
        if sum(sum(grid[y+dy][x+dx] for dy in zone[Y]) for dx in zone[X]) == 0:
            return (x+zone[DEPLACEMENT][X], y+zone[DEPLACEMENT][Y])
    return (x,y)



### on lance le bouzin
nbRounds = 0
elfesSeSontDeplaces = True
while elfesSeSontDeplaces:   # boucle des rounds
    nbRounds += 1

    ### Calcul des demandes de positions
    demandes   = [W*[None] for _ in range(H)]   # mise en cache dans un tableau, on gagne du temps par rapport à mettre @functools.cache sur positionDemandee
    nbDemandes = [W*[0] for _ in range(H)]      # nb Demandes sur une destination
    for y in range(minY,maxY+1):
        for x in range(minX, maxX+1):
            if grid[y][x]:
                nx,ny = positionDemandee(x,y)
                demandes[y][x] = (nx,ny)
                nbDemandes[ny][nx] += 1
    nMaxX = nMaxY = 0
    nMinX = W - 1
    nMinY = H - 1

    ### Calcul des nouvelle positions
    newGrid = [W*[False] for _ in range(H)]
    for y in range(minY,maxY+1):
        for x in range(minX, maxX+1):
            if not grid[y][x]:
                continue
            nx,ny = demandes[y][x]
            if nbDemandes[ny][nx] != 1:
                nx,ny = x,y
            newGrid[ny][nx] = True
            nMinX = min(nMinX, nx)
            nMaxX = max(nMaxX, nx)
            nMinY = min(nMinY, ny)
            nMaxY = max(nMaxY, ny)

    ### mise à jour
    elfesSeSontDeplaces = (newGrid != grid)
    grid = newGrid
    minX = nMinX 
    maxX = nMaxX 
    minY = nMinY 
    maxY = nMaxY 

    ### Contrôle de la marge et extension de grid au besoin
    if minY == 0 or maxY == H - 1:
        grid = [W * [False]] + grid + [W * [False]]
        minY += 1
        maxY += 1
        H += 2
    if minX == 0 or maxX == W -1:
        grid = [[False] + g + [False] for g in grid]
        minX += 1
        maxX += 1
        W += 2

    #for g in grid:
    #    print(''.join([c and '#' or '.' for c in g]))
    #print(10*"=")

    if (nbRounds == NB_ROUNDS):
        print("Réponse partie 1:", (maxY-minY+1)*(maxX-minX+1) - NB_ELFES)


print("Réponse partie 2:", nbRounds)