Re: Solution en Haskell

Ma solution est beaucoup plus rapide : 0,07s, donc assez négligeable devant le temps de démarrage de python.
Mais...
Je ne sais pas qu'elle fonctionne, je le constate.
Et ça exploite très fortement le fait qu'on ait trois liens à couper, sans cette information je ne sais pas quand m'arrêter, l'algo n'est plus du tout le même.

En gros je fais l'hypothèse que deux liens à couper ne sont pas proches (partageant un même sommet), et que je vais avoir un peu de chance.

Je pars d'un sommet, au pif, mais ça rate s'il s'agit d'un sommet d'une des arêtes à supprimer. Là je me dis que si je ne trouve pas de solution, je peux prendre un autre sommet au pif, normalement, au bout du 7è je suis certain d'avoir au moins essayé avec un sommet qui n'est pas dans une des arêtes à supprimer.
Là ça a fonctionné directement.

Je considère comme « exploré » toutes ses arêtes, et les sommets directement connectés.

Et j'itère :
* Je considère l'ensemble des arêtes liées à tous mes sommets, et pas déjà explorées.
* Je considère l'ensemble des nouveaux sommets accessibles via ces arêtes.
* Pour chacun de ces nouveaux sommets, si il est accédé par au moins deux des nouvelles arêtes, je l'ajoute.
* Et je reconstruit l'ensemble des arêtes explorées à partir des liens possibles entre mes sommets explorés.
* Il me reste un ensemble d'arêtes considérées, mais rejetées, et qui seront à nouveau considérées le coup d'après.
* Si je n'ajoute aucun nouveau sommet, j'ai a priori fini.

Normalement, si il n'y a pas deux arêtes à couper qui partagent un même sommet, je ne peux pas « traverser » ces arêtes avec mon algorithme.
Il se trouve que ça s'arrête très très vite sans donner de résultat, donc j'ai juste essayé un truc :
* Si l'ensemble des arêtes que je peux atteindre mais que je n'ai pas considérées n'est pas de taille 3, alors j'ajoute unilatéralement toutes les arêtes possibles : je ne suis pas allé assez loin, il faut que j'avance, et c'est la méthode la plus naïve pour avancer.
À noter que ça peut foirer si l'un de ces nouvelles arêtes et une des arêtes à couper.
Je n'ai pas regardé dans le détail, mais je pense que ce problème n'existe qu'au démarrage, il faudrait peut-être partir directement à deux arêtes de distance de mon sommet d'origine (la suite me prouvera que j'ai raison pour le démarrage, mais tort globalement).

Bref, ça a fonctionné puisqu'après mon algorithme s'est arrêté à trois arêtes accessibles mais mises de côté, et là on sait que c'est le bon résultat, pif paf, terminé.

L'algorithme mériterait bien plus de vérifications, et éventuellement une boucle sur un sommet de démarrage différent, jusqu'à tomber sur une solution.
Il faudrait au minimum identifier quand est-ce que j'ai besoin de mon hack pour avancer un peu plus loin dans le noir, peut-être faire une exploration en branches pour ajouter un sous-ensemble et tester, histoire de s'assurer qu'on va trouver un truc viable, ou tout explorer sans trouver.

Mais ça a fonctionné du premier coup.
On peut noter qu'il y a 1502 sommets et 3363 arêtes dans mes données, donc au final démarrer depuis un des sommets à éviter, ça serait surtout beaucoup de malchance, c'est la taille du problème qui m'a incité à tester cette approche, en me disant que j'avais plus de chance de tomber dans le « gras » du problème que pile là où il ne fallait pas.

J'ai cherché des simplifications, un peu, avant, comme de simplifier les triangles (A<->B<->C<->A), mais autant ça donne un peu quelque chose sur les données de test (on peut brute-forcer la recherche sans soucis : prendre trois arêtes et voir si on a coupé en deux), c'est inutile sur les données réelles, on simplifie de 42 arêtes, sur 3363 ça change rien.

Par contre, en nettoyant mon code, je vois que le « hack » sert trois fois : à 15 sommets à explorer (1ère itération, donc dès le début), à 54 sommets à explorer (3ème itération), puis à 217 sommets à explorer (345 déjà validés, 13ème itération !), et là on est quand même assez loin, on aurait très facilement pu mal tomber, sachant que le résultat arrive à 18 itérations.
Bilan, je dirais que j'ai plutôt eu de la chance avec mon sommet de départ...

Voilà le code nettoyé :

from sys import stdin
test = stdin.isatty()
r1, r2 = (54, 0) if test else (562912, 0)
t1, t2 = "Étape 1", "Étape 2"
ok, nok = "033円[38;5;118m✓033円[0m", "033円[38;5;196m✗033円[0m"
data = (__doc__ if test else stdin.read()).strip().splitlines()
ex1 = ex2 = 0
nodes = set()
flinks = set()
for d in data:
 a = d.replace(":", "").split(" ")
 nodes.update(a)
 s = a.pop(0)
 for b in a:
 flinks.add(frozenset((s, b)))
S = s # Soit S un sommet quelconque
def explore(s, links):
 explinks = {i for i in links if s in i}
 expnodes = {a for i in explinks for a in i}
 newnodes = expnodes.difference([s])
 print(expnodes, explinks, newnodes)
 i = 0
 while newnodes:
 i += 1
 newlinks = {
 i for i in links
 if i.intersection(expnodes)
 }.difference(explinks)
 exploring = [
 _ for i in newlinks
 for _ in i
 if _ not in expnodes
 ]
 newnodes = {i for i in exploring if exploring.count(i) > 1}
 expnodes.update(newnodes)
 explinks.update(
 i for i in links
 if i.issubset(expnodes)
 )
 # Hack when stopping too early: adding everything linked
 if not newnodes and len(newlinks.difference(explinks)) > 3:
 newnodes = set(exploring).difference(expnodes)
 expnodes.update(newnodes)
 print(f"{i}# newlinks[{len(newlinks)}], exploring[{len(exploring)}], newnodes[{len(newnodes)}], expnodes[{len(expnodes)}], explinks[{len(explinks)}]")
 print(f"{i}# newlinks[{len(newlinks)}], exploring[{len(exploring)}], newnodes[{len(newnodes)}], expnodes[{len(expnodes)}], explinks[{len(explinks)}]")
 return expnodes, newlinks.difference(explinks)
a, b = explore(S, flinks)
if len(b) != 3:
 print("ERROR, wrong result ahead")
ex1 = len(a) * (len(nodes) - len(a))

Pour une fois, mes expérimentations téléphoniques pour coder moins et avoir de la chance rapidement, ont portées leurs fruits, j'étais le premier surpris :)
Mais c'est rude de faire du code aussi approximatif, et de s'en contenter au bout du compte, ça heurte vraiment ma façon de penser.
Enfin, c'est pour ça que j'ai validé cette étoile avant la seconde du jour précédent.

• Yth.