• # python, vite fait bien fait

    Posté par  . Évalué à 4.

    Le parsing de l'input est presque plus long à écrire que l'application de règles : 4 boucles for imbriquées et 4 split contre 3 boucles while imbriquées.

    Voici mon code pour la partie deux. La partie est identique excepté la condition de sortie.

    import sys

W = 1000
H = 200

L = [[0 for _ in range(W)] for _ in range(H)]  # full or air

def s2li(s,sep=','):
    return list(map(int,s.split(sep)))

MAX_Y = 0
for l in sys.stdin.read().splitlines():
    lp = l.split(" -> ")
    for f,t in zip(lp,lp[1:]):
        (a,b,c,d)= (*s2li(f),*s2li(t))
        x0 = min(a,c)
        y0 = min(b,d)
        x1 = max(a,c)
        y1 = max(b,d)
        MAX_Y = max(MAX_Y, y1)
        for x in range(x0,x1+1):
            for y in range(y0,y1+1):
                L[y][x] = 1
for x in range(W):
    L[MAX_Y+2][x] = 1 # rock on the ground

stop = False
N = 0
while not stop:
    N += 1
    y = 0
    x = 500
    more = True  # can all left or right 
    while more and not stop:
        more = False
        while L[y][x]==0 : #and not stop:  # if only air
            y+=1
            stop = y == MAX_Y+2
        if L[y][x-1]==0: # can fall left
           x -= 1
           more = True
        elif L[y][x+1]==0: # can fall right
            x += 1
            more = True
        else:
            stop = y == 1 # can't put more sand
    L[y-1][x] = 2 # mark sand

print(N)

    Et une jolie nimage de la caverne remplie de sable:

    • [^] # Re: python, vite fait bien fait

      Posté par  . Évalué à 2.

      Comment as-tu généré l'image?

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

      • [^] # Re: python, vite fait bien fait

        Posté par  . Évalué à 2.

        J'aime bien utiliser le format PNM car c'est du texte et donc facile à générer.

        Sous linux, ça se visualise nativement. Mais ça peut être converti en PNG grâce à ImageMagic : convert a.pnm -scale 400% a.png

  • # En Python, modélisé

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

    from __future__ import annotations

import enum
import io
import itertools

from typing import Iterable, List, Tuple

import numpy as np
import numpy.typing as npt


Coords = Tuple[int, int]


class Material(enum.Enum):
    AIR = enum.auto()
    ROCK = enum.auto()
    SAND = enum.auto()


class Slice:
    def __init__(self, array: npt.ArrayLike, leak: Coords) -> None:
        self.matrix: npt.NDArray = np.array(array)
        self.leak = leak

    def pour(self) -> bool:
        """Inject a unit of sand.

        Return False if it was blocked, True if it fell into the void."""
        y, x = self.leak
        while y < self.matrix.shape[0] - 1:
            y_ = y + 1
            for x_ in (x, x - 1, x + 1):
                if self.matrix[y_, x_] is Material.AIR:
                    # Sand can flow down
                    y = y_
                    x = x_
                    break
            else:
                # Blocked
                self.matrix[y, x] = Material.SAND
                return False
        # Sand fell all the way down into the void
        return True

    def __str__(self) -> str:
        result = io.StringIO()
        for line in self.matrix:
            for point in line:
                if point is Material.AIR:
                    result.write(' ')
                elif point is Material.ROCK:
                    result.write('█')
                elif point is Material.SAND:
                    result.write('░')
                else:
                    assert False  # we covered all cases
            result.write('\n')
        return result.getvalue()

    def add_segment(self, start: Coords, end: Coords) -> None:
        y1, x1 = start
        y2, x2 = end
        if y1 == y2:
            x1, x2 = min(x1, x2), max(x1, x2)
            ys = (y1 for _ in range(x1, x2 + 1))
            xs = (x for x in range(x1, x2 + 1))
        elif x1 == x2:
            y1, y2 = min(y1, y2), max(y1, y2)
            ys = (y for y in range(y1, y2 + 1))
            xs = (x1 for _ in range(y1, y2 + 1))
        for y, x in zip(ys, xs):
            self.matrix[y, x] = Material.ROCK


