Reconocimiento de recorridos correctos

PorJosé A. Alonso 12-diciembre-201719-diciembre-2017

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

1	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

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

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

16 Comentarios

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

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

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)

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

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

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

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

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

Responder

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

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

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)

-- λ> 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

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

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

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

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

Responder

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

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

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

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

Responder

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

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 dice:

12-diciembre-2017 a las 23:59

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

Haskell

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

1
2
3
4

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

Donde recorridoCorrecto2 es tu función.

Responder

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

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

Responder

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

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

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]

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 dice:

18-diciembre-2017 a las 20:11

Falla en el primer ejemplo,

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

1
2

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

y debería de dar True.

Responder

Reconocimiento de recorridos correctos

Soluciones

16 Comentarios

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico

Soluciones

Se puede imprimir o compartir con

16 Comentarios

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico