🚲 Tanguy Ortolo a écrit 12508 commentaires

Ayé, j'ai résolu la partie 2. Mais je ne suis pas du tout satisfait de ma solution, c'est super efficace mais j'ai l'impression d'avoir triché.

Je vous explique. Pour la partie 1, j'ai écrit une fonction récursive qui donne le nombre de possibilités d'arrangements restants étant donné des choix déjà faits sur un certain nombre de sources. Elle prend en entrée un état d'avancement, qui indique :

• l'état de fonctionnement de la dernière source considérée (fonctionnelle ou hors service, pas inconnue, comme on va le voir.) ;
• la position de la dernière source considérée ;
• l'index du groupe courant de sources hors service ;
• le nombre de sources hors service actuellement comptabilisée dans le groupe courant.

Si on a considéré toutes les sources, ça renvoie directement 1 si le compte est bon (on a atteint le dernier groupe de sources cassées et il est exactement rempli) et 0 sinon.

Si on n'a pas encore considéré toutes les sources, ça regarde la suivante et ça itère sur ses états possibles (une source en état ne peut être qu'en état, une source cassée ne peut être que cassée et une source en état inconnu peut être les deux, évidemment) :
* pour un état hors service, si la dernière source considérée était en état, ça ouvre un nouveau groupe… si possible, c'est à dire s'il reste des groupes non considérés, sinon on est dans une impasse et ça continue ;
* pour un état en état (hmm…), si la dernière source considérée était hors service, ça vérifie si le compte de sources hors service correspond au groupe courant et si ce n'est pas le cas on est dans une impasse et ça continue ;
* dans les cas où on n'a pas continueé, on appelle la même fonction récursive pour l'étape d'après et on ajoute sa valeur de retour à celle qu'on va renvoyer.

Ce sera peut-être plus clair avec le code :

from collections.abc import Iterable, Iterator
from typing import Optional, Self
from enum import Enum

class Condition(Enum):
    OPE='.'
    BRK='#'
    UNK='?'

    def states(self) -> Iterator[Self]:
        if self is self.OPE:
            yield self
        elif self is self.BRK:
            yield self
        else:
            yield self.OPE  # type: ignore
            yield self.BRK  # type: ignore

class Condition(Enum):
    OPE='.'
    BRK='#'
    UNK='?'

    def states(self) -> Iterator[Self]:
        if self is self.OPE:
            yield self
        elif self is self.BRK:
            yield self
        else:
            yield self.OPE  # type: ignore
            yield self.BRK  # type: ignore

    def arrangements(self) -> int:
        def aux(condition: Condition, spring: int, group: int, count: int) -> int:
            if spring == len(self.springs) - 1:
                # Last spring has just been accounted for, time to check:
                # - we are at last group;
                # - that group is full.
                if (group == len(self.groups) - 1
                    and count == self.groups[-1]):
                    return 1
                return 0
            # Some springs have not been checked yet.
            next_spring = spring + 1
            next_group = group
            next_count = count
            possibilities = 0
            for next_condition in self.springs[next_spring].states():
                if next_condition is Condition.BRK:
                    if condition is Condition.OPE:
                        # Broken spring after an operational one opens
                        # new group… if possible.
                        if group == len(self.groups) - 1:
                            # Last group has already been checked and closed:
                            # dead end.
                            continue
                        # We can open next group
                        next_group += 1
                        next_count = 0
                    # Regardless of previous spring condition, increase current
                    # group count.
                    next_count += 1
                    if next_count > self.groups[next_group]:
                        # New current group is overfull: dead end.
                        continue
                if next_condition is Condition.OPE:
                    if condition is Condition.BRK:
                        # Operational spring after a broken one closes current
                        # group, time to check group count.
                        if count != self.groups[group]:
                            # Dead end
                            continue
                possibilities += aux(next_condition, next_spring, next_group, next_count)
            return possibilities
        return aux(Condition.OPE, -1, -1, 0)

