Je suis en train d’essayer le challenge Tead.
J’ai un algo que je trouve relativement simple mais qui consomme un peu trop il semblerait
Je passe jusqu’au test 7. Et au 8 ème test j’obtiens :
Le délai d’exécution du processus a été dépassé. Cela peut signifier que
votre solution n’est pas suffisament optimisée pour traiter certains cas.
Mon algo consiste à stocker les noeuds et les relations entre le noeuds dans un un dictionnaire.
Ensuite de calculer le chemin le plus longue du graphe et d’en déduire le temps de propagation.
Le challenge Teads a une solution simple avec une complexité en O(N), mais elle peut être contre-intuitive. Sans en dire trop (surtout qu’is s’agit d’un challenge pour un job), tu es sur la bonne piste mais tu n’as sans doute pas la bonne méthode pour trouver le plus long chemin.
On supposera qu’il n’y a jamais de relation cyclique dans ce réseau.
Je crois que c’est surtout un problème d’optimisation. Une solution est de créer le graph en O(n). Ensuite il faut trouver la profondeur d’un arbre B dont les feuilles sont les noeuds n’ayant q’un voisin dans le graph fourni par le challenge. Il faut trouver un B de profondeur minimum en O(n). Je l’ai fait en Java, bonne chance “matooouse”!
Salut,
L’information se propage sur ton arbre depuis un sommet jusqu’aux feuilles.
Une idée d’algo en O(n) consiste a propager l’information dans le sens inverse ;).
Need help… Building graph manually and tracing path is very hard for big input. My program is failing for test case 5,6,7,8,9 which are really big graph to debug. @codingame some UI tool would help to debug.
if somebody tell me longest path for those input will help me to debug.
J’ai réussi le challenge, mais j’aimerais qu’on m’en dise un peu plus sur le principe d’algo en O(n)… Je suis un autodidacte de la prog, alors les algos connus surtout pour les graphs, la physique les maths etc… j’y connais rien…
Je n’ai que mon bon sens pour m’aider… Ce qui n’est parfois pas suffisant (cf : Mars Lander - Niveau 2)
@helmer_valentin : En fait, plutôt que d’évaluer la profondeur de chaque noeud et de prendre la plus faible, tu peux élaguer ton arbre en coupant les feuilles…
Is this puzzle solvable in JavaScript?
Or do I have to use C or the like?
I brought the Path-finding Algorithm down to O(N) complexity, since it is a simple, undirected, a-cyclic graph, But I still fail the test cases 6, 7, 8, 9 and for the final score I fail 4, 5, 6, 7, 8, 9.
I think it should be solvable in JS, considering my not-completely-optimized PHP solution can solve 8 times the test case 9 before timeouting.
Path-finding here should actually be a simple BFS, so your issue is probably more about how you use it. As you noted, it’s an acyclic graph, thus it has a neat property for this puzzle.
Les algorithmes connus sont souvent, dans leur principe, des algorithmes simples à comprendre intuitivement.
Leur codage, en revanche, peut parfois être un peu plus ardu si on débute en programmation ou si on a du mal avec la manière de penser algorithmique. Certains langages, comme Python, permettent presque d’écrire le code comme on pense l’algorithme au détriment de la rapidité (j’ai résolu ce problème comme ça).
