Advent of Code 2021 Day 17

Le problème

Parties 1 et 2

Le problème d’aujourd’hui nous emmène face à une fosse océanique. Pour vérifier si les clés de notre traîneau (c’est quand même l’élément déclencheur de l’advent of code de cette année) se trouvent dans cette fosse, on décide d’y envoyer une sonde. Cette sonde est envoyée depuis le sous-marin avec une vitesse initiale verticale et horizontale. Seulement, cette vitesse initiale est constamment modifiée du fait des frottements avec l’eau et du courant marin.

Ainsi, la vitesse de la sonde évolue avec les règles suivantes :

La position en x de la sonde augmente à chaque étape de v_x ;
La position en y de la sonde augmente à chaque étape de v_y ;
À chaque étape :
- Si v_x est strictement positif, alors v_x diminue de 1 ;
- Si v_x est strictement négatif, alors v_x augmente de 1 ;
- Si v_x est nul, alors on laisse cette valeur inchangée ;
- Quoiqu’il arrive, v_y diminue de 1 à chaque étape.

Je réunis encore une fois les deux parties parce qu’elles peuvent être réalisées conjointement et assez simplement.

En effet, dans la première partie, on nous explique qu’il existe donc plusieurs valeurs de vitesse initiale permettant à la sonde d’arriver dans la fosse. L’objectif est de déterminer la plus grande valeur de y atteinte, tout en faisant que la sonde tombe dans la fosse. Dans la seconde partie, on nous demande de compter le nombre total de vitesses initiales permettant à la sonde d’arriver dans la fosse.

Pour la première partie, j’y suis allé un peu brute force. Je crée un dictionnaire dont les clés sont les couples (v_x, v_y) qui représentent les vitesses initiales, et dont les valeurs sont la liste des positions successives prises par la sonde. Pour savoir quand arrêter de calculer ces valeurs, j’ai défini une fonction has_missed() qui permet de déterminer si la sonde a raté son objectif. Cette limite est déterminée de la façon suivante, où S représente la position initiale de la sonde, # les positions successives, T un point de la fosse, et X les zones qui nous assurent que la sonde a raté son objectif. Cela se traduit donc par : x > x_max or y < y_min.

.............#....#............XXXXXXXXXX
.......#..............#........XXXXXXXXXX
...............................XXXXXXXXXX
S........................#.....XXXXXXXXXX
...............................XXXXXXXXXX
...............................XXXXXXXXXX
...........................#...XXXXXXXXXX
...............................XXXXXXXXXX
....................TTTTTTTTTTTXXXXXXXXXX
....................TTTTTTTTTTTXXXXXXXXXX
....................TTTTTTTT#TTXXXXXXXXXX
....................TTTTTTTTTTTXXXXXXXXXX
....................TTTTTTTTTTTXXXXXXXXXX
....................TTTTTTTTTTTXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Une fois que l’on a construit le dictionnaire, il faut le trier pour ne garder que les éléments qui atteignent la fosse pour ensuite déterminer la valeur maximale atteinte pour y. Le dictionnaire permet également de déterminer le nombre de vitesses initiales permettant à la sonde d’atteindre la fosse.

Pour optimiser un peu cet algorithme, il faut jouer un peu sur les valeurs possibles de v_x et v_y. Là, je ne me suis pas cassé la tête :

v_x est compris entre 0 et 2 * x_max (une valeur négative ne permettrait pas de revenir dans les x positifs) ;
v_y est compris entre -2 * x_max et 2 * x_max, ce qui est peut-être largement trop mais bon… Ça fait le boulot assez rapidement.

Voici donc ma solution pour les deux parties de cette journée :

def parse_input_data():
    with open('input-large.txt', 'r') as data:
        remove_chunk = len('target area: ')
        line = data.readline()[remove_chunk:]
        x, y = line.split(', ')
        x, y = x[2:], y[2:]
        x_start, x_end = [int(i) for i in x.split('..')]
        y_start, y_end = [int(i) for i in y.split('..')]
        return range(x_start, x_end+1), range(y_start, y_end+1)


def build_candidates(vx, vy, x_r, y_r):
    """
    Construit la liste des positions pour (vx, vy) donné
    :param vx: Vitesse initiale en x
    :param vy: Vitesse initiale en y
    :param x_r: Liste des coordonnées en x de la fosse
    :param y_r: Liste des coordonnées en y de la fosse
    :return: Liste des positions pour (vx, vy) donné
    """
    x, y = (0, 0)
    candidates = [(x, y)]
    while not has_missed(x, y, x_r, y_r):
        vx, vy, x, y = next_position(vx, vy, x, y)
        candidates.append((x, y))
    return candidates


def next_position(vx, vy, x, y):
    """
    Calcule la prochaine position et met à jour la vitesse de la sonde
    :param vx: Vitesse initiale en x
    :param vy: Vitesse initiale en y
    :param x: Coordonnée en x de la position actuelle de la sonde
    :param y: Coordonnée en y de la position actuelle de la sonde
    :return: Nouvelle vitesse suite aux frottements+courant, et nouvelle position
    """
    x += vx
    if vx > 0:
        vx -= 1
    y += vy
    vy -= 1
    return vx, vy, x, y


def keep_candidates(candidates, x_r, y_r):
    """
    Parcourt le dictionnaire pour ne garder que les éléments qui montrent que
    la sonde peut atteindre la fosse.
    :param candidates: Dictionnaire ((vx, vy): [positions de la sonde])
    :param x_r: Liste des coordonnées en x de la fosse
    :param y_r: Liste des coordonnées en y de la fosse
    :return: Dictionnaire avec des vitesses initiales qui permettent à la sonde
             d'atteindre la fosse
    """
    final_candidates = dict()
    for velocity, positions in candidates.items():
        for (x, y) in positions:
            if x in x_r and y in y_r:
                final_candidates[velocity] = positions
                break
            if has_missed(x, y, x_r, y_r):
                break
    return final_candidates


def has_missed(x, y, x_r, y_r):
    return x > max(x_r) or y < min(y_r)


def find_max(final_candidates):
    max_y = 0
    max_velocity = None
    for velocity, positions in final_candidates.items():
        for x, y in positions:
            if y > max_y:
                max_velocity = velocity
                max_y = y
    print(max_velocity)
    return max_y


def solve_part_one():
    x_r, y_r = parse_input_data()
    x_r, y_r = list(x_r), list(y_r)
    candidates = dict()
    for vx in range(max(x_r)*2*):
        for vy in range(-max(x_r)*2, max(x_r)*2):
            candidates[(vx, vy)] = build_candidates(vx, vy, x_r, y_r)
    final_candidates = keep_candidates(candidates, x_r, y_r)
    max_y = find_max(final_candidates)
    print(max_y)
    print(len(final_candidates.keys()))

Les difficultés

Pour cette journée, la principale difficulté que j’ai éprouvée aura été de se décider de ne pas chercher de jolie solution et d’y aller brute force à la place. J’ai donc tâtonné pour les différentes valeurs des bornes pour les boucles for, afin d’obtenir un résultat correct dans un temps acceptable.

Après avoir trouvé les bons résultats, je me suis lancé dans une tentative d’optimiser un peu mon code, ce qui a finalement abouti au programme présenté plus haut.

2021-12-17

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