Solution to Fib-Frog by codility

11 Mar

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)).

21 Replies to “Solution to Fib-Frog by codility

    • 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.

  1. Mine sollution:

    • optimize and simplify Damian’s solution:

  2. 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 🙂

  3. 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].

  4. my PHP-version with 100%

  5. 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%

  6. My solution, very clean, well explained, and scores 100% on Codility.

  7. 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

Leave a Reply

Your email address will not be published. Required fields are marked *

Please put your code into a <pre>YOUR CODE</pre> section. Thanks and Happy Coding!