🚲 Tanguy Ortolo a écrit 12285 commentaires

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")

Un détail tout de même, ça semble évident mais ça peut demander un peu de concentration pour ne pas l'oublier en court de route : tant que vous n'êtes pas arrivé à vos fins, c'est à dire que vous n'avez pas assez d'informations, il ne faut pas donner le moindre indice qui laisserait soupçonner que vous n'appréciez pas ce démarchage.

Éviter par exemple des phrases comme « Au fait, comment avez-vous eu mon numéro de téléphone ? » Si votre interlocuteur commence à soupçonner que son appel vous dérange, il risque de ne pas vous croire si vous vous prétendez intéressé, et l'appel ne durera pas longtemps. Pas assez longtemps pour obtenir les infos que vous souhaitez en tout cas.

Ces démarcheurs savent très bien que ce qu'ils font est illégal, même s'ils prétendent parfois le contraire. Et sachant qu'ils peuvent être poursuivis, ou avoir diverses emmerdes comme être radiés de la plate-forme CPF, ils commencent à être assez méfiants.

L'autre jour, j'ai oublié ce principe et demandé directement à une démarcheuse où elle travaillait. Elle m'a fait répéter la question, et après avoir compris ma demande, elle a raccroché sans y mettre la moindre forme. Ni refus, ni excuse, ni au-revoir, juste raccroché. Si ce n'est pas de la méfiance, ça…

À titre d'exemple, j'ai pu piéger une entreprise de formation professionnelle qui se livrait au démarchage téléphonique. Sans doute sous-traité, mais ce n'est pas mon problème, les agissements d'un sous-traitant engagent évidemment la responsabilité de son donneur d'ordre.

Je me suis montré intéressé par une formation en langue anglaise, très utile pour mon travail. Le démarcheur m'a alors fait rappeler par un responsable des inscriptions, et je m'attendais au pire, c'est à dire à ce qu'il me demande mon numéro de sécurité sociale et qu'il réinitialise avec mon aide mon mot de passe pour accéder lui-même à mon compte CPF et m'inscrire à sa formation. Ç'aurait été une arnaque selon les règles, mais non, c'était un peu plus honnête, il m'a juste demandé mon adresse électronique, celle inscrite sur le compte CPF, ce qui lui a suffit à me pré-inscrire à des formations.

Vérification faite, les formations apparaissaient bien comme des propositions à valider, avec un organisme de formation tout à fait identifiable, en tout cas par la plate-forme CPF. J'en avais assez, et la fin de la discussion téléphonique a été assez intéressante :

• C'est bon, je vois bien les formations. Je vous remercie, j'ai toutes les informations qu'il me faut.
• Attendez, je peux vous expliquer la façon dont les formations vont se passer.
• Ce ne sera pas nécessaire, vraiment, j'ai tout ce qu'il me faut.
• Non, je ne vous ai pas expliqué…
• Si si, j'en sais assez je vous dit.
• Assez pour quoi ?
• Assez pour signaler votre démarchage illicite.
• Vous n'étiez pas intéressé par la formation ?
• Non, désolé, j'avais juste besoin d'informations pour le signalement.
• Vous nous avez tendu un piège alors ?
• C'est ça. Ça vous a plu ?
• Mais c'est dégueulasse ce que vous faites !
• Ah non, moi j'aide à faire respecter la loi. Ce que vous faites en revanche, c'est illégal. Si j'ai besoin d'une formation, je suis assez grand pour aller la chercher tout seul. Allez, bonne journée.

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

Bravo pour l'implémentation de mon idée !

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é…

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…

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")

On peut tricher en moins craignos. Un indice :

$ file 13.in
13.in: JSON data

Pour la définition de aoc.group_lines(lines: str), cf. hier

from __future__ import annotations

import itertools

from typing import Iterable, Iterator, List, Optional, Tuple, Union

import aoc


