Puntos alcanzables en un mapa

6 Comentarios

1. Haskell

   import qualified Data.Set as S import Data.Array import Data.List type Punto = (Int,Int) type Mapa = Array Punto Int alcanzables :: Mapa -> Punto -> [Punto] alcanzables p (i,j) = nub (aux (p!(i,j)) (S.fromList [(i,j)]) (i,j)) where aux a t (x,y) = (x,y):concatMap addM (filter q m) where addM = aux a (S.union (S.fromList m) t) q (x,y) = 1 <= x && x <= c && 1 <= y && y <= d && a == p!(x,y) && S.notMember (x,y) t m = [(x-1,y),(x+1,y),(x,y-1),(x,y+1)] (c,d) = (snd.bounds) p esAlcanzable :: Mapa -> Punto -> Punto -> Bool esAlcanzable p a b = elem b (alcanzables p a)

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

   import qualified Data.Set as S import Data.Array import Data.List type Punto = (Int,Int) type Mapa  = Array Punto Int   alcanzables :: Mapa -> Punto -> [Punto] alcanzables p (i,j) = nub (aux  (p!(i,j)) (S.fromList [(i,j)]) (i,j))      where aux a t (x,y) = (x,y):concatMap addM (filter q m)             where  addM = aux a (S.union (S.fromList m) t)                    q (x,y) = 1 <= x && x <= c && 1 <= y && y <= d && a == p!(x,y) && S.notMember (x,y) t                    m = [(x-1,y),(x+1,y),(x,y-1),(x,y+1)]                    (c,d) = (snd.bounds) p   esAlcanzable :: Mapa -> Punto -> Punto -> Bool                   esAlcanzable p a b = elem b (alcanzables p a)

   Responder

