[Community Puzzle] Longest Road

[LiuSiyang]

Hope to add the maximum number of players in the problem description(Translated by Google)

[ChestNuts87]

after some hours, i have managed to code DFS algo with a success for all tests.
No cheat, everything is calculated

but when I submit, test 4 and 6 and non validated…
Cold you help me ?

[5DN1L]

Did you try this custom case? (Check out the original post to see the custom case properly formatted.)

[Community Puzzle] Longest Road

The message about hardcoded solution is just a general information. If your code fails one of the validators it means that it is not handling one of the edge cases correctly. You can experiment with Custom test cases to try and figure it out (you must enable Expert mode in settings to see it). Try something like this (not the actual validator, but similar): 5 aA##c #a##c b###C bBb#c ##bcc Expected output is C 5

You could also try creating your own custom cases to test your code, e.g. by flipping the grid horizintally or vertically.

[ChestNuts87]

thank you for your prompt answer @5DN1L
it works with this example too.

By the way test 4 is now validated in submission too… but i have changed nothing!

ok… i go back to work and i will try tonight… let see

Thank you again @5DN1L !!

[quote="[Community Puzzle] Longest Road, post:22, topic:190734"]
aA##c #a##c b###C bBb#c ##bcc
[/quote]

[ChestNuts87]

pb solved

so happy

[Kashing]

Hi there, great puzzle to work on your fundamentals i.e., not too long, nor too hard, but with some twists to keep it interesting.

I have come into a bit of a headache with validator6 which was the only failing test, it must have an interesting edge case, that should be implemented in the regular test case for exhaustivity.

[5DN1L]

Haha, but nope, it’s not an edge case. The validator is a mirror image of the test case and two chars changed (road<->empty).

[frederic-junier]

Hello, my code does not pass the last validator 6, for each related component (one per character) I search the diameter of the spanning tree with two successive dfs, is it a false lead? My code works for the 5DN1L example with C 5. What is the particularity of the last validator?

[wyenat]

Very fun puzzle overall.
Yet another puzzle showing how absurdly powerful recursive functions are.

[5DN1L]

Please refer to this answer:

[Community Puzzle] Longest Road

Haha, but nope, it’s not an edge case. The validator is a mirror image of the test case and two chars changed (road<->empty).

[frederic-junier]

Thanks, problem solved. My algo of diameter search by related component cannot work because some nodes count in the distance calculation and others do not. A calculation running a dfs from all possible nodes is enough.

[racko]

Isn’t this puzzle, in the general case, as difficult as Longest path problem - Wikipedia, i.e. NP-hard?

[Jumpmaster]

I don’t have a formal background in CS so I could be wrong, but to my understanding a problem being NP-hard, NP-complete, etc. simply refers to the amount of computational time required to find a solution. The difficulty of the problem does not necessarily relate to the amount of time an algorithm takes to solve the problem. This puzzle and its test cases were designed to be solved with basic recursion algorithms without running into timeouts. So I would not say it is as difficult in general especially compared to java_coffee_cup’s example, but it is a very similar problem.

[java_coffee_cup]

Yes, the puzzle design allows some very difficult situations that is too hard to solve within the time limit. That difficult situation currently does not appear in test cases but theoretically it can appear and nothing can stop it to appear.

This potential problem can be reduced by defining some constraints to restrain the search space to a reasonable range.