Question: https://codility.com/demo/take-sample-test/fib_frog
Question Name: Fib-Frog or FibFrog
To solve this question, we are using the Breadth First Search with pruning. For a game with N intermediate nodes, the count of Fibonacci numbers, to say CF, is proportional to log(N) [Wikipedia]. And with our pruning, for each node, there are CF attempts to jump. So the total number of overall attempts is proportional to N*CF = N*log(N). That is, the worst-case time complexity is O(N*log(N)).
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 | def fibonacciDynamic(n): # Generate and return all the Fibonacci numbers, # less than or equal to n, in descending order. # n must be larger than or equal to one. fib = [0] * (n + 2) fib[1] = 1 for i in xrange(2, n + 2): fib[i] = fib[i - 1] + fib[i - 2] if fib[i] > n: return fib[i-1: 1: -1] elif fib[i] == n: return fib[i: 1: -1] def solution(A): class Status(object): # Object to store the status of attempts __slots__ = ('position', 'moves') def __init__(self, pos, moves): self.position = pos self.moves = moves return lenA = len(A) # Array length fibonacci = fibonacciDynamic(lenA+1) # Fibonacci numbers statusQueue = [Status(-1,0)] # Initially we are at position # -1 with 0 move. nextTry = 0 # We are not going to delete the tried attemp. # So we need a pointer to the next attemp. accessed = [False] * len(A) # Were we in this position before? while True: if nextTry == len(statusQueue): # There is no unprocessed attemp. And we did not # find any path yet. So no path exists. return -1 # Obtain the next attemp's status currentStatus = statusQueue[nextTry] nextTry += 1 currentPos = currentStatus.position currentMoves = currentStatus.moves # Based upon the current attemp, we are trying any # possible move. for length in fibonacci: if currentPos + length == lenA: # Ohhh~ We are at the goal position! return currentMoves + 1 elif currentPos + length > lenA or A[currentPos + length] == 0 or accessed[currentPos + length]: # Three conditions are moving too far, no # leaf available for moving, and being here # before respectively. # PAY ATTENTION: we are using Breadth First # Search. If we were here before, the previous # attemp must achieved here with less or same # number of moves. With completely same future # path, current attemp will never have less # moves to goal than previous attemp. So it # could be pruned. continue # Enqueue for later attemp. statusQueue.append( Status(currentPos + length, currentMoves+1)) accessed[currentPos + length] = True |
Very nice! I used the same idea and wrote the Java solution that got 100% on Codility. Here it is
https://gist.github.com/jianlica/9579661
Thanks for sharing your solution!
Nice idea! Isn’t that using O(nlogn) memory in worst case? I used a solution using dynamic programming, computing minimal number of steps required to get to position K. The Fibonacci calculation is a bit ugly though:-). Posted here:
https://gist.github.com/bbekier/9782904
I think the memory is O(n). Because each position is marked as “accessed” for one and only one time, the statusQueue is of size O(n).
Actually the number of Fibonacci, less than 100,000 here, is constant. So the time is also O(n), if we pre-compute these Fibonacci numbers.
You could also spare the extra memory for the access and instead just set the corresponding element of A to 0.
Mine sollution:
Fixed the typo according to your comments. Thanks!!!
optimize and simplify Damian’s solution:
First, congrats to the new looking of your blog! Haven’t been here for couple weeks!
Again, here is my dummy code. Codility is cheating! We are not supposed to enter the world of DP yet! There is one more tutorial to go… 🙂
Ugly C++ solution with top-down DP recursively…
I am not sure why fibonacci sequence up to N is proportional to log(N), can you explain a bit more?
———————————
Here goes a cleaner version. Sorry for the mess in the previous comment…
bottom-up DP.
Thanks and welcome back!!!
For the fibonacci sequence, up to N, there are at most log(N) fibonacci numbers, which is a math question.
PS: I merged your comments 🙂
Looks much better! Thank you for fixing the indents!
in terms of O(logN), my math is bad. It’s not intuitive to me, for the case of 1e6, both 10 based log and e based ln doesn’t come close to 31…Maybe this is just a bad example…
What’s 31 here? Probably it is 2-based.
There are 31 Fibonacci numbers in range of [0,1000000].
Big O, such as O(logN) is used to measure the order of complexity, rather than the exact cost (here the exact number of Fibonacci numbers).
Hi, I’ve got 100% using Java and DP approach. Sorry for not commenting the code.
I would really love to get in touch with you regarding this solution. As you say it gets “Perfect Score” when submitted to Codility. I would like to understand how it works and especially why it isn’t necessary to calculate the Fib numbers as every other solution seems to be doing. My email is [email protected].
my PHP-version with 100%
Hmm seems like this solution no longer works and only achieves a 58% on codility due to timeouts. However, it did help me visualize how to solve the problem, so thank you for that!
Update: Disregard! Had a typo in my version of it. Still achieves 100%
To Err Is Human 🙂
My solution, very clean, well explained, and scores 100% on Codility.
This is my 100% soluction in C++:
https://app.codility.com/demo/results/trainingX4MTMT-MCS/
The code is pretty similar to yours. BFS but I used a queue