6 kyu
Skills Master
220 of 388el-f
Loading description...
Algorithms
Data Structures
Graph Theory
Trees
This comment has been reported as {{ abuseKindText }}.
Show
This comment has been hidden. You can view it now .
This comment can not be viewed.
- |
- Reply
- Edit
- View Solution
- Expand 1 Reply Expand {{ comments?.length }} replies
- Collapse
- Spoiler
- Remove
- Remove comment & replies
- Report
{{ fetchSolutionsError }}
-
-
Your rendered github-flavored markdown will appear here.
-
Label this discussion...
-
No Label
Keep the comment unlabeled if none of the below applies.
-
Issue
Use the issue label when reporting problems with the kata.
Be sure to explain the problem clearly and include the steps to reproduce. -
Suggestion
Use the suggestion label if you have feedback on how this kata can be improved.
-
Question
Use the question label if you have questions and/or need help solving the kata.
Don't forget to mention the language you're using, and mark as having spoiler if you include your solution.
-
No Label
- Cancel
Commenting is not allowed on this discussion
You cannot view this solution
There is no solution to show
Please sign in or sign up to leave a comment.
This comment has been hidden.
In python the default recursion limit is 1000. This kata has trees with sizes that will make your solution recurse much more than that ;)
Python, don't make me cry :(
This kata's description is art! You could print it and hang on a wall to remind you how beautiful a documentation could be.
suggested tag:
treesThis comment has been hidden.
Not a kata issue, it's just how python works. Default arguments are evaluated only ONCE, this means your set is always the same set in every invocation of the function.
Read more here. (notice the Important warning)
Thanks :)
I want to solve it, just so that I may marvel at the (probable) css magic in the description!
:)
This comment has been hidden.
Hi, your bug is in the
do - while, it will terminate whencurrentIndexis 0 instead of whencurrentIndexisundefined.Thanks for replying, literally the zeroes in fixed tests can occur in the beginning, auto generated ones misleaded me :D, as they put zeros in the middle.
Eventually worth adding a test with 0 at the beginning.
Java translation
I used the same random test bounds as Rust and tests run in 9-12 seconds (of 16 available, including 3 seconds compile/startup time)
very well written translation! approved :)
Rust translation
I've tuned tests to take roughly 8s to complete with my reference solution. The vast majority of that time is spent on the hardest test suite, obviously.
Approved, thanks!
The description should be edited to reflect the tuned size limit (300000). I'm not sure whether the edit should be Rust-specific or not
description updated, thanks.
Why is input
usizeand outputu32? It doesn't make sense. Either everything should beusizeor everythingu32.input is usize because we are mainly dealing with indices, and it makes things more convenient. As for the u32 output, I honestly can't remember what my reasoning was. Given that I can't remember, one might assume that it can't have been a good reason. However, I am also prone to bouts of amnesia, so perhaps there was a rationale for that decision. However, I can't come up with one on the spot. I therefore am forced to conclude that a usize output would do just as well. I will update the translation presently.
Updated. Output is now usize. Existing solutions may have been invalidated as a result.
u32is the smallest appropriate type, given the size limit in the description. This reasoning and choice seems fine to me.usizeis also fine.Tests (in Python, at least) seem too strict. I was surprised to see my solution run up against the limit. Checking a few other solutions, it appears mine isn't an outlier. I'd tone the tests down to allow for errant factors: if my solution had taken just 500ms longer (e.g. startup time, random test misfortune, what have you), it would have timed out, and my immediate response would be to assume my approach was faulty, which it isn't.
Hi, I ran your solution about 20 times with it averaging about 10s with the highest rt indeed being 11.5s, so it should consistently pass with about 1-2s to spare.
In any case, I reduced the average tests run time by about 300ms, so should be safer now :)
Scala translation
Performance tests are a bit conservative due to runner start up time being inconsistent, but should be approximately equivalent to Python in terms of what is allowed through (based off my testing at least)
approved, thanks!
This comment has been hidden.
The input type is an array. The array describes the tree as written in the kata's description.
This comment has been hidden.
This comment has been hidden.
"notification": see above
note: in the code I suggested, most max depths will be approximately the same in the different branches. Problem being, if you allow 0 as number of children, you will ended up at some point with several independant trees => require a more complex generation.
This comment has been hidden.
This comment has been hidden.
I updated the kata with your implementation + suggestions, thank you :)
(I forgot to mention it, but you could have included the titles for the describe blocks in the loop infos, so that you don't duplicate the blocks/calls either)
done.
Super cool kata!
It seems like the random tests allow for self-referential skills as well as multi-skill cycles. Are these intended to be included?
Skills that unlock themselves apart from 0 are not intentional, fixed. (although it doesn't affect the intended approach). Mutual dependencies are not strictly intentional, but I think they are fine to keep.
While not breaking a particular implementation, it seems like multi-skill cycles don't make sense given the description. Especially with the one parent rule, unless they include zero.
Neat task.