El Mastermind es un juego que consiste en deducir un c\u00f3digo num\u00e9rico formado por una lista de n\u00fameros. Cada vez que se empieza una partida, el programa debe elegir un c\u00f3digo, que ser\u00e1 lo que el jugador debe adivinar en la menor cantidad de intentos posibles. Cada intento consiste en una propuesta de un c\u00f3digo posible que propone el jugador, y una respuesta del programa. Las respuestas le dar\u00e1n pistas al jugador para que pueda deducir el c\u00f3digo.<\/p>\n
Estas pistas indican lo cerca que estuvo el n\u00famero propuesto de soluci\u00f3n a trav\u00e9s de dos valores: la cantidad de aciertos es la cantidad de d\u00edgitos que propuso el jugador que tambi\u00e9n est\u00e1n en el c\u00f3digo en la misma posici\u00f3n. La cantidad de coincidencias es la cantidad de d\u00edgitos que propuso el jugador que tambi\u00e9n est\u00e1n en el c\u00f3digo pero en una posici\u00f3n distinta.<\/p>\n
Por ejemplo, si el c\u00f3digo que eligi\u00f3 el programa es el [2,6,0,7] el jugador propone el [1,4,0,6], el programa le debe responder acierto (el 0, que est\u00e1 en el c\u00f3digo original en el mismo lugar, tercero), y una coincidencia (el 6, que tambi\u00e9n est\u00e1 en el original, pero en la segunda posici\u00f3n, no en el cuarto como fue propuesto). Si el jugador hubiera propuesto el [3,5,9,1], habr\u00eda obtenido como respuesta ning\u00fan acierto y ninguna coincidencia, ya que no hay n\u00fameros en com\u00fan con el c\u00f3digo original. Si se obtienen cuatro aciertos es porque el jugador adivin\u00f3 el c\u00f3digo y gan\u00f3 el juego.<\/p>\n
Definir la funci\u00f3n<\/p>\n
\n mastermind :: [Int] -> [Int] -> (Int,Int)\n<\/pre>\ntal que (mastermind xs ys) es el par formado por los n\u00fameros de aciertos y de coincidencias entre xs e ys. Por ejemplo,<\/p>\n
\n mastermind [3,3] [3,2] == (1,0)\n mastermind [3,5,3] [3,2,5] == (1,1)\n mastermind [3,5,3,2] [3,2,5,3] == (1,3)\n mastermind [3,5,3,3] [3,2,5,3] == (2,1)\n mastermind [1..10^6] [1..10^6] == (1000000,0)\n<\/pre>\nSoluciones<\/h4>\n\nimport qualified Data.Set as S\nimport Test.QuickCheck (quickCheck)\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\nmastermind :: [Int] -> [Int] -> (Int, Int)\nmastermind xs ys =\n (length (aciertos xs ys), length (coincidencias xs ys))\n\n-- (aciertos xs ys) es la lista de las posiciones de los aciertos entre\n-- xs e ys. Por ejemplo,\n-- aciertos [1,1,0,7] [1,0,1,7] == [0,3]\naciertos :: Eq a => [a] -> [a] -> [Int]\naciertos xs ys =\n [n | (n,x,y) <- zip3 [0..] xs ys, x == y]\n\n-- (coincidencia xs ys) es la lista de las posiciones de las\n-- coincidencias entre xs e ys. Por ejemplo,\n-- coincidencias [1,1,0,7] [1,0,1,7] == [1,2]\ncoincidencias :: Eq a => [a] -> [a] -> [Int]\ncoincidencias xs ys =\n [n | (n,y) <- zip [0..] ys,\n y `elem` xs,\n n `notElem` aciertos xs ys]\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\nmastermind2 :: [Int] -> [Int] -> (Int, Int)\nmastermind2 xs ys =\n (length aciertos2, length coincidencias2)\n where\n aciertos2, coincidencias2 :: [Int]\n aciertos2 = [n | (n,x,y) <- zip3 [0..] xs ys, x == y]\n coincidencias2 = [n | (n,y) <- zip [0..] ys, y `elem` xs, n `notElem` aciertos2]\n\n-- 3\u00aa soluci\u00f3n\n-- ===========\n\nmastermind3 :: [Int] -> [Int] -> (Int, Int)\nmastermind3 xs ys = aux xs ys\n where aux (u:us) (v:vs)\n | u == v = (a+1,b)\n | v `elem` xs = (a,b+1)\n | otherwise = (a,b)\n where (a,b) = aux us vs\n aux _ _ = (0,0)\n\n-- 4\u00aa soluci\u00f3n\n-- ===========\n\nmastermind4 :: [Int] -> [Int] -> (Int, Int)\nmastermind4 xs ys =\n (length aciertos4, length coincidencias4)\n where\n aciertos4, coincidencias4 :: [Int]\n aciertos4 = [n | (n,x,y) <- zip3 [0..] xs ys, x == y]\n xs' = S.fromList xs\n coincidencias4 = [n | (n,y) <- zip [0..] ys, y `S.member` xs', n `notElem` aciertos4]\n\n-- Equivalencia de las definiciones\n-- ================================\n\n-- La propiedad es\nprop_mastermind :: [Int] -> [Int] -> Bool\nprop_mastermind xs ys =\n all (== mastermind xs1 ys1)\n [mastermind2 xs1 ys1,\n mastermind3 xs1 ys1,\n mastermind4 xs1 ys1]\n where n = min (length xs) (length ys)\n xs1 = take n xs\n ys1 = take n ys\n\nverifica_mastermind :: IO ()\nverifica_mastermind = quickCheck prop_mastermind\n\n-- La comprobaci\u00f3n es\n-- \u03bb> verifica_mastermind\n-- +++ OK, passed 100 tests.\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- La comparaci\u00f3n es\n-- \u03bb> mastermind [1..10^4] (map (*2) [1..10^4])\n-- (0,5000)\n-- (14.17 secs, 11,209,750,408 bytes)\n-- \u03bb> mastermind2 [1..10^4] (map (*2) [1..10^4])\n-- (0,5000)\n-- (0.83 secs, 8,190,200 bytes)\n-- \u03bb> mastermind3 [1..10^4] (map (*2) [1..10^4])\n-- (0,5000)\n-- (0.61 secs, 7,339,232 bytes)\n-- \u03bb> mastermind4 [1..10^4] (map (*2) [1..10^4])\n-- (0,5000)\n-- (0.03 secs, 8,910,128 bytes)\n<\/pre>\n