Re: python et lib de graph

Ah, classe :)
J'ai rien de joli à montrer ce coup-ci.
Mais bon, journée présentiel au taf hier, trois heures dans la voiture, 4h en réunions, j'ai à peine eu le temps de bricoler une solution, en ayant réfléchi sur le trajet...

J'ai fait un parcours de graphe inventé à la volée : je n'ai jamais été fichu de retenir le moindre des algos de parcours que j'ai pu apprendre, alors je suis condamné à réinventer la roue !

J'ai des cases en entrée, je regarde pour chacune d'elles où elles peuvent aller (haut, bas, gauche, droite, si la différence de hauteur est bonne), et si je n'ai pas déjà été là (donc matrice des cases visitées avec distance au départ dedans).
Je note l'ensemble des cases nouvellement visitées, et j'itère sur cet ensemble.
Donc a priori inutile de stocker le score pour le retrouver et calculer la suite comme dans mon code plus bas : il suffit de compter les étapes.

Instinctivement, je me suis dis que ça pouvait grossir, et donc j'ai décidé de manger le problème par les deux bouts, donc j'explore en montant depuis "S" et en descendant depuis "E".
Je stocke des scores positifs en montant, et négatifs en descendant.
Si je rencontre une case visitée depuis l'autre bout (case négative si je monte ou positive si je descends), j'ai fait la liaison.
En pratique je peux m'arrêter là : si je suis en train de monter c'est étape*2+1, si je suis en train de descendre c'est étape*2+2.
Dans mon code j'additionne les valeurs absolues : la valeur que j'aurais dû mettre dans la case, et celle déjà présente, et j'ai mon résultat.

Pour l'exercice 2, comme je fournis déjà une liste de case par itération, il suffit de mettre comme liste de démarrage tout les "a" et le "S", vraiment rien à coder, la dernière ligne du programme et basta.

Ah, et j'ai aligné, je bosse sur un tableau à une dimension, au lieu d'une matrice.
Et les mouvements possibles ne sont pas (haut, bas, gauche droite) mais (-1, +1, -largeur, +largeur) et un mouvement doit être dans [0, taille[

Allez, trêve de blabla, code !

heights = {
 v: (26 if k == 27 else k) or 1
 for k, v in enumerate("SabcdefghijklmnopqrstuvwxyzE")
}
input = [line for line in sys.stdin.read().strip().splitlines()]
w, h = len(input[0]), len(input)
size = w * h
moves = [1, -1, w, -w]
input = "".join(input)
map = [heights[c] for c in input]
start = input.index("S")
end = input.index("E")
def test(score, newpos, height, sign):
 """
 False : mouvement impossible
 True : mouvement possible vers case non visitée
 int : mouvement possible vers case visitée, retourne le score de cette case
 """
 if newpos < 0 or newpos >= size:
 return False
 if (sign > 0 and map[newpos] > height + 1)\
 or (sign < 0 and map[newpos] < height - 1):
 return False
 if score[newpos] is None:
 return True
 return score[newpos]
def move(score, pos, sign=1):
 height = map[pos]
 visited = []
 solution = False
 for m in moves:
 newpos = pos + m
 t = test(score, newpos, height, sign)
 if not t: # Movement not allowed
 continue
 if t is True: # New tile visited
 score[newpos] = score[pos] + sign
 visited.append(newpos)
 continue
 if t * sign > 0: # Already visited
 continue
 # Visited from the other side : solution found !
 visited.append(newpos)
 solution = min(
 solution or size,
 1 + sign * score[pos] - sign * score[newpos]
 )
 return visited, solution
def main(s1, s2):
 score = [
 0 if (pos in s1 or pos in s2) else None
 for pos in range(size)
 ]
 unfinished = True
 while unfinished:
 v1, v2 = [], []
 for pos in s1:
 v, solution = move(score, pos, 1)
 v1 += v
 if solution:
 print(score)
 print(f"Path found in {solution} moves !")
 unfinished = False
 for pos in s2:
 v, solution = move(score, pos, -1)
 v2 += v
 if solution:
 print(score)
 print(f"Path found in {solution} moves !")
 unfinished = False
 s1, s2 = v1, v2
main([start], [end])
main([pos for pos, height in enumerate(map) if height == 1], [end])

• Yth.