OK, this looked like a monster a week ago, but I solved it with simple recursion and cycle detection, which felt like brute forcing but I guess is actually DFS. Can’t be easy with a high level concept like that, but isn’t too challenging either. Medium difficulty seems about right to me.
Ugh, the tag for existing puzzles is DFS. I like that someone decided this should be “Depth first search” except now I have both skills.
Updated the difficulty to medium since that seemed to be the general consensus. Thanks for all the discussion everyone! This was my first puzzle submission, and hearing all your feedback has been super helpful. Hope you all enjoyed it.
Hi !
I only get a 83% score because of the validator 4 which fail.
But I can’t understand why since my solution isn’t “hard coded”.
I used a loop which first detect every players (A, B, …) before applying DFS.
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):
I had the same issue and couldn’t find the issue until I saw the new testcase in here since I was using a > instead of >= in one place.
An extra testcase with the shortest longest road (5) would be great!
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.
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?
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.
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.
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.