[Community Puzzle] Tree Paths

https://www.codingame.com/training/easy/tree-paths

Send your feedback or ask for help here!

Created by @gareve,validated by @Pduhard,@LastRick and @kayou.
If you have any issues, feel free to ping them.

I don’t understand why are the tags DFS and BFS added to this puzzle. Neither of such search is necessary.

3 Likes

I said as much during submission. It looks like a tree but you could solve it without.

The puzzle is fun but I think the description is misdirecting the coders into building binary trees. So far all solutions in C++ except one (and mine) did a variant of a binary tree (with relation parent -> children) and then had troubles finding the path as they start from root. Much easier solution is to store reverse relations (child -> parent).

Maybe call it “reverse binary tree lookup” or a bit more enigmatic: “Backtracing”? Or put a hint in the description?

At least maybe this will point to another possible solution.

The hint is in the fact that it’s an easy puzzle.

To be fair I usually ignore tags and go with my own ideas. If I’m stuck then sure tags can help, but since this is an easy puzzle you can find a simple solution of your own.

2 Likes

Hey guys :slight_smile:
I have trouble passing validators 1 and 2, despite the fact that other validators and all provided unit tests are OK… do you know what behavior are these two testing please?
Thanks!

EDIT
Nevermind, nailed it :wink:

1 Like

Do you guys know what validators 1 and 2 are? I seem to keep failing on them. Thank you

Validators 1 and 2 are exactly identical to testcases 1 and 2 except that nodes are labelled differently.
Maybe your problem is that you assume that the root is always labelled 1 in your algorithm ?

4 Likes

I pass every test and every validator except validator 4 and I have no idea why

Hard to say … But i can give you 2 more tests similar to this validator

9
6
4
1 3 2
2 4 5
3 9 8
8 7 6

Left Right Right

and

9
6
4
1 3 2
2 4 5
3 8 9
8 7 6

Left Left Right
4 Likes

Thanks so much.
validator 4 was the only case with a tree with more than a root parent having the target in the last input line.
I overwrote my loop index in a way that would always skip the last iteration and the root was handled as a special case.

Hello everyone,
I pass every test, but when i submitted my code, Validator 2 and 3 was wrong.
I have no idea why … Is there some personalized test i can get, for debug ?

Thanks a lot !

Ah merchi pour les tests additionnels (+50XP :-)), j’avais fait un sorted(directions, reverse=True) au lieu de direction.reverse(), en gros je rajoutais un tri à la con lol