Menu Close

Reconocimiento de recorridos correctos

José A. Alonso,

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 (\(x,y) -> x >= 0 && y >= 0) 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 (\(x,y) -> x >= 0 && y >= 0) 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
Medio
, , , ,

16 soluciones de “Reconocimiento de recorridos correctos”

  1. Responder
    angruicam1 
    import Data.List (scanl’)
 
recorridoCorrecto :: Int -> [(Int,Int)] -> Bool
recorridoCorrecto n ((a,b):ps) = b == 0 && (all g $ scanl’ f a ps)
  where f :: Int -> (Int,Int) -> Int
        f a (c,d) | any (< 0) [a,c,d] = -1
                  | otherwise         = a + c - d
        g :: Int -> Bool
        g x = x >= 0 && x <= n
recorridoCorrecto _ _          = True
    • Responder
      angruicam1

      Realmente no nos importa el valor de a en la primera guarda de f, por tanto podemos mejorar la eficiencia de la siguiente forma:

      import Data.List (scanl')
 
recorridoCorrecto :: Int -> [(Int,Int)] -> Bool
recorridoCorrecto n ((a,b):ps) = b == 0 && (all g $ scanl' f a ps)
  where f :: Int -> (Int,Int) -> Int
        f a (c,d) | c < 0 || d < 0  = -1
                  | otherwise       = a + c - d
        g :: Int -> Bool
        g x = x >= 0 && x <= n
recorridoCorrecto _ _          = True
 
-- Comparación de la eficiencia
--  λ> recorridoCorrecto (10^6) $ replicate (10^6) (1,0)
--  True
--  (3.64 secs, 912,116,400 bytes)
--  λ> recorridoCorrecto2 (10^6) $ replicate (10^6) (1,0)
--  True
--  (2.84 secs, 584,114,000 bytes)
      • Responder
        angruicam1

        Aunque habría que añadirle que a debe ser mayor que d para corregirle un error:

        import Data.List (scanl')
 
recorridoCorrecto :: Int -> [(Int,Int)] -> Bool
recorridoCorrecto n ((a,b):ps) = b == 0 && (all g $ scanl' f a ps)
  where f :: Int -> (Int,Int) -> Int
        f a (c,d) | c < 0 || d < 0 || a < d = -1
                  | otherwise               = a + c - d
        g :: Int -> Bool
        g x = x >= 0 && x <= n
recorridoCorrecto _ _          = True
        • Responder
          angruicam1

          Y ya que estamos, para corregir los casos con ps = [] y n < 0 quitamos la última línea, y también nos podemos ahorra comprobar b == 0 y de paso el segundo argumento:

          import Data.List (scanl')
 
recorridoCorrecto :: Int -> [(Int,Int)] -> Bool
recorridoCorrecto n = all g . scanl' f 0
  where f :: Int -> (Int,Int) -> Int
        f a (c,d) | c < 0 || d < 0 || a < d = -1
                  | otherwise               = a + c - d
        g :: Int -> Bool
        g x = x >= 0 && x <= n
  2. Responder
    alerodrod5 
     
variacion :: [(Int,Int)] -> [Int]
variacion xs = [x-y | (x,y) <-xs]
 
numeroDeViajeros :: [(Int,Int)] -> [Int]
numeroDeViajeros xs = zipWith (+) p (tail p)
  where p = variacion xs
 
recorridoCorrecto :: Int -> [(Int,Int)] -> Bool
recorridoCorrecto n xs = all (> 0) y && all (< n) y
  where y = numeroDeViajeros xs
    • Responder
      angruicam1

      Buenas, la definición es incorrecta. Por ejemplo:

      -- λ> recorridoCorrecto 1 [(2,0)]
-- False
-- (0.00 secs, 112,736 bytes)
-- λ> recorridoCorrecto2 1 [(2,0)]
-- True
-- (0.00 secs, 112,840 bytes)

      Donde recorridoCorrecto2 es tu función.

      • Responder
        alerodrod5

        Cierto es, el error radica en que cuando defino numeroDeViajeros olvido el valor inicial, quedaría así:

         
variacion :: [(Int,Int)] -> [Int]
variacion xs = [x-y | (x,y) <-xs]
 
numeroDeViajeros :: [(Int,Int)] -> [Int]
numeroDeViajeros xs = x:zipWith (+) (x:p) p
  where (x:p) = variacion xs
 
 
recorridoCorrecto :: Int -> [(Int,Int)] -> Bool
recorridoCorrecto n xs = all (> 0) y && all (< n) y
  where y = numeroDeViajeros xs

        Muchas gracias.

        • Responder
          alerodrod5

          Una última variación :

          variacion :: [(Int,Int)] -> [Int]
variacion xs = [x-y | (x,y) <-xs, x>=0&& y>=0]
 
cabeza ((x,y):xs) | y==0 = True
                | otherwise = False
 
numeroDeViajeros :: [(Int,Int)] -> [Int]
numeroDeViajeros xs |variacion xs /= [] = x:zipWith (+) (x:p) p
                    | otherwise = []
  where (x:p) = variacion xs
 
 
recorridoCorrecto :: Int -> [(Int,Int)] -> Bool
recorridoCorrecto 0 _ = False
recorridoCorrecto n xs | cabeza xs && variacion xs /=[] = all (>= 0) y && all (< n) y
                       | otherwise = False 
  where y = numeroDeViajeros xs
          • alerodrod5

            Me he dado cuenta de un problema con los negativos, así como que numeroDeViajeros no era correcta

             
import Data.List 
 
variacion :: [(Int,Int)] -> [Int]
variacion xs = [x-y | (x,y) <-xs]
 
cumple ((x,y):xs) | y==0&& (x>=0) =and( map aux xs)
                  | otherwise = False
                    where aux (x,y) = x>=0 && y>=0
 
numeroDeViajeros :: [(Int,Int)] -> [Int]
numeroDeViajeros xs |(x:ys) /= [] = f (variacion xs)
                    | otherwise = []
  where (x:ys) = variacion xs
f xs = map sum (inits xs)
 
 
recorridoCorrecto :: Int -> [(Int,Int)] -> Bool
recorridoCorrecto _ [] = True
recorridoCorrecto n xs | cumple xs && variacion xs /=[] = all (>= 0) y && all (< = n) y
                       | otherwise = False 
  where y = numeroDeViajeros xs
  3. Responder
    agumaragu1 
    recorridoCorrecto :: Int -> [(Int,Int)] -> Bool
recorridoCorrecto n xs = aux n xs 0
  where aux c ((i,o):ps) a = a >= o && i >= 0 && o>= 0 && a+i-o <= c && aux c ps (a+i-o)
        aux _ [] _ = True
  4. Responder
    mirmednav 
    recorridoCorrecto :: Int -> [(Int,Int)] -> Bool
recorridoCorrecto n = null . filter g . scanl f 0
     where f :: Int -> (Int,Int) -> Int
           f a (b,c) = a + b - c
           g x = n < x || x < 0
    • Responder
      angruicam1

      Buenas, la definición no es correcta. Por ejemplo:

      -- λ> recorridoCorrecto 2 [(0,-1)]
-- False
-- λ> recorridoCorrecto2 2 [(0,-1)]
-- True

      Donde recorridoCorrecto2 es tu función.

  5. Responder
    antnavoro 
    recorridoCorrecto :: Int -> [(Int,Int)] -> Bool
recorridoCorrecto p = aux 0
  where aux :: Int -> [(Int,Int)] -> Bool
        aux n ((a,b):xs) | b > n = False
                         | n > p = False
                         | otherwise = a>=0 && b>=0 && aux (n+a-b) xs
        aux n [] = p >= 0 && n <= p
  6. Responder
    josmoncos 
    recorridoCorrecto :: Int -> [(Int,Int)] -> Bool
recorridoCorrecto x [] = True
recorridoCorrecto x ((a,b):ps) | nViajerosEnBus [(a,b)] > x = False
                               | otherwise = recorridoCorrecto (x - nViajerosEnBus[(a,b)]) ps && nViajerosEnBus [(a,b)] > 0
 
recorridoCorrecto :: Int -> [(Int,Int)] -> Bool
recorridoCorrecto x [] = True
recorridoCorrecto x ((a,b):ps) | nViajerosEnBus [(a,b)] > x = False
                               | otherwise = recorridoCorrecto (x - nViajerosEnBus[(a,b)]) ps && nViajerosEnBus [(a,b)] > 0
    • Responder
      josmoncos 
      recorridoCorrecto :: Int -> [(Int,Int)] -> Bool
recorridoCorrecto x [] = True
recorridoCorrecto x ((a,b):ps) | p > x = False
                               | otherwise = recorridoCorrecto (x - p) ps && p > 0
                                 where p = nViajerosEnBus [(a,b)]
nViajerosEnBus :: [(Int, Int)] -> Int
nViajerosEnBus ps = suben ps - bajan ps
 
suben :: [(Int, Int)] -> Int
suben ps = sum [x | (x,y) <- ps]
 
bajan :: [(Int, Int)] -> Int
bajan ps = sum [y | (x,y) <- ps]
      • Responder
        antgongar

        Falla en el primer ejemplo,

        λ> recorridoCorrecto 20 [(3,0),(9,1),(4,10),(12,2),(6,1)]
False

        y debería de dar True.

Escribe tu solución

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.