6 kyu
Fibonacci Reloaded
1,004 of 2,298BattleRattle
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.
Quite criptic description imho :(
python new test framework + python 3.11v. updated in this fork
Approved
I literally just copied my inefficient af solution from this kata (https://www.codewars.com/kata/522551eee9abb932420004a0/python) and passed lol
This made me learned something about memoization, thanks!
And now i discovered the memoization with your comment
Pet peeve.
Ruby 3.0 should be enabled.
Description should use language specific blocks.
Enabled in this fork
Our fib() function must be faster!Where? It's normal fibo implementation...This comment has been hidden.
don't forget the spoiler! (I added it to your comment)
@rowcased it's not a spoiler. That algorithm isn't going to pass the test anyway. The purpose of the kata is to not write that kind of algorithm.
It is for another kata.
Python implementation is cool. Satisfied kata.
This kata still broken with wrong test after 3 years?
You didn't specify the language, but based on your profile I guess it's ruby. However, I see no issues with the ruby version.
I just checked on multiple sites how fibonacci works and all the test cases are wrong if I follow the fibonacci definition.
I know this is late, but the kata defines 0 as the 1st fibonnaci number.
Haskell : https://www.codewars.com/kumite/5b888df175b54687290000ae?sel=5b888df175b54687290000ae
Python version is broken (printing my result as a verification that the expected/actual are not swapped).
Fixed.
Bumped the Python and Ruby tests to 100 each and changed the fib range from 0-1000 to 1-100000 so there's at least a small performance requirement now and it's more of a 6kyu.
Please, read this and reverse you changes.
I'm aware of the recursion limit (it applies in Ruby and JS as well). But this is supposed to be at least somewhat of a performance kata as per the description, and a recursive function doesn't fit the bill here.
Could you check that all Python solutions were not invalidated? I believe the reference is broken somehow.
Bah, made a mistake copy/pasting and left the original solution in there by mistake. Give me a minute; you're right.
Idk what you were talking about but Python version doesn't require performant solution at all.
No, it doesn't, but the absolute slowest solutions don't pass anymore. This kata talked about "wanting things to be faster" and the slowest solution I could think of passed everything in about 10ms (Ruby too). Now it's at least not as awful; this was more of a stop-gap measure than a complete overhaul.
Then I see no difference between this kata and this (though the latter has rubbish test suite (and should be retired probably)), and it should be downranked.
I agree (although this kata predates that one by 2.5+ years), but that isn't possibnle at the moment afaik. This one's just irritated me for a long time so I wanted to :P
At least at the moment this is the only adequate fibonacci kata with normal test suite instead of 1-3 fixed tests.
If there was suppoesd to be a performance component to this, I don't think it was implemented..
Still broken.
Duplicate and incorrect kata. Please correct test for n = 0 and n > 80 (due to random inputs).
if not n: return 1and conversion to float are necessary for a solution to be correct.Random input tests still failing for Python.
This Kata is a duplicate of http://www.codewars.com/kata/memoized-fibonacci. Perhaps this one should be retired.
The python test checks for
fib(0)and expects 1 as an answer. I find it hard to calculate the 0th element of a list...fixed
Still having this erorr. Can the author please fix it?
Seems to be fixed
Yep I got this error as well
Same:
It should work for random inputs too: 1779979416004714189 should equal 1.7799794160047142e+18
Seems to be fixed
It looks like a bug in Python random tests:
Seems to be fixed
Hi BattleRattle,
I have just translated this kata into both Python and Ruby, if you want to approve them. I made this versions a bit more challenging as you don't have to worry (too much) about number precision.
On a side note, I could implement Binet's formula in Python, while even on Ruby I didn't get to work with the bigdecimal gem, so instead I opted to go for the memoized version; well, they both should work for good now, but feel free to ask me for any improvement you may wish :)
I agree with edalorzo. The Fibonacci's sequence is defined by next mathematical function: f(x -> x >= 2) = f(x-1) + f(x-2). For the 0 and 1 values, the Fibonacci's function results are the same values, 0 and 1.
Please, review this kata because I also think that it's a little wrong.
Thanks.
I won't change this kata anymore and I already explained, why:
An additional reason is that I don't want to invalidate all the solutions.
The fibonacci sequence is wrong in this Kata. The basis case should be fib(0) = 0 and fib(1) = 1. The test expects fib(1) to be 0. That's wrong.
it clearly states what is expected, if you want your code to return 0 for fib(n = 0) just start off with an n--....
Then this Kata is not about Fibonacci, is just a sequence of numbers.
The sequence is based on the rules of Fibonacci, but simply shifted by 1 position. And since this is mentioned in the description, I don't see the problem here.
It's still fibonacci. The sequence is exactly the same. The only thing that is different is the starting index.
judging by the solutions that have passed (wasn't expecting my first attempt to pass, but it did) this isn't really testing for speed, I don't know if you have the required tools to for instance test clock cycles used, but I feel like this should either be scrapped as a duplicate or improved to demand very high performance.
This looks like its a duplicate of this kata
I know the other kata, but that one only tests until the 25th Fibonacci number. My kata requires the algorithm to be faster in order to not end in an time-out.
Ah ok makes sense. I thought that might be it but its not clear in the description because of the examples given. Would be good to mention that high nth values will be used and that the real challenge is to beat the time-out.
FYI we are planning on increasing the sandbox timeout a bit to try to compensate for when the server is heavily loaded.
The performance test here isn't just testing high nth values, but testing the same high nth values multiple times, which require some sort of caching/memoization to pass.