Forum Programmation.autre Avent du Code jour 15

Posté par  (Mastodon) . Licence CC By‑SA.
Étiquettes :
2
15
déc.
2022

En ce jour 15 nous explorons le vide intersidéral avec des robots automatisés qui vont s'éparpiller dans l'infini, et scanner les alentours.
Ils sont super évolués, mais bon, en vrai ils se posent un peu n'importe où, et détectent uniquement une balise, la plus proche d'eux.
Là où ils sont malins c'est qu'ils font un pas de côté s'il y a deux balises à la même distance, comme ça, flemmards qu'ils sont, il n'en voient plus qu'une seule.

Avec notre super transmetteur magique à l'écran pété dans les épisodes précédents, et qui a pris la flotte, on a la position des robots-senseurs, et de la balise qu'il voient.

L'espace est grand, 4 millions de parsecs (ou de m, ou d'angström ou de cases, comme vous voulez, ya pas d'échelle) de côté.
Mais quand je vous dis que les robots sont super balaise : ils arrivent à couvrir l'intégralité de la zone, sauf une position, à 38 robots !

Et faut la trouver cette position, parmi les 16 000 008 000 001 de positions possibles.
Autant dire que la force brute ça va pas le faire.

  • Yth.

  • # Force Brute.

    Posté par  (Mastodon) . Évalué à 2. Dernière modification le 15 décembre 2022 à 10:37.

    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.

    • [^] # Re: Force Brute.

      Posté par  . Évalué à 2. Dernière modification le 15 décembre 2022 à 12:00.

      Ma partie 2 prend 1min 30 (sur un PC un peu vieillot).
      L'idee de l'optim c'est de ne pas lister toute les valeur ou le beacon ne peut pas etre present pour un sensor mais definir l'intervale par ses limites, et faire l'union des intervales. Car il y a tres peu d'intervales mais ils sont enormes.

      C'est quoi ton optim qui donne 19 secondes?

      Excusez l'absence d'accents dans mes commentaires, j'habite en Australie et n'ai pas de clavier francais sous la main.

      • [^] # Re: Force Brute.

        Posté par  (Mastodon) . Évalué à 2.

        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.

        • [^] # Re: Force Brute.

          Posté par  (Mastodon) . Évalué à 2. Dernière modification le 15 décembre 2022 à 13:05.

          En très pythonesque, l'itération par nombre premier se fait comme ça :

          def iter():
    step, line = 747319, zone
    while True:
        yield line
        line = (line + step) % zone

for line in iter():
    ...
          • Yth.

          • [^] # Re: Force Brute.

            Posté par  (Mastodon) . Évalué à 2.

            D'ailleurs, en utilisant la technique de l'exercice 2 on peut refaire l'exercice 1 en immédiat :

            # Pas de zone comme pour l'exo1, on retourne les intervalles comme pour l'exo2
class RobotSensor:
    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 self.sx-deltax, self.sx+deltax

sensors = [RobotSensor(*(int(x) for x in line)) for line in data]
r = sorted([sensor[line_to_check] for sensor in sensors if line_to_check in sensor])

xmin, xmax, holes = r[0][0], 0, 0
for s, e in r:
    if s > xmax:
        holes += s - xmax
    xmax = max(xmax, e)
beacons = len(set(s.bx for s in sensors if s.by == line_to_check))
result1 = xmax - xmin + 1 - holes - beacons
print(f"No beacon on {result1} positions"
      f" [{xmin}->{xmax}, {holes} holes and {beacons} beacons]\n")

            Le calcul est immédiat.

            • Yth.

            • [^] # Re: Force Brute.

              Posté par  (Mastodon) . Évalué à 2. Dernière modification le 16 décembre 2022 à 11:27.

              Alors j'ai un bug : il faut écrire if s > xmax + 1: à la place de if s > xmax:.

              Paradoxalement ça ne pose aucun problème avec les données réelles, mais ça bugge avec les données de test, où sur un bord entre deux zone, adjacentes sur 6 cases, je trouve des trous que je ne devrais pas trouver.

              Bref.

              • Yth.

  • # Unions d'intervalles

    Posté par  (site web personnel) . Évalué à 3.

    Voilà, avec une implémentation des unions d'intervalles sécants.

    from __future__ import annotations

import re

from collections import namedtuple
from typing import Tuple, Iterable, List, Optional, Type

import aoc


Coords = Tuple[int, int]


class Point(namedtuple('Point', ['x', 'y'])):
    __slots__ = ()

    def __str__(self) -> str:
        return "({},{})".format(self.x, self.y)

    def dist(self, other: Point) -> int:
        return abs(self.x - other.x) + abs(self.y - other.y)


