Menu Close

Etiqueta: assocs

Búsqueda de la mina

José A. Alonso, ,

En este ejercicio, se representa un mapa mediante una lista de listas de la misma longitud donde todos sus elementos son 0 menos uno (que es un 1) que es donde se encuentra la mina. Por ejemplo, en el mapa

   0 0 0 0
   0 0 0 0
   0 1 0 0

la posición de la mina es (2,1).

Definir la función

   posicionMina :: [[Int]] -> (Int,Int)

tal que (posicionMina m) es la posición de la mina en el mapa m, Por ejemplo,

   posicionMina [[0,0,0,0],[0,0,0,0],[0,1,0,0]]  ==  (2,1)

Soluciones

import Data.List (elemIndex)
import Data.Array (assocs, listArray)
 
-- 1ª solución
posicionMina :: [[Int]] -> (Int,Int)
posicionMina xss = (length yss, length ys)
  where (yss,xs:_) = break (1 `elem`) xss
        ys         = takeWhile (/= 1) xs
 
-- 2ª solución
posicionMina2 :: [[Int]] -> (Int,Int)
posicionMina2 xss = divMod p (length (head xss))
  where Just p = elemIndex 1 (concat xss)
 
-- 3ª solución
posicionMina3 :: [[Int]] -> (Int,Int)
posicionMina3 xss =
  (fst . head . filter ((1 ==) . snd) . assocs) a
  where m = length xss - 1
        n = length (head xss) - 1
        a = listArray ((0,0),(m,n)) (concat xss)

Otras soluciones

  • Se pueden escribir otras soluciones en los comentarios.
  • El código se debe escribir entre una línea con <pre lang="haskell"> y otra con </pre>

Pensamiento

“La vida de un matemático está dominada por una insaciable curiosidad, un deseo que raya en la pasión por resolver los problemas que estudia.”

Jean Dieudonné.

Leer más →

Diccionario inverso

José A. Alonso, ,

El inverso de un diccionario d es el diccionario que a cada valor x le asigna la lista de claves cuyo valor en d es x. Por ejemplo, el inverso de

   [("a",3),("b",2),("c",3),("d",2),("e",1)])

es

   [(1,["e"]),(2,["d","b"]),(3,["c","a"])]

Definir la función

   inverso :: (Ord k, Ord v) => Map k v -> Map v [k]

tal que (inverso d) es el inverso del diccionario d. Por ejemplo,

   λ> inverso (fromList [("a",3),("b",2),("c",3),("d",2),("e",1)])
   fromList [(1,["e"]),(2,["d","b"]),(3,["c","a"])]
   λ> inverso (fromList [(x,x^2) | x <- [-3,-2..3]])
   fromList [(0,[0]),(1,[1,-1]),(4,[2,-2]),(9,[3,-3])]

Soluciones

import Data.Map ( Map
                , assocs
                , deleteFindMin
                , empty
                , fromList
                , fromListWith
                , insertWith
                )
import qualified Data.Map as M 
 
 
-- 1ª definición
inverso :: (Ord k, Ord v) => Map k v -> Map v [k]
inverso d = fromListWith (++) [(y,[x]) | (x,y) <- assocs d]
 
-- 2ª definición
inverso2 :: (Ord k, Ord v) => Map k v -> Map v [k]
inverso2 d
  | M.null d  = empty
  | otherwise = insertWith (++) y [x] (inverso2 e)
  where ((x,y),e) = deleteFindMin d
Leer más →

Perímetro más frecuente de triángulos rectángulos

José A. Alonso, ,

El grado perimetral de un número p es la cantidad de tres triángulos rectángulos de lados enteros cuyo perímetro es p. Por ejemplo, el grado perimetral de 120 es 3 ya que sólo hay 3 triángulos rectángulos de lados enteros cuyo perímetro es 120: {20,48,52}, {24,45,51} y {30,40,50}.

Definir la función

   maxGradoPerimetral :: Int -> (Int,[Int])

tal que (maxGradoPerimetral n) es el par (m,ps) tal que m es el máximo grado perimetral de los números menores o iguales que n y ps son los perímetros, menores o iguales que n, cuyo grado perimetral es m. Por ejemplo,

   maxGradoPerimetral   50  ==  (1,[12,24,30,36,40,48])
   maxGradoPerimetral  100  ==  (2,[60,84,90])
   maxGradoPerimetral  200  ==  (3,[120,168,180])
   maxGradoPerimetral  400  ==  (4,[240,360])
   maxGradoPerimetral  500  ==  (5,[420])
   maxGradoPerimetral  750  ==  (6,[720])
   maxGradoPerimetral  839  ==  (6,[720])
   maxGradoPerimetral  840  ==  (8,[840])
   maxGradoPerimetral 1500  ==  (8,[840,1260])
   maxGradoPerimetral 2000  ==  (10,[1680])
   maxGradoPerimetral 3000  ==  (12,[2520])

Soluciones

import Data.List
import Data.Array (accumArray, assocs)
 
-- 1ª solución                                                      --
-- ===========
 
maxGradoPerimetral1 :: Int -> (Int,[Int])
maxGradoPerimetral1 p = (m,[x | (n,x) <- ts, n == m])
    where ts    = [(length (triangulos x),x) | x <- [1..p]] 
          (m,_) = maximum ts 
 
