Problema:

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).

Este problema es mucho mas fácil, nos dice que hay una ranita que quiere ir de X a Y saltando una distancia D, cuando lo mire lo primero que hice fue hacerlo así:

Solución lenta O(Y-X):


def slow_solution(X, Y, D):
    jumps = 0
    for jump in xrange(X, Y, D): jumps += 1
    return jumps

Pero no paso la prueba de codility, me arrojo 100% de correctness y 0% de performance, esto paso por que al final del problema te dice que esta esperando una solución con O(1) y mi solución es O(Y-X) al estar haciendo una iteracion sobre el punto de inicio hasta el punto final, así que mejore mi código:

Solucion O(1) con importaciones:


from __future__ import division
import math
def fast_solution(X, Y, D):
    return int(math.ceil((Y-X) / D))

De esta manera obtuve 100% en performance y 100% de correctness, que era lo que estaba buscando, pero si se fijan estoy importando math y division para algo tan simple, pero como no tenia mucha experiencia en cuanto a como maneja Python las operaciones matemáticas como la división y demás, por ejemplo Python por default redondea hacia abajo y por eso uso math.ceil para redondear hacia arriba y si no importas división en el tope de tu archivo no toma en cuanto los decimales y te devuelve un objeto de tipo int.

Al final preferí hacer la solucion con if, else y mas lineas de código pero sin importar nada y conservando el performance, incluso es mas rapido:

Solución


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

Lo que hago es que primero checo si la división de la distancia total (Y-X) entre la distancia de los saltos de la ranita (D) es igual a 0 regreso (Y-X) // D y si no retorno lo mismo mas 1 esto por que las divisiones en Python como lo comentaba te retornan objetos de tipo int, por ejemplo 100 / 3 te retorna 33 no 33.333333.

Aquí esta el repo con todas mis soluciones de codility: https://github.com/OmarIbannez/codility-lessons

It's only fair to share...Share on Facebook10Tweet about this on TwitterShare on Google+0Share on LinkedIn0Share on Reddit0Pin on Pinterest0Email this to someone

One thought on “FrogJmp

  1. Octavio says:

    Podrías intentar esta solución? Algunos lenguajes tienen “redondeo hacia abajo” y otros “redondeo hacia cero”, que en los positivos es lo mismo pero en los negativos no.

    return -((X – Y) // D)

Leave a Reply

Your email address will not be published. Required fields are marked *

Comment moderation is enabled. Your comment may take some time to appear.