[Community Puzzle] Plague, Jr

Edit : now i’m stuck like some posters above, I.e : the Advanced case, i find a diameter of 10 instead of 26.

Could we at least have the “start pad”, so we can see what’s wrong with our diameter research (i don’t have enough patience for testing 999 pad myself unfortunately).

thx you

I tried to find a way to answer your question w/o giving too much hints, but it’s hard. Maybe it’s that: Imagine that you have 2 tapes with different, but known lengths. Stick them together. You have 1 tape and you know the length of it. Do you need to know where the middle position is to calculate the half of the length of the new tape? No. One more hint: this is a typical divide and conquer task.

Thx for answering, i understood your tip with my above neighbour JBM.
The thing here is a problem with the third test (advanced case) where like some other ppl i found a diameter of 10 instead of 26.
Do you have the “optimal” start node so i can manage finding why my code didn’t find the right diameter ?

There is no optimal, or dedicated node. You can solve all puzzles from any node. Try to understand the divide and conquer algorithm in which you split the main task to several and identical small ones.

I must have some difficulties with english because it’s not what I mean.

More precisely, my question is : what pair of node can generate a diameter of 26 ?
With that, I can track my algorithm when it go through them. So I can debug when I compute the diameter because you can understand i can’t debug 499500 possibilities ((999+1)*999/2) manually.
Usually, the last unit test are more harder to pass than the first one. Here it’s not the case…
I would never thought I would have one day so much difficulties with a simple bfs :frowning:

Edit : for those who have reached the 13 result of diameter for the advanced case, here a tip which saved me : don’t forget to NOT return something if you find a “dead end”.
the different unit test pass because the first neighbour never end into a “dead end” (at least, not the pair of node which let us compute the maximum diameter).

When you find the longest path, you find the shortest time…

Is this a binary tree or a generic tree? are there several trees or just one?

Why should there even be a tree? That word doesn’t appear in the statement, let alone “binary” or “generic”.

1 Like

sry, i mean if a pad can have more than 3 rods? I would find that a helpful indication.

Well I don’t see anything in the statement preventing that.

This is not I call easy puzzle …

This is not I will call and Easy Puzzle. Still learnt a lot in my first tree puzzle. Special thanks to @jdm.

1 Like

I am able to pass all but the ‘Donut Case’ test case. I still get the right results for All the tests. The ‘Donut Case’ is failing because my code is taking too long to process. I am trying to find the maximum of the shortest path (bfs) between a random node and all other nodes. And from that maximum node, again bfs to find the maximum of shortest paths and so on until the maximum nodes are visited already (so I get to do only 2 or 3 bfs). To find the shortest path from one node (say 0) to all other nodes in the Donut Case, takes more time. Any clue as to how to optimize?

Got it working somehow… can you please validate?

Many thanks!

I just finished this puzzle, it’s a nice one but imo it doesn’t belong in the easy category.
Finding the longest path in a graph is generally considered NP hard, this is not something you want to throw at beginners.

Don’t exaggerate. It’s only N^3.
And that’s not even required here.

1 Like

You might want to update the wiki then : https://en.wikipedia.org/wiki/Longest_path_problem

@Djoums You’re confusing the (actual) longest path with the diameter (the longest of the shortest paths between any two vertices).

2 Likes