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 &gt;= y
        position += d
        positions &lt;&lt; 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 &gt;= y
    x += d
    jumps += 1
  end
  jumps
end


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