Bon, pour la partie 2, c'est beaucoup trop long, évidemment. Et donc, faute de trouver une astuce, vu le genre de paramètres de la fonction, j'ai bêtement utilisé un…

C'est… bizarre comme façon de penser je trouve. Non ?

Trève de blabla, l'implémentation :

class History:
    def __init__(self, values: Iterable[int]):
        self.firsts: list[int] = []
        self.lasts: list[int] = []
        current_values = list(values)
        while any(value != 0 for value in current_values):
            self.firsts.append(current_values[0])
            self.lasts.append(current_values[-1])
            next_values: list[int] = []
            for i in range(len(current_values) - 1):
                next_values.append(current_values[i + 1] - current_values[i])
            current_values = next_values

    @classmethod
    def import_line(cls, line: str) -> Self:
        return cls(int(word) for word in line.split())

    def prev(self) -> int:
        return sum((-1)**i * value for (i, value) in enumerate(self.firsts))

    def next(self) -> int:
        return sum(value for value in self.lasts)

En fait, si on y réfléchit un peu, on s'aperçoit qu'il n'est pas utile de stocker toute la liste, ni toute la liste des dérivées, ni toute la liste des dérivées secondes, etc. Tout ce dont on a besoin, c'est :

• pendant la phase de calcul des dérivées, la liste des valeurs de la dernière dérivée calculée, pour pouvoir vérifier si elle sont toutes nulles ;
• pour pouvoir extrapoler, les dernières valeurs – et pour la seconde partie, les premières valeur – de chaque dérivée jusqu'à la dernière significative.

Par exemple, en cours de calcul :

10  13  16  21  30  45  68 ← données d'origines
10                      68 ← données stockées
   3                  23
     0   2   4   6   8
       ?   ?   ?   ?

En fin de calcul :

10                      68 ← données stockées
   3                  23
     0               8
       2           2

Pour extrapoler à droite, si vous prenez le temps de vérifier ce qui se passe, il suffit en fait de faire la somme de toutes les dernières valeurs.

Et pour extrapoler à gauche, la somme de toutes les valeurs, en passant en négatif celles d'une ligne sur deux. Ou, pour le dire autrement, la somme du produit des premières valeurs multipliées par moins un élevé à une puissance égale au rang de la ligne d'où vient la valeur courante.

Bon, aujourd'hui nous sommes dans le cas d'un problème avec une solution naïve qui ne passe pas à l'échelle. Mais personnellement, comme l'optimisation de la première partie était quand même assez simple, j'ai fait un strike, la deuxième partie était résolue en changeant simplement une constante.

import itertools

from collections.abc import Iterable
from typing import Self

import aoc


Coords = tuple[int, int]


class Image:
    def __init__(self, galaxies: Iterable[Coords], factor: int):
        ys: set[int] = set()
        xs: set[int] = set()
        self.galaxies: set[Coords] = set()
        for galaxy in galaxies:
            self.galaxies.add(galaxy)
            ys.add(galaxy[0])
            xs.add(galaxy[1])
        # Space expansion factor: 2 everywhere…
        self.yfactor = [factor] * (max(ys) + 1)
        self.xfactor = [factor] * (max(xs) + 1)
        # … except where galaxies were found.
        for y in ys:
            self.yfactor[y] = 1
        for x in xs:
            self.xfactor[x] = 1

    def distance(self, g1: Coords, g2: Coords) -> int:
        y1, x1 = g1
        y2, x2 = g2
        ymin, ymax = min(y1, y2), max(y1, y2)
        xmin, xmax = min(x1, x2), max(x1, x2)
        return (sum(self.yfactor[y] for y in range(ymin, ymax))
                + sum(self.xfactor[x] for x in range(xmin, xmax)))

    @classmethod
    def import_lines(cls, lines: Iterable[str], factor: int) -> Self:
        return cls(((y, x)
                    for y, line in enumerate(lines)
                    for x, char in enumerate(line.rstrip())
                    if char == '#'),
                   factor)