def import_segments(
        lines: Iterable[str]
        ) -> Tuple[List[Coords], List[Tuple[Coords, Coords]]]:
    points: List[Coords] = []
    segments: List[Tuple[Coords, Coords]] = []

    def coords(word: str) -> Coords:
        parts = word.split(',')
        if len(parts) != 2:
            raise ValueError("unexpected number of coordinates")
        return int(parts[1]), int(parts[0])

    for line in lines:
        words = line.rstrip().split(' -> ')
        segment_points = [coords(word) for word in words]
        points.extend(segment_points)
        segments.extend(itertools.pairwise(segment_points))
    return points, segments


def import_slice1(lines: Iterable[str]) -> Slice:
    points, segments = import_segments(lines)
    y_leak, x_leak = 0, 500
    points.append((y_leak, x_leak))
    xmin = min(x for _, x in points) - 1
    xmax = max(x for _, x in points) + 1
    ymin = min(y for y, _ in points)
    ymax = max(y for y, _ in points)
    if ymin < 0:
        raise ValueError("unexpected negative coordinate")
    xshift = xmin
    matrix = np.full(((ymax + 1), xmax - xshift + 1), Material.AIR)
    result = Slice(matrix, (0, 500 - xshift))
    for (y1, x1), (y2, x2) in segments:
        result.add_segment((y1, x1 - xshift), (y2, x2 - xshift))
    return result


def import_slice2(lines: Iterable[str]) -> Slice:
    points, segments = import_segments(lines)
    y_leak, x_leak = 0, 500
    points.append((y_leak, x_leak))
    xmin = min(x for _, x in points)
    xmax = max(x for _, x in points)
    ymin = min(y for y, _ in points)
    ymax = max(y for y, _ in points) + 2  # including the floor
    # Update xmin and xmax to accomodate a pyramid of sand
    xmin = min(xmin, x_leak - (ymax - y_leak))
    xmax = max(xmax, x_leak + (ymax - y_leak))
    if ymin < 0:
        raise ValueError("unexpected negative coordinate")
    xshift = xmin
    matrix = np.full(((ymax + 1), xmax - xshift + 1), Material.AIR)
    result = Slice(matrix, (0, 500 - xshift))
    for (y1, x1), (y2, x2) in segments:
        result.add_segment((y1, x1 - xshift), (y2, x2 - xshift))
    result.add_segment((ymax, xmin - xshift), (ymax, xmax - xshift))
    return result


def solve1(lines: Iterable[str]) -> int:
    """Solve part 1 of today's puzzle"""
    slice_ = import_slice1(lines)
    for i in range(10000):
        if slice_.pour():
            return i
    raise ValueError("Simulantion did not end within expected limit")


