Frog jumping algorithm

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.

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.

StackExchange Code Review Q#85534, answer score: 4