class Element:
    def __init__(self, value: Union[List[Element], int]):
        self.value = value

    def __lt__(self, other: Element) -> bool:
        if isinstance(self.value, int) and isinstance(other.value, int):
            return self.value < other.value
        if isinstance(self.value, list) and isinstance(other.value, list):
            for self_elt, other_elt in zip(self.value, other.value):
                if self_elt < other_elt:
                    return True
                if other_elt < self_elt:
                    return False
            # Ran out of elements on one of the lists
            return len(self.value) < len(other.value)
        if isinstance(self.value, int):
            return Element([self]) < other
        if isinstance(other.value, int):
            return self < Element([other])
        assert False  # should not happen: we covered all cases

    def __eq__(self, other: object) -> bool:
        if not isinstance(other, Element):
            return NotImplemented
        if isinstance(self.value, int) and isinstance(other.value, int):
            return self.value == other.value
        if isinstance(self.value, list) and isinstance(other.value, list):
            return (len(self.value) == len(other.value)
                    and all(self_elt == other_elt for self_elt, other_elt
                            in zip(self.value, other.value)))
        if isinstance(self.value, int):
            return Element([self]) == other
        if isinstance(other.value, int):
            return self == Element([other])
        assert False  # should not happen: we covered all cases

    def __str__(self) -> str:
        if isinstance(self.value, int):
            return str(self.value)
        elif isinstance(self.value, list):
            return '[{}]'.format(
                    ','.join(str(element) for element in self.value))
        assert False  # should not happen: we covered all cases


def import_element(chars: Iterable[str]) -> Element:
    element: Optional[Element] = None
    lists: List[List[Element]] = []  # List[List[Element]]
    current_list: Optional[List[Element]] = None
    current_int: Optional[int] = None
    for char in chars:
        if char == '[':
            if current_int is not None:
                raise ValueError("unexpected beginning of list")
            if current_list is not None:
                lists.append(current_list)
            current_list = []
        elif char == ']':
            if current_list is None:
                raise ValueError("unexpected end of list")
            # If we were parsing an int, add it before closing current list
            if current_int is not None:
                current_list.append(Element(current_int))
                current_int = None
            if lists:
                # We are closing a sub-list
                prev_list = lists.pop()
                prev_list.append(Element(current_list))
                current_list = prev_list
            else:
                # We are closing the top-level list
                element = Element(current_list)
                current_list = None
        elif char.isdecimal():
            value = int(char)
            if current_int is None:
                current_int = value
            else:
                current_int = 10 * current_int + value
                continue
        elif char == ',':
            if current_list is None:
                raise ValueError("unexpected separator")
            if current_int is not None:
                current_list.append(Element(current_int))
                current_int = None
        elif char == '\n':
            pass
        else:
            raise ValueError("unexpected character")
    if element is None:
        raise ValueError("nothing to parse")
    return element


def import_pairs(lines: Iterable[str]) -> Iterator[Tuple[Element, Element]]:
    for group in aoc.group_lines(lines):
        elements = [import_element(line) for line in group]
        if len(elements) != 2:
            raise ValueError("unexpected group length")
        yield (elements[0], elements[1])


def import_elements(lines: Iterable[str]) -> Iterator[Element]:
    for line in lines:
        if line and line != '\n':
            yield import_element(line)


def solve1(lines: Iterable[str]) -> int:
    """Solve part 1 of today's puzzle"""
    pairs = import_pairs(lines)
    return sum(i + 1 for i, (elt1, elt2) in enumerate(pairs) if elt1 < elt2)


def solve2(lines: Iterable[str]) -> int:
    """Solve part 2 of today's puzzle"""
    elements: Iterable[Element] = import_elements(lines)
    div1 = import_element("[[2]]")
    div2 = import_element("[[6]]")
    elements = sorted(itertools.chain(elements, (div1, div2)))
    key = 1
    for i, element in enumerate(elements):
        if element == div1 or element == div2:
            key *= i + 1
    return key

