Re: Jour 3

Je propose à mon tour mon approche de la deuxième partie du jour 3.

Même chose : j'évite l'approche récursive en faisant une seule passe sur chaque banc de pile. On a donc une complexité en n×ばつm mais on peut la considérer linéaire si on part du principe que le nombre de piles à combiner est constant (2 dans la première phase, 12 dans la seconde).

Étant donné que d'une part, 20000 sera toujours supérieur à 19999, pour chaque pile dans le banc examiné, on a tout intérêt à remplacer la première pile qu'elle dépasse dans le jeu et invalider les suivantes.

La première ligne « continue » au début de la deuxième boucle sert à gérer la fin du banc de pile : lorsqu'il reste moins de douze piles à examiner dans le banc, on ne peut plus remplacer les premières (parce qu'il n'y en aurait plus assez pour remplir le jeu) mais il en reste suffisamment pour remplacer les dernières.

from functools import reduce
puzzle2_mode = True
row_count = 0
total = 0
battery_num = 12 if puzzle2_mode else 2
with open(input_file_name) as f:
 row_count += 1
 for l in f:
 l = l.strip()
 ll = len(l)
 cells = [ 0 ] * battery_num
 for i,n1 in enumerate(l):
 n1 = int(n1)
 for j,n2 in enumerate(cells):
 if ll - i - battery_num + j < 0: continue
 if n2 >= n1: continue
 cells = cells[0:j] + [n1]
 cells += [ 0 ] * (battery_num - len(cells))
 break
 jolts = reduce(lambda j,c: j*10+c, cells, 0)
 total += jolts
 print(l, cells, jolts)
print("Nombre de bancs :", row_count)
print("Total des jolts :", total)