-- (triangulos p) es el conjunto de triángulos rectángulos de perímetro
-- p. Por ejemplo,
--    triangulos 120  ==  [(20,48,52),(24,45,51),(30,40,50)]
triangulos :: Int -> [(Int,Int,Int)]
triangulos p = 
    [(a,b,c) | a <- [1..q],
               b <- [a..q],
               let c = p-a-b,
               a*a+b*b == c*c]
    where q = p `div` 2
 
-- 2ª solución                                                      --
-- ===========
 
maxGradoPerimetral2 :: Int -> (Int,[Int])
maxGradoPerimetral2 p = (m,[x | (n,x) <- ts, n == m])
    where ts    = [(n,x) | (x,n) <- numeroPerimetrosTriangulos p, n > 0]
          (m,_) = maximum ts 
 
-- (numeroPerimetrosTriangulos p) es la lista formado por los números de
-- 1 a p y la cantidad de triángulos rectángulos enteros cuyo perímetro
-- es dicho número. Por ejemplo,
--    ghci>  [(p,n) | (p,n) <- numeroPerimetrosTriangulos 70, n > 0]
--    [(12,1),(24,1),(30,1),(36,1),(40,1),(48,1),(56,1),(60,2),(70,1)]
numeroPerimetrosTriangulos :: Int -> [(Int,Int)] 
numeroPerimetrosTriangulos p = 
    assocs (accumArray (\x _ -> 1+x) 0 (1,p) (perimetrosTriangulos p))
 
-- (perimetrosTriangulos p) es la lista formada por los perímetros y los
-- lados de los triángulos rectángulos enteros cuyo perímetro es menor o
-- igual que p. Por ejemplo,
--    ghci> perimetrosTriangulos 70
--    [(12,(3,4,5)),   (30,(5,12,13)),(24,(6,8,10)),  (56,(7,24,25)),
--     (40,(8,15,17)), (36,(9,12,15)),(60,(10,24,26)),(48,(12,16,20)),
--     (60,(15,20,25)),(70,(20,21,29))]
perimetrosTriangulos :: Int -> [(Int,(Int,Int,Int))]
perimetrosTriangulos p =
    [(q,(a,b,c)) | a <- [1..p1],
                   b <- [a..p1],
                   esCuadrado (a*a+b*b), 
                   let c = raizCuadradaE (a*a+b*b), 
                   let q = a+b+c,
                   q <= p]
    where p1 = p `div` 2
 
-- (esCuadrado n) se verifica si n es un cuadrado. Por ejemplo,
--    esCuadrado 25  ==  True
--    esCuadrado 27  ==  False
esCuadrado :: Int -> Bool
esCuadrado n = a*a == n
    where a = raizCuadradaE n
 
-- (raizCuadradaE n) es la raíz cuadrada entera de n. Por ejemplo,
--    raizCuadradaE 25  ==  5
--    raizCuadradaE 27  ==  5
--    raizCuadradaE 35  ==  5
--    raizCuadradaE 36  ==  6
raizCuadradaE :: Int -> Int
raizCuadradaE = floor . sqrt . fromIntegral
 
-- 3ª solución                                                      --
-- ===========
 
maxGradoPerimetral3 :: Int -> (Int,[Int])
maxGradoPerimetral3 p = (m,[x | (n,x) <- ts, n == m])
    where ts    = [(n,x) | (x,n) <- numeroPerimetrosTriangulos2 p, n > 0]
          (m,_) = maximum ts 
 
-- (numeroPerimetrosTriangulos2 p) es la lista formado por los números de
-- 1 a p y la cantidad de triángulos rectángulos enteros cuyo perímetro
-- es dicho número. Por ejemplo,
--    ghci>  [(p,n) | (p,n) <- numeroPerimetrosTriangulos2 70, n > 0]
--    [(12,1),(24,1),(30,1),(36,1),(40,1),(48,1),(56,1),(60,2),(70,1)]
numeroPerimetrosTriangulos2 :: Int -> [(Int,Int)] 
numeroPerimetrosTriangulos2 p = 
    [(head xs, length xs) | xs <- group (sort (perimetrosTriangulos2 p))]
 
-- (perimetrosTriangulos2 p) es la lista formada por los perímetros de
-- los triángulos rectángulos enteros cuyo perímetro es menor o igual
-- que p. Por ejemplo, 
--    perimetrosTriangulos2 70  ==  [12,30,24,56,40,36,60,48,60,70]
perimetrosTriangulos2 :: Int -> [Int]
perimetrosTriangulos2 p =
    [q | a <- [1..p1],
         b <- [a..p1],
         esCuadrado (a*a+b*b), 
         let c = raizCuadradaE (a*a+b*b), 
         let q = a+b+c,
         q <= p]
    where p1 = p `div` 2
 
-- Comparación de eficiencia
-- =========================
 
-- La comparación es
--    ghci> maxGradoPerimetral1 1000
--    (8,[840])
--    (120.08 secs, 21116625136 bytes)
--    ghci> maxGradoPerimetral2 1000
--    (8,[840])
--    (0.66 secs, 132959056 bytes)
--    ghci> maxGradoPerimetral3 1000
--    (1000,[1])
--    (0.66 secs, 133443816 bytes)
Leer más →