Codility Problema 4.a — FrogRiverOne
Solución de problemas de lógica computacional de la pagina https://app.codility.com/
Ingles
A small frog wants to get to the other side of a river. The frog is initially located on one bank of the river (position 0) and wants to get to the opposite bank (position X+1). Leaves fall from a tree onto the surface of the river.
You are given an array A consisting of N integers representing the falling leaves. A[K] represents the position where one leaf falls at time K, measured in seconds.
The goal is to find the earliest time when the frog can jump to the other side of the river. The frog can cross only when leaves appear at every position across the river from 1 to X (that is, we want to find the earliest moment when all the positions from 1 to X are covered by leaves). You may assume that the speed of the current in the river is negligibly small, i.e. the leaves do not change their positions once they fall in the river.
For example, you are given integer X = 5 and array A such that:
A[0] = 1 A[1] = 3 A[2] = 1 A[3] = 4 A[4] = 2 A[5] = 3 A[6] = 5 A[7] = 4In second 6, a leaf falls into position 5. This is the earliest time when leaves appear in every position across the river.
Write a function:
def solution(X, A)that, given a non-empty array A consisting of N integers and integer X, returns the earliest time when the frog can jump to the other side of the river.
If the frog is never able to jump to the other side of the river, the function should return −1.
For example, given X = 5 and array A such that:
A[0] = 1 A[1] = 3 A[2] = 1 A[3] = 4 A[4] = 2 A[5] = 3 A[6] = 5 A[7] = 4the function should return 6, as explained above.
Write an efficient algorithm for the following assumptions:
- N and X are integers within the range [1..100,000];
- each element of array A is an integer within the range [1..X].
Español
Una pequeña rana quiere llegar al otro lado de un río. La rana se encuentra inicialmente en una orilla del río (posición 0) y quiere llegar a la orilla opuesta (posición X + 1). Las hojas caen de un árbol a la superficie del río.
Se le da una matriz A que consta de N números enteros que representan las hojas que caen. A [K] representa la posición donde cae una hoja en el momento K, medida en segundos.
El objetivo es encontrar el momento más temprano en el que la rana puede saltar al otro lado del río. La rana solo puede cruzar cuando aparecen hojas en todas las posiciones del río desde 1 hasta X (es decir, queremos encontrar el momento más temprano en el que todas las posiciones desde 1 hasta X están cubiertas por hojas). Puede suponer que la velocidad de la corriente en el río es insignificante, es decir, las hojas no cambian de posición una vez que caen en el río.
Por ejemplo, se le da un entero X = 5 y una matriz A tal que:
A [0] = 1 A [1] = 3 A [2] = 1
A [3] = 4 A [4] = 2 A [5] = 3
A [6] = 5 A [7] = 4En el segundo 6, una hoja cae en la posición 5. Este es el momento más temprano en que aparecen hojas en todas las posiciones del río.
Escribe una función:
def solución (X, A)que, dada una matriz A no vacía que consta de N números enteros y un entero X, devuelve el momento más temprano en el que la rana puede saltar al otro lado del río.
Si la rana nunca puede saltar al otro lado del río, la función debería devolver -1.
Por ejemplo, dado X = 5 y una matriz A tal que:
A [0] = 1 A [1] = 3 A [2] = 1
A [3] = 4 A [4] = 2 A [5] = 3
A [6] = 5 A [7] = 4la función debería devolver 6, como se explicó anteriormente.
Escriba un algoritmo eficiente para las siguientes suposiciones:
- N y X son números enteros dentro del rango [ 1 .. 100.000 ];
- cada elemento de la matriz A es un número entero dentro del rango [ 1 .. X].
Entendiendo el problema
Lo mas complejo de este problema es el comprenderlo 😅, pase dos días en esta labor. Eso sumado al ejemplo con trampa del problema, me hizo codificar varias propuestas de solución pero ninguna correcta. Si tu lo hiciste, puedes confirmar lo que a mi me paso, solo cumplía el primer test, los demás, concluían mal.
El problema formula que dado una lista de valores y un valor a buscar, se debe devolver la posición donde cumple la siguiente condición:
- Los valores recorridos son todos los generados desde la unidad hasta el numero buscado. Si la lista no esta formada por todos estos valores, se devuelve -1, caso contrario, la posición en la lista correcta. Esto quiere decir, por ejemplo, que si se da un valor de búsqueda 7, para que la rana salte, se debe cumplir que ya hay hojas con valores [1,2,3,4,5,6,7] indistintamente de su orden o de valores repetidos.
El caso de ejemplo del problema plantea un caso con la trampa de que el valor que cumple esta condición, se encuentre en la posición 6, es decir (N+1), siendo N=5. Sin embargo, es una coincidencia, no es para todos los casos.
Existirán casos donde no se cumpla la condición, como el de la siguiente figura. Se tiene una lista con valores [1,3,1,4,2,3,1,4], con un valor de búsqueda A=5, en este caso no se cumple la condición para dar el salto. Esto arroja que la respuesta es -1. Es decir, la rana no puede saltar.
Entendiendo la Solución
Para la codificación se debe obligatoriamente, usar un iterador que recorra todas las posiciones de la lista de entrada. Mientras recorre la lista de entrada, se agrega los valores a un set() o conjunto. Este tipo de dato de Python, NO almacena datos repetidos, es decir, si tengo una lista con los valores [1,2,2,2,3,3,4,5], esta lista almacenada como un conjunto set() será (1,2,3,4,5).
En el contexto del problema, este tipo de dato permite evitar la validación de existencia de cada valor en el conjunto que se esta creando. Posterior a esto, se valida si el tamaño del conjunto creado con los valores de la lista de valores, es igual al valor A buscado. Si se cumple la condición de igualdad, se devolverá el valor del indice, donde se cumpla la condición. Caso contrario, se devuelve el valor -1.
Código de Solución — Python
El código fuente de este problema y otros mas (HackerRank, Codility):