class Interval:
    def __init__(self, start: int, end: int) -> None:
        if start >= end:
            raise ValueError("unsupported empty or negative interval")
        self.start = start
        self.end = end

    def __str__(self) -> str:
        return "[{},{}[".format(self.start, self.end)

    def __len__(self) -> int:
        return self.end - self.start

    def __contains__(self, value: int) -> bool:
        return value >= self.start and value < self.end

    def intersects(self, other: Interval) -> bool:
        return max(self.start, other.start) < min(self.end, other.end)

    def union_update(self, other: Interval) -> bool:
        if not self.intersects(other):
            return False
        self.start = min(self.start, other.start)
        self.end = max(self.end, other.end)
        return True


class Sensor:
    def __init__(self, position: Point, beacon: Point):
        self.position = position
        self.beacon = beacon
        self.range = position.dist(beacon)

    def covers(self, y: int) -> bool:
        dist = abs(y - self.position.y)
        return dist <= self.range

    def coverage(self, y: int) -> Optional[Interval]:
        if not self.covers(y):
            return None
        else:
            dist = abs(y - self.position.y)
            return Interval(self.position.x - self.range + dist,
                            self.position.x + self.range + 1 - dist)

    re_line = re.compile(r'^Sensor at x=(-?\d+), y=(-?\d+): '
                         + r'closest beacon is at x=(-?\d+), y=(-?\d+)\n?$')

    @classmethod
    def import_line(class_, line: str) -> Sensor:
        match = class_.re_line.match(line)
        if match is None:
            raise ValueError("invalid sensor description")
        position = Point(int(match.group(1)), int(match.group(2)))
        beacon = Point(int(match.group(3)), int(match.group(4)))
        return class_(position, beacon)


class SensorArray:
    def __init__(self, sensors: Iterable[Sensor]):
        self.sensors = list(sensors)

    @classmethod
    def import_lines(class_, lines: Iterable[str]) -> SensorArray:
        return class_(Sensor.import_line(line) for line in lines)

    def coverage(self, y: int) -> List[Interval]:
        intervals: List[Interval] = []
        for sensor in self.sensors:
            if not sensor.covers(y):
                continue
            new_interval = sensor.coverage(y)
            if new_interval is None:
                continue
            new_intervals: List[Interval] = []
            for interval in intervals:
                if not new_interval.union_update(interval):
                    # new_interval did not absorb interval
                    new_intervals.append(interval)
            new_intervals.append(new_interval)
            intervals = new_intervals
        return intervals


def solve1(lines: Iterable[str]) -> int:
    """Solve part 1 of today's puzzle"""
    array = SensorArray.import_lines(lines)
    beacons = {sensor.beacon for sensor in array.sensors}
    y = 2000000
    coverage = array.coverage(y)
    total = 0
    for interval in coverage:
        total += len(interval)
        total -= sum((beacon.y == y and beacon.x in interval)
                     for beacon in beacons)
    return total


