4 kyu
Set Closure Generator
180 of 246ecolban
Loading description...
Streams
Algorithms
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.
Interesting kata, for those who doesn't now how to solve it my suggestion to solve after double-linear, and n-linear katas
JS translation
Approved.
Scala translation
A recent Haskell translation has modified the description. Make sure this translation is not undoing those changes.
It isn't, dw. It was just cleaner to do it the way I did (making the Haskell block the same as the Scala block).
Thanks. Approved!
.
Haskell translation
Thanks. Approved.
Input is not a set but a list. That list is not necessarily sorted and may contain duplicates.
This should very much be specified in the description.
I'd rather fit the tests to the description than the description to the tests.
approved by someone.
Description never specified the input is sorted, and it isn't in Python either.
Tests definitely should not generate duplicate entries though, Python explicitly generates sets (and then splats those sets into varargs which is a design choice of all time).
It would be acceptable if sorting remains unspecified; the description gives only sorted examples but at least there is an example test with an unsorted list.
The description explicitly specifies sets though, and those cannot contain duplicates. This must be addressed, one way or the other.
This comment has been hidden.
This comment has been hidden.
Ah, I guess that makes sense regarding re-forking.
Here's the updated Haskell translation
Approved.
I think you forked your original translation, and updated the description. You could have just forked the kata, and you would have had the current description automatically.
This comment has been hidden.
This comment has been hidden.
This comment has been hidden.
How attached are you to any Python-specificity of this, or would you be fine with us translating to other languages (specifically Scala and JS)?
Please go ahead and translate. The description may need to be updated. E.g., Scala could use a stream.
I would have Scala return either an Iterator or LazyList depending on what you think is better. I would suggest a
LazyListpersonally since it allows some fun and creative solutions.It's been a while since I dabbled in Scala. I see that, since then, Stream has been deprecated in favor of LazyList.
.
One last question -
Longs orBigInts?We went with BigInts because we didn't want to change the description too much.
JS doesn't have the stack for the Haskell solution ( I wrote it, it works, but it overflows the stack when used even slightly seriously ) or the datatype for the Python solution ( I didn't write it, but I could. Installed modules seem not to address this glaring gap in JS ).
:[
This comment has been hidden.
This comment has been hidden.
This comment has been hidden.
This comment has been hidden.
I didn't look at reference solutions; I went with top voted solutions. My bad.
MrOrnix' Haskell solution also does the 1e5 from 1e3 of 1e6 in 2 and a bit seconds ( I rewrote the monotonicity test ), but the problem is (a) JS has no memoising for generators, so recalculation, and (b) stack.
I just now had a look at the Scala and Python reference solutions, but I couldn't immediately make sense of them. I have no idea what these "candidates" are you speak of.
ETA: yeah, the Haskell reference solution is a hundred times slower. My solution also does 2.something seconds, the reference solution can do 1e3 instead of 1e5 elements.
Please use better variable names in test code guys ..
I forked a solution that did not import a heap and simplified the code quite a bit here (
dshould be namedmultipliers, and the input should have another name, but it's a lot better already ). I think I get the candidate thing now.I explain it in this comment.
That helps, thanks.
JS translation in progress here.
I think I have seen the monotonicity test fail twice, but I'm not sure that's not just cosmic radiation on ridiculous numbers. The code should be bulletproof ( famous last words .. ).
This comment has been hidden.
Also Johan, I can provide a refactored and annotated version of the Scala author solution if you'd like. Most of the bits that differ from how you'd do it in Haskell are just memoization tricks.
Is the pending JS translation in any way unsatisfactory? Or could it be approved?
Looks fine to us but we'll leave it to ecolban to approve.
This comment has been hidden.
Hey I have a question, forgive me if this sounds silly I'm very much a beginner to this. But if I generate the full closure of S, won't the code just keep running forever because it's an infinite set? Or is there something specific I'm supposed to do that I'm just not understanding yet?
Read up on generators here.
python new test frameworks
Thanks! Approved.
.
Quite challenging finding out the optimal solution to this kata, well done, congratulations.
See this
Thanks. Fixed.
.
care to add more tests with numbers that may generate the same values in different ways? (one of my earlier version failed only the monotinicity test because of that. Tho, now I see that this test is actually random, so... I post rather an issue than a suggestion)
->
closure_gen(2,5,6,15), for instance, would be a good addition to the fixed tests.Added the test you suggested. Please mark this issue as resolved if you are satisfied.
:+1:
(btw: there is a bit of work on your
Shallowest path across the river, but nothing to long to do. Iirc, once the issues are resolved, it's approvable. Would be cool that you take care of it, it's a good one. :) )Is it just me or is this test now missing from Python?
That seemed like a hard one. My basic problem was running out of time. Had to find a clever way to generate. Could you elaborate more on your (impressive) solution?
This comment has been hidden.