Au fait, vu les visualisations, vous avez évidemment remarqué que loin d'être une gorge de rivière, nous avions plutôt affaire à l'île de Numenor une montagne en forme d'étoile, n'est-ce pas ?

from __future__ import annotations

import itertools
import math
import re

from typing import Callable, Iterable, Iterator, List, Tuple


class Test:
    def __init__(self, div: int, rcpt1: int, rcpt2: int):
        self.div = div
        self.rcpt1 = rcpt1
        self.rcpt2 = rcpt2

    def __call__(self, n: int):
        if n % self.div == 0:
            return self.rcpt1
        else:
            return self.rcpt2


class Monkey:
    def __init__(self, number: int, items: List[int], op: Callable[[int], int], test: Test) -> None:
        self.number = number
        self.items = items
        self.op = op
        self.test = test
        self.activity = 0

    _re_monkey = re.compile(r'^Monkey (\d+):?\n?$')
    _re_items = re.compile(r'^\s*Starting items: (.*)\n?$')
    _re_op = re.compile(r'^\s*Operation: (.*)\n?$')
    _re_test = re.compile(r'^\s*Test: divisible by (\d+)\n?$')
    _re_true = re.compile(r'^\s*If true: throw to monkey (\d+)\n?$')
    _re_false = re.compile(r'^\s*If false: throw to monkey (\d+)\n?$')

    @classmethod
    def import_lines(class_, lines: Iterable[str]) -> Monkey:
        lines = iter(lines)
        number = int(class_._re_monkey.match(next(lines)).group(1))
        items = [int(word) for word in class_._re_items.match(next(lines)).group(1).split(', ')]
        op = import_op(class_._re_op.match(next(lines)).group(1))
        div = int(class_._re_test.match(next(lines)).group(1))
        rcpt1 = int(class_._re_true.match(next(lines)).group(1))
        rcpt2 = int(class_._re_false.match(next(lines)).group(1))
        test = Test(div, rcpt1, rcpt2)
        return class_(number, items, op, test)


def group_key() -> Callable[[str], int]:
    key = 0
    def aux(line: str):
        nonlocal key
        if line.rstrip() == '':
            key += 1
        return key
    return aux


def group_lines(lines: Iterable[str]) -> Iterable[Iterable[str]]:
    for _, group in itertools.groupby(lines, group_key()):
        yield (line for line in group if line.rstrip() != "")


_re_op_unary = re.compile("^new = old ([+*]) (\d+)$")
_re_op_binary = re.compile("^new = old ([+*]) old$")
def import_op(line: str) -> Callable[[int], int]:
    if (m := _re_op_unary.match(line)) is not None:
        arg = int(m.group(2))
        if m.group(1) == '+':
            return lambda old: old + arg
        if m.group(1) == '*':
            return lambda old: old * arg
        raise ValueError("unrecognized operator")
    if (m := _re_op_binary.match(line)) is not None:
        if m.group(1) == '+':
            return lambda old: 2 * old
        if m.group(1) == '*':
            return lambda old: old ** 2
        raise ValueError("unrecognized operator")
    raise ValueError("unrecognized operation arity")


class Game:
    def __init__(self, monkeys: dict[int, Monkey]) -> None:
        self.monkeys = monkeys

    def round(self) -> None:
        for monkey in self.monkeys.values():
            for item in monkey.items:
                item = monkey.op(item)
                item //= 3
                rcpt = monkey.test(item)
                monkey.activity += 1
                self.monkeys[rcpt].items.append(item)
            monkey.items = []

    @classmethod
    def import_lines(class_, lines: Iterable[str]) -> Game:
        monkeys = {}
        for group in group_lines(lines):
            monkey = Monkey.import_lines(group)
            monkeys[monkey.number] = monkey
        return class_(monkeys)

    def business(self) -> int:
        activity = sorted(monkey.activity for monkey in self.monkeys.values())
        return activity[-1] * activity[-2]


