[Community Puzzle] Tree Paths

Puzzles
#29

When storing all the input in some data structure of your choice, make sure that you can easily lookup any node’s left child, right child, and also it’s parent.
Then, you can make a loop, starting from the target node, always moving towards the parent, while you reach the root. When moving up, you can decide whether the node where you came from was the left or the right child of the parent. By storing this info, by the time you reached the root, you have the full puzzle answer, but in reverse order.

PS: I see you solved 3 puzzles on CG. There are plenty of puzzles, some are much easier than this one. It is not a problem to put this aside, solve some others and to come back to this only later.

#30

Thank you so much for the advice . Obviously i solved 3 puzzles in CG i am just starting.

If i understand , the first thing is to store the tree ( all node value ) in a data structure like an array. After that , searched the target value , once found go back to the root.

My question is how to remember the direction a node come from.

#31

Let’s assume you came from node “x” and moved to its parent, node “y”, (y = parent[x]). You can check whether if (left[y] == x) or elseif (right[y] == x).

#32

Thank you very much TBali , I really appreciate you it , but i think i have to give i tried my best but nothing .

THANK YOU FOR YOUR SUPPORT .

#34

i tried this in bash. creating an actual tree on the file system. using the command line tool “find” to traverse the tree and find the target for me.
all tests work. all validators work except validator 4.
the test cases given in this thread all work.
any help?

#35

Validator 4 is the same as test case 4 except for the second input (i.e. index of the target node). That means you may debug your code by varying that input to see for what input value your code gives a wrong output.

#36

thank you for the tip. i tried all 9 possible values in the tree. all were working correctly. i even tried replacing some numbers with symbols like “-”. even then it still worked correctly. i fear the problem is elsewhere.

#37

What are your outputs for each of the 9 possible values?

#38

thank you for double checking. i very well could have made a concentration error.

for this input

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

output for all X

X Output
1 Root
2 Left
3 Right
4 Left Left
5 Left Right
6 Right Right Left
7 Right Right Right
8 Right Right
9 Right Left

i did this table twice to double check against copy paste errors.

1 Like
#39

Ah ok, yes, all outputs are correct. You should have passed validator 4 then. Yup, probably a concatenation error.

#40

just to clarify: my code still does not pass validator 4.

my remark about my possible concentration error was referring to the laborious task of manually entering the number and expected output. i very well could have made a mistake there. but now i have double (triple) checked with confirmation from a third party (thank you 5DN1L) that my code is indeed returning the correct result. still not passing validator 4.

#41

That is weird. Try testing it within CodinGame as a custom test case and see what error you get.

#42

i did test it within codingame using the custom test case feature. that was where i did the laborious manual task.

#43

Oh I see. In that case you may have to test in the contribution view. If required, we can discuss by PM here.

#44

i solved the problem with validator 4. with help from 5DN1L.

the problem is the missing last newline in the input. it caused my bash code to not handle the last line. validator 4 is the only test case where the target key is in the last line. i modified my code so it appends a last newline and now validator 4 works.

what really confused me was: when testing using the custom test feature in the codingame ide the input does have a last newline. so when i tested all possible target nodes for test case 4 in the custom test feature my code worked flawlessly. but in the validation the input had no last newline so my code did not work for validator 4.

this is a bit aggravating but i guess such is life for the bash hacker.

more details and background info:

most command line tools expect a line to be terminated by a newline. some tools behave differently if a line is not terminated by a newline.

the typical bash script loop to read lines from stdin

while read line ; do
    something with "$line"
done

will not handle the last line if the last line does not have a terminating newline.

demo

printf '1\n2\n3' | while read line ; do
    echo $line
done

will print

1
2

the third line is not handled because it lacks a terminating newline.

the thing is: read still read the line. so the contents of the variable $line is 3. but since it did not encounter a newline and instead encountered an “end of input” it returned an “error” which caused the while loop to exit without executing the body. so the last line is not handled.

to workaround this you can do

while read line || [ -n "$line" ] ; do

or

grep "" | while read line ; do

read here for more info

bash - Shell script read missing last line - Stack Overflow

2 Likes
#45

Good easy puzzle.
But looks like the first parameter N is unnecessary.

#46

It allows you to do it with arrays instead of hashmaps, which makes it easier for some languages.

#47

I’m somehow passing all test cases, and all custom test cases listed here, and failing validator 1 and 2 when submitting.

Any hints on what validator 1/2 are and why they may fail while 3, 4 and 5 pass?

#48

Not sure, but you may try to create similar custom cases to test your code. That should be relatively easy because the number of possibilities is limited. (Number of nodes = 3 and the number of nodes with two children = 1 for tests/validators 1 and 2.)

1 Like
#49

Thanks for the response.
I had made an assumption about the root of the tree that didn’t hold true.
Solved it by reversing the solution.