Frog jumping algorithm

Question

I took a test on Codility for coding the minimum number of frog jumps to reach from position x to position y:

A small frog wants to get to the other side of the road. The frog is currently located at position X and wants to get to a position greater than or equal to Y. The small frog always jumps a fixed distance, D. Count the minimal number of jumps that the small frog must perform to reach its target.

Write a function: def solution(x, y, d) that, given three integers X, Y and D, returns the minimal number of jumps from position X to a position equal to or greater than Y.

For example, given:
X = 10
Y = 85
D = 30

the function should return 3, because the frog will be positioned as follows:

after the first jump, at position 10 + 30 = 40

after the second jump, at position 10 + 30 + 30 = 70

after the third jump, at position 10 + 30 + 30 + 30 = 100 Assume that:

X, Y and D are integers within the range [1..1,000,000,000];

X ≤ Y.

Complexity: expected worst-case time complexity is O(1);

expected worst-case space complexity is O(1).

Here is my solution:

def solution(x, y, d)
    position = x
    positions = []
    until position >= y
        position += d
        positions << position
    end
    return positions.length

end

This solution works, but got a performance score of 0% and a correctness score of 100%.

My solution works on smaller data sets, but always times out on larger data sets.

Answer 1

It's a math problem more than a programming problem.

The distance to cover is \$y - x\$, so we divide that with our "speed", d, and round up to get the number of jumps. No loops or anything, just arithmetic.

The only trick is that if d is an integer, our division will be imprecise, since \$\frac{85-10}{30} = 2.5\$ but the decimal gets dropped by everything being treated as integers.

So we can either make d a float using to_f, or we can use fdiv to force a more precise, floating point division.

Using the latter, you get:

def solution(x, y, d)
  (y - x).fdiv(d).ceil
end

The return can be skipped, since this is Ruby.

Using to_f you could do:

def solution(x, y, d)
  jumps = (y - x) / d.to_f
  jumps.ceil
end

Finally, as Caridorc points out, renaming the arguments could make this even clearer

def solution(start, goal, jump_distance)
  (goal - start).fdiv(jump_distance).ceil
end

---

The above is the more correct solution (again, it's a math problem), but if we pretend that we do need a loop, you don't need the array for anything. Instead you could just do:

def solution(x, y, d)
  jumps = 0
  until x >= y
    x += d
    jumps += 1
  end
  jumps
end

Again, not the right solution for the problem, but a better one than using an array.

Answer 2

• Use longer names (you are not forced to use the one letter names they say)
• Repeated subtraction is division, you may express it with the symbol /

:

def solution(start_position, end_position, jump_distance)
    delta_space = end_position - start_position
    return (delta_space.to_f / jump_distance).ceil
end

Answer 3

Flambino's answer is great. I will add another way to solve this; although, as Flambino points out, it is a math problem and loops aren't needed. That said, you can use an Enumerator.

def jumps_needed(location:, destination:, jump_distance:)
  location.step(destination, jump_distance).size
end

The step method returns an Enumerator object, which responds to the size method. The enumerator's size is the number of jumps (or loop iterations) that the frog needs to reach its destination.

step can take up to two arguments; the first is the goal, or the value needed for the enumerator to terminate, and the second is the value by which to increment the goal.