def part1(lines: aoc.Data) -> int:
    """Solve puzzle part 1: determine total galaxy distances considering an
    expansion factor of 2."""
    image = Image.import_lines(lines, 2)
    total = 0
    for g1, g2 in itertools.combinations(image.galaxies, 2):
        total += image.distance(g1, g2)
    return total

def part2(lines: aoc.Data) -> int:
    """Solve puzzle part 2: determine total galaxy distances considering an
    expansion factor of 1000000."""
    image = Image.import_lines(lines, 1000000)
    total = 0
    for g1, g2 in itertools.combinations(image.galaxies, 2):
        total += image.distance(g1, g2)
    return total

Attention, spoiler, ne lisez pas si vous en êtes à la première partie et que vous ne voulez pas vous gâcher le plaisir de devoir peut-être réfléchir à nouveau pour implémenter la deuxième.

Deuxième partie

En fait l'espace s'étend plus vite que vous ne l'imaginiez. Les lignes et colonnes qui ne contiennent aucune galaxie ne prennent pas deux fois plus de place, mais un million. Bonne chance et attention à l'OOM killer.

Et pour la deuxième partie, résolue grâce à l'idée de Pierre :

class Map:
    def simplify(self) -> None:
        connecteds: npt.NDArray[np.bool_] = np.zeros(self.matrix.shape, dtype=np.bool_)
        currents: set[Coords] = {self.start}
        while len(currents) > 0:
            nexts: set[Coords] = set()
            for current in currents:
                if connecteds[current]:
                    continue
                connecteds[current] = True
                nexts.update(self.neighs(current))
            currents = nexts
        for index, connected in np.ndenumerate(connecteds):
            if not connected:
                self.matrix[index] = Tile(0)

    def area(self) -> int:
        total = 0
        for line in self.matrix:
            inside: bool = False
            for tile in line:
                if inside and tile is Tile(0):
                    total += 1
                if Tile.NORTH in tile:
                    inside = not inside
        return total

Première étape, simplifier la carte en virant tous les tuyaux inutiles. Comme pour la première partie, c'est basé sur un parcours de proche en proche pour identifier les tuyaux connectés au point de départ. Ensuite, on parcours tout, puis on met à zéro les tuiles qui contenaient des tuyaux non connectés.

En fait, on parcours chaque ligne en gardant en mémoire si on est à l'intérieur de la boucle de tuyaux ou non. Seulement, à l'intérieur ou à l'extérieur, c'est ambigu lorsqu'on est justement sur un tuyau qui fait partie du réseau. Donc, pour être plus précis, on s'intéresse au fait que la zone en haut à gauche de chaque tuile est à l'intérieur ou non. Et vous pouvez faire tous les schémas que vous voulez, la seule chose qui fait changer l'état intérieur/extérieur de la zone en haut à gauche de la tuile suivante, c'est la présente d'un tuyau connecté au nord.

Quant à l'aire, les tuiles qui y contribuent sont celles qui sont à l'intérieur et qui sont vides (après élimination de tuyaux inutiles). Voilà !

C'est pour moi l'occasion d'utiliser enum.Flag qui correspond très bien à des trucs qui peuvent avoir une superposition d'états, ici des tuyaux connectés dans différentes directions.

from collections.abc import Iterable, Sequence
from typing import Optional, Self

import enum
import io

import numpy as np
import numpy.typing as npt

import aoc


Coords = tuple[int, int]