def solve2(lines: Iterable[str]) -> int:
    """Solve part 2 of today's puzzle"""
    slice_ = import_slice2(lines)
    for i in range(100000):
        _ = slice_.pour()
        if slice_.matrix[slice_.leak] is Material.SAND:
            return i + 1
    raise ValueError("Simulantion did not end within expected limit")

  • # Pistes pour la partie 2

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

    Je me demande s'il ne serait pas possible de résoudre la partie 2 bien plus vite, en calculant l'aire des zones protégées par des rochers.

    En effet, le nombre d'unités de sables tombées, c'est l'aire d'une triangle plein, moins celle des rochers qu'il contient, moins l'aire des zones protégées par ces derniers.

    Ceci dit, déterminer la zone protégée par l'ensemble des rochers, c'est loin d'être évident. La zone protégée par un segment horizontal, c'est facile, c'est un triangle dessous. La zone protégée par un segment vertical, c'est facile, c'est rien du tout. Mais quand on commence à avoir des segments horizontaux et verticaux qui se touchent, ça devient compliqué.

    Allez, une autre piste, sans doute pas beaucoup plus simple. On dirait qu'on peut déterminer la zone protégée par des rochers, non pas seulement par calcul, mais aussi par une simulation bizarre : faire couler de l'air depuis le bas vers le haut et regarder où il s'accumule. Mais ça pose le problème d'introduire cet air : il faut qu'il s'accumule et qu'il traverse en même temps les segments…

  • # Beaucoup de temps pour animer et afficher joli

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

    Parce que un truc de 351 * 175 dans le terminal c'est galère quand même…

    Bref, j'ai perdu plein de temps à faire une animation pas trop lente (j'ai fini par exponentiellement sauter des images : j'affiche l'image 2n), et réussir à faire entrer ça proprement dans le terminal. Après coup j'ai réalisé qu'il suffisait d'afficher chaque grain de sable une fois calculé, au lieu de tout retracer… Dans un terminal… Diantre…

    J'avais un bug débile aussi pour l'exo 2, comme je voulais un sol pas trop large pour l'affichage, j'ai essayé d'être intelligent, et ça n'a pas marché, j'ai fini par faire un affichage avec un sol pas très large, puis rajouter un sol très très large.

    Après j'ai triché et j'ai juste mis le sol en dur aux bonnes dimensions pour tout afficher, une fois le résultat obtenu.

    Deux belles images :
    Premier exercice
    Deuxième exercice

    Et un code probablement trop complexe.
    L'affichage déjà

    class display:
    sand = " "  # "▒"
    sandcolor = 220
    void = " "
    rock = " "  # "█"
    rockcolor = 94
    start = "+"

    def __init__(self, x0, x1, y0, y1, *rocks):
        self.x0, self.x1, self.y0, self.y1 = x0, x1, y0, y1
        self.bg = [[
            f"{self.color(bg=0)}{self.void}" for x in range(x0, x1+1)
        ] for y in range(y0, y1+1)]
        for x in rocks:
            self.bg[x[1]-y0][x[0]-x0] = f"{self.color(bg=self.rockcolor)}{self.rock}"
        self.bg[0][500-x0] = self.start
        self.background = "\n".join(
            "".join(self.bg[y][x] for x in range(len(self.bg[0])))
            for y in range(len(self.bg))
        )
        self.width = len(self.bg[0])
        self.height = len(self.bg)

    def color(self, bg=None, fg=None, rgb=None):
        bg = f"\033[48;5;{bg}m" if bg else ""
        fg = f"\033[38;5;{fg}m" if fg else ""
        fg = f"\033[38;2;{rgb[0]};{rgb[1]};{rgb[2]}m" if rgb else fg
        if not bg and not fg:
            return "\033[0m"
        return f"{bg}{fg}"

    def cursor(self, row=0, col=0):
        if row < 0:
            row = self.height - row
        return f"\033[{row+1};{col+1}H"

    def __call__(self, *items, wait=0):
        print(self.str(items))
        if wait:
            time.sleep(wait)

    def item(self, item):
        return (
            f"{self.cursor(col=item[0]-self.x0, row=item[1]-self.y0)}"
            f"{self.color(bg=self.sandcolor)}"
            f"{self.sand}"
        ) if (
            item[0] >= self.x0 and
            item[0] <= self.x1 and
            item[1] >= self.y0 and
            item[1] <= self.y1
        ) else ""

    def str(self, items):
        return (
            f"{self.cursor()}"
            f"{self.color()}"
            f"{self.background}"
            f"{''.join(self.item(item) for item in items)}"
        )

    Et le code en lui-même :

    def input():
    for line in sys.stdin:
        x = list(tuple(map(int, r.split(','))) for r in line.split(' -> '))
        for _ in zip(x[:-1], x[1:]):
            yield _


