Codility Problema 3.a — Frog Jmp
Solución de problemas de lógica computacional de la pagina https://app.codility.com/
Count minimal number of jumps from position X to Y.
Ingles
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 = 30the 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
Write an efficient algorithm for the following assumptions:
- X, Y and D are integers within the range [1..1,000,000,000];
- X ≤ Y.
Español
Una pequeña rana quiere llegar al otro lado de la carretera. La rana se encuentra actualmente en la posición X y quiere llegar a una posición mayor o igual que Y. La rana pequeña siempre salta una distancia fija, D.
Cuente el número mínimo de saltos que debe realizar la pequeña rana para alcanzar su objetivo.
Escribe una función:
def solución (X, Y, D)que, dados tres enteros X, Y y D, devuelve el número mínimo de saltos desde la posición X a una posición igual o mayor que Y.
Por ejemplo, dado:
X = 10 Y = 85 D = 30la función debería devolver 3, porque la rana se posicionará de la siguiente manera:
- después del primer salto, en la posición 10 + 30 = 40
- después del segundo salto, en la posición 10 + 30 + 30 = 70
- después del tercer salto, en la posición 10 + 30 + 30 + 30 = 100
Escriba un algoritmo eficiente para las siguientes suposiciones:
- X, Y y D son números enteros dentro del rango [ 1 .. 1,000,000,000 ];
- X ≤ Y.
Entendiendo el problema
El problema de salto es un problema de optimización, tiene un punto de partida X y un punto de llegada Y, se condiciona a numero D de salto, para acercarse al punto de llegada. Si bien puede llegar exactamente en N pasos, puede haber casos de prueba donde pase el punto de llegada, y para tal debe darse la cantidad N de saltos suficientes y necesarios para llegar.
Siendo así, el ejemplo propuesto con X = 10, Y = 85, D = 30, forma una serie de números tales que para
N=1 Llegada: 10 + 30(1) = 40
N=2 Llegada: 10 + 30(2) = 70
N=3 Llegada: 10 + 30(3) = 100
En este caso, con N=3 se sobrepaso el punto de llegada, sin embargo, es el mínimo valor que cumple la condición. Proponiendo así la siguiente formula de cálculo, que debe ser optimizada para cantidad de [ 1 a 1,000,000,000 ].
Para N saltos, el punto de llegada sera:
Y_2=10+30(N)Entendiendo la solución
La solución en funcionalidad es sencilla, ya que con un sencillo bucle for, se encuentra el N apropiado que cumpla con las condiciones del problema. Sin embargo, los bucle for tienen un costo computacional alto, teniendo problemas de rendimiento cuando las cifras son grandes, y el iterador tiene que recorrer uno por uno los números hasta encontrar el N apropiado.
La segunda solución busca una optimización a este iterador, para esta solución se opta por un principio matemático. Para tal se busca la distancia (diferencia) del punto de partida y punto de llegada. Posterior a este cálculo se realiza una división exacta (operador //) entre la diferencia encontrada y el D salto dado. Esta división exacta devuelve la parte entera de una división.
Ejemplo de división exacta:
5//3=16//3=215//3=5
Si esta división tiene un modulo de 0, es decir, es una división sin parte decimal, el salto indicado es el resultado de la división exacto. Caso contrario, es la división exacta mas una unidad.
El código propuesto en la siguiente sección, contempla las dos soluciones, en la primera se cumple los objetivos de funcionalidad al 100%, sin embargo su performance es muy bajo, obteniéndose una calificación global del 68%. En el segundo caso, se cumple al 100% los objetivos de funcionalidad y performance.
Código de Solución — Python
El código fuente de este problema y otros mas (HackerRank, Codility):
