Advent of code

◂ 15 décembre 2022 ▸

  Beacon Exclusion Zone : Calculer un point isolé sur énorme surface (hors de zones avec distance Manhattan)

Sensor at x=2302110, y=2237242 … 

Sensor at x=47903, y=2473047:  … 

1. code_partie1.py
2. code_partie2.py
3. code_partie2_faconPartie1.py

### Comme pour la partie 1, mais sur chacune des 4 millions de lignes à surveiller.
### Prend 1 minute 20 pour être exécuté

TAILLE_ZONE = 4000000

def distanceManhattan(pt1, pt2):
    return abs(pt1[0]-pt2[0]) + abs(pt1[1] - pt2[1])


sensors = []
allX = []

f = open("input.txt", 'r')
lines = [line[:-1] for line in f.readlines()]
for line in lines:
    [x1, y1, x2, y2] = list(map( lambda t : int(t[-1] in ",:" and t[2:-1] or t[2:]), filter(lambda t:t[0] in 'xy', line.split())))
    distance = distanceManhattan((x1,y1), (x2,y2))
    sensors.append( ((x1,y1), distance) )

    allX += [x1-distance-1, x1+distance+1]   # extrêmes de la zone



intervallesExclus = (TAILLE_ZONE + 1) * [None]
for i in range(len(intervallesExclus)):
    intervallesExclus[i] = []

print("chargement ok.")

nbS = 0
for ((x,y), dist) in sensors:
    print("next sensor", str(round(nbS/len(sensors)*100))+'%')
    nbS += 1
    for i in range(dist + 1):
        intervalle = [max(0,x - dist + i), min(TAILLE_ZONE, x + dist - i)]
        ys = (y-i,y+i)
        if i == 0:
            ys = (y,)
        for y1 in ys:
            if (y1 < 0 or y1 > TAILLE_ZONE):
                continue
            intE = intervallesExclus[y1]
            intE.append(intervalle[:])
            intE.sort()
            j = 0
            while j < len(intE) - 1:
                int1 = intE[j]
                int2 = intE[j+1]
                if int1[1] >= int2[0] - 1:
                    intervallesExclus[y1][j][1] = max(int1[1],int2[1])
                    intE = intervallesExclus[y1]
                    intE.pop(j+1)
                else:
                    j += 1


for y in range(0, TAILLE_ZONE+1):
    if (len(intervallesExclus[y]) > 1):
        x = intervallesExclus[y][0][1] + 1
        print("Réponse partie 2:", x * TAILLE_ZONE + y)
    elif (intervallesExclus[y] != [[0, TAILLE_ZONE]]):
        print("Réponse partie 2 à caculer soi-même pour Y=", y, "et intervalles=", intervallesExclus[y])