Examen 28/04/21

-- ==================================================================
-- Informática (1º del Grado en Matemáticas), Grupo 2, Turno 1
-- 3er examen de evaluación continua (28 de abril de 2021)
-- ------------------------------------------------------------------
-- Nombre: 
--
-- Apellidos: 
-- 
-- Usuario Virtual de la Universidad(UVUS):
-- ==================================================================

-- Nota 1: Es necesario que se pueda cargar el fichero. Es decir, que
-- no contenga errores sintácticos. Para ello, si alguna función no 
-- está terminada de programar o bien tiene algún error sintáctico,
-- debe estar comentada.
--
-- Nota 2: En cada ejercicio se valorará la corrección, claridad y 
-- eficiencia de la solución propuesta. Todos los ejercicios valen igual.
-- 
-- Nota 3: Todos los ejercicios valen igual. Se recomienda leer primero
-- todos los enunciados para planificar mejor el examen.

import Data.List
import Data.Matrix
import qualified Data.Vector as V
import I1M.Cola
--import ColaConListas

-- ----------------------------------------------------------------------
-- Ejercicio 1
-- ----------------------------------------------------------------------
-- Un bosque es una lista de árboles binarios. Representaremos los árboles
-- y los bosques mediante los siguientes tipos de datos

data Arbol  a = H a | N a (Arbol a) (Arbol a) deriving Show
data Bosque a = B [Arbol a] deriving Show

-- Define la función (hojasBosque b) tal que devuelva las hojas más
-- profundas de cada árbol del bosque, en el mismo orden. Por ejemplo:
-- > hojasBosque (B [t1,t2])  
-- [7,6,9,0]
-- > hojasBosque (B [t3,t2,t1])
-- [1,5,9,0,7,6]

t1,t2,t3 :: Arbol Int 
t1 = N 7 (N 9 (H 1) (N 5 (H 7) (H 6))) (H 5)
t2 = N 7 (N 9 (N 5 (H 9) (H 0)) (H 1)) (H 5)
t3 = N 7 (H 5) (N 9 (H 1) (H 5))

hojasBosque :: Bosque a -> [a]
hojasBosque (B as) = concatMap hojasProfundas as
  where
    hojasProfundas a = hojasP a (profundidad a) 0
    profundidad (H _) = 0
    profundidad (N _ i d) = 1 + max (profundidad i) (profundidad d)
    hojasP (H v) p n  
      | p == n = [v]
      | otherwise = []
    hojasP (N v i d) p n = (hojasP i p (n+1)) ++ (hojasP d p (n+1))

-- ---------------------------------------------------------------------

-- ---------------------------------------------------------------------
-- Ejercicio 2
-- ---------------------------------------------------------------------
-- Definir la función
--    anterior :: Eq a => a -> Cola a -> Maybe a
-- tal que (anterior x cs) es justo el elemento anterior a la primera 
-- ocurrencia de x en la cola cs o Nothing si x no pertenece a ys o si 
-- x es el primero de la cola. Usar solo funciones del TAD de colas
-- para resolver el ejercicio (es decir, no vale convertir la cola en
-- una lista). Por ejemplo,

c1 = foldl (flip inserta) vacia [3,5,2,5,7]
c2 = foldl (flip inserta) vacia "afdegdb"
c3 = foldl (flip inserta) vacia ["En","todo","la","medida"]

--    anterior 5 c1       ==  Just 3
--    anterior 9 c1       ==  Nothing
--    anterior 'd' c2     ==  Just 'f'
--    anterior "todo" c3  ==  Just "En"
--    anterior "En" c3    ==  Nothing
-- ---------------------------------------------------------------------

anterior :: Eq a => a -> Cola a -> Maybe a
anterior x c = aux c Nothing 
  where aux q v 
          | esVacia q = Nothing 
          | x == primero q = v 
          | otherwise = aux (resto q) (Just (primero q))

-- ---------------------------------------------------------------------

-- ----------------------------------------------------------------------
-- Ejercicio 3
-- ----------------------------------------------------------------------
-- Un tablero de Sudoku es aquel con 9x9 elementos dispuestos de la 
-- siguiente forma:
--  * Los valores son los números del 0 al 9
--  * Un valor del 1 al 9 no puede estar repetido en la misma fila ni en
--    la misma columna
--  * Un valor del 1 al 9 no puede estar repetido en el mismo cuadrante de 
--    3x3, siendo un cuadrante las submatrices de 3x3 del tablero, sin
--    solapamiento.
-- Define (valido m), tal que reciba una matriz m y compruebe si el 
-- tablero representado es un sudoku válido. Por ejemplo,
--   > valido sudoku0 == True
--   > valido sudoku1 == False
--   > valido sudoku2 == False
--   > valido sudoku3 == False

