Force Brute.

Soyons honnêtes, le premier exercice, je l'ai bourriné en force brute.
Objectif : soit une ligne donnée, trouver le nombre de cases qui ne contiennent pas de balises.
Donc les cases visibles par une robot-senseur quelconque, moins les balises sur la ligne (piège, haha !).

Je suis tombé dans un autre piège : il faut scanner la ligne 2 000 000, mais pour l'exemple (pour valider le code) il faut scanner la ligne 10. Mais bon, la réponse pour la ligne 10 du problème complet, c'pas la réponse attendue, bref...

La méthode bourrine :
* pour chaque robot-senseur qui voit la ligne donnée :
* faire un set() des cases vues set(range(début, fin)) ;
* union des sets() ;
* compter sa taille ;
* lister pour chaque robot-senseur sa balise, si elle est sur la bonne ligne ;
* supprimer les balises trouvées.

Ça marche en 1,25 secondes sur les données réelles, le résultat étant de 5838453 on a quand même fait un set-comprehension en double boucle d'une taille non négligeable.
La rumeur comme quoi Python c'est lent, c'pas toujours vrai hein, ya aucune optimisation dans mon code.

import sys
import re
def manhattan(x1, y1, x2, y2, *args):
 return abs(x1-x2) + abs(y1-y2)
class Sensor:
 def __init__(self, *args):
 self.sx, self.sy, self.bx, self.by, *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 range(self.sx-deltax, self.sx+deltax+1)
# inputs
line_to_check = 2000000 if len(sys.argv) <= 1 else int(sys.argv[1])
zone = line_to_check * 2
regex = re.compile(
 r"Sensor at x=(-?\d+), y=(-?\d+): "
 r"closest beacon is at x=(-?\d+), y=(-?\d+)")
data = [
 regex.match(line).groups()
 for line in sys.stdin
]
sensors = [Sensor(*(int(x) for x in line), zone) for line in data]
result1 = len(set(
 pos
 for sensor in sensors if line_to_check in sensor
 for pos in sensor[line_to_check]
)) - len(set(s.bx for s in sensors if s.by == line_to_check))
print(f"No beacon on {result1} positions\n")

Pour l'exercice 2, la méthode bourrine est hors de question.
Parce que sinon, mon PC serait toujours en train de calculer là.
Et l'énergie coûte plus cher que mon temps de cerveau disponible.
Optimisé, ça prend quand même 19 secondes, le ventilo a le temps de décoller.

• Yth.