Draft
Stone pile
7 of 15oybek
Loading description...
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.
Can't submit my solution even though it passes all tests (test and attempt in JavaScript). I see congratulation and offering Submit when ready, but there is no Submit button.
You can't submit in a Draft.
Sorry, but this is duplicate of already approved katas, here are some: https://www.codewars.com/kata/586e6b54c66d18ff6c0015cd https://www.codewars.com/kata/587387d169b6fddc16000002
got it!
I'll modify this kata then
Both those duplicates are in Python and Swift only. That would mean this kata should be translations to one of the others ( probably part I ).
Also, in this case, I'd excuse the author ( and myself ) for not finding those duplicates before publishing.
The other kata does not have random tests in Python ( though it does in Swift ). As long as that doesn't get fixed, I don't think this one need be retired. Neither should approve translations the other one already has though. Except for Python with random tests on this one.
Also, this kata should have consistent performance requirements across languages.
Seems we not looking the same thing, I've just checked both of the linked katas, and both have random tests in python(though not written in usual style)
@oybek You may consider increasing the limit of
nto30-36. Then the standard DP approach will not work in this kata. My JavaScript solution can handlen <= 37with 100 random tests.JavaScript translation
Nice done and thank you for the translation.
In Javascript solution even more concise
This comment has been hidden.
This comment has been hidden.
ok, I'll try to implement it, or to refute this hypothesis
Agree with you - it cant be optimized in such a way
I think doing that could have netted you a Nobel Prize. ( Or an Abel. ) Pity. :]
This comment has been hidden.
I would have thought so. Apparently there is a faster solution at least for small ( enough ) stones in the pile ( which this problem might or might not have, depending on what is "small enough" ). That means the generalised problem would appear to be
O(length * sum), which is a lot better thanO(exp length).I suspect
@monadiusdid that solution, but I haven't figured out exactly what he did though.This comment has been hidden.
I was living with the notion that
O(length * sum)was equivalent toO(n^2), which it may not be. I know not all NP-hard ( or -complete ) problems are impossible to solve, but the finer points of NP-Hard, NP-complete and related terminology are lost on me.OK, so it's an impossible problem in theory but a solvable one in practice. Is that about right? You could not scale it up infinitely in all dimensions, is that the lithmus test?
Performance requirements seem to be inconsistent now. My old Scala solution times out, but a high level, unoptimized solution in Haskell passes.
Actually, I don't understand how your Haskell solution got through. It takes 10 seconds without random tests and times out consistently when I fork and run it. You may have hit the jackpot when you submitted it; random tests can be very random of course.
That's not to say consistent, clear performance requirements would not be a good thing. With
O(exp n), this is not a performance kata anyway. Might be best to tone it down a little across the board.( Can this problem be optimised anyway? Or is the way everyone does it the best you can do? )
This comment has been hidden.
A fork of your solution with the random tests disabled consistently takes ~10 seconds. Except when it occasionally takes 5. I have seen this behaviour before - it's almost as if there's one server in a farm that's twice as fast as the rest, but you rarely run on that one.
That might also account for making it through the random tests unreplicatably.
I tried about 10 more times and it passed 2 times, so it's close. It can't be better than
O(exp(n)), but it can be worse if identical subsets are summed multiple times; although when the whole thing is exponential,nis almost a constant factor, it may be noticeable.This comment has been hidden.
This comment has been hidden.
This comment has been hidden.
That may be what Monadius has submitted. Thanks!
Haskell translation
Wonderfull and clean translation - approved
( Scala )
Needs more than
1random test. Try100.ok)
Done - 100 random tests
Did you check the performance? Java and Haskell max out at 20 for this reason I think.
ETA: judging by invalidated kata, 22 may be a bit much if it's done more often.
Yes, ref solution is passing tests (no timeout)
Other solutions time out with the new tests. But there may be other problems that invalidate them as well.
You want solutions though. If only because only people who can solve the kata can upvote it. And it's reasonable to give them some wiggle room - forcing a single (micro)optimised solution on them does not make for a good experience either. If they have the correct algorithm, within reason they should pass. Unless you intend this to be a performance kata, which would warrant a tag and a description warning. But I think you don't, not with an expected
O(exp n).I have some problems with test case - "minDiff on random generated piles should be ok" Input:
List(979860, 858272, 854452, 698901, 687688, 684485, 493090, 306875, 292611, 290339, 266237, 82990)Output:
I think the problem is in the test because my result is correct
My result: first stone = 3232868, second stone = 3262932, and min diff number = 30064
Ainur try to run your solution on this test:
Correct answer is
0(List(5, 5),List(3, 3, 4))Your algo says:
2Issue is closed, read above comment
Java (at least):
Hided solution used in testing
Putted random test inside 25 times loop
Done
This comment has been hidden.
The "random" tests are't dynamically random. This can easily be done again: https://www.codewars.com/kata/reviews/5d4955d52447aa000178de9d/groups/5d496b4257245b000127267d
But they are hided
Even in case when I wrote random test, how can I check it's correctness without having correct answer? Do I have to use myown solution for this purpose?
def minDiff ... = 0and all expected results are shown. If there are no specific properties that can be used to verify results, then yes, you should compare results to the results returned by your solution.Done
CW showing some solutions as wrong, even when they are passing all tests
Yeah, that happens sometimes.
package com.example.✔️ Removed
package com.example.✔️ Added note about empty pile case
Random tests needed.
ok
Added random tests, which has broke lot of solutions)