4 kyu
Big Big Big Padovan Number
170 of 575Valek
Loading description...
Performance
Algorithms
Big Integers
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.
Should probably switch to returning answers mod
1e9+7or similar. Poor design when most of the runtime is taken up by bigint maths that the user has no control over.For example, we converted our Scala translation to use
Longs instead and it can handle the performance tests in 5ms rather than 4000ms.Scala translation
Approved
Python new test framework required.
Fixed, module forbidder also updated.
Did you ban
sys? It's needed for large ints in Python.In what way is it needed? No solutions were invalidated and it was already banned before.
Also,
sysbeing banned is just part of the module forbidder in order to give it some chance of working.In particular I don't think you can solve the problem without a call to this:
sys.set_int_max_str_digits()Well when we consider that 200 people have, it would appear to be completely unncessary. We can't even work out how on earth using that would help tbh.
Yes you're right. I just get this error when I print the larger int values. I guess the ints get converted to strings first, and there's a limit on string lengths.
"ValueError: Exceeds the limit (4300) for integer string conversion; use sys.set_int_max_str_digits() to increase the limit"inttostrconversion in Python is comedically slow, I doubt the runner could even stringify the really fuckhuge numbers we get here in time to show them to you. Even if it can you still have the 1.5MB reporter buffer limit to deal with (I'm pretty sure the largest inputs don't even fit within it).Haskell and JS:
Fixed.
The Python test bounds were also a lie, it only ever went up to
1_000_000.is the use of gmpy2 banned or is my code just trippin?
Yes.
I find that my solution gives the following error message on Big Random Tests:- ValueError: Exceeds the limit (4300) for integer string conversion
For example, this happens with n = 878173. When I test this on my computer it returns a value which has a length of 107246. I don't have a string conversion in my solution so must assume that it is something in your test harness.
Chris
See above, this occurs when you print the integer value.
i thought memoized function would handle that ,but nah dictionary has a limit.
What is the maximum value for the test cases?
This comment has been hidden.
Was happy to find a working solution without any mathematical web search(using binomial coefficients), but it was far too slow, even after a lot of optimalization. After losing a lot of time, tried a few different algorithms only to find out, that none of them was fast enough. After even more search, found out what you ment by "use matrices", it should me more that a hint, you are very unlikely to find a different solution that does not time out. Which is very unsatisfying, since the problem could be solved in numerous interesting ways(not to mention ways you can come up with on your own, without reading pdfs), would it not include such huge numbers.
i wrote an O(n) solutions that saves the results in a global array so the the loop to find the next value starts from the last item in the array if it's not already in it. this algorithm only passes around 6 tests since the numbers are lines and lines of digits. any suggestions?
There is an algorithm better than linear. Do some more research, and see if mysterious hint at the end of the description is any helpful.
This comment has been hidden.
python: it's not said in the description that numpy is forbidden...
.
I've just noticed, that there is a mentioning in the "Task" section, so I've removed the line I just added.
@dolamroth: could you check on gitter, plz?
damn... Tho, I looked several time... :/
Hint: use matrices !!!!!!!
Anyone solved using ArrayList. When I am attempting, I am getting timeout at the last number. I have used BigInteger arrayList. ** Update ** I am able to solve the issue by changing the type and the attempt is successful. But when I am not able to submit after successfult attempt, getting time out error.
Niether of those method should work, I'm not closing this issue because I can see that your solution passes the test(which it shouldn't)
Thanks @XRFXLP. When I get some time, I will solve it without collection.
Interesting kata, but if this is 4 kyu, then Ulam Sequence (https://www.codewars.com/kata/5ac94db76bde60383d000038/python), which is much tougher, should be 4 kyu as well... :D
This kata was made back in 2016, and ranking rules were less strict then, AFAIK.
no, the problem is rather the python version itself, I believe (or not? dunno., I still didn't solve that one)
Wow, nice kata. Until now, I didn't know you could do that, and I suspect the strategies this unlocked will help to solve future challenges...
JavaScript translation
Haskell translation
like others I have problem with the last test case returning a stupid long number even when I only return 3944199426501073095 as BigInteger it fails that one
Padovan(1e6)is supposed to be a stupidly long number. The test is correct. Closing.This comment has been hidden.
Hello, I am having a problem with the actual test (performanceTest). I printed the value of my result in long ang BigInteger and they are correct but in actual test it returns a really long value. I even added a test in sample test that is exactly the same as the performanceTest and it was correct.
Same problem here. Printing the BigInteger shows that it is correct, but in the test says it is "19144941180031972349406008842018105306659865381...".
The test is correct, the solution for 1.000.000 is way to big to for a string. the test compares two BigInteger.
I don't get why my very first and simpliest approach is not working. It fails at 1.000.000 final test. If i put 1.000.000 on sample test by my own, it pass the test, but not yours. --> assertEquals(new BigInteger("3944199426501073095"),Padovan.Get(1000000)) on sample pass the test, on yours i get an gooooogle number. I think i'm missing something important, but can't see it.
your number for padavon 1.000.000 is way to small. the number is too big for a string to handle.
The kata is awaiting moderator's approval. Could someone approve it, or propose further issues to be resolved?
P.S. Same for Python translation.
Kata bump "Beta Status:Testing & feedback needed" Python translation bump
What does that mean? Solve more?
Message for admins/moderators to approve the kata, if it doesn't have issues.
P.S. "bump" is "bring up my post"
It is not approvable, it still says Testing & feedback needed. It will say Awaiting moderator approval when it's ready for approval.
I guess, only administrators are able to change it.
No, you can't change the beta status. It obviously needs more testing, feedback, solves, and upvotes.
Finally, it is "Awaiting moderator approval"
Python translation https://www.codewars.com/kumite/5d7b4ca6f204c100113c5086?sel=5d7b4ca6f204c100113c5086
I could post a Python translation, but is it viable, if kata is in beta since 2016?
if you post a python version it would need to be consistent with the original language, meaning you'd have a lot of things to forbid (namely, all science related modules).
Could you take a look and approve, if everything is OK, please?
https://www.codewars.com/kumite/5d7b4ca6f204c100113c5086?sel=5d7b4ca6f204c100113c5086
I didn't solve it so I cannot, sorry (I know the principle of how it must be solved, but I don't know how to actually find the proper implementation).
Ok. One more question: is it possible, that someone except the author resolves the issue, to get the kata published? I cannot do that, since I don't have enough honor yet.
A PU with enough honor can, yes. But it would need to update the kata.
btw: you didn't use numpy or something like that, in your translation? Because if you did, the translation isn't matching the initial version.
I didn't use any libraries.
:+1: then you "just" need to forbid them.
if you already solved one of those, open a fork and look at the preloaded part:
Looks difficult... Is it not enough to just set
sys.meta_pathto[]?Copied everything into preloaders, seems to work fine.
na wait, you need to update the tuple (at the end) with the names of the modules you wanna forbid!
@dolamrothDue to a bug, to get it into "awaiting moderator approval" status, you have to reapply your vote... I should probably learn some Java before approving any Java kata tho :yum:@Blind4Basics, ready. I thought initially, that this code blocks all imports except for random :)
@Steffan153, what do I need to do, again?
By the way, this was my first Java program.
Reapply your satisfication rating.
Ready (changed "very liked" to "somewhat liked").
For some reason it's still not approvable. I wouldn't approve it anyways tho, as I don't know Java.
To compensate for that, I have made a distinct kata. Please, take a look: https://www.codewars.com/kata/5d7bb3eda58b36000fcc0bbb
I looked up all the 1-3 kyu tasks in codewars, and have not found something similar.
I bet you just did a duplicate ;) (we already have tones of that kind of stuff and variations)
At least, it would be a duplicate with alive (yet) author :)
Could anyone translate this kata to Python, please?
There are no test assertions in the sample tests.
Fixed
Lower case is usually used for methods, even static ones. I recommend replacing
Getwithget. Otherwise a nice kata. Just waiting for the server to come back so I can submit my answer.Lower case is usually used for methods, even static ones. I recommend replacing
Getwithget. Otherwise a nice kata. Just waiting for the server to come back so I can submit my answer.Interesting kata... it would be nice to have a few tests in the example test box, though.
By the way, really enjoyed this one :-)
Moved into a issue
This comment has been hidden.
Its not the same task. Try to find 1,000,000-th number, if it takes more than 1-2 sec your solution won't pass.
Thanks
Just checked your solution, it will work :) I'm wonderig if you are able to fork it or add translation and I can approve it
Thanks
How do I go about that? (I am very new to this platform.)
Try to find "+ add new" in the language combobox
Can you try this link https://www.codewars.com/kata/big-big-big-padovan-number/translations
The page at that link says "We are unable to show you any translations at this time. You must first complete the kata." And there is no "add new" in the lang box either.
Can I use your solution as haskell solution?
Sure!