◂ 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
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 ]
def substract_test(a,b):
if b >= a:
return False
return a - b
def divide_test(a,b):
if a % b != 0:
return False
return a // b
def deconcat_test(a,b):
f = 10 ** len(str(b))
if a % f == b:
return a // f
return False
functions_part1 = [ substract_test, divide_test ]
functions_part2 = functions_part1 + [ deconcat_test ]
def possible(result, vals, functions):
if len(vals) == 1:
return result == vals[0]
for f in functions:
reduced_val = f(*vals[:2])
if not reduced_val:
continue
if possible(result, [reduced_val] + vals[2:], functions):
return True
return False
nb1 = nb2 = 0
for line in lines:
values = parse_ints(line)
target = values.pop(0)
values.append(target)
values.reverse()
result = values.pop()
if possible(result, values, functions_part1):
print("1", end='', flush=True)
nb1 += target
nb2 += target
elif possible(result, values, functions_part2):
print("2", end='')
nb2 += target
else:
print(".", end='')
print()
print("Réponse partie 1:", nb1)
print("Réponse partie 2:", nb2)