@XorMode see attached screenshot:
Well, it doesn’t have a specific name, it’s just test 6 
@nicolas_patrois, test 6 is one with 1267 links
at last! this task must be in very hard section
i have written it four times from draft with results 10%, 70%, 60% and at last 100%
i mastered Floyd–Warshall algorithm, but it was not working fast enough 
i ended with listing nodes which have only one link connected and deleting them then - this works
@ronlobo, @DobleD: your times seem very high, i achieve time around 1 ms on tests 1…7 and 10, on 8 i spend 35 ms, and on 9 - 53 ms
to measure time i use following function: http://www.freepascal.org/docs-html/rtl/dateutils/millisecondsbetween.html
@ronlobo, i think i can try to rewrite my solution in Darth now, to check your hypothesis
@bvs23bkv33 solved it yesterday.
Pretty small solution with about 50 lines of code…
The key is to remove the exits (nodes with just one adjacent node) from the graph until it’s empty and for each removal step count one up… (hope that’s not too much of a hint…) 
this thing has a name! Demukron Algorithm!
Awesome, but google gives me just 5 results for Demukron Algorithm
Do you have a link for a description of this algorithm?
Couldn’t find it on wikipedia as well…
so, you had only 5 search results, and did not read them all carefully? i can say even more, at least 3 of this results refer to same description text, despite of being different sources.
also what this algorith does is posted in this topic at least 5 times, people just keep describing this again and again in different words without proper name
and i found a name! that is all! i can add to my post that this is some sort of topologic sort and part of linear programming
1 Like
Great, congratulations on finding the name 
1 Like
HI
I’ve got the same issue as other. My solution pass t all the test, but when I validate it failed all of them.
I haven’t hard coded anything, I use a simplifed version of A* in lua. So there should be any trouble with the achieve time
Since there is no message I don’t konw why it failed.
Nope ^^ Though your final solution works well, there is also a very simple one using only a very simple graph algorithm and taking about the same time without any kind of optimization (in PHP at least so it could even be way faster) thus it can’t be a very hard puzzle.
@bvs23bkv33 After digging a bit deeper, it seems to be a simpler form of an expectation maximization algorithm
I did exactly this in Python, but still test 8 and 9 need too much time. 
What could I have made wrong?
Your algorithm is not the fastest one.
Well, over 2 week of struggling to create and optimize my Java code to pass this test (recursively travelling the whole tree from various nodes according to levels) i finally end up in a situation similar to others here: all test passed, but one of the validators (for me it was nr. 9) failed. This drove me crazy. Then i turned to this forum and among the comments found yours suggesting that a simple procedural erosion (i don’t care if it called Demukron Algoritm or so) will do the trick. Throwing out most of my previous code an implementing this simple algoritm resulted in a short, fast and flawlessly working code! A Big Thank To You for that!
Naturally, i learned a lot from this struggling about graph traversal as well as the Collections class including the speed of its methods, so it wasn’t just waste of time, but the main lesson taught was that a different view on a problem (and a different algorithm implemented) could really make the difference.
1 Like
You’re welcome, thanks 
validation test 10 failes on my code as well. I would not rewrite the whole code, but I am really interested, what kind of error does validation 10 find in my code
I think I found a solution that was not intended to be a solution by the puzzle designers. My solution passed all manual tests and validation tests. I can provide my algorithm and a small counter example to it.
Try to use BFS in C ++ or C #. I had no problems.
I have rewritten my code, its even more general, with no hardcoding, validator 10 still fails. Would appreciate, if a dev would explain what kind of error is validator 10 test is looking for. In general terms. Without explanation or feedback, I do not know what to change in my code.
Thank you in advance!
Having been frustrated all morning by code that times out on Tasks 8 and 9, I timed my Python code on my own computer, and discovered that it is taking its longest, by far, at the stage of loading the data! On my home machine, I see:
Task Data size (kB) Time (s)
7 20 0.1
8 394 50
9 600 144
The stage where I measure the tree takes 0.2s for Task 9. I conclude that I’m not timing out because my search is too slow!
Any hints as to how I could get the data-loading stage to move more speedily? I am current creating a dict (hash) of lists, with each key being a vertex and each list containing the vertex’s neighbours.
[Update: I broke out the data handling section a bit more and discovered that it’s not getting the data into memory, but the part where I construct my tree data structure. So I guess I need to think again about how I do that!]