Le problème

Partie 1

On retourne dans notre sous-marin, et il semblerait que l’on commence à s’ennuyer (vraiment ?!) puisque l’on va commencer à jouer au Bingo avec un calmar géant. Les grilles du Bingo sont de taille 5x5, et l’énoncé nous dit que seules les lignes et les colonnes comptent pour gagner (et pas les diagonales).

Le jeu de données est de la forme suivante :

7,4,9,5,11,17,23,2,0,14,21,24,10,16,13,6,15,25,12,22,18,20,8,19,3,26,1

22 13 17 11  0
 8  2 23  4 24
21  9 14 16  7
 6 10  3 18  5
 1 12 20 15 19

 3 15  0  2 22
 9 18 13 17  5
19  8  7 25 23
20 11 10 24  4
14 21 16 12  6

14 21 17 24  4
10 16 15  9 19
18  8 23 26 20
22 11 13  6  5
 2  0 12  3  7

Où la première ligne représente tous les nombres tirés les uns après les autres, et les lignes suivantes représentent les différentes grilles utilisées pour jouer contre le calmar géant.

L’objectif de la première partie est :

1. De déterminer la première grille à gagner ;
2. De calculer le produit entre le dernier nombre tiré (gagnant) et la somme des nombres restants dans la grille gagnante.

Comme pour les exercices du Jour 3, on commence à rentrer dans des exercices où il est important de bien modéliser son problème, et aussi de bien découper son programme en fonctions aussi petites que possible.

Algorithme utilisé

Avant de montrer les fonctions définies pour résoudre cette première partie, je vais commencer par décrire l’algorithme utilisé.

Avant même de calculer le résultat final, il faut être en mesure de déterminer si la grille gagnante. Pour déterminer la grille gagnante, il faut être en mesure de déterminer si une ligne ou une colonne a été entièrement marquée. Pour cela, je profite du fait que ces grilles ne contiennent que des nombres positifs ou nuls pour marquer les nombres tirés en changeant les valeurs dans les grilles par -1. Je n’aurai ainsi plus qu’à calculer la somme des lignes ou colonnes pour vérifier si celle-ci est égale à -5 ou pas. Pour le reste, il s’agit de bien lire les données en entrée pour pouvoir effectuer les manipulations décrites plus haut.

Dans le détail, cela fait :

1. On lit le jeu de données en entrée pour obtenir une liste des nombres tirés 
   et une liste des grilles (qui est donc une liste de listes 2D).
2. Pour chaque nombre dans la liste de nombres :
   i. Pour chaque grille dans la liste de grilles :
      a. Si `nombre` est dans `grille`, on change la valeur dans `grille` à -1
      b. On vérifie si `grille` est la grille gagnante:
         i. Si c'est le cas, on calcule le résultat final et le retourne

La solution

J’ai donc défini quatre fonctions “utilitaires” pour m’aider à résoudre cette première partie. Elles sont toutes présentées dans le programme ci-après, mais reprennent l’algorithme énoncé plus haut.

• La première, parse_input_data(), lit les données en entrées pour les transformer en une liste de nombres tirés et en une liste de grille de Bingo.
• La seconde, check_value(grid, number), vérifie si number se trouve dans la grille grid. Si c’est le cas, on va donc remplacer cette valeur par -1.
• La troisième, is_winner_grid(grid), vérifie si une grille est gagnante ou pas, en vérifiant ses lignes et ses colonnes.
• La quatrième, compute_score(grid, number), calcule le résultat final de la grille gagnante en multipliant number par la somme des nombres restants de le grille.

def parse_input_data():
    """
    Parses input data to produce usable data structures
    :return:
        - drawn_numbers: the list of numbers drawn
        - grids: the list of 2D lists of Integers
    """
    with open('input-large', 'r') as data:
        lines = data.read().splitlines()
        drawn_numbers = [int(x) for x in lines[0].split(',')]
        grids = []
        for i in range(2, len(lines[2:]), 6):
            grids.append([
                    [int(x) for x in lines[k].split(' ') if x != '']
                            for k in range(i, i+5)])
        return drawn_numbers, grids