class Game2(Game):
    def __init__(self, *args, **kwargs) -> None:
        super().__init__(*args, **kwargs)
        self.div = math.lcm(*(monkey.test.div for monkey in self.monkeys.values()))

    def round(self) -> None:
        for monkey in self.monkeys.values():
            for item in monkey.items:
                item = monkey.op(item) % self.div
                rcpt = monkey.test(item)
                monkey.activity += 1
                self.monkeys[rcpt].items.append(item)
            monkey.items = []


def solve1(lines: Iterable[str]) -> int:
    """Solve part 1 of today's puzzle"""
    game = Game.import_lines(lines)
    for _ in range(20):
        game.round()
    return game.business()


def solve2(lines: Iterable[str]) -> int:
    """Solve part 2 of today's puzzle"""
    game = Game2.import_lines(lines)
    for _ in range(10000):
        game.round()
    return game.business()

Ma première idée fonctionnait sur l'exemple mais pas sur les données réelles : parcourir récursivement une matrice de proche en proche en évitant simplement les endroits où on est déjà passé, ça atteint vite la limites de longueur de la pile d'appels.

Du coup, j'ai fait du Dijkstra. Enfin quelque chose inspiré de son algorithme en tout cas. Ça pourrait être fait de façon entièrement itérative, mais ça ne valait pas la peine, ça reste raisonnable en récursif.