class RockFormation:
    def __init__(self, input):
        self.finished = False
        self.source = (500, 0)
        self.carte = set()
        self.sand = set()
        for _ in input():
            self._add_rocks(*_)
        self.dim = self.calcdim(self.carte)
        self.rock = self.carte.copy()
        self.sand = set()

    def _add_rocks(self, r1, r2):
        x1 = min(r1[0], r2[0])
        x2 = max(r1[0], r2[0])
        y1 = min(r1[1], r2[1])
        y2 = max(r1[1], r2[1])
        self.carte.update(
            (x, y)
            for x in range(x1, x2+1)
            for y in range(y1, y2+1)
        )

    def add_rocks(self, r1, r2):
        self._add_rocks(r1, r2)
        self.dim = self.calcdim(self.carte)
        self.rock = self.carte.copy()

    def calcdim(self, carte):
        return (
            min(x[0] for x in carte),
            max(x[0] for x in carte),
            0,
            max(x[1] for x in carte),
        )

    def __call__(self):
        s = self._sand(*self.source)
        if not self.finished:
            if s in self.carte:
                print(f"Re-adding {s} !")
                raise IndexError
            self.carte.add(s)
            self.sand.add(s)
        if s == self.source:
            self.finished = True
        return s

    def _sand(self, x, y):
        if x < self.dim[0] or x > self.dim[1] or y == self.dim[3]:
            self.finished = True
            return x, y
        while (x, y+1) not in self.carte:
            y += 1
        if (x-1, y+1) not in self.carte:
            x, y = self._sand(x-1, y+1)
        elif (x+1, y+1) not in self.carte:
            x, y = self._sand(x+1, y+1)
        return x, y


def simulation(rocks):
    d()
    while rocks.finished is False:
        print(d.item(rocks()))


# Inputs
rocks = RockFormation(input)
# First simulation
d = display(*rocks.dim, *rocks.rock)
simulation(rocks)
result1 = len(rocks.sand)
print(f"{d.cursor(row=-4)}{d.color()}Resting sand : {len(rocks.sand)}")

# Second simulation preparation
rocks.finished = False
# Limited floor for display
# rocks.add_rocks(
#     (rocks.dim[0]-1, rocks.dim[3]+2),
#     (rocks.dim[1]+1, rocks.dim[3]+2)
# )
# d = display(*rocks.dim, *rocks.rock)
# # Big (not too huge) floor for simulation
# rocks.add_rocks(
#     (rocks.dim[0]-1000, rocks.dim[3]),
#     (rocks.dim[1]+1000, rocks.dim[3])
# )
# Enough floor knowing the solution
rocks.add_rocks((325, 174), (675, 174))
d = display(*rocks.dim, *rocks.rock)
simulation(rocks)
print(f"{d.cursor(row=-3)}{d.color()}", end='')
print(f"Resting sand : {result1}")
print(f"Filling sand : {len(rocks.sand)}")
print(f"Dimensions 1 : {dim1}")
print(f"Dimensions 2 : {rocks.dim}")
display2 = d.str(rocks.sand)