def check_value(grid, number):
    """
    If `number` is in the `grid`, we take advantage of the fact that all numbers
    are positive to change the value in the grid to -1.
    This will allow us to check for winning grids by comparing values with -5.
    :param grid: A bingo grid
    :param number: The last number to be drawn
    :return: None
    """
    for line in grid:
        if number in line:
            line[line.index(number)] = -1


def is_winner_grid(grid):
    """
    Since we are changing drawn values to -1 in each grid, a winning grid is a 
    grid where the sum of a row or of a column is equal to 5 (the size of the grid)
    :param grid: A bingo grid
    :return: True is the grid is a winner grid, False otherwise
    """
    for line in grid:
        if sum(line) == -5:
            return True
    for col_index in range(5):
        if sum([grid[x][col_index] for x in range(5)]) == -5:
            return True
    return False


def compute_score(grid, number):
    """
    Compute the final score asked to solve this day's exercises
    :param grid: A bingo grid
    :param number: The final drawn number that makes `grid` a winner grid
    :return: The product of `number` by the sum of all remaining values in `grid`
    """
    print(grid, number)
    grid_total = 0
    for row_index in range(5):
        for col_index in range(5):
            if grid[row_index][col_index] != -1:
                grid_total += grid[row_index][col_index]
    return number * grid_total


def solve_part_one():
    numbers, grids = parse_input_data()
    for number in numbers:
        for grid in grids:
            check_value(grid, number)
            if is_winner_grid(grid):
                return compute_score(grid, number)

Partie 2

Dans la partie 2, l’énoncé nous indique qu’il serait peut-être plus judicieux de laisser le calmar géant gagner. Cela implique que l’on va chercher à déterminer la grille qui sera la dernière à gagner avant de calculer son score de la même façon qu’en partie 1.

Les quatre fonctions utilitaires présentées plus haut vont donc servir à l’identique, il faut simplement s’assurer que l’on récupère bien la dernière grille gagnante. Pour cela, je ne me suis pas trop cassé la tête : j’ai créé une liste remaining_grids qui stocke les indices des différentes grilles. Lorsqu’une grille est gagnante, je retire son indice de remaining_grids jusqu’à ce qu’il ne me reste plus que la dernière grille gagnante.

Comme je l’annonce en commentaire, cette façon de faire n’est pas vraiment très optimisée puisque je vais continuer de parcourir les grilles déjà gagnantes.

def solve_part_two():
    numbers, grids = parse_input_data()
    # Although not optimized (because we are still looping through grids that have
    # already won, this allows to check for the final grid being validated.
    remaining_grids = list(range(len(grids)))
    for number in numbers:
        for grid_index, grid in enumerate(grids):
            check_value(grid, number)
            if is_winner_grid(grid):
                if grid_index in remaining_grids:
                    remaining_grids.remove(grid_index)
                    if not remaining_grids:
                        return compute_score(grid, number)

Les difficultés

Aujourd’hui, plusieurs difficultés sont à prendre en compte.

D’une part, c’est le premier jour où l’on a à gérer un tableau à deux dimensions. Cela implique toujours de faire un petit peu attention aux indices que nous manipulons.

Une deuxième difficulté est de correctement effectuer le marquage des nombres tirés. Pour ma part, j’ai donc décidé de remplacer ces valeurs dans les grilles par -1. D’autres solutions à base de structures de données plus complexes sont possibles mais il me semble que cette solution, bien que peu élégante, à au moins le mérite d’être facile à gérer.

Enfin, la dernière difficulté à mes yeux concerne l’algorithme pour déterminer la dernière grille gagnante. Le risque serait de filtrer les grilles au fur et à mesure en utilisant toujours la même variable grids, mais il faut dans ce cas faire très attention lors du parcours de cette liste (c’est l’exercice assez classique du “retirer les occurrences d’un élément e dans une liste” avec les erreurs provenant de l’utilisation d’une boucle for). J’ai donc contourné le problème en créant une liste d’indices remaining_grids à laquelle je retire les grilles gagnantes au fur et à mesure des tirages.