Le problème

Partie 1

L’exploration sous-marine continue, et on nous explique désormais que l’on a des coordonnées de cavités un peu trop chaudes que l’on souhaiterait éviter. Pour cela, on a un jeu de données en entrée qui présente plusieurs particularités :

1. Il s’agit d’un jeu de données en deux parties : une partie avec des coordonnées, une partie avec des “instructions de pliage” ;
2. Les coordonnées sont inversées par rapport à ce que l’on aurait l’habitude de voir.

Pour éclaircir ces deux points, voyons le jeu de données proposés :

6,10
0,14
9,10
0,3
10,4
4,11
6,0
6,12
4,1
0,13
10,12
3,4
3,0
8,4
1,10
2,14
8,10
9,0

fold along y=7
fold along x=5

Lorsque je dis que les coordonnées sont inversées cela signifie que la première valeur du couple (x, y) représente en fait l’indice de colonne, et que la seconde valeur représente l’indice de ligne. Cette inversion est probablement une des difficultés principales de l’exercice d’aujourd’hui.

Dans cette première partie de l’exercice, on nous explique donc que ces coordonnées représentent les coordonnées de cavités un peu trop chaudes. Mais ces coordonnées sont imprimées sur un papier transparent, et il faut en fait plier ce papier pour obtenir les coordonnées finales.

Ainsi, si on prend l’instruction fold along y=7, cela signifie que la ligne de coordonnées y = 7 devient la ligne selon laquelle on va plier le papier. Ainsi, toutes les cavités se retrouvant initialement en coordonnées y = 8 sont maintenant ajoutées en transparence sur les cavités de la ligne y = 6.

Une approche naïve serait de créer une grande matrice, et de la couper au fur et à mesure que l’on effectue des pliages. Une autre solution consiste à remarquer que :

• Si un pliage se fait en y, les éléments de la partie repliée vont avoir une nouvelle valeur y = y - 2*(y - y_pliage). La valeur en x reste inchangée.
• Si un pliage se fait en x, les éléments de la partie repliée vont avoir une nouvelle valeur x = x - 2*(x - x_pliage). La valeur en y reste inchangée.

Ainsi, on peut implémenter l’algorithme suivant :

coordonnées <- ensemble des coordonnées
Pour chaque pliage à faire:
    Si pliage en x_pliage:
        partie_gardée <- {coordonnée de coordonnées si coordonnée.x < x_pliage}
        partie_pliée <- coordonnées - partie_gardée
    Si pliage en y_pliage:
        partie_gardée <- {coordonnée de coordonnées si coordonnée.y < y_pliage}
        partie_pliée <- coordonnées - partie_gardée
    Pour chaque coordonnée de partie_pliée:
        partie_gardée += coordonnée transformée
    coordonnes <- partie_gardée

Puisque la première partie nous demande de compter le nombre de cavités après un seul pliage, on peut appeler cette fonction avec une liste contenant qu’un seul pliage. Cela nous donne la solution suivante :

def parse_input_data():
    """
    :return: coordinates, qui est un ensemble de coordonnées (x, y), avec la 
                même signification que dans l'énoncé
             folds, qui est une liste des pliages, de la forme (axe, valeur)
    """
    with open('input-large', 'r') as data:
        lines = data.read().splitlines()
        str_coordinates = lines[:lines.index('')]
        str_folds = lines[lines.index('')+1:]
        coordinates, folds = set(), []
        for coordinate in str_coordinates:
            x, y = tuple([int(c) for c in coordinate.split(',')])
            coordinates.add((x, y))
        for fold in str_folds:
            fold_instruction = fold.split(' ')[-1]
            axis, value = fold_instruction.split('=')
            value = int(value)
            folds.append((axis, value))
        return coordinates, folds


def fold(coordinates, folds):
    for axis, value in folds:
        unchanged_set = {c for c in coordinates if c[0] < value} if axis == 'x' \
                           else {c for c in coordinates if c[1] < value}
        mirrored_set = coordinates - unchanged_set
        for (x, y) in mirrored_set:
            if axis == 'x':
                unchanged_set.add((x - 2*(x - value), y))
            else:
                unchanged_set.add((x, y - 2*(y - value)))
        coordinates = unchanged_set
    print(len(coordinates))
    return coordinates


def solve_part_one():
    coordinates, folds = parse_input_data()
    fold(coordinates, [folds[0]])

Partie 2

Dans la partie 2, on doit désormais effectuer tous les pliages. On nous explique également que, suite à tous ces pliages, huit lettres seront affichées par la carte transparente. Et il faudra donc retrouver ces huit lettres.

Pour cela, on peut s’appuyer sur la fonction implémentée en partie 1 pour effectuer tous les pliages. Désormais, il s’agit de représenter ces points sur la carte, de sorte que cela soit lisible pour un humain.

J’ai donc exploré un peu les coordonnées finales obtenues après tous les pliages pour constater que la plus grande valeur de y était égale à 38. Avec huit lettres, j’ai donc supposé que chaque lettre avait une largeur de 5.

J’ai donc construit la variable grid, qui est en fait une liste de taille 6 (ce qui représente la hauteur des lettres), et de largeur 40. Puis, en parcourant les coordonnées des points après pliages, j’ai simplement changé les valeurs dans grid pour transformer les . en des #.

Puis, on peut simplement afficher ligne par ligne, en utilisant également la fonction join() qui permet de montrer tous les éléments composant une seule et même ligne sous la forme d’une chaîne de caractères.

def show_message(coordinates):
    grid = [['.'] * 40 for _ in range(6)]
    for (x, y) in coordinates:
        grid[y][x] = '#'
    for line in grid:
        print(''.join(line))
        

def solve_part_two():
    coordinates, folds = parse_input_data()
    coordinates = fold(coordinates, folds)
    show_message(coordinates)

Et pour les yeux, voici ce que la fonction show_message() m’affiche :

####.#..#..##..#..#..##..####.#..#..##..
...#.#.#..#..#.#..#.#..#.#....#..#.#..#.
..#..##...#..#.#..#.#....###..#..#.#....
.#...#.#..####.#..#.#....#....#..#.#....
#....#.#..#..#.#..#.#..#.#....#..#.#..#.
####.#..#.#..#..##...##..#.....##...##..

Les difficultés

Je trouve plusieurs difficultés dans cet exercice.

Le premier concerne l’inversion des indices qui nous impose donc de faire une petite gymnastique pour sortir de nos habitudes lorsque l’on manipule des matrices. Pour ma part, j’ai décidé de suivre ce que l’énoncé me disait, et seulement pour la partie 2 d’inverser les axes pour afficher le résultat final.

Une seconde difficulté concerne l’algorithme de pliage. J’imagine qu’il est assez naturel de penser à construire la carte complète sous la forme d’une matrice puis d’effectuer des transformations dessus, mais il y a pas mal de sources d’erreurs (justement à cause de l’inversion des axes). En analysant un peu la situation, et en comprenant que l’axe de pliage est en fait un axe de symétrie, on peut assez bien voir l’intérêt de ne gérer qu’un ensemble de coordonnées qui sera mis à jour à chaque pliage.

Malgré ces difficultés, j’ai trouvé l’exercice très intéressant puisqu’il nous demande encore une fois de faire preuve de souplesse d’esprit afin de trouver des solutions élégantes (mais peut être pas intuitives ou directes).