# Et enfin afficher le résultat pour les screenshots
w, h = tuple(os.get_terminal_size())
print("\n"*h)
print(display1)
print("\n"*h)
print(display2)
print(f"{d.cursor(row=-2)}{d.color()}", end='')

    Il faut vachement zoomer arrière dans le terminal, après c'est écrit trop petit pour lire, mais on a une belle animation :)

    • Yth.

    • [^] # Re: Beaucoup de temps pour animer et afficher joli

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

      Et maintenant, on allume le cerveau :

      Pour l'exercice 2, la base se calcule trivialement : le sable formant une pyramide, on sait qu'il va de 500-hauteur à 500+hauteur, vu qu'on a 174 de haut (de 0 à 173), la coursive est en 174, et le sol en 175, le sable s'entasse donc de 326 à 674, et le sol doit s'étendre une case plus loin : de 325 à 675, comme « triché » dans mon code, sauf que ça se calcule de façon sûre avec d'autres données en entrée.

      Pour l'exercice 2 encore, et suivant la remarque de Tanguy sur les zones protégées par les rochers pour calculer des surfaces :
      On va créer des cases « dark » sous les lignes.
      Une ligne de (x1, y1) à (x2, y2) avec x1<=x2 va générer une ligne protégée de gauche à droite de (x1+1, max(y1, y2)) à (x2-1, max(y1, y2)), donc si x1+1>x2-1 (ça arrive quand x1==x2, ligne verticale, ou quand la ligne horizontale fait 2 de large : x2=x1+1) on ne met rien.
      Après on peut filtrer les cases bouchées (dark et rocher) sur la zone de pyramide de sable, c'est à dire quand 500-y <= x <= 500+y pour chaque élément. Ici on ne supprime rien, donc on n'a pas à gérer d'éventuels effets de bord, avec une plateforme qui dépasse de la pyramide de sable et peut protéger une zone qui serait ensevelie si la source du sable était plus haute.
      La taille de la pyramide est, en prenant le triangle de droite et en le posant retourné au dessus du triangle de gauche, un carré de la hauteur totale, soit 175^2 = 30625 grains potentiels.
      Ici ça ne suffit pas : un mur vertical sous une plate-forme va protéger une zone. Donc il faut ne pas réduire la ligne sur un côté si on a un rocher juste là.
      Les données en entrée ne sont pas collaboratives, donc en fait on essaie toujours d'élargir la plate-forme qu'on considère pour la zone protégée du dessous, sur la gauche et la droite, puis on protège la ligne en dessous en retirant un élément à gauche et un à droite.
      -> Ça fonctionne, il faut juste faire très attention à protéger une ligne en dessous des derniers rochers, le niveau de la coursive, mais pas plus bas au niveau du sol et en dessous, en traitant les données en flux on n'a pas la taille de la zone, donc la position du sol, donc on doit élaguer après coup pour le décompte : tout ce qui est en y < 175.
      Voici l'image générée avec les rochers et les zones protégées en dessous :

      Titre de l'image

      Pour mon exemple, j'ai en zones protégées (rochers et dark) 1804 cases, donc 30625-1804 = 28821, c'est mon résultat !

      Pour les deux exercices :
      Quand le sable n'est pas en chute libre, il va s'empiler sur toutes les cases visiter, à terme, sauf à sortir du terrain de jeu pour l'exercice 1.
      Donc on n'est pas obligé de faire tomber le sable grain par grain, mais on peut poser des couches, avec un algo récursif.
      Il suffit de le faire prendre en remontant la récursion quand on a trouver où se poser en bas. Parce que si on ne trouve pas où se poser (exercice 1 uniquement), alors aucun grain suivant ne pourra se poser.
      C'est beaucoup plus simple à mettre en œuvre pour l'exo 2 puisqu'un fil de sable trouvera toujours un endroit où s'arrêter, donc on peut remplir en descendant, et explorer à la fois à gauche et à droite en bas de chaque chute libre.
      Pour l'exo 1, si on parcours normalement, qu'on pose les grains en remontant de la récursion et pas avant de descendre, et qu'on sort brutalement (exception python en haut de l'exploration) dès qu'on est au bout, on devrait avoir le résultat.

      Je ne l'ai pas encore fait, il est tard, je devrais commencer ma journée de taf quand même :D

      • Yth.

  • # Optimisation

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

    Visiblement, il y a une optimisation possible : une si un grain de sable, lâché du point de départ, tombe à un endroit, on peut lâcher ce grain et les suivants de cet endroit, jusqu'à ce qu'il soit ensablé…

    • [^] # Re: Optimisation

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

      Avec ladite optimisation :

      from __future__ import annotations

import enum
import io
import itertools

from typing import Iterable, Iterator, List, Tuple

import numpy as np
import numpy.typing as npt


Coords = Tuple[int, int]


class Material(enum.Enum):
    AIR = enum.auto()
    ROCK = enum.auto()
    SAND = enum.auto()