class Tile(enum.Flag):
    NORTH = enum.auto()
    SOUTH = enum.auto()
    EAST = enum.auto()
    WEST = enum.auto()

    def __str__(self) -> str:
        if self is self.__class__(0):
            return ' '
        # if self is self.EAST:
        #     return '╶'
        # if self is self.WEST:
        #     return '╴'
        if self.NORTH in self:  # type: ignore
            if self.EAST in self:  # type: ignore
                return '╚'
            if self.WEST in self:  # type: ignore
                return '╝'
            if self.SOUTH in self:  # type: ignore
                return '║'
            # if self is self.NORTH:
            #     return '╵'
        if self.SOUTH in self:  # type: ignore
            if self.EAST in self:  # type: ignore
                return '╔'
            if self.WEST in self:  # type: ignore
                return '╗'
            # if self is self.SOUTH:
            #     return '╷'
        if self.EAST in self:  # type: ignore
            if self.WEST in self:  # type: ignore
                return '═'
        # if self is self.WEST:
        #     return '╴'
        raise ValueError('unexpected value %s' % repr(self))

    def vector(self) -> Coords:
        if self is self.NORTH:
            return (-1, 0)
        if self is self.SOUTH:
            return (1, 0)
        if self is self.EAST:
            return (0, 1)
        if self is self.WEST:
            return (0, -1)
        raise ValueError('cannot convert multiple directions to vector')

    @classmethod
    def import_char(cls, char: str) -> Self:
        if char == '.' or char == ' ':
            return cls(0)
        if char == '|':
            return cls.NORTH | cls.SOUTH  # type: ignore
        if char == '-':
            return cls.EAST | cls.WEST  # type: ignore
        if char == 'L':
            return cls.NORTH | cls.EAST  # type: ignore
        if char == 'J':
            return cls.NORTH | cls.WEST  # type: ignore
        if char == '7':
            return cls.SOUTH | cls.WEST  # type: ignore
        if char == 'F':
            return cls.SOUTH | cls.EAST  # type: ignore
        raise ValueError('unsupported pipe description %s' % char)

Et la carte maintenant :

class Map:
    def __init__(self, array: Sequence[Sequence[Tile]], start: Coords):
        self.matrix: npt.NDArray[np.object_] = np.array(array)
        self.ly, self.lx = self.matrix.shape
        self.start = start

    @classmethod
    def import_lines(cls, lines: Iterable[str]) -> Self:
        start: Optional[Coords] = None

        array: list[list[Tile]] = []
        for y, line in enumerate(lines):
            array.append([])
            for x, char in enumerate(line.rstrip()):
                if char == 'S':
                    start = (y, x)
                    array[-1].append(Tile(0))
                else:
                    array[-1].append(Tile.import_char(char))

        map_ = cls(array, (0, 0))
        if start is not None:
            y, x = start
            connections = Tile(0)
            if y >= 1 and Tile.SOUTH in map_[y - 1, x]:
                connections |= Tile.NORTH
            if y < map_.ly - 1 and Tile.NORTH in map_[y + 1, x]:
                connections |= Tile.SOUTH
            if x >= 1 and Tile.EAST in map_[y, x - 1]:
                connections |= Tile.WEST
            if x < map_.lx - 1 and Tile.WEST in map_[y, x + 1]:
                connections |= Tile.EAST
            map_[y, x] = connections
            map_.start = start
            return map_
        else:
            raise ValueError('start position not found')

    def neighs(self, coords: Coords) -> Iterable[Coords]:
        y, x = coords
        for direction in self[coords]:
            dy, dx = direction.vector()
            y_, x_ = y + dy, x + dx
            if y_ >= 0 and y_ < self.ly and x_ >= 0 and x_ < self.lx:
                yield y_, x_

    def __getitem__(self, coords: Coords) -> Tile:
        return self.matrix[coords]

    def __setitem__(self, coords: Coords, value: Tile):
        self.matrix[coords] = value

    def __str__(self):
        s = io.StringIO()
        for line in self.matrix:
            for tile in line:
                s.write(str(tile))
            s.write('\n')
        return s.getvalue()

    def farthest(self) -> int:
        distances: npt.NDArray[np.int_] = np.full(self.matrix.shape, -1, dtype=np.int_)
        distance = 0
        currents: set[Coords] = {self.start}
        while len(currents) > 0:
            nexts: set[Coords] = set()
            for current in currents:
                if distances[current] >= 0:
                    continue
                distances[current] = distance
                nexts.update(self.neighs(current))
            currents = nexts
            distance += 1
        return distances.max()

La solution est donnée par la méthode Map.farthest(). C'est un parcours itératif de proche en proche :

