Codility Frog Jump solutions [closed]

Question

Problem details from Codility:

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.

Method 1:

def solution(X, Y, D):
    if (X == Y):
        jumps = 0
    elif Y-X % D == 0:
        jumps = (Y-X)/D
    else:
        jumps = ((Y-X)/D) + 1
    return jumps

Method 2:

def solution(X, Y, D):
    d = Y-X
    jumps=d/D
    rem=d%D
    if rem != 0:
        jumps+=1
    return jumps

I submitted the Method1 solution and received a 55% score. On the other hand, Method2 got 100%. It's not clear to me why Method2 is better than Method1. Could someone please explain?

Answer 1

Method 1 sometimes gives wrong solution because it has a bug:

def solution(X, Y, D):
    if (X == Y):
        jumps = 0
    elif Y-X % D == 0:
        jumps = (Y-X)/D
    else:
        jumps = ((Y-X)/D) + 1
    return jumps

In the elif there, Y-X should have been within brackets, because % has higher precedence than - operator. In other words, Y - X % D is not the same as (Y - X) % D.

Other than that, they are practically equivalent. I would clean up the formatting and remove some obvious temporary variables, like this:

def solution(X, Y, D):
    jumps = (Y - X) / D
    if (Y - X) % D > 0:
        return jumps + 1
    return jumps

In particular, in the if instead of incrementing with jumps += 1, I return the value immediately, because I prefer to avoid mutating variables in general.

Answer 2

janos' answer is good.

Let's me add a few simple independant comments on top of his solution :

• Unlike C or C++, Python's modulo operator (%) always return a number having the same sign as the denominator (divisor). Thus, as D is supposed to be positive, (Y - X) % D >= 0. Therefore, your check could be written if (Y - X) % D != 0 or in a more Pythonic way : if (Y - X) % D.

• Python has a pretty cool divmod function. It computes quotient and reminder which is exactly what you want here. Your function becomes :

  def solution(X, Y, D):
      q, r = divmod(Y-X, D)
      if r > 0:
          return q + 1
      return q
  

• You could avoid the repeted return jump by using the ternary operator : return jumps + (1 if (Y - X) % D > 0 else 0). Also, from the Python 3 doc and the Python 2 doc:

The two objects representing the values False and True are the only Boolean objects. The Boolean type is a subtype of plain integers, and Boolean values behave like the values 0 and 1, respectively, in almost all contexts, the exception being that when converted to a string, the strings "False" or "True" are returned, respectively.

thus, you can write this : return jumps + bool((Y - X) % D > 0).

By taking all comments into account, your code becomes :

def solution2(X, Y, D):
    q, r = divmod(Y-X, D)
    return q + bool(r)

It cannot really get any simpler, can it ?

---

It seems like I dove into the code before turning my brain on.

You can use math.ceil and everything will go fine :

import math
def solution2(X, Y, D):
    return math.ceil((Y-X)/float(D))

Note that I used a bit of a hack to have floating number division. In Python 3, this is the default behavior for division and you can have it easily with from __future__ import division.

Answer 3

Your first code block has a bug which was pointed out by @janos. The second block produces the right answers. But, there's an even better way to do this calculation, and it's a type of problem that is common in computer programming....

What is the least I need to do to cover a given range?

In this case, what you want to do is to calculate the range, you know the 'step', and you want to find out how many steps to take. The trick to a solution is to know the furthest you can step to, while still starting from in the range.

In this case, you need to 'hop' from X to Y in hops of size D. The range range is Y - X. The furthest you can hop while still being in the range is range - 1. The next hop from that furthest point in the range will be range - 1 + D. That's the furthest valid result. The end result for the number of hops is the 'integer' number of hops to the furthest point (integer division to the rescue - note that / means something different in Python 3.x vs. Python 2.x - // is floor (or integer) division now):

range = Y - X
furthest = (range - 1) + D
hops = furthest // D

This can simplify down to the answer:

def solution(X, Y, D):
    return ((Y - X) - 1 + D) // D