[Community Puzzle] Longest Road

Puzzles
#1

https://www.codingame.com/training/easy/longest-road

Send your feedback or ask for help here!

Created by @Jumpmaster,validated by @David_Augusto_Villa,@Bavoen and @About.
If you have any issues, feel free to ping them.

#2

Unless I’m mistaken, Loops and Branches and its validator are incorrect. I count 17 a’s and a couple more b’s than claimed, all connected.

#3

I haven’t solved this yet, but my understanding is that you need to calculate the longest possible path, so for the last test the “A 13” seems to be correct with this path:

.....
A#a#.
..aa#
#.###
a....

(Note: capital A is part of the path but not counted for the length.)

PS: maybe there is a simple approach that I have overlooked, but this puzzle seems to me harder than a typical ‘easy’ category, even if the small test cases allow suboptimal algorithms.
PS2: But you were one of the approvers, weren’t you?

2 Likes
#4

There are no problems with testcases/validators.
A chain should have no branch and end if it leads to an already encountered path.

I’m ok with the easy ranking but I wouldn’t mind a medium ranking either, it lies somewhere in between.
Because it’s a piece of cake if you’re familiar with cycle detection but if you’re not, figuring it out by yourself is not that easy.

#6

Check to see that you’re not allowing diagonal moves along a path. (I had the same count on my first run, fwiw. My fingers just typed in the “nearest neighbor test” from some past problem on their own, I guess. :^)

#7

I approved before the cycle case was added. The language has been clarified to resolve this misunderstanding. I’ll rework the problem at some point, but I do wonder about the difficulty now.

#8

It’s way harder with the cycle case.

#9

Allowing cycles steps into a difficult territory that the test cases do not cover.

A fully legitimate example:

9
a#aaaa#aa
a#aaaa#aa
a#aaaa#aa
a##aa###a
aaaaa#aAa
a###aaa#a
aaaa#aa#a
aaaa#aa#a
aaaa#aa#a

max length is 50

How about…

10
Aaaaaaaaaa
aaaaaaaaaa
aaaaaaaaaa
aaaaaaaaaa
aaaaaaaaaa
aaaaaaaaaa
aaaaaaaaaa
aaaaaaaaaa
aaaaaaaaaa
aaaaaaaaaa

max length is 99

Free to try it.

1 Like
#10

I pass your first custom test case, but timeout at your second one.
Because of the cycles, I start DFS from every cell and that is way too much for this kind of map.
Maybe, if map size would have been limited to 8*8, then the current path could have been encoded into a single int64, leading to some speedup. But the branch factor for a full ‘a’ map is still extremely high.
Most likely, there are much better applicable algorithms than mine, but the given ‘easy’ category led me to brute-force… I code with a hammer, not my fingers. :slight_smile:

#11

I can pass the first one in Python locally in ~6 sec, the second one is ofc out of reach.

But I don’t think those validators you propose really fit the description, it’s supposed to be roads so you can expect '#'s to properly separate them.
So even one 2 x 2 submatrix of 'a’s (let’s call that a clearing) would feel weird here. You would never see that in a classical maze / maze with cycles.
And you can see that not a single testcase has such clearings.

So not a real problem for me as it is, but yes it would have been if there was at least one testcase with a 2 x 2 clearing (cause you could legitimately wonder for bigger clearings in validators).

#13

Trying to solve it by dfs but have to adjust the standard algorithm to go through every possible combination of directions priorities. The code becomes a monster quickly.

#14

You can just run a regular DFS from each alphabetic char.
If you call the DFS recursively like this:

  • mark the node encountered
  • call DFS()
  • unmark the node,

the search won’t explose (unless you try it on the kind of validator java_coffe_cup mentionned) and you’ll just have to update your max length at each deadend.

#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!