[Community Puzzle] Longest Road

Puzzles
#17

I first had the same doubt as you. I double checked the puzzle description.

If a player has at least 5 consecutive (NON-REPEATING) roads then they can be awarded the “longest road” victory points.

The roads cannot be repeated. They must be travelled from the start point to the end without backtracking.

#18

So there is nothing to ban a road like this to be valid…
image

It cannot happen just because the author code cannot solve it.

Instead of pushing solution target to the extreme, why the statement and game rule not adjust itself to limit some “too difficult” possibilities?

1 Like
#19

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.

#20

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.

4 Likes
#21

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.

Thanks

1 Like
#22

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

2 Likes
#23

Thanks !
I did it :slight_smile:

#24

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!

#25

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

#26

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 ?

#27

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

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

1 Like
#28

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]

1 Like
#29

pb solved :slight_smile:

so happy

1 Like
#30

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.

#31

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). :smile:

1 Like
#32

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?

#33

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

2 Likes
#34

Please refer to this answer:

1 Like
#35

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.

2 Likes
#36

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