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

def sign(x):
    return (x > 0 and 1) or (x < 0 and -1) or 0

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

# dire si le point est solution ou non
def verifierPoint(x, y, sensors):
    TAILLE_ZONE = 4000000
    if x < 0 or x > TAILLE_ZONE or y < 0 or y > TAILLE_ZONE:
        return False
    for s in sensors:
        if distanceManhattan(s['pt'], (x,y)) <= s['distance']:
            return False
    print("Réponse partie 2:", (x,y), TAILLE_ZONE*x+y)
    return True



f = open("input15.txt", "r")
lines = [line[:-1] for line in f.readlines()]
sensors = []
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( { 'x':x1, 'y':y1, 'pt':(x1,y1), 'distance':distance, 'beacon':(x2,y2)} )


# Un point isolé est forcément au bord de quatre zones
#   bbbb aaaa           cccc dddd
#    bbbb aaaa         cccc dddd
#     bbbb#aaaa   et  cccc#dddd
#      bbbb aaaa     cccc dddd
#       bbbb aaaa   cccc dddd
#
# Ces zones ont un écart de 2 entre elles.

# Trouvons toutes les paires avec un tel écart: 
bordsMontants = []
bordsDescendants = []
for i in range(0, len(sensors)-1):
    s1 = sensors[i]
    for j in range(i+1, len(sensors)):
        s2 = sensors[j]
        if distanceManhattan(s1['pt'], s2['pt']) == s1['distance'] + s2['distance'] + 2:
            sgnX = sign(s2['x'] - s1['x'])
            sgnY = sign(s2['y'] - s1['y'])
            d1 = s1['distance'] + 1
            d2 = s2['distance'] + 1
            coins = [  (s1['x']+sgnX*d1, s1['y']),  (s1['x'], s1['y']+sgnY*d1),  (s2['x']-sgnX*d2, s2['y']),  (s2['x'], s2['y']-sgnY*d2)  ]   # marche aussi avec sign = 0
            bouts = (sorted(coins))[1:3]
            longueur = abs(bouts[0][0] - bouts[1][0]) + 1
            segment = [longueur, bouts]
            
            if sgnX != sgnY:
                bordsMontants.append(segment)
            else:
                bordsDescendants.append(segment)


# Deux techniques possibles, la 1re plus lente, la seconde immédiate
# (1) Entre bords montants et descendants, on prend la catégorie avec les segments
#     les plus courts au total, et on cherche le point isolé sur eux.

if sum(l for [l,b] in bordsMontants) < sum(l for [l,b] in bordsDescendants):
    bords = bordsMontants
    directionY = 1
else:
    bords = bordsDescendants
    directionY = -1

for (l, (b1, b2)) in bords:
    for i in range(l):
        verifierPoint(b1[0] + i, b1[1] + directionY*i, sensors)


# (2) On fait les intersections de chaque paire bord montant / bord descandant
#     et on teste. Sans doute que les bord de longueur 1 (descendant et montant à la fois)
#     devraient être appairés à la fois avec ceux qui montent et ceux qui descendent ?
#     Avec mes données, il n'y a qu'un segment qui monte et qu'un qui descend, de toute façon…

for (lm,((xm,ym),_)) in bordsMontants:
    for (ld,((xd,yd),_)) in bordsDescendants:
        if (xm + ym + xd + yd ) % 2 == 1:
            continue
        (x,y) = ( (xm - ym + xd + yd) // 2 , (-xm + ym + xd + yd) // 2 )
        if x >= xm and x >= xd and x < xm+lm and x < xd+ld:
            verifierPoint(x,y, sensors)