Menu Close

Conflictos de horarios

José A. Alonso,

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

5 Comments

  1. josejuan
    Responder 
    import Data.Matrix (Matrix, getRow)
import Data.Vector (toList)
import Data.List (transpose)
 
cursosConflictivos :: Horario → [Int] → Bool
cursosConflictivos mx = any ((1<) ∘ length ∘ filter id) ∘ transpose ∘ map (toList ∘ (`getRow` mx))
  2. manvermor
    Responder 
    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
    Responder 
    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
    Responder 
    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
    Responder 
    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.