5 kyu
Happy Numbers (performance edition)
106FArekkusu
Loading description...
Performance
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.
Really interesting mathematical kata to apply some dynamic programming techniques to.
nice kata, maybe a low 4kyu?
edit: oh wait nvm, https://www.codewars.com/kata/5ecef4a6640dbb0032bc176d
My Python solution is timing out and I'm trying to figure out how much time is calculating the happy numbers and how much is finding "elements less than n" but when I return a fixed result to make it faster, I get this exception:
File "tests.py", line 34, in it_1 test.assert_equals(act, exp, "Wrong result for {}".format(n)) NameError: name 'act' is not defined
Possibly the answer is "then don't do that" but exceptions aren't very user-friendly.
there was a bug in the tests. Should be ok, now (the feedback, I mean)
Thanks. My solution is failing properly now. But at least it's failing in 2.5ms, so that's a good start.
... and I finally got it to work. Awful, awful solution. Much to learn from the other methods.
Exceptional Kata!
Not that difficult but you really have to be efficient.
Thanks to the author!
wdym not that difficult... I spent a little too long on this kata (~6 hours, with breaks in between)
After optimization, my code takes less than 4.5 seconds for the random high value inputs (59090,114742,104721,194554,15314,293211,198561,118033,243374,138837,73094,33641,105638,281895,52600,193311,214239,66672,188339,221677,87299,127372,74204). I still see the error 'execution timeout 12000ms'. Is there something wrong with the tests?
I think we still have to make our code faster
When I test my code with your list, I'm ~ 1.5 seconds. And I still have the timeout.
and
is 9s/10s
but if I try 5_000 tests I must keep numbers < 12_000 in order to get < 12s
@FArekkusu :
Can you provide more info about the structure of the test set you use?
~1.5 sec is very impressive. You definitely should not get the timeout
Everything's in the description. What else do you need?
2 days, no more ideas.
Am I about to resign ?
Reading the discription I pretentiously thought I had a clear path to the solution. Then ...
I've tried to call the less possible sum_of_digit_sq with memories, sieves, and permutations - because 137 has the same happinest than713 -
many things but no result ...
5000 times 300_000 numbers to test = 1.5 billions of operations if only one operation per number.
%time for i in range(1_500_000_000) : i + 11min 54sClearly that's not the good way, have to make a U-turn to get out of the tunnel.
Obviously, all 300k numbers are not tested 5k times each.
Although, for some reason the reference solution "became slower" at some point. I made a quick fix to bring it back to ~4.9 sec, so at least your solution must not be faster to pass anymore.
This comment has been hidden.
Your program should remember what it has and has not done. That's all really ¯\_(ツ)_/¯
But I would also suggest you try your solution with different big inputs. You may be thinking that passing all 5000 tests is your main problem but it is also possible that your code is not efficient enough to compute
performant_numbers(N)whereN > 150,000.There really are three separate problems to handle
You can intentionally fail your tests at certain points and optimize these portions of your solution separately e.g. by using a single test case with an increasingly higher number or by adding a class variable which counts how many times a function has been called and start returning zeroes after that to fail the test. This way you will get much better feedback than 'oops, wrong'
This comment has been hidden.
Thank you. I checked it. For the number 50 my code needs 349 rounds in the loop and for no. 100 is 723 rounds. Pretty sure, i can make it better. But just to check no. 100 it is one round.
This comment has been hidden.
@dagro - my point was to use your tests to see how much work you can get done before timing out See how fast you can generate it for a number up to 300,000 and go from there :) My first successful attempt managed 8.5 seconds for that one number It took me the better part of 3 evenings to make everything happen in < 7s and I would not have believed it possible at first
This comment has been hidden.
This comment has been hidden.
This comment has been hidden.
Damn I have spent so much time on finishing this kata just to realize that my code runs over the time limit. The code is good, it can give back the happy numbers for any length, but it can't handle 30 000 tests in 6 seconds. ~ Just came here to cry because I suck. Will give it a try tomorrow ;)
We're still holding our breath :) Would be happy to help if you're stuck on something in particular.
I generate the happy numbers up to the test limits; I check the first 143 items against the list found on wikipedia (all correct); I also get the correct number of happy numbers under 10^5, 10^6 (checked against wikipedia); and I also checked my list against a list created withe the "naive method" (seems correct). But when I hit the random tests, I get some very uninformative results for all the tests:
"Value is not what was expected".I understand from the earlier discussions that you do some kind of comparison without
assert_equalsto speed things up, but once you hit an error, the test suite should stop and a proper error should be displayed. Also, gradually building up the test range would make debugging easier (e.g. first few tests up to n = 1000, then up to n = 10000, etc.)It's because passed tests are not printed, only failed tests are shown.
Yes, somehow
Test.expectis a couple times faster so it's used instead ofTest.assert_equals. Added the error message informing you whichncaused the problem.As of building up the test cases gradually - IMO it's unnecessary. If your solution is wrong - it won't pass the tests, whatever way they are implemented, and surely you can add your own sample tests using Wikipedia as a reference to see that your algorithm is actually working correctly. Moreover, I left a link to the not-performant version of the kata (which is available in JS only) so you can practice there first.
approved, and I went back to
assert_equalsin case a test is wrong so that the infos are available (@FArekkusu: the problem was not to use one or the other, but to use assertions at each tests)I had to realize (again) that handling/slicing large lists is slow, so one should use [a certain module] to do that :-)
This comment has been hidden.
republished with:
I realised we were cross-publishing when it prompted it about "you're gonna lose your progress if you close the tab". We ended up doing it again O_o
Well, thanks for the update.
I had made a mistkae in the anticheat check: just corrected it => please refresh the edit panel if you're in it. ;)
Nah, I'm not editing anything now. It's in a more or less ready state now, so I'll leave it until any issues/whatever start arising.
There's nothing about maximum code length in the description.
Because it was added after B4B's suggestion to prevent hard-coding the result.
new issue, sorry:
digging with a different approach, I faced the following:
This fork execute 4000 tests in 2,8s only while using the assertion code you use, it needs 11s average. That means that the assertion calls are actually the slowest part of your code. Take a look at the way I implemented the tests, to gain performances.
This comment has been hidden.
Replaced assertion. Added hard coing countermeasure (going to check it now but should be ok).
This comment has been hidden.
Errrr... I don't know what you just did, but you invalidated ALL the solutions (even yours, apparently) ;)
I have no idea what's happening and site is terribly laggy for me now so I hardly can do anything at all.
well, all is ok in the trainer... :o
Let me take a look in the edit panel...
Updated now. Both yours and mine solutions are valid.
When I said I'd take a look, that would have meant that you stop trying to republish, so that we avoid the crossed publications problems... .)
well, see my message at the top. If you still have the editor opened in a tab, please refresh it before any new publication.
needs fixed tests too in the test cases
Are you raising an issue just to raise an issue?
Fine, I've added one test (yes, seriously), even though this kata is clearly not about passing fixed ones.
firstly, it's good practice
secondly, it's REALLY annoying, when submitting a wrong code to get a completely useless feedback with thausends of values printed in the assertion message. So yes, you have to put fixed tests (you really should put all the sample tests at the beginning), to make the warrior at ease).
That is true. It's easy to forget when writing a kata that it's nice to have a baseline in the form of a few tests which always expect the same result to compare your results to every time :)
You're slow. You can push the things harder. ;)
That would be nice, but I don't want to copy-paste other solutions which are faster for the sake of making it harder and harder (and eventually making this kata passable only by tryhards like you). If I can optimize my code myself, that would be a different story...
This comment has been hidden.
This comment has been hidden.
This comment has been hidden.
well, you actually mean that precisely. The thing is: the author's solution use the same kind of algo than you used. So unless he finally agrees to upgrade the internal solution to increase the upper bound (the last fixed test should ask for this bound, to be sure that all solutions will generate all the numbers), your solution will still pass.
EDIT: I tried to push further FArekkusu's solution and mine: even generating up to 800000, the difference on the generation time is only around 0,5s (mine against mine: 7,5s / mine against his: 8,1s). That without the random tests. It could be hard to eliminate one approach franckly and be sure than the other will pass whatever the exact implementation is. It's surely possible to go further using other technics, but then, that won't be 5 kyu anymore, I guess.
This comment has been hidden.
wrong function name in the sample tests.
For some reason I didn't get any error about "sample tests being not passable" O_o