Diferencia entre revisiones de «Relación 24»
De Informática de 1º de Matemáticas [Curso 2021-22, Grupo 3]
(Página creada con «<source lang='haskell'> -- I1M 2021-22: Relación 24 -- Funciones de entrada/salida: El juego Nim -- Departamento de Ciencias de la Computación e Inteligencia Artificial -…») |
|||
Línea 41: | Línea 41: | ||
-- finalizado [1,3,0,0,1] == False | -- finalizado [1,3,0,0,1] == False | ||
-- ---------------------------------------------------------------------------- | -- ---------------------------------------------------------------------------- | ||
- Álvaro Galisteo: | |||
finalizado :: Tablero -> Bool | finalizado :: Tablero -> Bool | ||
finalizado = | finalizado t = all (== 0) t | ||
-- ---------------------------------------------------------------------------- | -- ---------------------------------------------------------------------------- | ||
Línea 53: | Línea 55: | ||
-- jugada [4,3,2,1,0] 2 1 == [4,2,2,1,0] | -- jugada [4,3,2,1,0] 2 1 == [4,2,2,1,0] | ||
-- ---------------------------------------------------------------------------- | -- ---------------------------------------------------------------------------- | ||
- Álvaro Galisteo: | |||
jugada :: Tablero -> Int -> Int -> Tablero | jugada :: Tablero -> Int -> Int -> Tablero | ||
jugada = | jugada t m n = take (m-1) t ++ [(t !! (m-1)) - n] ++ drop m t | ||
-- ---------------------------------------------------------------------------- | -- ---------------------------------------------------------------------------- | ||
Línea 64: | Línea 68: | ||
-- piezas 3 == " * * *" | -- piezas 3 == " * * *" | ||
-- ---------------------------------------------------------------------------- | -- ---------------------------------------------------------------------------- | ||
- Álvaro Galisteo: | |||
piezas :: Int -> String | piezas :: Int -> String | ||
piezas = | piezas 0 = "" | ||
piezas n = " *" ++ piezas (n-1) | |||
-- ---------------------------------------------------------------------------- | -- ---------------------------------------------------------------------------- | ||
Línea 76: | Línea 83: | ||
-- 2: * * * | -- 2: * * * | ||
-- ---------------------------------------------------------------------------- | -- ---------------------------------------------------------------------------- | ||
- Álvaro Galisteo: | |||
escribeMonton :: Int -> Int -> IO () | escribeMonton :: Int -> Int -> IO () | ||
escribeMonton = | escribeMonton m n = putStr ((show m) ++ ":" ++ (piezas n)) | ||
-- ---------------------------------------------------------------------------- | -- ---------------------------------------------------------------------------- | ||
Línea 92: | Línea 102: | ||
-- 5: * | -- 5: * | ||
-- ---------------------------------------------------------------------------- | -- ---------------------------------------------------------------------------- | ||
- Álvaro Galisteo: | |||
escribeTablero :: Tablero -> IO () | escribeTablero :: Tablero -> IO () | ||
escribeTablero = | escribeTablero t = sequence_ [putStrLn ((show (n+1)) ++ ":" ++ (piezas (t!!n))) | n <- [0..(length t - 1)]] | ||
-- ---------------------------------------------------------------------------- | -- ---------------------------------------------------------------------------- | ||
Línea 113: | Línea 126: | ||
-- 3 | -- 3 | ||
-- ---------------------------------------------------------------------------- | -- ---------------------------------------------------------------------------- | ||
- Álvaro Galisteo: | |||
leeNumero :: String -> IO Int | leeNumero :: String -> IO Int | ||
leeNumero = | leeNumero xs = do putStr xs | ||
x <- getLine | |||
if and [elem y numero | y <- x] | |||
then return (read x :: Int) | |||
else do putStr "ERROR: Entrada incorrecta \n" | |||
leeNumero xs | |||
where numero = "0123456789" | |||
-- ---------------------------------------------------------------------------- | -- ---------------------------------------------------------------------------- | ||
Línea 136: | Línea 157: | ||
-- 2 | -- 2 | ||
-- ---------------------------------------------------------------------------- | -- ---------------------------------------------------------------------------- | ||
- Álvaro Galisteo: | |||
eligeMonton :: Tablero -> IO Int | eligeMonton :: Tablero -> IO Int | ||
eligeMonton = | eligeMonton t = do x <- leeNumero "Qué montón eliges? " | ||
if x > (length t) | |||
then do putStr "ERROR: Número de montón incorrecto \n" | |||
eligeMonton t | |||
else if t !! (x-1) == 0 | |||
then do putStr "ERROR: El montón está vacío \n" | |||
eligeMonton t | |||
else return x | |||
-- ---------------------------------------------------------------------------- | -- ---------------------------------------------------------------------------- | ||
Línea 158: | Línea 188: | ||
-- 2 | -- 2 | ||
-- ---------------------------------------------------------------------------- | -- ---------------------------------------------------------------------------- | ||
- Álvaro Galisteo: | |||
eligePiezas :: Tablero -> Int -> IO Int | eligePiezas :: Tablero -> Int -> IO Int | ||
eligePiezas = | eligePiezas t m = do x <- leeNumero " Cuántas piezas coges? " | ||
if x > (t!!(m-1)) || x == 0 | |||
then do putStr "ERROR: Número de piezas incorrecto \n" | |||
eligePiezas t m | |||
else return x | |||
-- ---------------------------------------------------------------------------- | -- ---------------------------------------------------------------------------- | ||
Línea 168: | Línea 204: | ||
-- tal que '(cambiaJugador j)' es el jugador distinto a 'j'. | -- tal que '(cambiaJugador j)' es el jugador distinto a 'j'. | ||
-- ---------------------------------------------------------------------------- | -- ---------------------------------------------------------------------------- | ||
- Álvaro Galisteo: | |||
cambiaJugador :: Int -> Int | cambiaJugador :: Int -> Int | ||
cambiaJugador = | cambiaJugador 1 = 2 | ||
cambiaJugador 2 = 1 | |||
-- ---------------------------------------------------------------------------- | -- ---------------------------------------------------------------------------- | ||
Línea 207: | Línea 246: | ||
-- Ha ganado el jugador 1 | -- Ha ganado el jugador 1 | ||
-- ---------------------------------------------------------------------------- | -- ---------------------------------------------------------------------------- | ||
- Álvaro Galisteo: | |||
juegoNim :: Tablero -> Int -> IO () | juegoNim :: Tablero -> Int -> IO () | ||
juegoNim = | juegoNim t j = do escribeTablero t | ||
putStrLn ("Turno del jugador " ++ show j) | |||
m <- eligeMonton t | |||
n <- eligePiezas t m | |||
if finalizado (jugada t m n) | |||
then putStrLn ("Ha ganado el jugador " ++ show j) | |||
else juegoNim (jugada t m n) (cambiaJugador j) | |||
-- ---------------------------------------------------------------------------- | -- ---------------------------------------------------------------------------- | ||
Línea 223: | Línea 271: | ||
-- ---------------------------------------------------------------------------- | -- ---------------------------------------------------------------------------- | ||
listaNumeros :: String -> [Int] | - Álvaro Galisteo: | ||
listaNumeros = | |||
listaNumeros :: String -> [Int] | |||
listaNumeros "" = [] | |||
listaNumeros xs = if and [isDigit y || y == ' ' | y <- xs] | |||
then [(read x :: Int)] ++ listaNumeros (drop (length x + 1) xs) | |||
else [] | |||
where x = takeWhile (/= ' ') xs | |||
-- ---------------------------------------------------------------------------- | -- ---------------------------------------------------------------------------- | ||
Línea 281: | Línea 335: | ||
-- Ha ganado el jugador 1 | -- Ha ganado el jugador 1 | ||
-- ---------------------------------------------------------------------------- | -- ---------------------------------------------------------------------------- | ||
- Álvaro Galisteo: | |||
nim :: IO () | nim :: IO () | ||
nim = | nim = do putStr "Escribe la lista de números de piezas de cada montón: " | ||
x <- getLine | |||
if listaNumeros x == [] | |||
then do putStrLn "ERROR: La lista de números es incorrecta" | |||
nim | |||
else juegoNim (listaNumeros x) 1 | |||
-- ---------------------------------------------------------------------------- | -- ---------------------------------------------------------------------------- | ||
-- En el juego del Nim, un tablero perdedor es un tablero en el que el jugador | -- En el juego del Nim, un tablero perdedor es un tablero en el que el jugador | ||
Línea 355: | Línea 416: | ||
-- descomposicionBase2 10 == [8,2] | -- descomposicionBase2 10 == [8,2] | ||
-- ---------------------------------------------------------------------------- | -- ---------------------------------------------------------------------------- | ||
- Álvaro Galisteo: | |||
descomposicionBase2 :: Int -> [Int] | descomposicionBase2 :: Int -> [Int] | ||
descomposicionBase2 = | descomposicionBase2 0 = [] | ||
descomposicionBase2 n = reverse (filter (/=0 ) [f (xs!!p) p | p <- [0..(length xs - 1)]]) | |||
where xs = (map (`rem` 2) ((takeWhile (/=1) (iterate (`div` 2) n)) ++ [1])) | |||
f x y = if x == 1 then 2^y else 0 | |||
-- ---------------------------------------------------------------------------- | -- ---------------------------------------------------------------------------- | ||
Línea 370: | Línea 437: | ||
-- descomposicionTablero [8,5,3] == [(8,1),(4,2),(1,2),(2,3),(1,3)] | -- descomposicionTablero [8,5,3] == [(8,1),(4,2),(1,2),(2,3),(1,3)] | ||
-- ---------------------------------------------------------------------------- | -- ---------------------------------------------------------------------------- | ||
- Álvaro Galisteo: | |||
descomposicionTablero :: Tablero -> [(Int,Int)] | descomposicionTablero :: Tablero -> [(Int,Int)] | ||
descomposicionTablero = | descomposicionTablero t = [(x,p) | p <- [1..(length t)], x <- descomposicionBase2 (t!!(p-1)) ] | ||
-- ---------------------------------------------------------------------------- | -- ---------------------------------------------------------------------------- | ||
Línea 384: | Línea 453: | ||
-- reduceParejas [(2,2),(1,2),(2,3),(1,3)] == [] | -- reduceParejas [(2,2),(1,2),(2,3),(1,3)] == [] | ||
-- ---------------------------------------------------------------------------- | -- ---------------------------------------------------------------------------- | ||
- Álvaro Galisteo: | |||
reduceParejas :: [(Int,Int)] -> [(Int,Int)] | reduceParejas :: [(Int,Int)] -> [(Int,Int)] | ||
reduceParejas = | reduceParejas pms = aux pms [] [] | ||
where aux xs ys zs | xs == [] = zs | |||
| elem (fst(head xs)) ys = aux (drop 1 xs) (filter (/= fst(head xs)) ys) (filter (f (fst(head xs))) zs) | |||
| otherwise = aux (drop 1 xs) ([fst(head xs)] ++ ys) ([head xs] ++ zs) | |||
f x y = fst y /= x | |||
-- ---------------------------------------------------------------------------- | -- ---------------------------------------------------------------------------- | ||
Línea 398: | Línea 473: | ||
-- montonConMayorPotenciaDesparejada [(2,3)] == 3 | -- montonConMayorPotenciaDesparejada [(2,3)] == 3 | ||
-- ---------------------------------------------------------------------------- | -- ---------------------------------------------------------------------------- | ||
- Álvaro Galisteo: | |||
montonConMayorPotenciaDesparejada :: [(Int,Int)] -> Int | montonConMayorPotenciaDesparejada :: [(Int,Int)] -> Int | ||
montonConMayorPotenciaDesparejada = | montonConMayorPotenciaDesparejada pms = snd (head(filter (f (maximum [fst xs | xs <- pms])) pms)) | ||
where f x y = fst y == x | |||
-- ---------------------------------------------------------------------------- | -- ---------------------------------------------------------------------------- | ||
Línea 412: | Línea 490: | ||
-- piezasSobrantes [(2,3)] 3 == 2 | -- piezasSobrantes [(2,3)] 3 == 2 | ||
-- ---------------------------------------------------------------------------- | -- ---------------------------------------------------------------------------- | ||
- Álvaro Galisteo: | |||
piezasSobrantes :: [(Int,Int)] -> Int -> Int | piezasSobrantes :: [(Int,Int)] -> Int -> Int | ||
piezasSobrantes = | piezasSobrantes pms m = sum [fst xs | xs <- (filter (f m) pms)] - sum [fst xs | xs <- (filter (f' m) pms)] | ||
where f x y = snd y == x | |||
f' x y = snd y /= x | |||
-- ---------------------------------------------------------------------------- | -- ---------------------------------------------------------------------------- | ||
Línea 420: | Línea 502: | ||
-- buscaEleccionGanadora :: Tablero -> (Int,Int) | -- buscaEleccionGanadora :: Tablero -> (Int,Int) | ||
-- tal que '(buscaEleccionGanadora t)' es un par '(m,n)' donde 'm' es un número | -- tal que '(buscaEleccionGanadora t)' es un par '(m,n)' donde 'm' es un número | ||
-- de montón válido en el tablero 't', | -- de montón válido en el tablero 't', | ||
-- entonces tras tomar 'n' piezas del montón 'm' en el tablero 't', el tablero | -- entonces tras tomar 'n' piezas del montón 'm' en el tablero 't', el tablero | ||
-- es perdedor. En caso de que el tablero original sea perdedor entonces se | -- es perdedor. En caso de que el tablero original sea perdedor entonces se | ||
Línea 431: | Línea 512: | ||
-- buscaEleccionGanadora [7] == (1,7) | -- buscaEleccionGanadora [7] == (1,7) | ||
-- ---------------------------------------------------------------------------- | -- ---------------------------------------------------------------------------- | ||
- Álvaro Galisteo: | |||
buscaEleccionGanadora :: Tablero -> (Int,Int) | buscaEleccionGanadora :: Tablero -> (Int,Int) | ||
buscaEleccionGanadora = | buscaEleccionGanadora t = if x == [] | ||
then (montonConMayorPotenciaDesparejada (descomposicionTablero t),1) | |||
else (y, piezasSobrantes x y) | |||
where x = reduceParejas (descomposicionTablero t) | |||
y = montonConMayorPotenciaDesparejada x | |||
-- ---------------------------------------------------------------------------- | -- ---------------------------------------------------------------------------- | ||
Línea 506: | Línea 593: | ||
-- He ganado | -- He ganado | ||
-- ---------------------------------------------------------------------------- | -- ---------------------------------------------------------------------------- | ||
- Álvaro Galisteo: | |||
juegoNimC :: Tablero -> Int -> IO () | juegoNimC :: Tablero -> Int -> IO () | ||
juegoNimC = | juegoNimC t j = do putStr "\n" | ||
escribeTablero t | |||
putStr "\n" | |||
if j == 2 | |||
then do putStrLn ("Me toca jugar ") | |||
if finalizado (jugada t (fst x) (snd x)) | |||
then do putStr "\n" | |||
escribeTablero (jugada t (fst x) (snd x)) | |||
putStr "\n" | |||
putStrLn ("He ganado ") | |||
else juegoNimC (jugada t (fst x) (snd x)) (cambiaJugador j) | |||
else do putStrLn ("Te toca jugar ") | |||
m <- eligeMonton t | |||
n <- eligePiezas t m | |||
if finalizado (jugada t m n) | |||
then do putStr "\n" | |||
escribeTablero (jugada t m n) | |||
putStr "\n" | |||
putStrLn ("Has ganado ") | |||
else juegoNimC (jugada t m n) (cambiaJugador j) | |||
where x = buscaEleccionGanadora t | |||
-- ---------------------------------------------------------------------------- | -- ---------------------------------------------------------------------------- | ||
-- Ejercicio 20: Definir la acción | -- Ejercicio 20: Definir la acción | ||
Línea 588: | Línea 697: | ||
-- He ganado | -- He ganado | ||
-- ---------------------------------------------------------------------------- | -- ---------------------------------------------------------------------------- | ||
- Álvaro Galisteo: | |||
nimC :: IO () | nimC :: IO () | ||
nimC = | nimC =do putStr "Escribe la lista de números de piezas de cada montón: " | ||
t <- getLine | |||
if listaNumeros t == [] | |||
then do putStrLn "ERROR: La lista de números es incorrecta" | |||
nimC | |||
else do j <- leeNumero "Quién empieza a jugar, tú (1) o yo (2)? " | |||
if j/=1 && j/=2 | |||
then do putStrLn "ERROR: El número es incorrecto " | |||
nimC | |||
else do putStrLn "Suerte, te va a hacer falta ... " | |||
juegoNimC (listaNumeros t) j | |||
-- ============================================================================ | -- ============================================================================ | ||
</source> | </source> |
Revisión del 15:15 2 abr 2022
-- I1M 2021-22: Relación 24
-- Funciones de entrada/salida: El juego Nim
-- Departamento de Ciencias de la Computación e Inteligencia Artificial
-- Universidad de Sevilla
-- ============================================================================
-- ============================================================================
-- Librerías auxiliares
-- ============================================================================
import Data.Char
import Data.List
-- ============================================================================
-- El Nim es un juego en el que se dispone de un conjunto de montones de
-- piezas y dos jugadores retiran alternativamente por turno cualquier cantidad
-- de piezas de un único montón. El ganador es el que retira la última pieza.
--
-- En nuestra versión del juego se pide a los jugadores que indiquen la lista
-- de números de piezas de cada montón.
-- ============================================================================
-- ----------------------------------------------------------------------------
-- Representación
-- ----------------------------------------------------------------------------
-- El conjunto de montones (que llamaremos tablero de juego o simplemente
-- tablero) se representará como una lista de números indicando el número de
-- piezas de cada montón. Con esta representación, un conjunto de montones
-- podría ser [5,4,3,2,1].
type Tablero = [Int]
-- ----------------------------------------------------------------------------
-- Ejercicio 1. Definir la función
-- finalizado :: Tablero -> Bool
-- tal que '(finalizado t)' se verifica si 't' es el tablero de un juego
-- finalizado; es decir, sin piezas. Por ejemplo,
-- finalizado [0,0,0,0,0] == True
-- finalizado [1,3,0,0,1] == False
-- ----------------------------------------------------------------------------
- Álvaro Galisteo:
finalizado :: Tablero -> Bool
finalizado t = all (== 0) t
-- ----------------------------------------------------------------------------
-- Ejercicio 2. Definir la función
-- jugada :: Tablero -> Int -> Int -> Tablero
-- tal que '(jugada t m n)' es el tablero obtenido a partir del tablero 't'
-- eliminando 'n' piezas del montón 'm'. Se considera que 'm' es un montón
-- válido para el tablero 't' con al menos 'n' piezas. Por ejemplo,
-- jugada [4,3,2,1,0] 2 1 == [4,2,2,1,0]
-- ----------------------------------------------------------------------------
- Álvaro Galisteo:
jugada :: Tablero -> Int -> Int -> Tablero
jugada t m n = take (m-1) t ++ [(t !! (m-1)) - n] ++ drop m t
-- ----------------------------------------------------------------------------
-- Ejercicio 3. Definir la función
-- piezas :: Int -> String
-- tal que '(piezas n)' es una cadena que representa un montón con 'n' piezas.
-- Por ejemplo,
-- piezas 3 == " * * *"
-- ----------------------------------------------------------------------------
- Álvaro Galisteo:
piezas :: Int -> String
piezas 0 = ""
piezas n = " *" ++ piezas (n-1)
-- ----------------------------------------------------------------------------
-- Ejercicio 4. Definir la acción
-- escribeMonton :: Int -> Int -> IO ()
-- tal que '(escribeMonton m n)' muestra en pantalla el contenido del montón
-- 'm' con 'n' piezas. Por ejemplo,
-- escribeMonton 2 3 =>
-- 2: * * *
-- ----------------------------------------------------------------------------
- Álvaro Galisteo:
escribeMonton :: Int -> Int -> IO ()
escribeMonton m n = putStr ((show m) ++ ":" ++ (piezas n))
-- ----------------------------------------------------------------------------
-- Ejercicio 5. Definir la acción
-- escribeTablero :: Tablero -> IO ()
-- tal que '(escribeTablero t)' muestra en pantalla el contenido del tablero
-- 't'. Por ejemplo,
-- escribeTablero [3,4,1,0,1] =>
-- 1: * * *
-- 2: * * * *
-- 3: *
-- 4:
-- 5: *
-- ----------------------------------------------------------------------------
- Álvaro Galisteo:
escribeTablero :: Tablero -> IO ()
escribeTablero t = sequence_ [putStrLn ((show (n+1)) ++ ":" ++ (piezas (t!!n))) | n <- [0..(length t - 1)]]
-- ----------------------------------------------------------------------------
-- Ejercicio 6. Definir la acción
-- leeNumero :: String -> IO Int
-- tal que '(leeNumero xs)' muestra en pantalla una nueva línea con la cadena
-- 'xs', después lee una cadena y comprueba que la cadena leida es un número
-- natural. En este caso, devuelve el número natural correspondiente y en caso
-- contrario debe mostrar un mensaje informativo y volver a ejecutarse. Por
-- ejemplo,
-- leeNumero "Qué montón eliges? " =>
-- Qué montón eliges? 4
-- 4
-- leeNumero "Cuántas piezas coges? " =>
-- Cuantas piezas coges? c
-- ERROR: Entrada incorrecta
-- Cuantas piezas coges?
-- 3
-- ----------------------------------------------------------------------------
- Álvaro Galisteo:
leeNumero :: String -> IO Int
leeNumero xs = do putStr xs
x <- getLine
if and [elem y numero | y <- x]
then return (read x :: Int)
else do putStr "ERROR: Entrada incorrecta \n"
leeNumero xs
where numero = "0123456789"
-- ----------------------------------------------------------------------------
-- Ejercicio 7. Definir la acción
-- eligeMonton :: Tablero -> IO Int
-- tal que '(eligeMonton t)' devuelve un número entero correspondiente a un
-- montón de los del tablero 't' que tenga un número positivo (no nulo) de
-- piezas, leido con la función 'leeNumero'. Si el valor leido no se
-- corresponde con un montón del tablero 't' o se corresponde con un montón
-- que no tiene piezas, se debe mostrar un mensaje informativo y volver a
-- ejecutarse. Por ejemplo,
-- eligeMonton [1,2,0,2,1] =>
-- Qué montón eliges? c
-- ERROR: Entrada incorrecta
-- Qué montón eliges? 6
-- ERROR: Número de montón incorrecto
-- Qué montón eliges? 3
-- ERROR: El montón está vacío
-- Qué montón eliges? 2
-- 2
-- ----------------------------------------------------------------------------
- Álvaro Galisteo:
eligeMonton :: Tablero -> IO Int
eligeMonton t = do x <- leeNumero "Qué montón eliges? "
if x > (length t)
then do putStr "ERROR: Número de montón incorrecto \n"
eligeMonton t
else if t !! (x-1) == 0
then do putStr "ERROR: El montón está vacío \n"
eligeMonton t
else return x
-- ----------------------------------------------------------------------------
-- Ejercicio 8. Definir la acción
-- eligePiezas :: Tablero -> Int -> IO Int
-- tal que '(eligePiezas t m)' devuelve un número entero correspondiente a un
-- conjunto de piezas del montón 'm' en el tablero 't', leido con la función
-- 'leeNumero'. Si el valor leido es cero o excede del número de piezas del
-- montón 'm' en el tablero 't', se debe mostrar un mensaje informativo y
-- volver a ejecutarse. Por ejemplo,
-- eligePiezas [1,2,0,2,1] 2 =>
-- Cuántas piezas coges? c
-- ERROR: Entrada incorrecta
-- Cuántas piezas coges? 0
-- ERROR: Número de piezas incorrecto
-- Cuántas piezas coges? 4
-- ERROR: Número de piezas incorrecto
-- Cuántas piezas coges? 2
-- 2
-- ----------------------------------------------------------------------------
- Álvaro Galisteo:
eligePiezas :: Tablero -> Int -> IO Int
eligePiezas t m = do x <- leeNumero " Cuántas piezas coges? "
if x > (t!!(m-1)) || x == 0
then do putStr "ERROR: Número de piezas incorrecto \n"
eligePiezas t m
else return x
-- ----------------------------------------------------------------------------
-- Ejercicio 9. Los jugadores se representan por los números 1 y 2. Definir
-- la función
-- cambiaJugador :: Int -> Int
-- tal que '(cambiaJugador j)' es el jugador distinto a 'j'.
-- ----------------------------------------------------------------------------
- Álvaro Galisteo:
cambiaJugador :: Int -> Int
cambiaJugador 1 = 2
cambiaJugador 2 = 1
-- ----------------------------------------------------------------------------
-- Ejercicio 10. Definir la acción
-- juegoNim :: Tablero -> Int -> IO ()
-- tal que '(juegoNim t j)' es el juego para dos jugadores desarrollado a
-- partir del tablero 't' y el turno del jugador 'j'. Por ejemplo,
-- juegoNim [0,1,0,1,0] 2 =>
--
-- 1:
-- 2: *
-- 3:
-- 4: *
-- 5:
--
-- Turno del jugador 2
-- Qué montón eliges? 2
-- Cuántas piezas coges? 1
--
-- 1:
-- 2:
-- 3:
-- 4: *
-- 5:
--
-- Turno del jugador 1
-- Qué montón eliges? 4
-- Cuántas piezas coges? 1
--
-- 1:
-- 2:
-- 3:
-- 4:
-- 5:
--
-- Ha ganado el jugador 1
-- ----------------------------------------------------------------------------
- Álvaro Galisteo:
juegoNim :: Tablero -> Int -> IO ()
juegoNim t j = do escribeTablero t
putStrLn ("Turno del jugador " ++ show j)
m <- eligeMonton t
n <- eligePiezas t m
if finalizado (jugada t m n)
then putStrLn ("Ha ganado el jugador " ++ show j)
else juegoNim (jugada t m n) (cambiaJugador j)
-- ----------------------------------------------------------------------------
-- Ejercicio 11. Definir la función
-- listaNumeros :: String -> [Int]
-- tal que '(listaNumeros xs)' es la lista de números enteros positivos que
-- forman la cadena 'xs', separados por espacios en blanco. En caso de que la
-- cadena 'xs' contenga algo que no sea un número o espacios en blanco, debe
-- devolver la lista vacía. Por ejemplo,
-- listaNumeros "1 2 3 4 5" == [1,2,3,4,5]
-- listaNumeros "1 2 a b c" == []
-- listaNumeros "" == []
-- ----------------------------------------------------------------------------
- Álvaro Galisteo:
listaNumeros :: String -> [Int]
listaNumeros "" = []
listaNumeros xs = if and [isDigit y || y == ' ' | y <- xs]
then [(read x :: Int)] ++ listaNumeros (drop (length x + 1) xs)
else []
where x = takeWhile (/= ' ') xs
-- ----------------------------------------------------------------------------
-- Ejercicio 12. Definir la acción
-- nim :: IO ()
-- consistente en una partida del Nim entre dos jugadores. Por ejemplo,
-- nim =>
-- Escribe la lista de números de piezas de cada montón: a b
-- ERROR: La lista de números es incorrecta
-- Escribe la lista de números de piezas de cada montón: 2 3 4
--
-- 1: * *
-- 2: * * *
-- 3: * * * *
--
-- Turno del jugador 1
-- Qué montón eliges? 3
-- Cuántas piezas coges? 3
--
-- 1: * *
-- 2: * * *
-- 3: *
--
-- Turno del jugador 2
-- Qué montón eliges? 3
-- Cuántas piezas coges? 1
--
-- 1: * *
-- 2: * * *
-- 3:
--
-- Turno del jugador 1
-- Qué montón eliges? 2
-- Cuántas piezas coges? 2
--
-- 1: * *
-- 2: *
-- 3:
--
-- Turno del jugador 2
-- Qué montón eliges? 1
-- Cuántas piezas coges? 2
--
-- 1:
-- 2: *
-- 3:
--
-- Turno del jugador 1
-- Qué montón eliges? 2
-- Cuántas piezas coges? 1
--
-- 1:
-- 2:
-- 3:
--
-- Ha ganado el jugador 1
-- ----------------------------------------------------------------------------
- Álvaro Galisteo:
nim :: IO ()
nim = do putStr "Escribe la lista de números de piezas de cada montón: "
x <- getLine
if listaNumeros x == []
then do putStrLn "ERROR: La lista de números es incorrecta"
nim
else juegoNim (listaNumeros x) 1
-- ----------------------------------------------------------------------------
-- En el juego del Nim, un tablero perdedor es un tablero en el que el jugador
-- siempre pierde haga lo que haga, por ejemplo [1,1] o incluso [0], siempre
-- que el contrincante juege de la mejor manera posible. Por otro lado, un
-- tablero ganador es un tablero en el que el jugador puede realizar una
-- elección de piezas que da lugar a un tablero perdedor, por ejemplo [1,2] o
-- incluso [2].
--
-- Una estrategia ganadora consiste en identificar una propiedad que se cumpla
-- únicamente en los tableros perdedores y tal que, ante un tablero ganador,
-- permita decidir qué movimiento se ha de hacer para dar lugar a un tablero
-- perdedor. De esta forma, siempre que no tengamos un tablero ganador,
-- podremos hacer un movimiento que lo transforme en un tablero perdedor,
-- dejando dicha situación al contrincante.
--
-- En el juego del Nim, la propiedad que da lugar a la estrategia ganadora
-- consiste en comprobar que en las descomposiciones como suma de potencias
-- distintas de base 2 de las cantidades de piezas de cada montón, hay una
-- cantidad par de potencias del mismo exponente. Por ejemplo,
-- ·) En el tablero [1,2,3], 1 y 2 ya son potencias de 2 y 3 = 1+2. Por tanto
-- en las descomposiciones como suma de potencias distintas de base 2 de las
-- cantidades de este tablero hay dos 1 y dos 2. De aquí que el tablero sea
-- perdedor.
-- ·) En el tablero [3,5,6], 3 = 1+2, 5 = 1+4 y 6 = 2+4. Por tanto en las
-- descomposiciones como suma de potencias distintas de base 2 de las
-- cantidades de este tablero hay dos 1, dos 2 y dos 4. De aquí que el
-- tablero sea perdedor.
--
-- Para identificar la elección adecuada que da lugar a un tablero perdedor a
-- partir de un tablero ganador se actúa de la siguiente forma:
-- ·) Se descomponen como suma de potencias distintas de base 2 todas las
-- cantidades del tablero
-- ·) Se eliminan todas las parejas de potencias iguales, dejando sólo una
-- ocurrencia de las potencias que aparecen un número impar de veces
-- ·) Se escoge el montón al que pertenezca la potencia más alta que haya
-- quedado
-- ·) Se toma de dicho montón la diferencia entre la suma de las potencias que
-- hayan quedado en el montón elegido y la suma de las potencias que hayan
-- quedado en los montones restantes
-- ·) De esta forma en las descomposiciones como suma de potencias distintas de
-- base 2 de las cantidades del tablero resultante se dejan una cantidad par
-- de potencias del mismo exponente
--
-- Por ejemplo, dado el tablero [3,5,7], se tiene:
-- 3 = 1 + 2
-- 5 = 1 + 4
-- 7 = 1 + 2 + 4
-- Si quitamos las parejas de potencias iguales nos queda 1 en el tercer
-- montón. La elección adecuada sería una pieza del tercer montón.
--
-- Otro ejemplo, dado el tablero [3,6,8], se tiene:
-- 3 = 1 + 2
-- 6 = 2 + 4
-- 8 = 8
-- Si quitamos las parejas de potencias iguales nos queda 1 en el primer
-- montón, 4 en el segundo montón y 8 en el tercer montón. La elección adecuada
-- sería 8-(1+4) = 3 piezas del tercer montón.
--
-- En los siguientes ejercicios se desarrolla esta estrategia ganadora.
-- ----------------------------------------------------------------------------
-- ----------------------------------------------------------------------------
-- Ejercicio 13: Definir la función
-- descomposicionBase2 :: Int -> [Int]
-- tal que '(descomposicionBase2 n)' es una lista con la descomposición del
-- número natural 'n' como suma de potencias distintas de base 2. Por ejemplo:
-- descomposicionBase2 8 == [8]
-- descomposicionBase2 7 == [4,2,1]
-- descomposicionBase2 10 == [8,2]
-- ----------------------------------------------------------------------------
- Álvaro Galisteo:
descomposicionBase2 :: Int -> [Int]
descomposicionBase2 0 = []
descomposicionBase2 n = reverse (filter (/=0 ) [f (xs!!p) p | p <- [0..(length xs - 1)]])
where xs = (map (`rem` 2) ((takeWhile (/=1) (iterate (`div` 2) n)) ++ [1]))
f x y = if x == 1 then 2^y else 0
-- ----------------------------------------------------------------------------
-- Ejercicio 14: Definir la función
-- descomposicionTablero :: Tablero -> [(Int,Int)]
-- tal que '(descomposicionTablero t)' es la lista de parejas '(p,m)' formadas
-- por cada uno de los montones 'm' del tablero 't' y cada uno de los valores
-- que surgen de la descomposición en potencias distintas de base 2 del número
-- de piezas de dicho montón. Por ejemplo:
-- descomposicionTablero [8] == [(8,1)]
-- descomposicionTablero [8,5] == [(8,1),(4,2),(1,2)]
-- descomposicionTablero [8,5,3] == [(8,1),(4,2),(1,2),(2,3),(1,3)]
-- ----------------------------------------------------------------------------
- Álvaro Galisteo:
descomposicionTablero :: Tablero -> [(Int,Int)]
descomposicionTablero t = [(x,p) | p <- [1..(length t)], x <- descomposicionBase2 (t!!(p-1)) ]
-- ----------------------------------------------------------------------------
-- Ejercicio 15: Definir la función
-- reduceParejas :: [(Int,Int)] -> [(Int,Int)]
-- tal que '(reduceParejas pms)' es el resultado de eliminar de la lista de
-- parejas 'pms', todos los pares de elementos que representen la misma
-- potencia de 2 en dos montones de un tablero. Por ejemplo:
-- reduceParejas [(8,1),(4,2),(1,2),(2,3),(1,3)] == [(2,3),(4,2),(8,1)]
-- reduceParejas [(8,1),(2,2),(1,2),(2,3),(1,3)] == [(8,1)]
-- reduceParejas [(2,2),(1,2),(2,3),(1,3)] == []
-- ----------------------------------------------------------------------------
- Álvaro Galisteo:
reduceParejas :: [(Int,Int)] -> [(Int,Int)]
reduceParejas pms = aux pms [] []
where aux xs ys zs | xs == [] = zs
| elem (fst(head xs)) ys = aux (drop 1 xs) (filter (/= fst(head xs)) ys) (filter (f (fst(head xs))) zs)
| otherwise = aux (drop 1 xs) ([fst(head xs)] ++ ys) ([head xs] ++ zs)
f x y = fst y /= x
-- ----------------------------------------------------------------------------
-- Ejercicio 16: Definir la función
-- montonConMayorPotenciaDesparejada :: [(Int,Int)] -> Int
-- tal que '(montonConMayorPotenciaDesparejada pms)' es el número 'm' para el
-- que existe una pareja '(p,m)' en la lista no vacía de parejas 'pms', con un
-- mayor valor de 'p'. Por ejemplo,
-- montonConMayorPotenciaDesparejada [(2,3),(4,2),(8,1)] == 1
-- montonConMayorPotenciaDesparejada [(8,2),(4,1)] == 2
-- montonConMayorPotenciaDesparejada [(2,3)] == 3
-- ----------------------------------------------------------------------------
- Álvaro Galisteo:
montonConMayorPotenciaDesparejada :: [(Int,Int)] -> Int
montonConMayorPotenciaDesparejada pms = snd (head(filter (f (maximum [fst xs | xs <- pms])) pms))
where f x y = fst y == x
-- ----------------------------------------------------------------------------
-- Ejercicio 17: Definir la función
-- piezasSobrantes :: [(Int,Int)] -> Int -> Int
-- tal que '(piezasSobrantes pms m)' es la diferencia entre la suma de los
-- valores 'p' de las parejas de la forma '(p,m)' de la lista de parejas 'pms'
-- y la suma de los valores 'p' de las restantes parejas de 'pms'. Por ejemplo,
-- piezasSobrantes [(2,3),(4,2),(8,1)] 1 == 2
-- piezasSobrantes [(8,2),(4,1)] 2 == 4
-- piezasSobrantes [(2,3)] 3 == 2
-- ----------------------------------------------------------------------------
- Álvaro Galisteo:
piezasSobrantes :: [(Int,Int)] -> Int -> Int
piezasSobrantes pms m = sum [fst xs | xs <- (filter (f m) pms)] - sum [fst xs | xs <- (filter (f' m) pms)]
where f x y = snd y == x
f' x y = snd y /= x
-- ----------------------------------------------------------------------------
-- Ejercicio 18: Definir la función
-- buscaEleccionGanadora :: Tablero -> (Int,Int)
-- tal que '(buscaEleccionGanadora t)' es un par '(m,n)' donde 'm' es un número
-- de montón válido en el tablero 't',
-- entonces tras tomar 'n' piezas del montón 'm' en el tablero 't', el tablero
-- es perdedor. En caso de que el tablero original sea perdedor entonces se
-- devuelve el par '(m,1)' donde 'm' es un montón del tablero 't' con un número
-- de piezas maximal. Por ejemplo,
-- buscaEleccionGanadora [7,5,3] == (3,1)
-- buscaEleccionGanadora [8,4] == (1,4)
-- buscaEleccionGanadora [8,8] == (2,1)
-- buscaEleccionGanadora [7] == (1,7)
-- ----------------------------------------------------------------------------
- Álvaro Galisteo:
buscaEleccionGanadora :: Tablero -> (Int,Int)
buscaEleccionGanadora t = if x == []
then (montonConMayorPotenciaDesparejada (descomposicionTablero t),1)
else (y, piezasSobrantes x y)
where x = reduceParejas (descomposicionTablero t)
y = montonConMayorPotenciaDesparejada x
-- ----------------------------------------------------------------------------
-- Ejercicio 19: Definir la acción
-- juegoNimC :: Tablero -> Int -> IO ()
-- tal que '(juegoNimC t j)' es el juego para un jugador contra la computadora,
-- desarrollado a partir del tablero 't' y el turno del jugador 'j' (1 si es el
-- turno del jugador y 2 si es el turno de la computadora), en el que la
-- computadora utiliza la heurística ganadora. Por ejemplo,
-- juegoNimC [3,6,8] 1 =>
--
-- 1: * * *
-- 2: * * * * * *
-- 3: * * * * * * * *
--
-- Te toca jugar
-- Qué montón eliges? 3
-- Cuántas piezas coges? 3
--
-- 1: * * *
-- 2: * * * * * *
-- 3: * * * * *
--
-- Me toca jugar
--
-- 1: * * *
-- 2: * * * * *
-- 3: * * * * *
--
-- Te toca jugar
-- Qué montón eliges? 2
-- Cuántas piezas coges? 3
--
-- 1: * * *
-- 2: * *
-- 3: * * * * *
--
-- Me toca jugar
--
-- 1: * * *
-- 2: * *
-- 3: *
--
-- Te toca jugar
-- Qué montón eliges? 1
-- Cuántas piezas coges? 2
--
-- 1: *
-- 2: * *
-- 3: *
--
-- Me toca jugar
--
-- 1: *
-- 2:
-- 3: *
--
-- Te toca jugar
-- Qué montón eliges? 1
-- Cuántas piezas coges? 1
--
-- 1:
-- 2:
-- 3: *
--
-- Me toca jugar
--
-- 1:
-- 2:
-- 3:
--
-- He ganado
-- ----------------------------------------------------------------------------
- Álvaro Galisteo:
juegoNimC :: Tablero -> Int -> IO ()
juegoNimC t j = do putStr "\n"
escribeTablero t
putStr "\n"
if j == 2
then do putStrLn ("Me toca jugar ")
if finalizado (jugada t (fst x) (snd x))
then do putStr "\n"
escribeTablero (jugada t (fst x) (snd x))
putStr "\n"
putStrLn ("He ganado ")
else juegoNimC (jugada t (fst x) (snd x)) (cambiaJugador j)
else do putStrLn ("Te toca jugar ")
m <- eligeMonton t
n <- eligePiezas t m
if finalizado (jugada t m n)
then do putStr "\n"
escribeTablero (jugada t m n)
putStr "\n"
putStrLn ("Has ganado ")
else juegoNimC (jugada t m n) (cambiaJugador j)
where x = buscaEleccionGanadora t
-- ----------------------------------------------------------------------------
-- Ejercicio 20: Definir la acción
-- nimC :: IO ()
-- consistente en una partida del Nim entre un jugador y la computadora, que
-- usa la estrategia ganadora descrita anteriormente. Por ejemplo,
-- nimC =>
-- Escribe la lista de números de piezas de cada montón: 3 5 7
-- Quién empieza a jugar, tú (1) o yo (2)? 2
-- Suerte, te va a hacer falta ...
--
-- 1: * * *
-- 2: * * * * *
-- 3: * * * * * * *
--
-- Me toca jugar
--
-- 1: * * *
-- 2: * * * * *
-- 3: * * * * * *
--
-- Te toca jugar
-- Qué montón eliges? 3
-- Cuántas piezas coges? 2
--
-- 1: * * *
-- 2: * * * * *
-- 3: * * * *
--
-- Me toca jugar
--
-- 1: *
-- 2: * * * * *
-- 3: * * * *
--
-- Te toca jugar
-- Qué montón eliges? 2
-- Cuántas piezas coges? 2
--
-- 1: *
-- 2: * * *
-- 3: * * * *
--
-- Me toca jugar
--
-- 1: *
-- 2: * * *
-- 3: * *
--
-- Te toca jugar
-- Qué montón eliges? 2
-- Cuántas piezas coges? 2
--
-- 1: *
-- 2: *
-- 3: * *
--
-- Me toca jugar
--
-- 1: *
-- 2: *
-- 3:
--
-- Te toca jugar
-- Qué montón eliges? 1
-- Cuántas piezas coges? 1
--
-- 1:
-- 2: *
-- 3:
--
-- Me toca jugar
--
-- 1:
-- 2:
-- 3:
--
-- He ganado
-- ----------------------------------------------------------------------------
- Álvaro Galisteo:
nimC :: IO ()
nimC =do putStr "Escribe la lista de números de piezas de cada montón: "
t <- getLine
if listaNumeros t == []
then do putStrLn "ERROR: La lista de números es incorrecta"
nimC
else do j <- leeNumero "Quién empieza a jugar, tú (1) o yo (2)? "
if j/=1 && j/=2
then do putStrLn "ERROR: El número es incorrecto "
nimC
else do putStrLn "Suerte, te va a hacer falta ... "
juegoNimC (listaNumeros t) j
-- ============================================================================