sudoku0, sudoku1, sudoku2, sudoku3 :: Matrix Int
sudoku0 = fromLists [[9,2,0,8,0,0,0,4,0],[0,0,1,3,4,0,0,0,6],[4,0,3,0,5,6,8,0,0],[2,1,0,0,6,4,5,0,0],[0,0,4,5,0,0,0,0,0],[6,0,5,1,0,2,4,7,0],[0,0,8,0,2,0,0,1,3],[0,4,0,0,1,0,0,0,0],[0,9,7,6,0,3,2,0,4]]
sudoku1 = fromLists [[9,2,0,8,0,0,0,4,0],[0,0,1,3,4,0,0,0,6],[4,0,3,0,5,6,8,0,0]]
sudoku2 = fromLists [[9,2,0,8,0,0,9,4,0],[0,0,1,3,4,0,0,0,6],[4,0,3,0,5,6,8,0,0],[2,1,0,0,6,4,5,0,0],[0,0,4,5,0,0,0,0,0],[6,0,5,1,0,2,4,7,0],[0,0,8,0,2,0,0,1,3],[0,4,0,0,1,0,0,0,0],[0,9,7,6,0,3,2,0,4]]
sudoku3 = fromLists [[9,2,0,8,0,0,0,4,0],[0,0,1,3,4,0,0,0,6],[4,0,3,0,5,6,8,0,0],[2,1,0,0,6,4,5,0,0],[0,0,4,5,0,0,0,0,0],[6,0,5,1,0,2,4,7,0],[0,0,8,0,2,0,0,1,3],[0,4,0,0,1,0,0,2,0],[0,9,7,6,0,3,2,0,4]]


valido :: Matrix Int -> Bool
valido m 
  | nr /= 9 || nc /= 9 = False -- Tamano no valido
  | all (\x -> notElem x [0..9]) (toList m) = False -- Hay elementos no en [0..9]
  | or [ valRepetidoSudo (V.toList (getRow i m)) | i <- [1..nr]] = False -- Hay elementos repetidos en una fila
  | or [ valRepetidoSudo (V.toList (getCol j m)) | j <- [1..nc]] = False -- Hay elementos repetidos en una columna
  | or [ valRepetidoSudo (toList (submatrix i (i+2) j (j+2) m)) | i <- [1,4,7], j <- [1,4,7]] = False -- Hay elementos repetidos en un cuadrante
  | otherwise = True -- Tablero correcto
  where nr = nrows m
        nc = ncols m

valRepetidoSudo :: [Int] -> Bool    
valRepetidoSudo xs = ys /= nub ys
  where ys = filter (/=0) xs  -- el cero no cuenta puesto que son casillas vacías

-- ---------------------------------------------------------------------

-- ----------------------------------------------------------------------
-- Ejercicio 4
-- ----------------------------------------------------------------------
-- Define un programa interactivo en el que:
--   1. Se le pida al usuario una fila f, una columna c y un valor v. 
--   2. Mostrar un mensaje que indique si los valores introducidos por
--   el usuario son correctos o no. Es decir:
--      * f, c y v son números entre el 1 y el 9
--      * en la posición (f,c) de la matriz sudoku0 (ejercicio 3) hay un 0.

-- Por ejemplo, el primer intento es inválido por los valores, el segundo
-- porque no hay un 0 en la posición (1,1), y el tercero es correcto.
-- > main
-- Indica una fila
-- 0
-- Indica una columna
-- 6
-- Indica un valor
-- -1
-- Incorrecto
-- > main
-- Indica una fila
-- 1
-- Indica una columna
-- 1
-- Indica un valor
-- 1
-- Incorrecto
-- > main
-- Indica una fila
-- 1
-- Indica una columna
-- 3
-- Indica un valor
-- 1
-- Correcto

main :: IO()
main = do
  putStrLn "Indica una fila"
  f' <- getChar
  getChar
  putStrLn "Indica una columna"
  c' <- getChar
  getChar
  putStrLn "Indica un valor"
  v' <- getChar
  getChar
  let f = convierte f' 
      c = convierte c' 
      v = convierte v' 
  if (valorNum f && valorNum c && valorNum v && sudoku0!(f,c) == 0) then do
      putStrLn "Correcto"
    else 
      putStrLn "Incorrecto"
  where valorNum c = elem c [1..9]    -- incluyendo Data.Char podríamos usar isDigit  y c/='0'
        convierte c = read [c]::Int   -- incluyendo Data.Char podríamos usar digitToInt

-- -------------------------------------------------------------------