Advent of Code 2021 Day 11

Le problème

Partie 1

Nouveau jour, nouveau problème, nouvelle chose qu’on apprend : l’existence de pieuvres Dumbo. Si ça ce n’est pas joli : une pieuvre Dumbo

Bref, aujourd’hui (et comme pour l’an passé au même jour d’ailleurs), c’est Cellular Automata Day !

Notre jeu de données est une matrice 10x10 contenant des valeurs comprises entre 0 et 9 :

Ici, l’automate effectue la procédure suivante :

À chaque étape :
1. Chaque valeur augmente de 1 ;
2. Si une valeur est strictement supérieure à 9 (une pieuvre Dumbo rayonne) :
  1. Les voisins de cette valeur augmentent encore de 1 ;
  2. Si ces voisins atteignent une valeur strictement supérieure à 9, ils vont également impacter leurs voisins respectifs ;
  3. Si une pieuvre a déjà rayonné à cette étape, alors sa valeur restera bloquée à 0 jusqu’à la fin de l’étape.

Dans cette première partie, on nous demande de compter le nombre total de fois que les pieuvres auront rayonné après 100 itérations. Ma solution se trouve juste après :

def read_input():
    with open('input-large', 'r') as data:
        return [[int(x) for x in line] for line in data.read().splitlines()]


def increase_level(grid):
    """
    Increases all levels by 1.
    :param grid: The grid of octopuses' levels
    :return: The grid with each level increased by one
    """
    grid = [[elt + 1 for elt in line] for line in grid]
    return grid


def get_neighbours(x, y):
    """
    Get the coordinates of all valid neighbours (i.e, not off the edge).
    :param x: The x-value in the grid we search neighbours for
    :param y: The y-value in the grid we search neighbours for
    :return: A list of (x_neighbour, y_neighbour) values that represent neighbours
    """
    neighbours = [(x - 1, y - 1), (x - 1, y), (x - 1, y + 1),
                  (x, y - 1),                 (x, y + 1),
                  (x + 1, y - 1), (x + 1, y), (x + 1, y + 1)]
    valid_neighbours = [(x_neighbour, y_neighbour)
                        for x_neighbour, y_neighbour in neighbours
                        if x_neighbour in range(10) and y_neighbour in range(10)]
    return valid_neighbours


def flash(grid):
    """
    Identifies which octopus flashes in a single step, and propagates its energy to
    its neighbours until no octopus can flash anymore.
    :param grid: The grid of octopus' levels
    :return: The number of octopuses that has flashed in this step
    """
    count_flash = 0
    flashes = set()     # Octopuses that still have to flash this step
    has_flashed = set() # Octopuses that have already flashed and can't anymore
    for x, line in enumerate(grid):
        for y, element in enumerate(line):
            if element > 9:
                flashes.add((x, y))
    while flashes:      # Loop through all octopusese that have to flash
        x, y = flashes.pop()
        neighbours = get_neighbours(x, y)
        for x_neighbour, y_neighbour in neighbours:
            # Only increase an octopus's value if it has not flashed already
            if (x_neighbour, y_neighbour) not in has_flashed:
                grid[x_neighbour][y_neighbour] += 1
                # Add an octopus to `flashes` if it needs to flash next
                if grid[x_neighbour][y_neighbour] > 9:
                    flashes.add((x_neighbour, y_neighbour))
        # After we're done for an octopus, we set it back to 0, add it to the 
        # set of `has_flashed`, and increase the count of octopuses that have
        # flashed, before looping to the next octopus.
        grid[x][y] = 0
        has_flashed.add((x, y))
        count_flash += 1
    return count_flash


def solve_part_one():
    grid = read_input()
    count = 0
    for _ in range(100):
        grid = increase_level(grid)
        count += flash(grid)
    print(count)

Partie 2

Dans la seconde partie, on nous explique qu’il existe une étape pour laquelle toutes les pieuvres sont synchronisées et rayonnent en même temps. Il s’agit alors de trouver le numéro de cette itération.

Pour cela, il suffit de définir une fonction qui permet de vérifier si la matrice ne contient que des zéros (toutes les pieuvres viennent de rayonner), puis de procéder aux étapes de la Partie 1 tant que cette fonction ne renvoie pas la valeur True.

def all_flashed(grid):
    """
    Determines if the grid only contains 0s, meaning that all octopuses have flashed
    synchronously.
    :param grid: The grid of octopuses' levels
    :return: True if all octopuses have flashed in this current step.
    """
    all_has_flashed = True
    for row in grid:
        for element in row:
            if element != 0:
                return False
    return all_has_flashed


def solve_part_two():
    grid = read_input()
    count = 0
    while not all_flashed(grid):
        grid = increase_level(grid)
        flash(grid)
        print(grid)
        count += 1
    print(count)

Les difficultés

Jour d’automate cellulaire, l’important est de bien modéliser les étapes. Pour cela, il faut :

Bien déterminer les voisins de chaque point ;
Bien gérer la liste (ou plutôt l’ensemble) des pieuvres qui doivent rayonner ;
Bien gérer la liste (ou plutôt l’ensemble) des pieuvres qui ont déjà rayonné à une étape donnée.

Après quoi, il faut simplement implémenter les règles pour que toutes celles-ci se produisent simultanément et à chaque étape. Encore un problème bien sympathique, et qui nécessite de faire preuve d’un peu de minutie lors de la manipulation des matrices de nombres. Pour cette fois-ci, on ne s’embête pas trop lorsque l’on augmente les valeurs des niveaux d’énergie des pieuvres. On s’aide du fait que les listes sont passées par référence aux fonctions pour changer son état, tout en bloquant ce qu’il est nécessaire de bloquer à chaque étape (i.e., qu’une pieuvre rayonne et ne soit pas à 0 à la fin de l’étape).

2021-12-11

https://patrickwang.fr/posts/advent-of-code-2021-day-11/