1. on construit une matrice de distances au point de départ, initialisée avec des -1 partout ;
2. on commence avec une distance courante de zéro et le point de départ comme unique point courant, mais plus tard on en aura plusieurs (en pratique, deux, mais ça pourrait être plus si on avait des tuyaux trifides) ;
3. pour chaque point courant si aucune distance n'a été précédemment relevée, on note la distance courante et on place ses voisins reliés dans l'ensemble des prochains points courants ;
4. on continue, et on ne s'arrête que quand il n'y a plus aucun point courant.

Ah, et une petite précision, les services Google Play, c'est un ensemble de logiciels propriétaires, de démons vraisemblablement, qui implémentent des trucs pas présents dans Android Open Source. Et pas mal de logiciels propriétaires pour Android, et même quelques logiciels libres, dépendend de ses fonctionnalités. :-(

D'où, donc, le besoin, lorsqu'on veut utiliser un système d'exploitation plus ou moins libre genre LineageOS, d'installer soit les services Google Play, soit microG.

Oui alors comme je disais, c'est plus compliqué que ça. microG est là pour remplacer les services Google Play. Attention, j'ai bien dit les services Google Play, ce qui n'est pas Google Play Store.

Bref. Ça implique deux choses :

• ne pas avoir déjà les services Google Play qui tournent : quand on installe LineageOS sans installer en plus les applications Google, on est dans ce cas-là ;
• que microG puisse se faire passer pour les services Google Play.

Et c'est ce dernier point qui complique tout, parce que les logiciels pour Android ont un genre de signature qui prouve leur identité. Je ne connais pas bien le sujet, mais en tout cas, pour que microG puisse se faire passer pour les services Google Play, il faut que le système d'exploitation accepte de faire croire qu'il a la signature de ces derniers. Par conséquent, il faut un système d'exploitation qui prenne en charge la falsification de signature (en fait c'est plutôt une falsification de vérification de signature je pense).

Donc, pour que microG fonctionne, inutile d'essayer simplement de l'installer depuis F-Droid, ça ne marchera pas. Deux possibilités :

• soit installer un système d'exploitation qui prend directement ça en charge, et qui intègre déjà microG tant qu'à faire : c'est le cas de LineageOS for microG, une variante de LineageOS qui ajoute précisément cela ;
• soit être root et installer des trucs qui permettront cette falsification de signature.

C'est un petit peu plus compliqué que ça. microG, c'est une implémentation libre des services Google. Installer des logiciels depuis Google Play sans compte Google ne fait pas partie de ses fonctionnalités.

Installer des logiciels du Google Play Store sans Google Play, ça se fait avec Aurora Store, un logiciel disponible dans F-Droid. Rien à voir avec microG à priori.

Seulement, le problème, c'est que l'Identité Numérique La Poste inclut un piège, à son lancement, qui fait en gros :

1. récupérer le nom du logiciel avec lequel j'ai été installé ;
2. si ce logiciel n'est pas « Google Play » :
   1. afficher « Il faut m'installer avec Google Play, connard. D'accord ? »
   2. se terminer.

Du coup, pour pouvoir l'utiliser, il faut soit l'installer avec Google Play, soit trouver un truc qui ne déclenche pas ce piège. Par exemple, j'ai trouvé qu'en l'installant avec Aurora Store en tant que root, ça empêche L'Identité Numérique La Poste de déterminer comment elle a été installée (ça doit récupérer un truc genre chaîne vide), ce qui suffit à ne pas le déclencher. Seulement pour ça, il faut être root sur son téléphone. Et ça, l'Identité Numérique La Poste n'aime pas non plus, il y a aussi un piège pour ça. Du coup, il faut un moyen de cacher qu'on est root. On atteint des niveaux de bidouille assez hauts.

Autant que je sache, le seul moyen consiste à bidouiller franchement :

https://linuxfr.org/users/elessar/journaux/utiliser-l-identite-numerique-la-poste-sans-google-play

Juste un mot sur la partie 2. En force brute évidemment, ça prendrait des mois. Il y a une astuce évidemment, seulement avec l'énoncé seul, je ne crois pas qu'il y ait moyen de soupçonner de quoi il s'agit.

En fait l'astuce ne vient pas des règles du jeu, mais des données elles-mêmes, qui sont conçues pour que les fantômes tournent en rond. Je ne vous en dit pas plus.

Tu n'es pas seul. Mais ce n'est pas pour ça qu'il existe une solution, hélas.

https://www.libreavous.org/ca-y-est-je-suis-un-fracture-du-numerique
https://www.librealire.org/emission-libre-a-vous-diffusee-mardi-24-octobre-2023-sur-radio-cause-commune
https://grisebouille.net/franceconnect-ou-gafamconnect/

Une énumération n'est pas nativement utilisable dans des ensembles ou en clef de dictionnaire ???

https://blog.yossarian.net/2020/03/02/Totally-ordered-enums-in-python-with-ordered_enum
https://stackoverflow.com/questions/42369749/use-definition-order-of-enum-as-natural-order

Comme j'aime bien modéliser, c'est un sujet où j'utilise naturellement des énumérations. Pour les cartes, comme pour les types de mains.

class Card(Enum):
    ONE   = '1'
    TWO   = '2'
    THREE = '3'
    …
    TEN   = 'T'
    JACK  = 'J'
    QUEEN = 'Q'
    KING  = 'K'

L'avantage en donnant aux cartes la valeur correspondant au caractère qui les représente, c'est que ça permet de les parser très facilement :

card = Card('A')

Le problème, c'est que je veux comparer les cartes. Et des énumérations, eh bien ça ne se compare pas. Pas sans implémenter au moins une fonction de comparaison. Et ça, c'est… pénible.

Je rêve donc d'une solution propre pour définir une classé énumérée dont les membres se comparent, simplement avec leur ordre de définition.

Je découvre cached_property, merci !

Petite subtilité sémantique, les cartes disponibles sont 23456789TJQK, ce qui signifie :

• deux
• trois
• quatre
• …
• neuf
• dix (T pour ten, soit 10)
• valet (J pour jack)
• dame (Q pour queen)
• roi (K pour king)

La raison d'utiliser la lettre T pour le dix vient de la nécessité de l'écrire en un seul caractère. 10, ça fait deux caractères…

Ah, d'accord, je comprends mieux.

Au fait, je vous conseille de garder ce code quelque part. Ça a des chances de resservir. :-)