class Slice:
    def __init__(self, array: npt.ArrayLike, leak: Coords) -> None:
        self.matrix: npt.NDArray = np.array(array)
        self.leak = leak

    def pour(self) -> Iterator[bool]:
        """Inject a unit of sand.

        Yields False if it was blocked, True if it fell into the void.
        Stops when the leak is clogged up by a mountain of sand."""
        # List of coordinates to pour sand from
        sources: List[Coords] = []
        # Start at the original leak
        y, x = self.leak
        while True:
            # Our unit of sand is injected at current coordinates (y, x)
            while y < self.matrix.shape[0] - 1:
                y_ = y + 1
                for x_ in (x, x - 1, x + 1):
                    if self.matrix[y_, x_] is Material.AIR:
                        # Sand can flow down:
                        # * current coordinate is a good place to pour next
                        #   sand unit from;
                        sources.append((y, x))
                        # * current sand unit falls down one level.
                        y = y_
                        x = x_
                        break
                else:
                    # Ways down exhausted, sand is blocked
                    self.matrix[y, x] = Material.SAND
                    # Get out of the descent loop
                    break
            else:
                # Descent ended, sand fell all the way down
                yield True
                continue
            # Descent did not end, sand got blocked
            yield False
            if not sources:
                # Nowhere to pour sand from, even the leak is clogged up
                break
            # Pour next sand unit from last good place
            y, x = sources.pop()

    def __str__(self) -> str:
        result = io.StringIO()
        for line in self.matrix:
            for point in line:
                if point is Material.AIR:
                    result.write(' ')
                elif point is Material.ROCK:
                    result.write('█')
                elif point is Material.SAND:
                    result.write('░')
                else:
                    assert False  # we covered all cases
            result.write('\n')
        return result.getvalue()

    def add_segment(self, start: Coords, end: Coords) -> None:
        y1, x1 = start
        y2, x2 = end
        if y1 == y2:
            x1, x2 = min(x1, x2), max(x1, x2)
            ys = (y1 for _ in range(x1, x2 + 1))
            xs = (x for x in range(x1, x2 + 1))
        elif x1 == x2:
            y1, y2 = min(y1, y2), max(y1, y2)
            ys = (y for y in range(y1, y2 + 1))
            xs = (x1 for _ in range(y1, y2 + 1))
        for y, x in zip(ys, xs):
            self.matrix[y, x] = Material.ROCK


def import_segments(
        lines: Iterable[str]
        ) -> Tuple[List[Coords], List[Tuple[Coords, Coords]]]:
    points: List[Coords] = []
    segments: List[Tuple[Coords, Coords]] = []

    def coords(word: str) -> Coords:
        parts = word.split(',')
        if len(parts) != 2:
            raise ValueError("unexpected number of coordinates")
        return int(parts[1]), int(parts[0])

    for line in lines:
        words = line.rstrip().split(' -> ')
        segment_points = [coords(word) for word in words]
        points.extend(segment_points)
        segments.extend(itertools.pairwise(segment_points))
    return points, segments


def import_slice1(lines: Iterable[str]) -> Slice:
    points, segments = import_segments(lines)
    y_leak, x_leak = 0, 500
    points.append((y_leak, x_leak))
    xmin = min(x for _, x in points) - 1
    xmax = max(x for _, x in points) + 1
    ymin = min(y for y, _ in points)
    ymax = max(y for y, _ in points)
    if ymin < 0:
        raise ValueError("unexpected negative coordinate")
    xshift = xmin
    matrix = np.full(((ymax + 1), xmax - xshift + 1), Material.AIR)
    result = Slice(matrix, (0, 500 - xshift))
    for (y1, x1), (y2, x2) in segments:
        result.add_segment((y1, x1 - xshift), (y2, x2 - xshift))
    return result


