Re: Jour 11

Une journée - encore - sans ordinateur, avec une résolution en très peu de temps de réflexion, et un calcul instantané sur téléphone.

Pour l'exercice 2, un cache bien posé, un découpage en trois sous-graphes entre svr->fft->dac->out, et la supposition qu'il n'y avait pas de boucles.
En fait, avec des boucles, de toute façon l'énoncé est infaisable, puisqu'on doit dénombrer les chemins possible, une seule boucle où que ce soit sur un seul chemin permet un nombre infini de chemins.
Les boucles ça se gère en cas de recherche du plus court chemin.

Si j'avais eu 0 entre fft et dac, j'aurais inversé les deux, et pour le cas général, additionner les deux semble pertinent.

J'ai aussi fait une fonction d'analyse des données pour faire le cas d'exemple, où les données sont différentes entre l'exercice 1 et le 2, d'où le clear_cache aussi.

Ma multiplication finale c'est 3241 * 22130172 * 7345, donc avec un algo plus naïf, et surtout sans cache, on arrive à trouver les valeurs de svr à fft et de dac à out, mais pas de fft à dac, avec 22 millions de chemins.
En pratique, ma fonction paths est appelée 3102 fois entre les deux exercices, avec 1891 fois où le cache a répondu et 1211 fois où le contenu de la fonction a été exécuté, autant dire que c'est assez négligeable pour le dénombrement total de ~500 billions de chemins, et ça ne prend rien en RAM.

data = sys.stdin.read().strip().splitlines()
@cache
def paths(src="you",dst="out"):
 return 1 if src==dst else sum(paths(i,dst) for i in servers.get(src,[]))
def getservers(data):
 paths.cache_clear()
 return {
 a: b.strip().split()
 for l in data
 for a,b in [l.split(":")]
 }
servers=getservers(data)
ex1 = paths()
srv=paths("svr","fft")
fft=paths("fft","dac")
dac=paths("dac","out")
ex2 = srv*fft*dac

• Yth.