Número de islas rectangulares de una matriz

5 Comentarios

1. Haskell

   numeroDeIslas :: Array (Int,Int) Int -> Int numeroDeIslas xs = recorre (1,1) xs [] where recorre (0,0) _ _ = 0 recorre p@(y,z) xs ys | a && b = 1 + recorre (sig p) xs (p:ys) | a = recorre (sig p) xs (p:ys) | otherwise = recorre (sig p) xs ys where a = xs!p == 1 b = not ((elem (y-1,z) ys)||(elem (y,z-1) ys)) sig (a,b) | (a,b) == (m,n) = (0,0) | a == m = (1,b+1) | otherwise = (a+1,b) where (m,n) = snd (bounds xs)

   1 2 3 4 5 6 7 8 9 10 11 12

   numeroDeIslas :: Array (Int,Int) Int -> Int numeroDeIslas xs = recorre (1,1) xs []     where recorre (0,0) _ _ = 0           recorre p@(y,z) xs ys | a && b = 1 + recorre (sig p) xs (p:ys)                                 | a = recorre (sig p) xs (p:ys)                                 | otherwise = recorre (sig p) xs ys                where a = xs!p == 1                      b = not ((elem (y-1,z) ys)||(elem (y,z-1) ys))           sig (a,b) | (a,b) == (m,n) = (0,0)                     | a == m = (1,b+1)                     | otherwise = (a+1,b)               where (m,n) = snd (bounds xs)

   Responder

2. Haskell

   import Data.Array numeroDeIslas :: Array (Int,Int) Int -> Int numeroDeIslas p = aux p (1,1) [] aux :: Array (Int,Int) Int -> (Int,Int) -> [(Int,Int)] -> Int aux p (i,j) xs | (i,j) == snd (bounds p) = 0 | j > snd (snd (bounds p)) = aux p (i+1,1) xs | p!(i,j) == 0 = aux p (i,j+1) xs | p!(i,j) == 1 && q = aux p (i,j+1) ((i,j):xs) | p!(i,j) == 1 && not q = aux p (i,j+1) ((i,j):xs) + 1 where q = (i-1,j) `elem` xs || (i,j-1) `elem` xs

   1 2 3 4 5 6 7 8 9 10 11 12 13

   import Data.Array   numeroDeIslas :: Array (Int,Int) Int -> Int numeroDeIslas p = aux p (1,1) []   aux :: Array (Int,Int) Int -> (Int,Int) -> [(Int,Int)] -> Int aux p (i,j) xs | (i,j) == snd (bounds p)   = 0                | j > snd (snd (bounds p)) = aux p (i+1,1) xs                | p!(i,j) == 0              = aux p (i,j+1) xs                | p!(i,j) == 1 && q         = aux p (i,j+1) ((i,j):xs)                | p!(i,j) == 1 && not q     = aux p (i,j+1) ((i,j):xs) + 1        where q = (i-1,j) `elem` xs || (i,j-1) `elem` xs

   Responder

3. Haskell

   numeroDeIslas :: Array (Int,Int) Int -> Int numeroDeIslas ax = (sum . concatMap compacta . agrupaColumnas . map compacta . agrupaFilas elementos) c where elementos = elems ax (a,(f,c)) = bounds ax compacta = concatMap (simplifica).group agrupaFilas :: [Int] -> Int -> [[Int]] agrupaFilas [] _ = [] agrupaFilas xs n = take n xs : agrupaFilas (drop n xs) n agrupaColumnas :: [[Int]] -> [[Int]] agrupaColumnas = M.toLists . M.transpose . M.fromLists simplifica :: [Int] -> [Int] simplifica (x:xs) | x == 1 = x : replicate (length xs) 0 | otherwise = x:xs

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

   numeroDeIslas :: Array (Int,Int) Int -> Int numeroDeIslas ax = (sum                  .  concatMap compacta                  .  agrupaColumnas                  .  map compacta                  .  agrupaFilas elementos) c               where                elementos = elems ax                (a,(f,c)) = bounds ax                compacta = concatMap (simplifica).group                               agrupaFilas :: [Int] -> Int -> [[Int]] agrupaFilas [] _ = [] agrupaFilas xs n = take n xs : agrupaFilas (drop n xs) n   agrupaColumnas :: [[Int]] -> [[Int]] agrupaColumnas = M.toLists . M.transpose . M.fromLists   simplifica :: [Int] -> [Int] simplifica (x:xs) | x == 1    = x : replicate (length xs) 0                 | otherwise = x:xs

   Responder