Je ne comprends pas. On peut bien découper des intervalles à l'avance, si le découpage ne correspond pas exactement à aux intervalles définis pour les conversions, il va falloir redécouper non ?

Je veux dire, on peut bien couper l'intervalle de graines 46 546+34 234 234 en 46 546+999 999, 1 046 546 + 999 999, … 34 046 546 + 234 235, mais ça ne va pas aider si on doit ensuite convertir les graines 25 561 123+3 123 458 en quelque chose d'autre. Sauf si j'ai vraiment une chance monstrueuse, les limites de cet intervalle à convertir ne correspondent pas du tout à celles des intervalles de graines prédécoupés.

Donc on se retrouve de toute façon à faire de la découpe d'intervalles par intersection. Tant qu'à faire, autant le faire à partir des intervalles entiers, le prédécoupage n'a aucun intérêt. Qu'est-ce que j'ai loupé ?

Pour moi, à la lecture de l'énoncé, je n'y ai pas vu un problème d'algorithmique, mais de mathématiques. Une régate avec un temps de charge qui donne la vitesse pour dépasser la distance record en un temps limité, c'est une inéquation polynomiale de second degré.

Un polynôme de second degré

Soit la durée de la course, la distance record et t le temps de charge (notre variable). La vitesse atteinte est d'après l'énoncé égale au temps de charge. Sur la durée de la course, il ne reste plus que pendant lequel le bateau parcourra .

On charge à battre le record, soit :

Cela se normalise en :

