Advent of code

 1er décembre 2024 ▸

  Historian Hysteria : Tri, comparaison et recherche avec deux listes d'entiers.
40885   43247
   
14780   86274
   
35132   49508
   
      ⋮
Le code de base est en O(n²) à cause du count dans le for.
Pour la partie 2, on peut faire un algo en O(n) en comptant les diverses valeurs de tab1, puis en utilisant un tableau associatif permettant de retrouve le compte ensuite sans devoir repasser tab1 en revue à chaque fois. (Et pas besoin pour ça d'avoir les tableaux triés.)

code_part2_onePassNoDictIfSorted.py est un algo en O(n) — si on ne compte pas le temps de tri déjà fait pour la partie 1 — et sans mise en cache du nombre d'éléments de tab1.
  1. code.py
  2. code_part2_onePassNoDictIfSorted.py
with open("input.txt", 'r', encoding='utf-8') as f:
    numbers = [int(i) for i in f.read().split()]

tab1 = sorted(numbers[::2])
tab2 = sorted(numbers[1::2])

result2 = 0

while tab1 and tab2:
    n = 0
    val = tab1[0]
    while tab1 and tab1[0] == tab2[0]:
        n += 1
        tab1.pop(0)
    while tab2 and tab2[0] == val:
        result2 += n * val
        tab2.pop(0)
    while tab1 and tab1[0] < tab2[0]:
        tab1.pop(0)
    if tab1:
        while tab2 and tab2[0] < tab1[0]:
            tab2.pop(0)

print("Réponse partie 2:", result2)