-- ==================================================================
-- Informática (1º del Grado en Matemáticas), Grupo 2, Turno 2
-- 3er examen de evaluación continua (23 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. Si no, penalizará en la nota.
--
-- Nota 2: En cada ejercicio se valorará la corrección, claridad y
-- eficiencia de la solución propuesta.
--
-- Nota 3: Todos los apartados valen igual.
--
-- Nota 4: el fichero partida.txt se puede descargar aquí:
-- https://www.cs.us.es/~mdelamor/i1m/2020/partida.txt
import Data.List
import Data.Matrix
import I1M.Pila
-- ----------------------------------------------------------------------
-- Ejercicio 1
-- ----------------------------------------------------------------------
-- Un árbol genérico se dice escalonado si para cada nodo, la profundidad
-- de sus subárboles de izquierda a derecha es estrictamente creciente.
-- Es decir, la profundidad de un subárbol es siempre menor estricto que
-- que la profundidad del siguiente subárbol.
-- Por ejemplo, los árboles ej1 y ej3 son escalonados, pero ej2 no lo es.
--
-- A A A
-- / | \ / | \ / \
-- B C E B C E B D
-- | | \ | |\ / \
-- D F G D F G C E
-- ej1: | | ej2: | | ej3: |
-- H I H I F
-- | | |
-- J J G
data Arbol a = N a [Arbol a]
ejArbol1,ejArbol2 :: Arbol Char
ejArbol1 = N 'A' [N 'B' [], N 'C' [N 'D' []], N 'E' [N 'F' [N 'H' []], N 'G' [N 'I' [N 'J' []]]]]
ejArbol2 = N 'A' [N 'B' [N 'D' [N 'H' [N 'J' []]]], N 'C' [N 'F' [N 'I' []], N 'G' []], N 'E' []]
ejArbol3 = N 'A' [N 'B' [N 'C' []], N 'D' [N 'E' [N 'F' [N 'G' []]]]]
-- Define la función (escalonado a), tal que dado un árbol 'a' devuelva si
-- es escalonado. Por ejemplo,
-- escalonado ejArbol1 == True
-- escalonado ejArbol2 == False
-- escalonado ejArbol3 == True
-- Solución 1
escalonado :: Arbol a -> Bool
escalonado (N _ as) = and [escalonado a | a <- as] &&
and [ profundidad a < profundidad b | (a,b) <- (zip as (tail as))]
where
profundidad (N _ []) = 0
profundidad (N _ as) = 1 + (maximum [profundidad a | a <- as])
-- Solución 2
escalonado' :: Arbol a -> Bool
escalonado' (N _ as) = all escalonado' as && all (uncurry (<)) (zip ps (tail ps))
where
ps = map profundidad as
profundidad (N _ []) = 0
profundidad (N _ as) = 1 + (maximum . map profundidad) as
-- ---------------------------------------------------------------------
-- ----------------------------------------------------------------------
-- Ejercicio 2
-- ----------------------------------------------------------------------
-- Se pide definir un pequeño juego mediante un programa interactivo:
-- * El programa debe cargar un fichero, llamado partida.txt, con el
-- contenido de la partida inicial en una pila. El contenido es una
-- secuencia de símbolos '+' y '-'. No se debe mostrar dicho contenido
-- al usuario, ya que se trata de adivinarlo.
-- * El usuario, sin saber dicho contenido, debe intentar eliminar los
-- símbolos cargados. Para ello, hay que adivinar el último símbolo
-- introducido. Para ello, el usuario presiona una tecla, pulsa intro,
-- y procesamos el símbolo leído:
-- - Si el símbolo no es '+' ni '-', indicar que no es válido y
-- pedir de nuevo otro.
-- - Si el símbolo no coincide con la cima de la pila, añadir este
-- símbolo a la pila.
-- - Si el símbolo coincide con la cima, desapilar la pila.
-- - Cada 5 intentos, indicar el tamaño de la pila. También se debe
-- indicar justo al comenzar el juego.
-- - Si la pila es vacía, indicar un mensaje de enhorabuena.
-- Por ejemplo,
-- > main
-- Bienvenido al juego de la pila
-- Tamano de la pila: 4
-- Indica simbolo (+/-): +
-- Indica simbolo (+/-): 1
-- Simbolo no valido
-- Indica simbolo (+/-): 5
-- Simbolo no valido
-- Indica simbolo (+/-): +
-- Indica simbolo (+/-): -
-- Indica simbolo (+/-): -
-- Indica simbolo (+/-): +
-- Tamano de la pila: 3
-- Indica simbolo (+/-): +
-- Indica simbolo (+/-): -
-- Indica simbolo (+/-): +
-- Enhorabuena!! Has ganado!!
main :: IO()
main = do
putStrLn "Bienvenido al juego de la pila" -- mensaje de bienvenida
input <- readFile "partida.txt" -- lectura del fichero, solo un string
let pila = foldr apila vacia input -- cargar el contenido en la pila
juego pila 0 -- comenzamos el juego
juego :: Pila Char -> Int -> IO ()
juego p n = do
if (esVacia p) then do -- partida finalizada
putStrLn "Enhorabuena!! Has ganado!!"
return ()
else do
if (mod n 5 == 0) then -- cada 5 pasos, mostrar el contenido
putStrLn $ "Tamano de la pila: " ++ (show (lengthP p))
else putStr "" -- imprime nada
putStr "Indica simbolo (+/-): "
s <- getChar -- lee la tecla
getChar -- lee \n introducido después
if (notElem s "+-") then do
putStrLn "Simbolo no valido"
juego p n -- repetimos el proceso
else
juego (procesa p s) (n+1) -- siguiente paso
lengthP :: Pila a -> Int
lengthP p | esVacia p = 0
| otherwise = 1 + lengthP (desapila p)
procesa :: Pila Char -> Char -> Pila Char
procesa p c | cima p == c = desapila p
| otherwise = apila c p
-- ---------------------------------------------------------------------
-- ----------------------------------------------------------------------
-- Ejercicio 3
-- ----------------------------------------------------------------------
-- La difusión de una matriz es resultado de asignar a cada elemento
-- la media de su valor junto con la de sus vecinos dentro de la matriz
-- a una distancia d. Por ejemplo, sea ejMat la siguiente matriz
-- ┌ ┐
-- │ 1 0 1 2 7 1 │
-- │ 2 1 3 4 0 2 │
-- │ 1 2 3 6 9 1 │
-- │ 0 3 6 4 7 8 │
-- │ 3 4 5 1 1 9 │
-- └ ┘
-- Los valores a tener en cuenta para la posición (3,3) con distancia d=1
-- son:
-- 1 3 4
-- 2 3 6 la media es 3.5555556
-- 3 6 4
-- Los valores a tener en cuenta para la posición (3,3) con distancia d=2
-- son:
-- 1 0 1 2 7
-- 2 1 3 4 0
-- 1 2 3 6 9 la media es 3.04
-- 0 3 6 4 7
-- 3 4 5 1 1
-- Los valores a tener en cuenta para la posición (1,1) con distancia d=1
-- son:
-- 1 0
-- 2 1 la media es 1.0
ejMat :: Matrix Float
ejMat = fromLists [[1,0,1,2,7,1],[2,1,3,4,0,2],[1,2,3,6,9,1],[0,3,6,4,7,8],[3,4,5,1,1,9]]
-- Ejercicio 3.1. Define la función (difumina m d) tal que devuelva la matriz
-- resultante de aplicar difusión a la matriz m usando distancia d. Por ejemplo,
-- > difumina ejMat 1
-- ┌ ┐
-- │ 1.0 1.3333334 1.8333334 2.8333333 2.6666667 2.5 │
-- │ 1.1666666 1.5555556 2.4444444 3.8888888 3.5555556 3.3333333 │
-- │ 1.5 2.3333333 3.5555556 4.6666665 4.5555553 4.5 │
-- │ 2.1666667 3.0 3.7777777 4.6666665 5.111111 5.8333335 │
-- │ 2.5 3.5 3.8333333 4.0 5.0 6.25 │
-- └ ┘
-- > difumina ejMat 2
-- ┌ ┐
-- │ 1.5555556 2.1666667 2.8 2.8 3.25 3.5555556 │
-- │ 1.9166666 2.4375 3.1 3.5 4.0 4.25 │
-- │ 2.3333333 2.6 3.04 3.6 4.0 4.133333 │
-- │ 2.75 3.0 3.25 3.95 4.3125 4.3333335 │
-- │ 3.0 3.1666667 3.6666667 4.6 5.0 5.111111 │
-- └ ┘
difumina :: Fractional a => Matrix a -> Int -> Matrix a
difumina m d = matrix nr nc f
where f (i,j) = sum (vecinos i j) / genericLength (vecinos i j)
vecinos x y = [m!(i,j) | i <- [x-d..x+d], j <- [y-d..y+d], i>0, j>0, i<=nr, j<=nc]
nc = ncols m
nr = nrows m
-- Ejercicio 3.2. Define la función (numDifumina m d e) tal que devuelva el
-- número de veces a aplicar 'difumina' a una matriz m con distancia d hasta
-- obtener una matriz cuyos elementos sean iguales entre sí con un error
-- de diferencia e.
-- Por ejemplo,
-- > numDifumina (fromLists [[1,0,0,0],[0,1,0,0],[0,0,1,0],[0,0,0,1]]) 1 0.001 == 11
-- > numDifumina (fromLists [[1,0,0,0],[0,1,0,0],[0,0,1,0],[0,0,0,1]]) 2 0.001 == 4
-- > numDifumina ejMat 1 0.0001 == 87
-- > numDifumina ejMat 2 0.0001 == 24
numDifumina :: (Ord a,Floating a) => Matrix a -> Int -> a -> Int
numDifumina m d e = snd $ until (todoIgual . fst) (\(p,s) -> (difumina p d,s+1)) (m,0)
where todoIgual p = and [ abs (p!(1,1)-p!(i,j)) < e | i <- [1..nrows p], j <- [1..ncols p]]
-- ---------------------------------------------------------------------
![Informática de 1º de Matemáticas [Curso 2021-22, Grupo 2]](/WIKIS/I1M2021G2/resources/assets/logoUS.png)