Une fois qu'on a ça, la deuxième partie du puzzle ne pose pas spécialement de problème. Il y a tout de même deux façons de l'implémenter, une bête et méchante (on prend la première solution et on l'applique plusieurs fois), et une un rien plus futée.

from typing import Iterable, Iterator, List, Optional, Set, Tuple

import numpy as np


Coords = Tuple[int, int]


class Map:
    def __init__(self, matrix: np.ndarray) -> None:
        self.matrix = matrix
        self.ly, self.lx = matrix.shape

    def neighs(self, y: int, x: int) -> Iterator[Coords]:
        """Yield neighbours that are reachable from the given coordinates,
        considering movement rules (no climbing)"""
        for (dx, dy) in ((-1, 0), (1, 0), (0, -1), (0, 1)):
            y_ = y + dy
            x_ = x + dx
            if y_ < 0 or y_ >= self.ly or x_ < 0 or x_ >= self.lx:
                continue
            if self.matrix[y_, x_] - self.matrix[y, x] <= 1:
                yield y_, x_

    def _distances(self, starts: Iterable[Coords], end: Coords,
                   distances: np.ndarray) -> None:
        """Update distances matrix by computing walking distance from possible
        starts"""
        if starts == []:
            # Nothing left to explore
            return
        nexts = []  # List[Coords]
        for start in starts:
            start_dist = distances[start]
            if start_dist < 0:
                raise ValueError(
                        'cannot compute distances from uncharted point')
            for neigh in self.neighs(*start):
                neigh_dist = distances[neigh]
                if neigh_dist < 0 or start_dist + 1 < neigh_dist:
                    # This point has either never been checked before, or has
                    # been but we have a shorter path to it
                    distances[neigh] = start_dist + 1
                    nexts.append(neigh)
        # Update distances from the points we have just updated
        self._distances(nexts, end, distances)

    def min_dist(self, starts: List[Coords], end: Coords) -> int:
        distances = np.full_like(self.matrix, -1)
        """Return the minimal distance to reach end, starting from starts"""
        for start in starts:
            distances[start] = 0
        self._distances(starts, end, distances)
        return distances[end]


def import_lines(lines: Iterable[str]) -> Tuple[Map, Coords, Coords]:
    matrix = []  # type: List[List[int]]
    start = None
    end = None
    for y, line in enumerate(lines):
        matrix.append([])
        for x, char in enumerate(line.rstrip()):
            if char == 'S':
                start = (y, x)
                height = 0
            elif char == 'E':
                end = (y, x)
                height = 25
            else:
                height = ord(char) - ord('a')
            matrix[-1].append(height)
    if start is None or end is None:
        raise ValueError("no start or end position found")
    return Map(np.array(matrix)), start, end


def solve_both(lines: Iterable[str]) -> Tuple[int, int]:
    """Solve part 1 of today's puzzle"""
    map_, start, end = import_lines(lines)
    min1 = map_.min_dist([start], end)
    min2 = map_.min_dist([coords for coords, height  # type: ignore
                          in np.ndenumerate(map_.matrix)
                          if height == 0], end)
    return min1, min2

Euh, modulo leur PPCM évidemment !

Je n'ai pas encore résolu le problème de ce jour, dimanche c'est famille, mais ça va venir. 🙂

En lisant l'énoncé, tout de même, je m'étais dit que ça devait faire des nombres qui monteraient bien vite. En y réfléchissant, je pense que j'aurais tout seul pensé à travailler modulo leur PGCD.

Pour le code d'opération, l'eval vient tout de suite en tête bien sûr, mais ça me donne quand même quelques boutons, d'écrire du code qui a l'air d'un trou de sécurité. Réflexe professionnel je pense. À suivre, je dois toujours coder ça de toute façon.

Eh oh, je sais que j'écris du code-fleuve, mais pas la peine de se moquer non plus !

J'ai pas modélisé un CPU complet comme Tanguy, c'est un peu l'enclume pour écraser la mouche.

Ça reste à voir, ça. Il y a eu un AoC où on n'arrêtait pas de ressortir un processeur bizarroïde pour l'enrichir de nouvelles instructions et variantes d'instructions existantes.

Il y a un risque pour que ce ne soit pas la dernière fois que nous aurons à bidouiller avec du code machine de communicateur elfique…

Oui, la seconde partie apparaît alors avoir rentré la bonne réponse à la première partie. Et les données d'entrée et donc les bonnes réponses sont associées à une identité en effet.

Sans surprise, j'ai implémenté un CPU selon les spécifications fournies. Mais pour ce qui est de faire quelque chose à partir des états qu'il atteint à des cycles donnés, je me suis amusé à y introduire ce que j'ai appelé un débogueur, je vous laisse découvrir ça.

import io

from enum import Enum
from typing import Callable, Iterable, Iterator, List, Optional, Tuple


class Operation(Enum):
    addx = ('addx', 1, 2)
    noop = ('noop', 0, 1)

    def __init__(self, word: str, nargs: int, cycles: int) -> None:
        self.word = word
        self.nargs = nargs
        self.cycles = cycles


class Instruction:
    def __init__(self, op: Operation, *args: int) -> None:
        self.op = op
        if len(args) != op.nargs:
            raise ValueError(
                    "operator {} expect {} arguments".format(op, op.nargs))
        self.args = args


class CPU:
    def __init__(self, program: Iterable[Instruction],
                 debug: Optional[Callable[[int, int], None]] = None) -> None:
        self.X = 1
        self.cycle = 1
        self.program = program
        self.debug = debug

    def _apply(self, instruction: Instruction) -> None:
        if instruction.op is Operation.addx:
            self.X += instruction.args[0]
        elif instruction.op is Operation.noop:
            pass

    def _cycle(self) -> None:
        if self.debug is not None:
            self.debug(self.cycle, self.X)
        self.cycle += 1

    def run(self) -> None:
        last_instruction = None
        for instruction in self.program:
            for _ in range(instruction.op.cycles):
                self._cycle()
            self._apply(instruction)


def import_program(lines: Iterable[str]) -> Iterator[Instruction]:
    for line in lines:
        words = line.split()
        op = Operation[words[0]]
        args = [int(word) for word in words[1:]]
        yield Instruction(op, *args)


class StrengthSum:
    def __init__(self) -> None:
        self.strength = 0

    def __call__(self, cycle: int, value: int) -> None:
        if cycle in (20, 60, 100, 140, 180, 220):
            self.strength += cycle * value


class CRTDrawer:
    def __init__(self) -> None:
        self.crt = io.StringIO()

    @staticmethod
    def position(cycle: int) -> int:
        return (cycle - 1) % 40

    def __call__(self, cycle: int, value: int) -> None:
        position = self.position(cycle)
        if position == 0:
            self.crt.write('\n')
        if value - 1 <= position <= value + 1:
            self.crt.write('█')
        else:
            self.crt.write(' ')


class MultiDebug:
    def __init__(self, *debugs: Callable[[int, int], None]) -> None:
        self.debugs = debugs

    def __call__(self, cycle: int, value: int) -> None:
        for debug in self.debugs:
            debug(cycle, value)


def solve_both(lines: Iterable[str]) -> Tuple[int, str]:
    """Solve part 1 of today's puzzle"""
    program = import_program(lines)
    strength_report = StrengthSum()
    crt_drawer = CRTDrawer()
    cpu = CPU(program, debug=MultiDebug(strength_report, crt_drawer))
    cpu.run()
    return strength_report.strength, crt_drawer.crt.getvalue()

Tu peux te passer de la position initiale dans l'ensemble des positions visitées : après le premier mouvement, la queue de la corde y sera toujours.

Le problème parle de corde à nœuds, mais m'évoquerait plutôt une canne et ses canetons, pas vous ?

Bon, en fait, pas besoin d'énumérer de façon aussi laborieuse bien sûr :

from __future__ import annotations

from enum import Enum
from typing import Iterable, Iterator, Set, Tuple


Coords = Tuple[int, int]


class Direction(Enum):
    O  = ( 0,  0)
    U  = ( 0,  1)
    D  = ( 0, -1)
    L  = (-1,  0)
    R  = ( 1,  0)

    def __init__(self, dx, dy):
        self.dx = dx
        self.dy = dy


class Knot:
    def __init__(self, x: int, y: int):
        self.x = x
        self.y = y

    @property
    def coords(self) -> Coords:
        return (self.x, self.y)

    def move(self, direction: Direction) -> None:
        self.x += direction.dx
        self.y += direction.dy

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

    def follow(self, other: Knot) -> None:
        if self.dist(other) <= 1:
            return
        if self.x < other.x:
            self.x += 1
        if self.x > other.x:
            self.x -= 1
        if self.y < other.y:
            self.y += 1
        if self.y > other.y:
            self.y -= 1


class Rope:
    def __init__(self, n_knots: int) -> None:
        self.knots = [Knot(0, 0) for _ in range(n_knots)]

    @property
    def head(self) -> Knot:
        return self.knots[0]

    @property
    def tail(self) -> Knot:
        return self.knots[-1]

    def move(self, direction: Direction) -> None:
        self.head.move(direction)
        for i in range(1, len(self.knots)):
            leader = self.knots[i - 1]
            follower = self.knots[i]
            follower.follow(leader)


def import_lines(lines: Iterable[str]) -> Iterator[Direction]:
    for line in lines:
        word1, word2 = line.split()
        direction = Direction[word1]
        repeat = int(word2)
        for _ in range(repeat):
            yield direction


def solve_both(lines: Iterable[str]) -> Tuple[int, int]:
    """Solve both parts of today's puzzle"""
    rope = Rope(10)
    visited1 = set()  # type: Set[Coords]
    visited2 = set()  # type: Set[Coords]
    for direction in import_lines(lines):
        rope.move(direction)
        visited1.add(rope.knots[1].coords)
        visited2.add(rope.tail.coords)

    return len(visited1), len(visited2)

Ce serait sans doute plus joli avec des coordonnées indexées (une liste de coordonnées en somme) plutôt que nommées.

Mais ce n'est de toute façon pas très compréhensible, de cette façon-là.

#! /usr/bin/python3

# Advent of Code 2022, day 9

from __future__ import annotations

from enum import Enum
from typing import Iterable, Iterator, Set, Tuple


Coords = Tuple[int, int]


class Direction(Enum):
    O  = ( 0,  0)
    U  = ( 0,  1)
    D  = ( 0, -1)
    L  = (-1,  0)
    R  = ( 1,  0)
    UL = (-1,  1)
    UR = ( 1,  1)
    DL = (-1, -1)
    DR = ( 1, -1)

    def __init__(self, dx, dy):
        self.dx = dx
        self.dy = dy


class Knot:
    def __init__(self, x: int, y: int):
        self.x = x
        self.y = y

    @property
    def coords(self) -> Coords:
        return (self.x, self.y)

    def move(self, direction: Direction) -> None:
        self.x += direction.dx
        self.y += direction.dy

    def dist(self, other: Knot) -> int:
        """"Chebyshev distance! (Not really used in my code, actually)"""
        return max(abs(self.x - other.x), abs(self.y - other.y))

    def direction_to(self, other: Knot) -> Direction:
        dx = other.x - self.x
        dy = other.y - self.y
        if dx < -1:
            if dy < 0:
                return Direction.DL
            if dy == 0:
                return Direction.L
            if dy > 0:
                return Direction.UL
        if dx == -1:
            if dy < -1:
                return Direction.DL
            if -1 <= dy <= 1:
                return Direction.O
            if dy > 1:
                return Direction.UL
        if dx == 0:
            if dy < -1:
                return Direction.D
            if -1 <= dy <= 1:
                return Direction.O
            if dy > 1:
                return Direction.U
        if dx == 1:
            if dy < -1:
                return Direction.DR
            if -1 <= dy <= 1:
                return Direction.O
            if dy > 1:
                return Direction.UR
        if dx > 1:
            if dy < 0:
                return Direction.DR
            if dy == 0:
                return Direction.R
            if dy > 0:
                return Direction.UR
        assert False  # cannot happen, all cases were covered

    def follow(self, other: Knot) -> None:
        self.move(self.direction_to(other))


class Rope:
    def __init__(self, n_knots: int) -> None:
        self.knots = [Knot(0, 0) for _ in range(n_knots)]

    @property
    def head(self) -> Knot:
        return self.knots[0]

    @property
    def tail(self) -> Knot:
        return self.knots[-1]

    def move(self, direction: Direction) -> None:
        self.head.move(direction)
        for i in range(1, len(self.knots)):
            leader = self.knots[i - 1]
            follower = self.knots[i]
            follower.follow(leader)


def import_lines(lines: Iterable[str]) -> Iterator[Direction]:
    for line in lines:
        word1, word2 = line.split()
        direction = Direction[word1]
        repeat = int(word2)
        for _ in range(repeat):
            yield direction


def solve_both(lines: Iterable[str]) -> Tuple[int, int]:
    """Solve both parts of today's puzzle"""
    rope = Rope(10)
    visited1 = set()  # type: Set[Coords]
    visited2 = set()  # type: Set[Coords]
    for direction in import_lines(lines):
        rope.move(direction)
        visited1.add(rope.knots[1].coords)
        visited2.add(rope.tail.coords)

    return len(visited1), len(visited2)

J'aurais bien aimé éviter d'énumérer tous les cas de mouvement de suivi, mais je n'ai rien trouvé d'astucieux pour éviter cela.

J'espère que dans vos solutions perso, vous aurez pensé à utiliser, en arrivant à la deuxième partie, à utiliser une seule corde pour simuler les deux…

Une petite optimisation pour la première partie : si on arrive à une hauteur de 9, pas la peine de regarder plus loin, aucun arbre ne sera plus haut que ça.

Mais bon, la seconde partie est bien plus coûteuse en temps de toute façon.