◂ 7 décembre 2024 ▸
Bridge Repair : «Le compte est bon», mais avec 3 opérations différentes et uniquement de gauche à droite.
27905293: 1 3 67 91 5 5 293
2656278: 383 3 7 99 1 8
5824995: 5 1 8 2 1 89 1 6 4 2 47 3
⋮
Ajouté une petite optimisation : si un résultat intermédiaire est strictement plus grand que le résultat désiré, on sait déjà que c'est raté.
Attention, la comparaison doit être stricte ; si on finit avec un 1, alors le résultat peut rester constant.
Optimisation par utilisation des opérations à l'envers :
Énorme gain de temps (40 fois plus rapide et 150 fois moins d'appels de la fonction possible),
car on peut éviter plein de branches dès le moment où une opération de soustraction, division ou déconcaténation n'est pas possible.
- code.py
- code_optimReversedOperations.py
import operator
with open("input.txt", 'r', encoding='utf-8') as f:
lines = [line[:-1] for line in f.readlines()]
def parse_ints(line: str) -> list[int]:
return [ int(token) for token in line.replace(':', '').split() if token ]
### très légèrement plus rapide que x*10**(len(str(y))) + y ?
# def concat_ints(x, y):
# for f in [10, 100, 1000, 10_000, 100_000]:
# if y < f:
### return x * f + yI
functions_part1 = [operator.add, operator.mul]
functions_part2 = functions_part1 + [ lambda x,y: x*10**(len(str(y))) + y ]
def possible(result, vals, functions):
if len(vals) == 1:
return result == vals[0]
if vals[0] > result: # OPTIMISATION !
return False
for f in functions:
if possible(result, [f(*vals[:2])] + vals[2:], functions):
return True
return False
#return any(possible(result, [f(*vals[:2])] + vals[2:], functions) for f in functions) # Plus lent !
nb1 = nb2 = 0
for line in lines:
values = parse_ints(line)
result = values.pop(0)
if possible(result, values, functions_part1):
print("1", end='', flush=True)
nb1 += result
nb2 += result
elif possible(result, values, functions_part2):
print("2", end='')
nb2 += result
else:
print(".", end='')
print()
print("Réponse partie 1:", nb1)
print("Réponse partie 2:", nb2)