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

Y_LIGNE_SPECIALE = 2000000

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


sensors = []
balisesLigneSpeciale = set()
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
    if y2 == Y_LIGNE_SPECIALE:
        balisesLigneSpeciale.add((x2,y2))




# Première façon: calculer les intersection des zones avec la ligne Y_LIGNE_SPECIALE
intervallesExclus = []
for ((x,y), dist) in sensors:
    deltaY = abs(y - Y_LIGNE_SPECIALE)
    if deltaY > dist:
        continue
    intervalle = [x - (dist - deltaY), x + (dist - deltaY)]
    intervallesExclus.append(intervalle)
    intervallesExclus.sort()
    i = 0
    while i < len(intervallesExclus) - 1:
        int1 = intervallesExclus[i]
        int2 = intervallesExclus[i+1]
        if int1[1] >= int2[0]:
            intervallesExclus[i][1] = max(int1[1],int2[1])
            intervallesExclus.pop(i+1)
        else:
            i += 1


nb = 0
for (a,b) in intervallesExclus:
    nb += (b-a+1)
    for balise in balisesLigneSpeciale:
        if a <= balise[0] and balise[0] <= b:
            nb -= 1

print("Réponse partie 1:", nb)




# Autre façon très lente (40 secondes): vérifier, pour chaque point à la
# hauteur Y_LIGNE_SPECIALE, si un sensor l'exclut ou non

mnx = min(allX)
mxx = max(allX)

nb = 0
for x in range(mnx,mxx+1):
    if (x,Y_LIGNE_SPECIALE) in balisesLigneSpeciale:
        continue
    for (sens, dist) in sensors:
        if distanceManhattan(sens, (x,Y_LIGNE_SPECIALE)) <= dist:
            nb += 1
            break

print("Réponse partie 1:", nb)