◂ 5 décembre 2023 ▸
If You Give A Seed A Fertilizer : Faire des correspondances de nombres sur de larges intervalles qui se chevauchent
seeds: 364807853 408612163 302918330 …
seed-to-soil map:
2069473506 3732587455 1483883
3235691256 2348990120 6550341
⋮
soil-to-fertilizer map:
2700214958 2743391193 363795571
⋮
humidity-to-location map:
⋮
- code1.py
- code2.py
- code2_oo.py
- code2_oo_nonRecursif.py
- intervalle.py
""" Version orientée-objet. Utilise la classe Intervalle du fichier intervalle.py.
20 fois plus lent que la version non-OO de code2.py """
from intervalle import Intervalle
import re
f = open("input.txt", 'r', encoding='utf-8')
lines = [line[:-1] for line in f.readlines()]
def parse_ints(line: str) -> list[int]:
return [ int(tok) for tok in re.split('[^0-9]+', line) if tok ]
""" Pour les règles de transformations entre les différentes catégories
seed => soil => fertilizer => water => light => temperature => humidity => location """
Regle = tuple[Intervalle, int] # intervalle [a;b[ qui s'applique, décalage
Transformation = list[Regle] # Règles pour passer d'une catégorie à la suivante
transformations: list[Transformation] = []
seeds = parse_ints(lines[0])
seeds_groupes_par_pairs = zip(* [iter(seeds)]*2 )
# ou: seeds_groupes_par_pairs = zip( seeds[0::2], seeds[1::2] )
# ou: seeds_groupes_par_pairs = itertools.batched(seeds,2) # idéal, mais depuis Python 3.12
seeds_intervalles: list[Intervalle] = [Intervalle(a,a+d) for (a,d) in seeds_groupes_par_pairs]
# transformer la façon de décrire la règle dans input en une Regle plus lisible
def creer_regle(new_value_start: int, old_value_start: int, size: int) -> Regle:
intervalle_applique = Intervalle(old_value_start, old_value_start + size)
decalage = new_value_start - old_value_start
return (intervalle_applique, decalage)
for line in lines[1:]:
if not line:
continue
elif ':' in line:
print("Lecture des règles de " + line.split()[0])
transformations.append([])
continue
else:
transformations[-1].append( creer_regle(*parse_ints(line)) )
def calc_valeur_suivante(regles: Transformation, intervalle: Intervalle) -> list[Intervalle]:
for intervalle_regle, decalage in regles:
intersection = intervalle & intervalle_regle
if not intersection.est_vide():
retour = [intersection.decale(decalage)]
for inter in intervalle - intersection:
retour.extend(calc_valeur_suivante(regles, inter))
return retour
# Aucune règle appliquée, donc on renvoie l'original :
return [intervalle]
def calculer_intervalles_suivants(regles: Transformation, intervalles: list[Intervalle]) -> list[Intervalle]:
nouveaux_intervalles = []
for intervalle in intervalles:
nouveaux_intervalles.extend(calc_valeur_suivante(regles, intervalle))
return nouveaux_intervalles
intervalles = seeds_intervalles
for regles in transformations:
intervalles = calculer_intervalles_suivants(regles, intervalles)
print("Reponse partie 2:", min(inter.start for inter in intervalles))