Menu Close

Conflictos de horarios

Los horarios de los cursos se pueden representar mediante matrices donde las filas indican los curso, las columnas las horas de clase y el valor correspondiente al curso i y la hora j es verdadero indica que i tiene clase a la hora j.

En Haskell, podemos usar la matrices de la librería Data.Matrix y definir el tipo de los horarios por

   type Horario = Matrix Bool

Un ejemplo de horario es

   ejHorarios1 :: Horario
   ejHorarios1 = fromLists [[True,  True,  False, False],
                            [False, True,  True,  False],
                            [False, False, True,  True]]

en el que el 1º curso tiene clase a la 1ª y 2ª hora, el 2º a la 2ª y a la 3ª y el 3º a la 3ª y a la 4ª.

Definir la función

   cursosConflictivos :: Horario -> [Int] -> Bool

tal que (cursosConflictivos h is) se verifica para si los cursos de la lista is hay alguna hora en la que más de uno tiene clase a dicha hora. Por ejemplo,

   cursosConflictivos ejHorarios1 [1,2]  ==  True
   cursosConflictivos ejHorarios1 [1,3]  ==  False

Soluciones

import Data.Matrix
 
type Horario = Matrix Bool
 
ejHorarios1 :: Horario
ejHorarios1 = fromLists [[True,  True,  False, False],
                         [False, True,  True,  False],
                         [False, False, True,  True]]
 
--    horaConflictiva ejHorarios1 [1,2]   2  ==  True
--    horaConflictiva ejHorarios1 [1,3]   2  ==  False
--    horaConflictiva ejHorarios1 [1,2,3] 1  ==  False
horaConflictiva :: Horario -> [Int] -> Int -> Bool
horaConflictiva h is j =
  length [i | i <- is, h ! (i,j)] > 1
 
cursosConflictivos :: Horario -> [Int] -> Bool
cursosConflictivos h is =
  or [horaConflictiva h is j | j <- [1..n]]
  where n = ncols h
Posted in Avanzado

5 Comments

  1. josejuan
    import Data.Matrix (Matrix, getRow)
    import Data.Vector (toList)
    import Data.List (transpose)
     
    cursosConflictivos :: Horario → [Int]Bool
    cursosConflictivos mx = any ((1<)lengthfilter id) ∘ transpose ∘ map (toList ∘ (`getRow` mx))
  2. manvermor
    import Data.Matrix
    import qualified Data.Array as A
     
    type Horario = Matrix Bool
     
    ejHorarios1 :: Horario
    ejHorarios1 = fromLists [[True,  True,  False, False],
                             [False, True,  True,  False],
                             [False, False, True,  True]]
     
    cursosConflictivos :: Horario -> [Int] -> Bool
    cursosConflictivos h is = comprueba xs
        where xs = filter ((x,y) -> y == True) $ 
                          [(x,y) | (x,y) <- asociaciones  h, 
                                   z <- is, 
                                   fst x == z]
     
    comprueba :: (Eq a, Eq a2) => [((a1, a), a2)] -> Bool
    comprueba ((x,y):(z,t):xs) = 
        snd x == snd z && y == t || comprueba ((z,t):xs)
    comprueba _ = False
     
    asociaciones :: Matrix e -> [((Int, Int), e)]
    asociaciones h = A.assocs p
        where p     = A.listArray ((1,1),(m,n)) $ toList h 
              (m,n) = (nrows h, ncols h)
  3. manpende
    import Data.Matrix
    import qualified Data.Vector as V
     
    cursosConflictivos :: Horario -> [Int] -> Bool
    cursosConflictivos h (i:j:is) = 
        conflictivo hi hj || 
        cursosConflictivos h (i:is) || 
        cursosConflictivos h (j:is)
        where hi = V.toList $ getRow i h
              hj = V.toList $ getRow j h 
    cursosConflictivos _ _ = False
     
    conflictivo :: [Bool] -> [Bool] -> Bool
    conflictivo [] [] = False
    conflictivo (x:xs) (y:ys) 
        | x == False = restoConflictivo
        | y == False = restoConflictivo
        | x /= y     = restoConflictivo
        | otherwise  = True
        where restoConflictivo = conflictivo xs ys
  4. abrdelrod
    import Data.Matrix
     
    type Horario = Matrix Bool
     
    cursosConflictivos :: Horario -> [Int] -> Bool
    cursosConflictivos h is = any (> 1) (map (length . filter (== True)) (columnas h))
       where columnas p = [[p!(i,j) | i <- is] | j <- [1..ncols p]]
  5. Chema Cortés
    import Data.Matrix
     
    type Horario = Matrix Bool
     
    cursosConflictivos :: Horario -> [Int] -> Bool
    cursosConflictivos h is = any conflicto columnas
        where columnas = [[h!(i,j) | i <- is] | j <- [1..ncols h]
              conflicto xs = length (filter id xs) > 1

Escribe tu solución

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