Question: https://codility.com/demo/take-sample-test/ladder
Question Name: Ladder
To solve this question, there are two key points. Firstly, for a given N rungs, the number of different ways of climbing is the (N+1)th element in the Fibonacci numbers. Naturally, we could get the following answer. It works well. BUT the detected time complexity is O(L**2). What!!! How could it be?!
| def solution(A, B): limit = len(A) result = [0] * len(A) fib = [0] * (limit+2) fib[1] = 1 for i in xrange(2, limit + 2): fib[i] = fib[i - 1] + fib[i - 2] for i in xrange(limit): result[i] = fib[A[i]+1] % (1<<B[i]) return result |
So you need to know the second key to achieve 100/100 solution: how to do modulo computation in an optimized manner.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | def solution(A, B): limit = len(A) # The possible largest N rungs result = [0] * len(A) # The result for each query B = [(1<<item)-1 for item in B] # Pre-compute B for optimization # Compute the Fibonacci numbers for later use fib = [0] * (limit+2) fib[1] = 1 for i in xrange(2, limit + 2): fib[i] = fib[i - 1] + fib[i - 2] for i in xrange(limit): # To climb to A[i] rungs, you could either # come from A[i]-1 with an one-step jump # OR come from A[i]-2 with a two-step jump # So from A[i] rungs, the number of different ways of climbing # to the top of the ladder is the Fibonacci number at position # A[i] + 1 result[i] = fib[A[i]+1] & B[i] return result |
Yes, the detected time complexity is O(L) now.
UPDATE – 12/27/2014: thanks to @Martin. The old solution cannot pass the new test cases. We need to improve the performance again! In Python, the interger could be as large as the memory can hold. Therefore, we do not need to handle with the overflow issue. But at the same time, the big interger is kind of resource-consuming, for both time and space. To achieve a better performance, we need to avoid the big integers when we are computing the fib numbers. Actually, we do not need the full-bit fib number, because only some tailing bits are used in the final result.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | def solution(A, B): limit = max(A) # The possible largest N rungs result = [0] * len(A) # The result for each query modLimit = (1 << max(B)) - 1 # To avoid big interger in fibs # Compute the Fibonacci numbers for later use fib = [0] * (limit+2) fib[1] = 1 for i in xrange(2, limit + 2): fib[i] = (fib[i - 1] + fib[i - 2]) & modLimit for i in xrange(len(A)): # To climb to A[i] rungs, you could either # come from A[i]-1 with an one-step jump # OR come from A[i]-2 with a two-step jump # So from A[i] rungs, the number of different ways of climbing # to the top of the ladder is the Fibonacci number at position # A[i] + 1 result[i] = fib[A[i]+1] & ((1<<B[i])-1) return result |
what if A[i]=4 and B[i]=1? Then the way to cal modulo is wrong . But your solution can pass all the test cases. I’m confused about it.
Could you explain to me why whis case would not happen ?
Thanks!
Why is the way to calculate modulo wrong? If A[i]=4 and B[i]=1, we need the result as Fibonacci_number(4+1) % (2^1).
Got it.
I was wrong.
Thanks!
My pleasure to see my code helpful!
How to avoid O(L**2) complexity in java? I have no idea…
I know you write your code in Python, but maybe you have idea how to make it in java.
Here is my result:
https://codility.com/demo/results/demo833Q9X-4F7/
Do not use modulo operation. Use bit shift and bitwise AND operation instead.
Do not use LinkedList. Use Use normal array instead.
Then you should get 100/100.
Replacing ArrayList with normal array was enough, thanks a lot! 🙂
And for other, that’s my 100/100 in java:
https://codility.com/demo/results/demoR9XCB6-BQZ/
Thanks for sharing your Java solution!
If you want, I can put all my Java solutions, all 100/100. I’ve done lessons 1-7, 10-11. Just contact with me 🙂
Thanks for your willingness to share. I strongly recommend you to share them with GitHub. It is a free and widely used service. You could demo your skills and build your reputation there.
I’m surprised that it was enough. Does it mean that it’s easier to achieve enough performence in Java, compared with Python?
I do not think so. I believe, they have two different standards for the Python and Java.
Thanks! I had no idea that modulo with big numbers is so slow. In Ruby normal modulo was failing just in last performance test. So I’ve checked your blog, modified it and now it passess 100/100 and execution time is less than half then before.
Thanks for this tip!
btw. this is my Ruby solution: https://github.com/mrhead/codility/blob/master/ladder.rb
It is great to see my code be helpful! And thanks for sharing your solution!
I am not sure that this solution would work for C++. By problem formulation: the number of steps in ladder can be as much as 30000. So to calculate and keep Fibonacci numbers in array will not be possible as it is done in the example above (line:9-10). It will overflow long-long data type. I guess that the whole buzz about modulo operation. It offered in order to avoid this problem.Fortunately, it can be proved that recurrence Fn=Fn-1+Fn-2 works also under module transformation at any step. That can be used inside the loop to keep Fn manageable. However, since modulo 2^p can be different for any number in array A[i], we have to calculate several times and that increase complexity. We cannot create one static lookup Fibonacci array.
I am not sure about Python, but I have doubts that it can keep array of Fibonacci without overflowing up to 30000 elements? (the unknown to me test case bundle may not check that situation)
Awesome analysis! Actually you are right. We should do the modulo operation while computing the Fibonacci numbers in the line #8.
In Python, the range of intergers is unlimited, or say only limited by the memory size. So the Python code could pass the test.
This won’t work as values of A[i] are not ascending. In other words, you need either to store or map all of the used fibonacci numbers that you used, or to calculate them at each iteration.
However, there is a way to optimize your algorithm.
I’ve done it with java.
The idea is to calculate only the needed fibonacci numbers, and map them.
You are calculating fibonacci numbers for all the range (for all the possible values of fibonacci until the LIMIT or the size of A), while in reality, you only need that number of values in the worst cast scenario (that they exist in the input).
in other words: the size of array A, could be 30000. but values could be of the range [1,10]. In your code, to solve the problem, you are calculating fibonacci numbers for 30000.
Now for the C++ version, a dynamic array could be allocated, or a linked list, of a custom class, where long long ( or 2 integers ) can be used (why not?) (in this case, functions for adding should be implemented to cover the overflow) (or covering only the first 8 bits of the integer is sufficient) Notice that B[i] is of the range: [1,30], this means that the problem by definition, and Sheng’s solution needs a representation on no more than 30 bits (less than an integer). It can be easily proven that the upper part of the long long is not needed and we only need to AND the lower part with the B calculation that Sheng suggested.
Another suggestion for C++ is to do binary sum.
something like: (a+b) & 255
I know that there isn’t much difference between O(N) and O(3N) but I think O(N) that I have is still better than O(3N) above.
However, here’s my 100/100 solution in java
https://codility.com/demo/results/demoKQUD46-C5W/
First of all, thank you for the awesome discussion.
I did use the cache to store all the value of fib, in fib = [0] * (limit+2). It stores all the value from fib(0) to the up bound (fib(L+1)). Therefore, I do not need to consider whether A[i] is or is not ascending.
Finally, I did used the bitwise operation in my final solution.
Hallo Sheng,
I haven’t solved this problem before, so it might have changed it’s description in the meantime. But your solution no longer works.
https://codility.com/demo/results/demo6YYRQB-BRJ/
The issue is, that you compute your fib sequence up to the len(A) insted of max(A)
http://www.martinkysel.com/codility-ladder-solution/ -> https://codility.com/demo/results/demo5GEKAR-CPS/
Long time no see btw 😉
Nice to see you again!
I cannot remember the previous description neither. Thanks for your reminder! And I will update the solution.
BTW, in the new solution, both len(A) and max(A) works well. But max(A) is better.
Hello, Sorry i might be asking very naive question. But i didn’t understand the logic that one could ascend to Nth rung by Fibonacci(N+1) ways.
I could notice it by examples but i don’t exactly understand the logic.
Could someone please help me understand the same.
Let the f(x) be the number of different ways to achieve the step x.
To achieve step x, you could
either jump from x – 1 by one rung
or jump from x – 2 by two rungs
Therefore f(x) = f(x – 1) + f(x – 2).
I used almost the same method as your first solution except declare an empty list instead of a fixed size list ( i.e. result = [] instead of result = [0] * len(A) ). It got 100/100 score and the time complexity is O(L).
Probably the huge size of array declaration leads to timeout I guess.
Also in Python? IMO, allocation memory in batch, like [0] * len(A), should be more efficient than dynamically increasing it.
Hi, I hope this is still working….I’m trying to understand what the ladder problem is asking…I don’t understand basically what I have to return..I see the example and according what I think module is it doesn’t make any sense…I guess it is because I wrong about what a module is…but according to the first post, I read this ” If A[i]=4 and B[i]=1, we need the result as Fibonacci_number(4+1) % (2^1)” It’s what I understand that the problem is asking and for me module(%) is for example is a divide 3 by 2 I get 1,5 the module for me is 5….well knowing that the vector example that is returned in the ladder example doesn’t match with this definition….I use C++ and % is module and It’s what I believe you suggested but I must have not understood anything……thanks!!!
Yes, you misundertood the module operation. Please refer to Wikipedia: https://en.wikipedia.org/wiki/Modulo_operation
I didn’t expect there were these much discussion for this one. Is it all about the reminder of Fibonacci numbers that is sufficient to meet the need of possible 2 to the power of N (N<=30)?
In order to meet O(L) time complexity, each calculation must be finished in O(1), which will require some memorization up front. However, it's not possible to calculate Fibonacci(30000) without the help of some BigInteger implementation. Luckily, Codility only asks the reminder of some 2^N. So, we only need to store the reminder of any Fibonacci using 2^L as the divisor. This will make sure we have all bits necessary to do any modulo of 2^p, given p in vector B.
Hi, found the solution in ruby 100/100
Thanks!
Would it be better to calculate the Fibonacci numbers using the formula in a lambda?
fib = lambda x: int(( pow((1+sqrt(5))/2,x) – pow((1-sqrt(5))/2,x))/sqrt(5))
Strangely, it doesn’t. I am not sure why though.
I did not check the reason to fail. However, it does not improve the performance in any way, because we need all the numbers from fib(1) to fib(N).
My C++ 100/100 solution:
My 100% C++ solution