Codility Fib Frog Java solution

FibFrog is the first exercise in lesson 13, Fibonacci numbers, in Codility. The aim is to get a frog to jump across the river. The river has leaves, the positions of which are defined in a given array. The frog can jump only on leaves and the length of the frogs jump must be a number that appears in the Fibonacci sequence.
This video shows my solution to FibFrog. It takes a bit of working out and my initial attempt, using a depth first search, does not work out. There is also quite a bit of optimising to do to make the algorithm efficient. The video is divided into chapters, so if you just want to see the solution, you can skip forward.
Eventually, I get 100% on Codility.
00:00 Start
00:17 Task Description.
04:01 Fibonacci sequence.
08:17 Attempt 1 Depth first recursive method.
32:13 Attempt 2 Breadth first method.
38:42 Optimisations.
43:46 Final explanation.
46:32 Final test.
50:29 Conclusion.

[@matejpodstrelenec3864]

As a first solution, I used depth search as well. Turned out to be very slow. Then I switched to breadth search, but still failed to reach 100 in performance.
After watching your video and doing the optimisations I am finally there!

[@javadave]

It wasn't an easy one.

[@seelawrie]

frogs and fibs 💚

[@cici6606]

How are you able to loop through each iteration one by one on Eclipse?

[@javadave]

Do you mean debug step by step? First you add a breakpoint on a line, then you run with the debug symbol (just to the left of the play button). Then you can press F6 to run step by step. It's worth having a read about this. Have a look at this... www.baeldung.com/eclipse-debugging . Its well worth your time.

[@cici6606]

@@javadave Aw wow, thanks very much! This is exactly what I meant. Never seen this being done before. Thanks for a fantastic video, this is a tricky one for sure ... hope I get to your level some day :)

[@cici6606]

@@javadaveJust curious, sorry I'm kinda a beginner with Codility. Lines 57 - 60. How would this work if we were able to make a jump at a higher Fibonacci number (say 5), this is added to newPositions (position+5).
But then because we're still in the for loop, the next lowest Fibonacci number is next. So we try a jump of 3. Say there also is a leaf at this position, so now both (position+5) and (position+3) are added to the newPositions array.
How does this work? Because if a jump can be made thats 5, I thought we would want to ignore any smaller jumps, as we are only looking at minimum jumps. So why do we keep iterating through the smaller Fibonacci numbers even when a jump has been found for that position? And adding any (position+fibonacciNumber) to the ArrayList, even after a higher jump value has been found? This is where I'm finding it difficult to follow 🤔
Hope my question makes sense, and thanks again for your brilliant videos

[@javadave]

@@cici6606 Lines 53-55 will return true if we can get to the target, so we won't go into the 57-60 loop. When we return true, the calling method know's we are done and returns the answer.

[@Matias001998]

This was a tough one

[@javadave]

Yes, I agree.

[@mechtarin]

I have been able to solve it in 1 hour debugging is an awesome thing but I wish we could see the other test cases

[@javadave]

Yes, its annoying when you get tripped up by some corner case that you didn't expect.

[@romawar1869]

Hi Dave !

[@javadave]

HI Roma, you are fast today!