4. Se puede calcular la función delta y contar las subidas o bajas. Equivalentemente puede hacerse calculando la función XOR y dividir por dos el resultado o, ya que tenemos enteros, simplemente restar y contar las subidas.

   Haskell

   numeroDeIslas m = length$ filter (<0) $ concatMap (map head . group) $ zipWith (zipWith (-)) ([0,0..]:rs) rs where rs = rows m -- ¿no existe ésta para `Data.Array`? rows a = [(a!) <$> range ((y, u), (y, v)) | let ((r, u), (s, v)) = bounds a, y <-[r..s]]

   1 2 3 4 5

   numeroDeIslas m = length$ filter (<0) $ concatMap (map head . group) $ zipWith (zipWith (-)) ([0,0..]:rs) rs   where rs = rows m   -- ¿no existe ésta para `Data.Array`? rows a = [(a!) <$> range ((y, u), (y, v)) | let ((r, u), (s, v)) = bounds a, y <-[r..s]]

   Responder

5. Haskell

   unos [] =0 unos (x:xs)| x==1 =1+ unos (dropWhile (==1) xs) | otherwise = unos xs subconjuntos :: Integer-> [Integer]->[[Integer]] subconjuntos p [] =[] subconjuntos p xs =(genericTake p xs):(subconjuntos p (genericDrop p xs)) estimacionApriori a = sum(map unos (subconjuntos ((snd.snd.bounds) a) (elems a))) pulir (xs:[]) = 0 pulir (xs:ys:css) = genericLength (intersect (f xs) (f ys)) + pulir (ys:css) estimacionAposteriori a = estimacionApriori a - pulir (subconjuntos ((snd.snd.bounds) a) (elems a)) l xs = zip xs [1..] m [] = [] m ((x,y):ys) | x==0 = m ys |otherwise = (x,y) :(m ys) adyacentes [(x,y)] = [[(x,y)]] adyacentes( (a,b):(c,d):xss )| b+1==d =[(a,b),(c,d)]:adyacentes((c,d):xss) | otherwise = [(a,b)]:adyacentes((c,d):xss) adyacentes []=[] g :: [(Integer,Integer)]->[(Integer,Integer)]->Bool g xs ys = head(reverse xs) == (head ys) p ::[[(Integer,Integer)]] -> [[(Integer,Integer)]] p( xs:ys:xss) | g xs ys = nub(union xs ys):p (xss) | otherwise = xs:p (ys:xss) p[[(x,y)]]=[[(x,y)]] p []=[] p [xs]=[xs] f :: [Integer] -> [[(Integer,Integer)]] f xs= p(p(adyacentes(m(l xs))))

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40

   unos [] =0 unos (x:xs)| x==1 =1+ unos (dropWhile (==1) xs)            | otherwise = unos xs   subconjuntos :: Integer-> [Integer]->[[Integer]] subconjuntos p [] =[] subconjuntos p xs =(genericTake p xs):(subconjuntos p (genericDrop p xs))     estimacionApriori a = sum(map unos (subconjuntos ((snd.snd.bounds) a) (elems a)))   pulir (xs:[]) = 0 pulir (xs:ys:css) = genericLength (intersect (f xs) (f ys)) + pulir (ys:css)                  estimacionAposteriori a = estimacionApriori a - pulir (subconjuntos ((snd.snd.bounds) a) (elems a))   l xs = zip xs [1..]   m [] = [] m ((x,y):ys) | x==0 = m ys              |otherwise = (x,y) :(m ys)   adyacentes [(x,y)] = [[(x,y)]] adyacentes( (a,b):(c,d):xss )| b+1==d =[(a,b),(c,d)]:adyacentes((c,d):xss)                             | otherwise = [(a,b)]:adyacentes((c,d):xss) adyacentes []=[]   g :: [(Integer,Integer)]->[(Integer,Integer)]->Bool g xs ys = head(reverse xs) == (head ys)   p ::[[(Integer,Integer)]] -> [[(Integer,Integer)]] p( xs:ys:xss) | g xs ys = nub(union xs ys):p (xss)                  | otherwise = xs:p (ys:xss) p[[(x,y)]]=[[(x,y)]] p []=[] p [xs]=[xs]   f :: [Integer] -> [[(Integer,Integer)]] f xs= p(p(adyacentes(m(l xs))))

   Responder