Dwarfs standing on the shoulders of giants puzzle discussion

Cool, now the only thing remaining is to convince the rest of the world.

2 Likes

thanks, it worked for me too

This is the error I found in mine. Fixing it got me to 100%. I was failing on “More complex hierarchy” prior to this test case.
5
2 3
4 5
5 6
6 2
4 3
My problem was that there was a short circuit 4-3 in the path 4-5-6-2-3

3 Likes

Hi all, I fail on “More complex hierarchy” and “Simple hierarchy in-depth” and I don’t understand why… I tried a lot of test :

[details=Summary]// complet graph.add(link: Link(from: 1, to: 2)) graph.add(link: Link(from: 1, to: 3)) graph.add(link: Link(from: 3, to: 4)) graph.add(link: Link(from: 2, to: 5)) graph.add(link: Link(from: 2, to: 4)) graph.add(link: Link(from: 10, to: 11)) graph.add(link: Link(from: 10, to: 1)) graph.add(link: Link(from: 10, to: 3)) // plusieurs courants graph.add(link: Link(from: 2, to: 3)) graph.add(link: Link(from: 8, to: 9)) graph.add(link: Link(from: 1, to: 2)) graph.add(link: Link(from: 6, to: 3)) graph.add(link: Link(from: 1, to: 2)) graph.add(link: Link(from: 1, to: 2)) //autre graph.add(link: Link(from: 1, to: 2)) graph.add(link: Link(from: 2, to: 3)) graph.add(link: Link(from: 1, to: 3)) // complex graph.add(link: Link(from: 2, to: 3)) graph.add(link: Link(from: 4, to: 5)) graph.add(link: Link(from: 5, to: 6)) graph.add(link: Link(from: 6, to: 2)) graph.add(link: Link(from: 4, to: 3)) //other graph.add(link: Link(from: 1, to: 2)) graph.add(link: Link(from: 2, to: 3)) graph.add(link: Link(from: 4, to: 5)) graph.add(link: Link(from: 5, to: 6)) graph.add(link: Link(from: 5, to: 2)) // other graph.add(link: Link(from: 5, to: 6)) graph.add(link: Link(from: 5, to: 3)) graph.add(link: Link(from: 6, to: 1)) graph.add(link: Link(from: 7, to: 4)) graph.add(link: Link(from: 6, to: 2)) graph.add(link: Link(from: 9, to: 4)) graph.add(link: Link(from: 4, to: 5)) graph.add(link: Link(from: 2, to: 8)) // other graph.add(link:Link(from:1, to:2)) graph.add(link:Link(from:1, to:3)) graph.add(link:Link(from:1, to:4)) graph.add(link:Link(from:1, to:5)) graph.add(link:Link(from:2, to:6)) graph.add(link:Link(from:2, to:7)) graph.add(link:Link(from:3, to:8)) graph.add(link:Link(from:4, to:8)) graph.add(link:Link(from:5, to:8)) graph.add(link:Link(from:7, to:9)) graph.add(link:Link(from:7, to:10)) graph.add(link:Link(from:7, to:11)) graph.add(link:Link(from:8, to:9)) // other graph.add(link:Link(from:1, to:2)) graph.add(link:Link(from:2, to:3)) graph.add(link:Link(from:2, to:4)) graph.add(link:Link(from:3, to:4)) graph.add(link:Link(from:4, to:5))
[/details]

all of this pass and a don’t know why… I tried in php and swift… thanks !

I, like many of you am having trouble with More Complex Hierarchy, but I think I may have found the problem with my algorithm even though I haven’t gotten the solution yet. Consider the following two sets of influencer,influenced pairs:

SET 1
1,2
2,3
2,4
3,4
4,5

SET 2
1,2
2,3
2,4
4,3
3,5

They might look different, but if you draw both of the graphs out with nodes represented as circles with the node label inside of them and the one-way connections from influencer to influenced represented as arrows, you can see that the two sets of data describe IDENTICAL graphs. The only difference between them is which node has the label “3” and which node has the label “4”. In terms of the nodes themselves and what’s connected to what, they’re topographically the same.

I found that my algorithm treats the two differently in that the order in which it visits the nodes matters and it was only able to try one path from node 2. Basically, with one way of labeling the 3 and 4 nodes, my algorithm would return the proper answer, but if you flipped the labels, it wouldn’t ever consider the longer path.

It’s almost certain that’s the problem with my code and maybe this will give some of you guys the insight to what might be wrong with your code. If you’re having problems with the complex hierarchy test, does your code treat the two datasets above equally?

5 Likes

Revamped my algorithm and what I mentioned above was EXACTLY what was wrong.

I’m disappointed that the calls for an extra test case or two went unanswered. Based on the latest post, I’ll try completely revamping my algorithm and see what I can do. It is frustrating that the “more complex case” is the only one giving me trouble and there is no indication of what that trouble might be. An extra test case that demonstrates this “complexity” would be greatly appreciated.

2 Likes

I also had a problem with the “More complex hierarchy” test case. After I solved the puzzle in a different way my solution passes 100% of test cases. It is possible that my first solution is incorrect but I think the problem was in low performance. (I use JavaScript)