def import_slice2(lines: Iterable[str]) -> Slice:
    points, segments = import_segments(lines)
    y_leak, x_leak = 0, 500
    points.append((y_leak, x_leak))
    xmin = min(x for _, x in points)
    xmax = max(x for _, x in points)
    ymin = min(y for y, _ in points)
    ymax = max(y for y, _ in points) + 2  # including the floor
    # Update xmin and xmax to accomodate a pyramid of sand
    xmin = min(xmin, x_leak - (ymax - y_leak))
    xmax = max(xmax, x_leak + (ymax - y_leak))
    if ymin < 0:
        raise ValueError("unexpected negative coordinate")
    xshift = xmin
    matrix = np.full(((ymax + 1), xmax - xshift + 1), Material.AIR)
    result = Slice(matrix, (0, 500 - xshift))
    for (y1, x1), (y2, x2) in segments:
        result.add_segment((y1, x1 - xshift), (y2, x2 - xshift))
    result.add_segment((ymax, xmin - xshift), (ymax, xmax - xshift))
    return result


def solve1(lines: Iterable[str]) -> int:
    """Solve part 1 of today's puzzle"""
    slice_ = import_slice1(lines)
    for i, fallen in enumerate(slice_.pour()):
        if fallen:
            return i
    raise ValueError("Simulation ended with unexpected sand leak clogged")


def solve2(lines: Iterable[str]) -> int:
    """Solve part 2 of today's puzzle"""
    slice_ = import_slice2(lines)
    for i, fallen in enumerate(slice_.pour()):
        if fallen:
            raise ValueError("Simulation ended with unexpected sand under the floor")
    return i + 1

      • [^] # Re: Optimisation

        Posté par  . Évalué à 2.

        J'ai essayé et ça ne m'a pas fait gagner grand chose. J'ai trouvé par contre une solution efficace.

        Au lieu de faire tomber un grain de sable, je regarde toutes les positions accessible depuis le point de départ avec comme règle les même mouvements qu'un pion aux échecs. Je passe de 27 minutes d’exécution à 0.7s.

        En groovy ça donne:

        import java.time.Duration
import java.time.Instant
import java.util.regex.Pattern

def start = Instant.now()
def sc = new Scanner(new File('input'))

record Point(int x, int y) {}

static Set<Point> readInput(Scanner sc) {
    def coordPattern = Pattern.compile("(\\d+),(\\d+)")
    def rocks = [] as Set<Point>

    while (sc.hasNextLine()) {
        def line = sc.nextLine()
        def matcher = coordPattern.matcher(line)
        Point prev = null
        while (matcher.find()) {
            def current = new Point(
                    Integer.parseInt(matcher.group(1)),
                    Integer.parseInt(matcher.group(2))
            )
            rocks << current
            if (prev != null) {
                for (def i = Math.min(prev.x(), current.x()); i < Math.max(prev.x(), current.x()); i++) {
                    rocks << new Point(i, current.y())
                }
                for (def j = Math.min(prev.y(), current.y()); j < Math.max(prev.y(), current.y()); j++) {
                    rocks << new Point(current.x(), j)
                }

            }
            prev = current
        }
    }
    return rocks
}

def rocks = readInput(sc)

def floor = rocks.max { it.y() }.y() + 2

def sand = 0
def newSands = [new Point(500, 0)]
while (!newSands.isEmpty()) {
    def nextSands = [] as Set<Point>
    for (s in newSands) {
        Set<Point> fallen = fall(s)
                .findAll { !rocks.contains(it) }
                .findAll { it.y() < floor }
        nextSands.addAll(fallen)
    }
    rocks.addAll(nextSands)
    sand += nextSands.size()
    newSands = nextSands
}

println(sand)
def duration = Duration.between(start, Instant.now())
println(duration)

static Set<Point> fall(Point sand) {
    return [
            sand,
            new Point(sand.x(), sand.y() + 1),
            new Point(sand.x() - 1, sand.y() + 1),
            new Point(sand.x() + 1, sand.y() + 1)
    ]
}

        https://linuxfr.org/users/barmic/journaux/y-en-a-marre-de-ce-gros-troll

Suivre le flux des commentaires

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