Le problème

Partie 1

Notre aventure se poursuit encore et toujours dans notre sous-marin, et voilà qu’une baleine géante nous poursuit (c’est possible de rencontrer une baleine géante à cette profondeur ?).

Cette baleine risque de nous percuter, mais un essaim de crabes en sous-marins vient à notre rescousse pour tenter de percer une cavité juste assez grande pour notre sous-marin. Le problème que l’on a est que ces crabes doivent être alignés pour pouvoir commencer à creuser, et qu’il faut donc commencer par les aider à s’aligner.

Notre jeu de données en entrée est donc une liste de positions initiales des crabes :

16,1,2,0,4,2,7,1,2,14

Ces crabes, aussi valeureux soient-ils, ont besoin d’essence pour que leurs sous-marins puissent s’aligner. Et un déplacement coûte 1 point d’essence. Par exemple, le premier crabe en position 16 aura besoin de 14 points d’essence pour se rendre en position 2.

Notre objectif est alors de trouver la position pour laquelle on va minimiser les points d’essence nécessaires pour que tous les crabes arrivent à cette position.

Ce problème permet de tester un peu nos connaissances mathématiques, puisque la médiane permet de déterminer exactement cette grandeur. Il ne reste après plus qu’à calculer la somme des distances parcourues par chaque crabe pour obtenir le résultat escompté.

from statistics import median


def parse_input_data():
    with open('input-large', 'r') as data:
        positions = [int(position) 
                        for position in data.read().splitlines()[0].split(',')]
        return positions


def compute_centroid(positions):
    """
    This function computes the median of each position before computing 
    the sum of all distances to this median.
    :param positions: The list of initial crab positiosn
    :return: The minimum distance travelled for each crab to be aligned
    """
    med = median(positions)
    distance = sum([abs(position - med) for position in positions])
    print(distance)


def solve_part_one():
    positions = parse_input_data()
    compute_centroid(positions)

Partie 2

Pour la deuxième partie, on nous dit désormais que la fonction de coût de déplacement n’est plus constante mais prend la forme de la somme des entiers de 1 à n, où n est la distance parcourue par un crabe.

Pour résoudre cette partie, j’ai décidé d’aller un peu plus brute force que dans les jours précédents. J’ai donc calculé toutes les sommes de distances cumulées pour les crabes pour des points médians allant de 0 à max(positions) + 1.

Ce n’est pas élégant, mais ça me donne la solution dans un temps raisonnable…

def solve_part_two():
    positions = parse_input_data()
    # Brute force algorithm:
    # For each crab at x_crab, we can compute the fuel required to travel to 
    # another location with the following equation:
    # travelled_distance = sum(range(1, abs(x_med - x_crab) + 1))
    # So we compute all distances for x_med in range(max(positions) + 1)
    # and take the minimum in this list: 
    result = min(
        # Outer sum to compute the total distance travalled by all crabs
        [sum(
            # We use the sum of consecutive integers: sum(1, n) = (n*n+1)/2
            [(abs(loop-position) * abs(1+loop-position)) / 2
             for position in positions])
                  for loop in range(max(positions) + 1)])
    print(result)

Les difficultés

Pour aujourd’hui, il n’y a pas de grandes difficultés dans la résolution des problèmes. Il s’agissait encore une fois de bien modéliser le problème, mais cette fois-ci d’un point de vue peut-être un peu plus mathématiques qu’informatique.

Ainsi, connaître l’existence de la médiane vient grandement simplifier la première partie. Puis, en analysant la fonction coût de la seconde partie, on peut écrire un algorithme brute force basé sur le calcul de cette fonction coût pour trouver le résultat souhaité.