2. Haskell

   {-# LANGUAGE FlexibleContexts #-} import Data.Set import Data.Array import Control.Monad.Writer type Punto = (Int,Int) type Mapa = Array Punto Int dirs = [(1,0),(-1,0),(0,1),(0,-1)] alcanzables :: Mapa ->Punto ->[Punto] alcanzables m p = execWriter $ rec empty p where ((xm, ym), (xM, yM)) = bounds m rec s q@(x,y) = if xm <= x && x <= xM && ym <= y && y <= yM && notMember q s && m!p == m!q then tell [q] >> foldM (\s' (u,v) ->rec s' (x+u,y+v)) (insert q s) dirs else return s esAlcanzable :: Mapa ->Punto ->Punto ->Bool esAlcanzable m p q = any (q==) (alcanzables m p)

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

   {-# LANGUAGE FlexibleContexts #-} import Data.Set import Data.Array import Control.Monad.Writer   type Punto = (Int,Int) type Mapa  = Array Punto Int   dirs = [(1,0),(-1,0),(0,1),(0,-1)]   alcanzables :: Mapa ->Punto ->[Punto] alcanzables m p = execWriter $ rec empty p   where ((xm, ym), (xM, yM)) = bounds m         rec s q@(x,y) =           if xm <= x && x <= xM && ym <= y && y <= yM && notMember q s && m!p == m!q             then tell [q] >> foldM (\s' (u,v) ->rec s' (x+u,y+v)) (insert q s) dirs             else return s   esAlcanzable :: Mapa ->Punto ->Punto ->Bool esAlcanzable m p q = any (q==) (alcanzables m p)

   Responder

3. A lo loco xD

   Haskell

   alcanzables :: Mapa ->Punto ->[Punto] alcanzables m p = foldl (const.nub.rec) [p] [1..length(indices m)] where rec ps = [q | p@(x,y) <-ps, q@(u,v) <-indices m, abs(x-u) + abs(y-v) < 2, m!q == m!p]

   1 2 3

   alcanzables :: Mapa ->Punto ->[Punto] alcanzables m p = foldl (const.nub.rec) [p] [1..length(indices m)]   where rec ps = [q | p@(x,y) <-ps, q@(u,v) <-indices m, abs(x-u) + abs(y-v) < 2, m!q == m!p]

   Responder

4. (No llega al último caso)

   Haskell

   alcanzables :: Mapa -> Punto -> [Punto] alcanzables m (a,b) = nub ((a,b):(aux [] (a,b))) where aux ys (a,b) | subconjunto v ys = ys | otherwise = concatMap (aux (v++ys)) v where v = vecinosValidos m (a,b) subconjunto :: Eq a => [a] -> [a] -> Bool subconjunto xs ys = all (`elem` ys) xs vecinos :: Mapa -> Punto -> [Punto] vecinos m (a,b) = [(i,j) | i <- [a-1..a+1], j <- [b-1..b+1], i/= a || j/= b, rangoValido m (i,j), i/=a-1 || j/= b+1, i/=a+1 || j/=b-1, i/= a-1 ||j/=b-1, i/=a+1 || j/= b+1] rangoValido :: Mapa -> Punto -> Bool rangoValido m (i,j) = inRange x i && inRange y j where x = (fst (fst (bounds m)), fst (snd (bounds m))) y = (fst (fst (bounds m)), snd (snd (bounds m))) vecinosValidos :: Mapa -> Punto -> [Punto] vecinosValidos m (a,b) = [(i,j) | (i,j) <- (vecinos m (a,b)), m!(i,j) == m!(a,b)] esAlcanzable :: Mapa -> Punto -> Punto -> Bool esAlcanzable m p1 p2 = elem p2 (alcanzables m p1)

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

   alcanzables :: Mapa -> Punto -> [Punto] alcanzables m (a,b) = nub ((a,b):(aux [] (a,b)))   where aux ys (a,b) | subconjunto v ys = ys                      | otherwise = concatMap (aux (v++ys)) v                        where v = vecinosValidos m (a,b)   subconjunto :: Eq a => [a] -> [a] -> Bool subconjunto xs ys = all (`elem` ys) xs     vecinos :: Mapa -> Punto -> [Punto] vecinos m (a,b) = [(i,j) | i <- [a-1..a+1], j <- [b-1..b+1], i/= a || j/= b, rangoValido m (i,j), i/=a-1 || j/= b+1, i/=a+1 || j/=b-1, i/= a-1 ||j/=b-1, i/=a+1 || j/= b+1]   rangoValido :: Mapa -> Punto -> Bool rangoValido m (i,j) = inRange x i && inRange y j                   where x = (fst (fst (bounds m)), fst (snd (bounds m)))                         y = (fst (fst (bounds m)), snd (snd (bounds m)))   vecinosValidos :: Mapa -> Punto -> [Punto] vecinosValidos m (a,b) = [(i,j) | (i,j) <- (vecinos m (a,b)), m!(i,j) == m!(a,b)]   esAlcanzable :: Mapa -> Punto -> Punto -> Bool esAlcanzable m p1 p2 = elem p2 (alcanzables m p1)

   Responder

   1. Usando para alcanzables la librería Set si llega al último caso (aunque tarda bastante más de un segundo)

      Haskell

      alcanzables :: Mapa -> Punto -> [Punto] alcanzables m (a,b) = nub ((a,b):(aux (empty) (a,b))) where aux c (a,b) | member (a,b) c = toList c |otherwise = concatMap (aux (S.insert (a,b) c)) v where v = vecinosValidos m (a,b)

      1 2 3 4 5

      alcanzables :: Mapa -> Punto -> [Punto] alcanzables m (a,b) = nub ((a,b):(aux (empty) (a,b)))   where aux c (a,b) | member (a,b) c = toList c                     |otherwise = concatMap (aux (S.insert (a,b) c)) v                        where v = vecinosValidos m (a,b)

      Responder

5. Haskell

   import Data.List import Data.Array type Punto = (Int,Int) type Mapa = Array Punto Int alcanzables :: Mapa -> Punto -> [Punto] alcanzables ma p = agente ma p (ma ! p) (bounds ma) [] agente ::Mapa -> Punto -> Int -> (Punto,Punto) -> [Punto] -> [Punto] agente m p@(a,b) n r xs = (mover m (a,b-1) n r . mover m (a,b+1) n r . mover m (a-1,b) n r . mover m (a+1,b) n r) (p:xs) correcto :: Mapa -> Punto -> Int -> (Punto,Punto) -> [Punto] -> Bool correcto m p@(x,y) n ((a,b),(c,d)) xs = a<= x && x <= c && b<= y && y <= d && p `notElem` xs && (m!p) == n mover :: Mapa -> Punto -> Int -> (Punto,Punto) -> [Punto] -> [Punto] mover m d n r ys = if correcto m d n r ys then agente m d n r ys else ys esAlcanzable :: Mapa -> Punto -> Punto -> Bool esAlcanzable m p1 p2 = p1 `elem` alcanzables m p2

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

   import Data.List import Data.Array   type Punto = (Int,Int) type Mapa  = Array Punto Int   alcanzables :: Mapa -> Punto -> [Punto] alcanzables ma p = agente ma p (ma ! p) (bounds ma) []   agente ::Mapa -> Punto -> Int -> (Punto,Punto) -> [Punto] -> [Punto] agente m p@(a,b) n r xs = (mover m (a,b-1) n r                         .  mover m (a,b+1) n r                         .  mover m (a-1,b) n r                         .  mover m (a+1,b) n r) (p:xs)   correcto :: Mapa -> Punto -> Int -> (Punto,Punto) -> [Punto] -> Bool correcto m p@(x,y) n ((a,b),(c,d)) xs = a<= x && x <= c && b<= y && y <= d && p `notElem` xs && (m!p) == n   mover  :: Mapa -> Punto -> Int -> (Punto,Punto) -> [Punto] -> [Punto] mover m d n r ys = if correcto m d n r ys then agente m d n r ys else ys   esAlcanzable :: Mapa -> Punto -> Punto -> Bool esAlcanzable m p1 p2 = p1 `elem` alcanzables m p2

   Responder