La partie gauche est un polynôme de second degré, en forme de cloche vers le haut. Ça tombe bien, si les données sont bien construites il devrait s'annuler en deux points, et être négatif entre les deux. Je sais très bien résoudre ça.

Résolution

Le discriminant de ce polynôme vaut :

Comme je disais, si les données sont bien construites, ça devrait être strictement positif et donner les racines suivantes :

En chargeant notre bateau pendant exactement ou , on égale le record. Entre et , on le dépasse.

Retour à la réalité fiction

Bon, c'est bien joli ça, on peut déterminer des temps minimum et maximum qui sont des réels, mais on nous demande un nombre de durées de charge possible, entières à la milliseconde près, pour dépasser strictement le record.

Si le temps minimum, par exemple, n'est pas entier, c'est facile, il faut charger pendant une durée supérieur ou égale à son arrondi à l'entier supérieur. Mais les cas limites sont importants, qu'en est-il si le temps minimum est entier ? Il faut charger pendant une durée supérieure ou égale à l'entier suivant.

En fait, la borne inférieure à considérer est l'entier inférieur au temps minimum, augmenté d'une unité. Mutatis mutandis pour le temps maximum.

Les bornes incluses de notre intervalle de durées possibles seront donc :

Quand au nombre d'options, c'est par conséquent la longueur de cet intervalle :

Partie 1, partie 2

Ce calcul s'applique aussi bien à la première qu'à la deuxième partie. Et c'est rapide, genre vraiment rapide puisque c'est simplement du calcul. Mieux encore, alors que pour la première partie il faut traiter trois ou quatre régates, pour la seconde il n'y en a plus qu'une seule, donc c'est trois ou quatre fois plus rapide. :-)

En pratique, en Python 3 ça prend dans les 50 millisecondes pour la première comme pour la seconde partie, mais je soupçonne que ce soit essentiellement la compilation et le temps de chargement de la machine virtuelle Python.

On arrive au genre d'exercice où la résolution simple de la première partie devient inapplicable à la seconde partie, parce qu'il lui faudrait plus de mémoire qu'il n'y en a sur Terre ou plus de temps que l'âge de l'univers. Là, on est plutôt dans le second cas, je dirais.

Bref, ce n'est pas la première fois que je me retrouve à couper des intervalles en morceaux, alors c'est cadeau, voici du code pour faire ça. Je réutilise le type range qui correspond plutôt bien au concept.

def intersects(range1: range, range2: range) -> bool:
    """Tell whether or not the two ranges have a part in common."""
    if range1.start >= range1.stop or range2.start >= range2.stop:
        raise ValueError("usupported empty range") 
    if range1.step != 1 or range2.step != 1:
        raise ValueError("unsupported stepped range")
    return range1.stop > range2.start and range2.stop > range1.start

def intersect(range1: range, range2: range) \
        -> tuple[Optional[range], Sequence[range], Sequence[range]]:
    """Given two ranges, returns:
    1. the eventual intersection of both ranges;
    2. parts of the first range that are not part of the second one;
    3. parts of the second range that are not part of the first one.
    """
    if range1.start >= range1.stop or range2.start >= range2.stop:
        raise ValueError("usupported empty range") 
    if range1.step != 1 or range2.step != 1:
        raise ValueError("unsupported stepped range")
    if not intersects(range1, range2):
        # Disjoint ranges
        return None, (range1,), (range2,)
    diff1: list[range] = []
    if range1.start < range2.start:
        diff1.append(range(range1.start, range2.start))
    if range2.stop < range1.stop:
        diff1.append(range(range2.stop, range1.stop))
    diff2: list[range] = []
    if range2.start < range1.start:
        diff2.append(range(range2.start, range1.start))
    if range1.stop < range2.stop:
        diff2.append(range(range1.stop, range2.stop))
    return (range(max(range1.start, range2.start),
                  min(range1.stop, range2.stop)),
            diff1, diff2)

fairphone affiche de très mauvais retours..

Le Fairphone 2, oui. Mais ça commence à dater, comme info, quand même. Depuis, on en est au Fairphone 4, en fait.