Reconocimiento de recorridos correctos
Se usará la misma representación del ejercicio anterior para las subidas y bajadas en el autobús; es decir, una lista de pares donde los primeros elementos es el número de viajeros que suben y los segundo es el de los que bajan.
Un recorrido es correcto si en cada bajada tanto el número de viajeros que suben como los que bajan son positivos, el número de viajeros en el autobús no puede ser mayor que su capacidad y el número de viajeros que bajan no puede ser mayor que el número de viajeros en el autobús. Se supone que en la primera parada el autobús no tiene viajeros.
Definir la función
recorridoCorrecto :: Int -> [(Int,Int)] -> Bool
tal que (recorridoCorrecto n ps) se verifica si ps es un recorrido correcto en un autobús cuya capacidad es n. Por ejemplo,
recorridoCorrecto 20 [(3,0),(9,1),(4,10),(12,2),(6,1)] == True recorridoCorrecto 15 [(3,0),(9,1),(4,10),(12,2),(6,1)] == False recorridoCorrecto 15 [(3,2),(9,1),(4,10),(12,2),(6,1)] == False recorridoCorrecto 15 [(3,0),(2,7),(4,10),(12,2),(6,1)] == False
el segundo ejemplo es incorrecto porque en la última para se supera la capacidad del autobús; el tercero, porque en la primera para no hay viajeros en el autobús que se puedan bajar y el cuarto, porque en la 2ª parada el autobús tiene 3 viajeros por lo que es imposible que se bajen 7.
Soluciones
-- 1ª definición recorridoCorrecto1 :: Int -> [(Int,Int)] -> Bool recorridoCorrecto1 _ [] = True recorridoCorrecto1 n ps = aux 0 ps where aux _ [] = True aux k ((a,b):ps) = 0 <= a && a <= n - k + b && 0 <= b && b <= k && aux (k + a - b) ps -- 2ª definición -- ============= recorridoCorrecto2 :: Int -> [(Int,Int)] -> Bool recorridoCorrecto2 n ps = all (\k -> 0 <= k && k <= n) (viajeros ps) -- (viajeros ps) es el número de viajeros después de cada parada del -- recorrido ps. Por ejemplo, -- viajeros [(3,0),(9,1),(4,10),(12,2),(6,1)] == [0,3,11,5,15,20] -- viajeros [(3,0),(2,7),(4,10),(12,2),(6,1)] == [0,3,-2,-8,2,7] viajeros :: [(Int,Int)] -> [Int] viajeros ps = aux [0] ps where aux ns [] = reverse ns aux (n:ns) ((a,b):ps) = aux (n+a-b:n:ns) ps -- 3ª definición -- ============= recorridoCorrecto3 :: Int -> [(Int,Int)] -> Bool recorridoCorrecto3 n ps = all (\k -> 0 <= k && k <= n) (viajeros3 ps) -- (viajeros3 ps) es el número de viajeros después de cada parada del -- recorrido ps. Por ejemplo, -- viajeros3 [(3,0),(9,1),(4,10),(12,2),(6,1)] == [0,3,11,5,15,20] -- viajeros3 [(3,0),(2,7),(4,10),(12,2),(6,1)] == [0,3,-2,-8,2,7] viajeros3 :: [(Int,Int)] -> [Int] viajeros3 = scanl (\k (a,b) -> k+a-b) 0