Advent of code

◂ 6 décembre 2023 ▸

  Wait For It : Trouver les meilleurs compromis entre durée de charge d'un bateau (le rend rapide) et le temps restant de course

Time:        49     97  … 

Distance:   263   1532  … 

1. code.py

import re, math, timeit

f = open("input.txt", 'r', encoding='utf-8')
lines = [line[:-1] for line in f.readlines()]

times, dists = ([ int(tok) for tok in re.split('[^0-9]+', line) if tok ] for line in lines)

def nb_fois_battu_basique(time, dist):
    """Donne le nombre de façon de battre le record de distance
       Façon naïve qui teste chaque possibilité."""
    nb_fois_battu = 0
    for temps_presse in range(1,time):  # 0 et time donnent 0, inutiles !
        if (time-temps_presse) * temps_presse > dist:
            nb_fois_battu += 1
    return nb_fois_battu


def nb_fois_battu_basique_avec_generateur(time, dist):
    """Donne le nombre de façon de battre le record de distance
       Façon naïve, mais avec générateur : plus lent de 10%"""
    return sum(1  for  temps_presse in range(1,time)  if  (time-temps_presse) * temps_presse > dist)



def nb_fois_battu_rapide(time, dist):
    """Donne le nombre de façon de battre le record de distance
       en résolvant l'inéquation (time-x) · x > dist
                           ↔    x² - time·x + dist < 0
       O(1) au lieu de O(n), donc résultat immédiat (mille fois plus rapide ici)."""
    delta = time**2 - 4*dist
    if delta <= 0:
        return 0
    sqrt_delta = math.sqrt(delta)
    x1 = (time - sqrt_delta) / 2
    x2 = (time + sqrt_delta) / 2
    return math.ceil(x2) - math.floor(x1) - 1
    

def reponse1(times, dists):
    return math.prod( nb_fois_battu(*time_dist)  for time_dist in zip(times, dists) )

def reponse2(times, dists):
    coller_valeurs = lambda tab: int(''.join(map(str,tab)))
    return nb_fois_battu( coller_valeurs(times), coller_valeurs(dists) )


## Exécution et mesure du temps mis :

coller_valeurs = lambda tab: int(''.join(map(str,tab)))
time, dist = map(coller_valeurs, (times, dists))
timer = timeit.Timer('timer.reponse2 = nb_fois_battu(time, dist)', globals=globals())

for nb_fois_battu in (nb_fois_battu_rapide, nb_fois_battu_basique, nb_fois_battu_basique_avec_generateur):
    print("****  Utilisation de " + str(nb_fois_battu).split()[1] + " :")

    print("Réponse partie 1:", reponse1(times, dists))

    temps = float('%.2g' % timer.timeit(10000 if nb_fois_battu == nb_fois_battu_rapide else 1))
    print("Réponse partie 2:", timer.reponse2)
    print('   Exécution en %s secondes' % temps)