Jour 12 - Cadeau empoisonné

Je vais être honnête: je suis un peu déçu par celui-ci, qui était extrêmement peu satisfaisant à résoudre. Ou plutôt: qu’il ne faut pas résoudre pour réussir…

Le puzzle a un format un peu plus compliqué que d’habitudes, même s’il n’est pas particulièrement compliqué à parser:

On a deux parties: d’abord on définit une série de formes, chacune avec un identifiant. Les # correspondent à des cases “utilisées”, les . à des cases vides. Ensuite on a une liste de “zones à remplir”, avec une taille (largeur x longueur) et combien de formes de chaque type il faut mettre dedans. Par exemple, pour la deuxième zone, on a un rectangle de taille 12x5 dans lequel on cherche à faire rentrer 1 forme de type 0, 1 forme de type 2, 2 formes de type 4 et 2 formes de type 5.

On peut tourner les formes dans tous les sens et faire des symétries verticales et horizontales, mais les formes évidemment ne peuvent pas se chevaucher (donc on ne peut pas avoir deux # sur la même case).

Le but est de trouver, pour chaque zone, s’il y a une solution valide pour mettre toutes les formes.

Récupération de l’input

On l’a fait quelques fois maintenant, donc je ne vais pas passer trop de temps dessus. J’ai défini un type Shape et un type Puzzle pour clarifier le code. Je me suis autorisé à utiliser la bibliothèque numpy pour stocker les formes, parce que ça rend les opérations de type “rotation” ou “symétrie” beaucoup plus facile. Le problème m’avait l’air suffisamment complexe comme ça. Chaque forme sera donc un tableau binaire à deux dimensions, et je les stocke dans un dictionnaire id -> forme. Pour les puzzles, je stocke la taille dans un tuple, puis une liste de “combien de chaque forme” il faut garder.

import numpy as np
from utils.inputs import load_input

type Shape = np.ndarray
type Puzzle = tuple[tuple[int, int], list[int]]

def prepare_data(data: str) -> tuple[dict[int, Shape], list[Puzzle]]:
    rows = data.split('\n')
    shapes = {}
    puzzles = []

    cur_shape = []
    shape_id = None
    for row in rows:
        if ':' in row and 'x' not in row:
            shape_id = int(row[:row.index(':')])
            cur_shape = []
        elif '.' in row or '#' in row:
            cur_shape.append([r=='#' for r in row])
        elif row == '':
            # close shape
            if shape_id is None:
                raise ValueError("shape_id shouldn't be None here")
            shapes[shape_id] = np.array(cur_shape)
            cur_shape = []
            shape_id = None
        else:
            puzzle_size, n_shapes = row.split(':')
            w, h = puzzle_size.split('x')
            n_shapes = [int(v) for v in n_shapes.strip().split(' ')]
            puzzles.append(((int(w), int(h)), n_shapes))
    return shapes, puzzles

Où je patauge un peu

Je ne voyais pas par où commencer, donc j’ai tenté quelques trucs pour essayer de mieux comprendre le problème. D’abord, une méthode pour calculer toutes les variations possibles d’une forme:

def rotate_right(shape: Shape) -> Shape:
    # = transpose, then flip horizontally
    t = shape.T
    return t[:, ::-1]
    
def variations(shape: Shape) -> list[Shape]:
    # rotate_right 3 times to get all rotations
    # flip each of them vertically to get the rest
    shapes: list[Shape] = [shape]
    new_shape = shape
    for _ in range(3):
        new_shape = rotate_right(new_shape)
        shapes.append(new_shape)
    for s in shapes[:]:
        shapes.append(s[::-1, :])    
    return shapes

Puis une méthode totalement naïve pour essayer de trouver le meilleur “fit” entre deux formes, en me disant que je pourrais peut-être itérativement rajouter des formes de la façon la plus compacte possible. Pour faire ça, je récupère toutes les variations des deux formes, j’initialise un tableau suffisamment grand pour contenir les deux formes, et pour chaque paire de variation j’essaie de faire glisser l’une sur l’autre, en gardant au final la forme qui occupe le plus petit rectangle possible. J’utilise pour ça numpy.trim_zeros, une fonction très pratique qui, depuis la version 2.2 de numpy, permet de récupérer uniquement le rectangle minimal qui n’exclut que des zéros dans un tableau. Utile.

def find_best_fit(a: Shape, b: Shape) -> Shape:
    a_vars = variations(a)
    b_vars = variations(b)

    maxshape = (a.shape[0]+2*b.shape[0], a.shape[1]+2*b.shape[1])
    best_score = math.prod(maxshape)
    best_fit = None
    for va in a_vars:
        for vb in b_vars:
            newarr = np.zeros(maxshape, dtype='int')
            newarr[b.shape[0]:b.shape[0]+a.shape[0], b.shape[1]:b.shape[1]+a.shape[1]] = va
            for i in range(maxshape[0]-b.shape[0]):
                for j in range(maxshape[1]-b.shape[1]):
                    newarr[i:i+b.shape[0], j:j+b.shape[1]] += vb
                    if newarr.max() > 1:
                        newarr[i:i+b.shape[0], j:j+b.shape[1]] -= vb
                        continue
                    score = math.prod(np.trim_zeros(newarr).shape)
                    if score < best_score:
                        best_fit = newarr.copy()
                        best_score = score
                    newarr[i:i+b.shape[0], j:j+b.shape[1]] -= vb
    if best_fit is None:
        raise ValueError("Couldn't fit the two shapes in any way. That's weird.")
    return np.trim_zeros(best_fit)

En testant un peu, ça me donne effectivement des formes raisonnablement “compactes” en sortie, mais ça ne m’aide pas sur le fond. Ca prend clairement trop de temps à calculer, au vu des quantités de combinaisons possibles, et ça ne me garantit même pas une solution optimale.

Solution accidentelle

Pour au moins avancer un peu, j’ai essayé de calculer la “place minimale” théorique que pourrait prendre une combinaison de formes, en comptant simplement le nombre de cases occupées par chaque forme. Dans le meilleur des cas, on arrive à toutes les imbriquer de manière compacte, sans trous.

La place occupée par une forme est simplement la somme des éléments du tableau. J’ai donc voulu regarder, sur l’exemple d’abord, si je pouvais tirer quelque chose de regarder la taille du rectangle à remplir, et la place minimale occupée par les pièces:

def main():
    shapes, puzzles = load_input(12, '_sample', prepare_data)
    footprints = [shape.sum() for shape in shapes.values()]

    for (w, h), n_shapes in puzzles:
        print(f"{w}x{h}={w*h}, {sum(v*footprints[s] for s, v in enumerate(n_shapes))}")

Dans les trois cas, la place occupée par les pièces est inférieure à la place disponible, donc selon ce critère “ça rentre”. Pourtant, l’énoncé nous indique bien que, pour le troisième puzzle, il n’y a pas de solution. Ce critère n’est donc pas suffisant – assez logiquement.

J’ai quand même voulu vérifier ce que ça donnait sur mon input, en me disant que je pourrais peut-être faire quelque chose de l’information: si une solution existe, cette méthode me donne en effet le nombre de cases vides qui seront présentes dans la solution. Je ne sais pas ce que je pourrais faire de cette information, mais quand on patauge, on prend tout.

Et là, j’ai tout de suite vu que, dans mon input, on a pas mal de cas où il n’y a aucune solution possible même avec un arrangement sans trous:

Bonne nouvelle, ça signifie que je peux éliminer d’office un certain nombre de puzzles, et ne devoir tester que les autres. Pour avoir une idée de combien, j’ai rajouté un compteur:

def main():
    # ...
    i = 0
    for (w, h), n_shapes in puzzles:
        print(f"{w}x{h}={w*h}, {sum(v*footprints[s] for s, v in enumerate(n_shapes))}")
        if w*h >= sum(v*footprints[s] for s, v in enumerate(n_shapes)):
            i += 1
    print(i)

Qui m’indique qu’il ne restera plus que 437 puzzles à résoudre, sur les 1000 de l’input.

J’ai failli en rester là, et continuer à réfléchir, parce que je n’ai clairement pas résolu le problème, et que sur l’exemple je n’exclus pas le puzzle qui ne fonctionne pas, mais n’ayant pas de meilleure idée pour l’instant j’ai soumis le résultat.

Conclusions provisoires

Comme l’an dernier, et apparemment comme d’habitude, il n’y a qu’une seule partie pour le dernier jour. C’est donc ainsi que se termine l’édition 2025. Enfin, il me reste à terminer le jour 10 pour compléter mon set d’étoiles.

Un peu mitigé par rapport à cette année. Il y avait beaucoup de puzzles très sympas et, pour la plupart je trouve, plus faciles que l’an dernier. Ce qui n’est pas un problème, j’aime bien le fait qu’ils n’ont pas tous occupés ma tête toute la journée (sauf le 10!). La difficulté est montée très brutalement. Le 10, s’il n’y a pas d’autre solution que la résolution algébrique, restera un type de difficulté que je n’aime pas trop, mais ça m’a tout de même amené dans des exercices de réflexion intéressant donc je n’ai rien contre.

Mais le point final est un peu raté, je trouve. Enfin, je ne veux pas trop me plaindre: il y a clairement énormément de temps, de passion et de talent derrière cet événement. Un tout grand merci à Eric qui l’anime depuis 11 ans!

Je n’ai pas encore complètement baissé les bras sur la deuxième partie du jour 10, il y aura donc peut-être encore un post-scriptum!