Re: Force Brute.

Voilà le code à rajouter, on refait la classe en ZoneSensor pour retourner les bornes de l'intervalle sur une ligne, et à l'intérieur de la zone [0, 4000000] :

class ZoneSensor:
 def __init__(self, *args):
 self.sx, self.sy, self.bx, self.by, self.zone, *self.other = args
 self.distance = manhattan(*args)
 def __contains__(self, line):
 return abs(self.sy-line) <= self.distance
 def __getitem__(self, line):
 deltax = self.distance - abs(self.sy-line)
 return max(0, self.sx-deltax), min(self.zone, self.sx+deltax)
zone = line_to_check * 2
sensors = [ZoneSensor(*(int(x) for x in line), zone) for line in data]
try:
 for line in range(zone, -1, -1):
 r = sorted([sensor[line] for sensor in sensors if line in sensor])
 if r[0][0] != 0:
 raise BaseException(0, line)
 xmax = 0
 for s, e in r:
 if s > xmax:
 raise BaseException(s-1, line)
 xmax = max(xmax, e)
 if xmax != zone:
 raise BaseException(zone, line)
 print("Nothing found, there is a bug")
except BaseException as e:
 x, y = e.args
 print(f"Beacon on position {x}, {y}, value={x*4000000+y}")

Le sorted au début de la boucle va ordonner par le premier élément du tuple, donc le début des intervalles, puis en cas d'égalité par le second. A partir de là on sait que les intervalles vont de gauche à droite.
On note la fin de notre intervalle consolidé, et si l'intervalle suivant commence après, bingo, on a trouvé !
On teste vite fait au début ou à la fin, si notre case à trouver ne serait pas au début ou à la fin, et voilà.

Et bien sûr, on va pas se fouler, exception quand on a trouvé quelque chose : on arrête tout et on jubile !

À noter que je pars de la ligne du bas, mon nez m'a dit que l'auteur allait fourber et mettre la ligne à trouver vers la fin, j'avais raison, la mienne est la 3 391 794.
C'est peut-être là où je gagne le plus de temps en fait.
Sinon, pour essayer d'avoir de la chance, on peut parcourir la zone avec un index qui se balade en parcourant tout.

• step = un nombre premier avec 4000000
• i = 4000000 # parce que line % 4000000 ne vaudra jamais 4000000
• i = (i + step) % 4000000

En moyenne on va mettre pareil que si on ne sait pas où est la ligne, mais on tape au milieu dès le début et comme la probabilité que l'auteur n'ait pas mis sa ligne proche du bord, pour empêcher la force brute, est assez élevée, on a plus de chance d'avoir de la chance.
De l'autre côté (lignes croissantes de 0 à 4000000) ça prend 1min11s, et bien sûr on a le même résultat.
Avec un step de 747319 (nombre premier, donc premier avec 4000000, choisi au pif), je trouve le résultat en 49 secondes, assez proche de la moitié de la recherche totale ((1m11s+19s)/2=45s).

• Yth.