def solve2(lines: Iterable[str]) -> int:
    """Solve part 2 of today's puzzle"""
    array = SensorArray.import_lines(lines)
    position: Optional[Point] = None
    for y in range(4000000):
        if y % 100000 == 0:
            print(y)
        coverage = array.coverage(y)
        if len(coverage) < 2:
            continue
        return min(interval.end for interval in coverage) * 4000000 + y
    raise ValueError("no solution found")

    • [^] # Re: Unions d'intervalles

      Posté par  (site web personnel) . Évalué à 3.

      Il va sans dire que je ne suis pas pleinement satisfait de la recherche en semi-force brute pour la deuxième étape, intellectuellement parlant.

      Mais bon, la flemme de concevoir et d'implémenter un algorithme d'union de parallélogrammes. Il y a des tas de cas, et autant avec des rectangles ça se fait bien en itérant sur chaque coordonnée, autant avec les parallélogrammes, c'est compliqué.

      • [^] # Re: Unions d'intervalles

        Posté par  . Évalué à 3.

        parallélogrammes

        Plus précisément ce sont des carrés tournés de 45°. Je sais pas si ça simplifie…

  • # Une solution brillante

    Posté par  (site web personnel) . Évalué à 3.

    Je viens de tomber sur une solution que je trouve assez géniale : https://github.com/JakubDotPy/aoc2022/blob/master/day15/part2.py

    La solution sera forcément à une intersection de frontières de zones couvertes par les capteurs. Bon, pas forcément, elle pourrait être dans un coin, mais c'est plus que douteux. On pourrait quand même tester.

    Bref, entre les intersections et les quatre coins de la grille, il n'est pas difficile de vérifier si l'un de ces points ne serait pas par hasard hors de portée de tous les capteurs…

    • [^] # Re: Une solution brillante

      Posté par  (Mastodon) . Évalué à 2.

      Ah, c'est joli ça, oui !
      Comme quoi on ferait mieux de réfléchir avant d'agir hein…

      • Yth.

      • [^] # Re: Une solution brillante

        Posté par  (site web personnel) . Évalué à 3. Dernière modification le 15 décembre 2022 à 22:19.

        Farpaitement !

        Et j'y ai aussi découvert les dataclasses. Très pratique ça, avec en plus l'option congélateur, ça va me simplifier la vie la prochaine fois que j'aurai affaire à des coordonnées.

        • [^] # Re: Une solution brillante

          Posté par  (Mastodon) . Évalué à 2. Dernière modification le 16 décembre 2022 à 15:29.

          Ah, c'est pas mal en effet !
          Plus d'init ou de repr, voire un triage automatiquement généré, ça va faire gagner du temps ce truc…

          • Yth, mon implémentation des intersection est sérieusement buggée…

    • [^] # Re: Une solution brillante

      Posté par  (site web personnel) . Évalué à 4. Dernière modification le 16 décembre 2022 à 09:14.

      J'y ai réfléchi cette nuit, on peut faire encore mieux. Premièrement parce qu'il n'est pas vraiment nécessaire de considérer les intersections de droites, mais seulement celles des segments qui délimitent les zones de chaque capteur (enfin, les segments juste un point plus loin en fait).

      Mais surtout parce que le point cherché est soit :

      • dans un coin du terrain et sur un segment ;
      • sur un bord du terrain et à l'intersection de deux segments ;
      • n'importe où ailleurs, mais à l'intersection de quatre segments.

      Bref, in n'a plus qu'à tester si un coin ne se trouverait pas sur un segment, et sinon, si on construit la liste des intersections, on n'a plus qu'à chercher si on ne trouve pas dedans :

      • un point qui serait sur un bord ;
      • un point qui s'y trouverait quatre fois.

  • # python, on a RAMé

    Posté par  . Évalué à 2.

    Un jour où la solution naïve à la première partie ne passe pas à l'échelle pour la seconde partie.

    J'ai d'abord fait une solution qui a explosé la RAM (4M*4M d'int, ça explose).
    Puis une solution sans rien en RAM mais qui explose le CPU (j'ai timeout à 10 minutes).
    Troisième solution qui est un compromis entre RAM et CPU. Je stocke des intervalles pour 4M de lignes ; comme les autres solutions présentées ici.
    Ça passe, en 40 secondes avec l'aide du JIT.

    code partie 2

    import sys

W = H = 4_000_000

# store position that are not reachable, row by row
L = [ [(0,0) for _ in range(32)] for _ in range(H+1) ]

for i,l in enumerate(sys.stdin.read().splitlines()):
    (_,_,X,Y,_,_,_,_,A,J) = l.split(" ")
    x, y = int(X[2:-1]), int(Y[2:-1])
    a, b = int(A[2:-1]), int(J[2:])
    d = abs(x-a)+abs(y-b)
    for ny in range(y-d, y+d+1):
        if ny>=0 and ny<=H:
            dy = abs(ny-y)
            dx = d-dy
            L[ny][i] = (x-dx,x+dx)

for (y,I) in enumerate(L):
    SI = sorted(I)
    maxx = 0
    for (a,b) in SI:
        if a>maxx+1:
            print(y, maxx+1, (maxx+1)*4_000_000+y)
            sys.exit(0)
        maxx = max(maxx,b)

    • [^] # Re: python, on a RAMé

      Posté par  (site web personnel) . Évalué à 4. Dernière modification le 16 décembre 2022 à 09:15.

      Tiens, je n'avais pas pensé à Pypy. Pour info, ma solution termine la seconde partie – ligne par ligne, avec calcul d'unions d'intervalles – en 2,7 s sous Pypy.

      • [^] # Re: python, on a RAMé

        Posté par  . Évalué à 2.

        À priori on a le même algo. Peut être ma fonction d'union d'intervalles moins efficace. Faudrait que je profile. Mais là j'ai deux jours de retard alors je vais passer :)

Suivre le flux des commentaires

Note : les commentaires appartiennent à celles et ceux qui les ont postés. Nous n’en sommes pas responsables.