Thanks for taking the time to post this reply (even though it was a few years ago now). It was a great help and forced me to rethink my algorithm. Having said that, it should not be up to fellow codingamers to point out things like this.

My passing algorithm treats both of those sets identically (depth = 5).

This is what helped me get the correct algorithm.

One of my other issues was confusing depth first SEARCHING with depth first TRAVERSAL. My code was a fair bit cleaner with the traversal (though it could stand some optimization).

1 Like

here another test for those who fail “More complex hierarchy”.
8
1 2
2 3
3 4
5 3
9 8
8 7
7 5
5 6
you must find 6.

Hi everyone !
Can you give me others tests, because i can t solve the 8th test, and i have already tried of your test.
it s so frustrating ! All my test passed and i can t understand why the 8th didn t pass …

1 Like

I have the same issue. The code works fine for all the testcases except the 8th in submit. It also returns the correct value for the other testcases were posted in this discussion. It still can be the algorythm needs some optimization, but i dont see what. So its 90% submitted, but cant go on with the solution, cause i havent found any cases which it would fail. Or maybe its just a timeout?

EDIT: Just solved it, my solution is differs from the usual approach in the basics, so its hard to tell without details what i did wrong. I used python and a list of lists which stored the possible successions. My code passed when i optimized it to not to be redundant. I hope this is not a big hint, but still helps! Good luck!

I wondering why you are supposed to use depth first search in comparison to breath-first search?

For anyone who wants more samples…

The sponsored puzzle Teads has similar data input suitable for this quiz.
Here is their Test4:

191
171 26
187 151
118 176
53 52
129 33
34 86
13 1
186 46
30 62
78 25
177 146
96 101
155 71
126 69
152 127
154 64
13 190
134 4
70 41
106 180
144 17
105 37
181 163
65 89
101 34
187 90
16 177
34 106
152 59
117 189
85 2
62 9
12 93
163 102
158 191
70 98
30 36
36 167
154 67
4 50
121 39
125 111
18 178
117 169
96 42
47 38
62 28
123 94
123 153
132 105
39 115
116 154
44 54
36 100
96 7
15 120
33 0
132 158
181 184
84 181
25 63
62 83
109 125
138 107
55 73
116 13
23 137
147 103
183 23
72 132
75 57
182 79
40 14
116 138
109 77
55 56
156 40
42 183
18 160
70 157
71 113
121 70
136 142
57 92
77 60
125 108
33 122
158 170
84 129
155 136
159 84
12 179
165 91
136 3
177 130
183 15
66 150
47 27
15 8
7 134
181 126
129 117
7 116
118 12
182 35
158 139
63 124
72 156
4 145
84 30
39 140
48 123
47 162
176 45
53 61
187 58
109 188
36 21
48 152
30 20
159 72
85 149
65 31
5 55
156 85
177 175
20 161
188 148
57 19
77 110
40 74
118 187
163 112
101 16
176 166
152 164
7 121
43 48
63 109
106 11
125 22
188 143
34 18
188 114
23 10
75 186
184 32
171 51
165 172
16 171
124 147
43 75
66 135
5 53
126 185
25 43
176 141
71 24
66 68
105 173
42 155
129 47
15 131
124 44
85 97
71 29
138 49
78 159
121 182
126 80
75 144
147 88
134 165
144 87
186 6
42 5
86 133
72 118
44 95
16 66
184 128
40 174
184 119
156 65
12 81
136 82
144 76
186 168
86 99
78 96
20 104

According to my calculation the answer is 6 in the Giant Shoulder exercise.

Same issue still. PYTHON3 solved to 90%. Only the More complex hierarchy fails. Has anyone teased out what exactly this test is checking for?

I created an array of nodes and recursively walked the graphs checking for shorter walks to each node, while accounting for multiple roots and disconnected trees.


These were my test cases:

3, [[1, 2], [1, 3], [3, 4]]
8, [[1, 2], [1, 3], [3, 4], [2, 4], [2, 5], [10, 11], [10, 1], [10, 3]]
4, [[2, 3], [8, 9], [1, 2], [6, 3]]
4, [[1,2],[2,3],[1,3],[4,5]]


I would be open to more test cases that I can throw at my algorithm, if anyone can suggest some.

[Edit] OH! I didn’t see these bottom posts. Will try some of their data sets.

[Edit 2] OK! Passed. For the record, if you have this problem you could be over thinking it like I was. You are simply looking for the longest POSSIBLE path, not the longest path that has no other shorter variant. I chopped out a few logic gates and bingo!

1 Like

I get 6 but I fail More Complex Hierarchy still.

Yes, your 2nd test case found my problem. This should be added to the IDE tests. I removed the check for not revisiting a node as it looks like the check is not necessary here. The problem statement should say that cycles don’t exist so people don’t go crazy trying to figure out why one test doesn’t work.

It’s actually written in the statement:

Note: It takes time for a thought to influence others. So, we will suppose that it is not possible to have a mutual influence between people, i.e. If A influences B (even indirectly through other people), then B will not influence A (even indirectly). Also, you can not influence yourself.

2 Likes

Hinted by some past posts, I tweeked my code to find the longest distance to the farthest node instead of finding the shortest distances. Now I get 100%.
I would say, add some tests related to that! This is so confusing!