Problème n°5 : de quoi tester vraiment

Possible d'avoir parmi les deux jeux d'exemples un jeu d'exemple un peu costaud qu'on puisse se frotter à quelque chose de costaud ? Parce que sinon pour vérifier le programme c'est pas simple :(

J'ai exactement eu le même problème ... Donc j'ai pris une feuille et j'ai passé 1 heure et demi à me créer un test un peu plus violent. C'est long, mais ça paye ^^

J'ai écrit un générateur de problème : nombre de noeuds aléatoire entre a et b (donnés à l'exécution), nombre d'arcs interdits aléatoires mais sans jamais isoler complètement un noeud... etc. Pour le moment j'ai généré une dizaine de problèmes (10 noeuds, 20 noeuds et 1 à 77 sommets) à chaque fois la solution minimale existait et mon script la trouve... j'attends de tomber sur un cas où ce ne serait pas le cas pour tester ensuite à la main :( Bref ça serait quand même plus sympa que les développeurs de Prologin nous donnent des données conséquentes (un peu comme codingame).

Aaaah mon générateur me trouve un problème à 20 noeuds sur lequel mon algo ne trouve pas la bonne solution (11 au lieu de 10)... j'améliore mon algo qui trouve maintenant 10 paires de talkies... et échec sur les 3 derniers tests :(

Oui, se serait bien d'avoir une entrée de test très longue (avec au moins une centaine de sommets) pour qu'on puisse pousser un peu l'algo et voir déjà s'il fonctionne puis pour tester son efficacité. Je vais aussi me mettre à faire un générateur, c'est une bonne idée. En attendant je continue à tester les cas particuliers à la main, je trouve cela plus efficace.

Vraiment pas évident de trouver un test non trivial où le nombre de talkies n'est pas optimal. Pour le moment, sur 20 problèmes générés (de taille variable entre 20 et 200 noeuds) pas tombé dessus.

Il y a un test assez simple que mon algo n'arrive pas à passer ! Il faut 8 îles, et dessiner un octogone avec les contraintes. La solution optimale est 4 talkies, mais il y a un moyen d'en trouver 5 en suivant mon algo. Je suis en train de me creuser la tête pour passer ce test-là !