Caminos en una retícula

El problema de los caminos en una retícula consiste en, dada una retícula rectangular con m filas y n columnas, determinar todos los caminos para ir desde el vértice inferior izquierdo hasta el vértice superior derecho donde los movimientos permitidos son mover hacia el siguiente vértice a la derecha o arriba.

Por ejemplo, en la siguiente retícula un posible camino es el indicado en rojo.

Para representar los caminos se definen los siguientes tipos de datos:

    data Direccion = D | A deriving (Show, Eq)
    type Camino = [Direccion]

1 2	data Direccion = D \| A deriving (Show, Eq) type Camino = [Direccion]

Por tanto, el camino de la figura anterior se representa por la lista [D,D,A,D,A].

Definir las funciones

   caminos  :: Int -> Int -> [Camino]
   nCaminos :: Int -> Int -> Integer

1 2	caminos :: Int -> Int -> [Camino] nCaminos :: Int -> Int -> Integer

tales que

(caminos m n) es la lista de los caminos en una retícula rectangular con m filas y n columnas. Por ejemplo,

     λ> caminos 2 2
     [[A,A,D,D],[A,D,A,D],[A,D,D,A],[D,A,A,D],[D,A,D,A],[D,D,A,A]]
     λ> caminos 1 3
     [[A,A,A,D],[A,A,D,A],[A,D,A,A],[D,A,A,A]]
     λ> caminos 2 3
     [[A,A,A,D,D],[A,A,D,A,D],[A,A,D,D,A],[A,D,A,A,D],[A,D,A,D,A],[A,D,D,A,A],
      [D,A,A,A,D],[D,A,A,D,A],[D,A,D,A,A],[D,D,A,A,A]]

λ> caminos 2 2

[[A,A,D,D],[A,D,A,D],[A,D,D,A],[D,A,A,D],[D,A,D,A],[D,D,A,A]]

λ> caminos 1 3

[[A,A,A,D],[A,A,D,A],[A,D,A,A],[D,A,A,A]]

λ> caminos 2 3

[[A,A,A,D,D],[A,A,D,A,D],[A,A,D,D,A],[A,D,A,A,D],[A,D,A,D,A],[A,D,D,A,A],

[D,A,A,A,D],[D,A,A,D,A],[D,A,D,A,A],[D,D,A,A,A]]

(nCaminos m n) es el número de los caminos en una retícula rectangular con m filas y n columnas. Por ejemplo,

     nCaminos 2 2  ==  6
     nCaminos 1 3  ==  4
     nCaminos 2 3  ==  10
     length (show (nCaminos 20000 30000))  ==  14612
     length (show (nCaminos 30000 20000))  ==  14612

nCaminos 2 2 == 6

nCaminos 1 3 == 4

nCaminos 2 3 == 10

length (show (nCaminos 20000 30000)) == 14612

length (show (nCaminos 30000 20000)) == 14612

Soluciones

import Data.List (genericLength)

data Direccion = D | A deriving (Show, Eq)

type Camino = [Direccion]

-- Definición de caminos
-- =====================

caminos :: Int -> Int -> [Camino]
caminos 0 n = [replicate n A]
caminos m 0 = [replicate m D]
caminos m n = [A:xs | xs <- caminos m (n-1)] ++
              [D:xs | xs <- caminos (m-1) n]

-- 1ª definición de nCaminos
-- =========================

nCaminos1 :: Int -> Int -> Integer
nCaminos1 m n = genericLength (caminos m n)

-- 2ª definición de nCaminos
-- =========================

nCaminos2 :: Int -> Int -> Integer
nCaminos2 0 n = 1
nCaminos2 m 0 = 1
nCaminos2 m n = nCaminos2 m (n-1) + nCaminos2 (m-1) n

-- 3ª definición de nCaminos
-- =========================

-- Los caminos desde (0,0) a (m,n) son las permutaciones con repetición
-- de m veces la D y n veces la A. Por tanto, su número es
--    (m+n)! / m!*n!

nCaminos3 :: Int -> Int -> Integer
nCaminos3 m n = 
    fact (m+n) `div` (fact m * fact n)

fact :: Int -> Integer
fact n = product [1..fromIntegral n]

-- 4ª solución de nCaminos
-- =======================

nCaminos4 :: Int -> Int -> Integer
nCaminos4 m n = 
    product [a+1..a+b] `div` product [2..b]
    where m' = fromIntegral m
          n' = fromIntegral n
          a  = max m' n'
          b  = min m' n'

-- Comparación de eficiencia
-- =========================

--    λ> nCaminos1 10 10
--    184756
--    (3.50 secs, 656,909,648 bytes)
--    λ> nCaminos2 10 10
--    184756
--    (0.50 secs, 47,330,272 bytes)
--    λ> nCaminos3 10 10
--    184756
--    (0.01 secs, 0 bytes)
--    λ> nCaminos4 10 10
--    184756
--    (0.01 secs, 0 bytes)
-- 
--    λ> nCaminos2 10 15
--    3268760
--    (8.83 secs, 1,142,623,080 bytes)
--    λ> nCaminos3 10 15
--    3268760
--    (0.01 secs, 0 bytes)
--    λ> nCaminos4 10 15
--    3268760
--    (0.00 secs, 0 bytes)
--
--    λ> let n = 2*10^4 
--    (0.01 secs, 0 bytes)
--    λ> length (show (nCaminos3 n n))
--    12039
--    (8.41 secs, 2,369,767,480 bytes)
--    λ> length (show (nCaminos4 n n))
--    12039
--    (2.98 secs, 833,386,648 bytes)

import Data.List (genericLength)

data Direccion = D | A deriving (Show, Eq)

type Camino = [Direccion]

-- Definición de caminos

-- =====================

caminos :: Int -> Int -> [Camino]

caminos 0 n = [replicate n A]

caminos m 0 = [replicate m D]

caminos m n = [A:xs | xs <- caminos m (n-1)] ++

[D:xs | xs <- caminos (m-1) n]

-- 1ª definición de nCaminos

-- =========================

nCaminos1 :: Int -> Int -> Integer

nCaminos1 m n = genericLength (caminos m n)

-- 2ª definición de nCaminos

-- =========================

nCaminos2 :: Int -> Int -> Integer

nCaminos2 0 n = 1

nCaminos2 m 0 = 1

nCaminos2 m n = nCaminos2 m (n-1) + nCaminos2 (m-1) n

-- 3ª definición de nCaminos

-- =========================

-- Los caminos desde (0,0) a (m,n) son las permutaciones con repetición

-- de m veces la D y n veces la A. Por tanto, su número es

-- (m+n)! / m!*n!

nCaminos3 :: Int -> Int -> Integer

nCaminos3 m n =

fact (m+n) `div` (fact m * fact n)

fact :: Int -> Integer

fact n = product [1..fromIntegral n]

-- 4ª solución de nCaminos

-- =======================

nCaminos4 :: Int -> Int -> Integer

nCaminos4 m n =

product [a+1..a+b] `div` product [2..b]

where m' = fromIntegral m

n' = fromIntegral n

a = max m' n'

b = min m' n'

-- Comparación de eficiencia

-- =========================

-- λ> nCaminos1 10 10

-- 184756

-- (3.50 secs, 656,909,648 bytes)

-- λ> nCaminos2 10 10

-- 184756

-- (0.50 secs, 47,330,272 bytes)

-- λ> nCaminos3 10 10

-- 184756

-- (0.01 secs, 0 bytes)

-- λ> nCaminos4 10 10

-- 184756

-- (0.01 secs, 0 bytes)

-- λ> nCaminos2 10 15

-- 3268760

-- (8.83 secs, 1,142,623,080 bytes)

-- λ> nCaminos3 10 15

-- 3268760

-- (0.01 secs, 0 bytes)

-- λ> nCaminos4 10 15

-- 3268760

-- (0.00 secs, 0 bytes)

-- λ> let n = 2*10^4

-- (0.01 secs, 0 bytes)

-- λ> length (show (nCaminos3 n n))

-- 12039

-- (8.41 secs, 2,369,767,480 bytes)

-- λ> length (show (nCaminos4 n n))

-- 12039

-- (2.98 secs, 833,386,648 bytes)

7 Comentarios

import Data.List

data Direccion = D | A deriving (Show, Eq)
type Camino = [Direccion]


caminos  :: Int -> Int -> [Camino]
caminos x y = nub (permutations (replicate y A ++ replicate x D))

nCaminos :: Int -> Int -> Integer
nCaminos x y = 
  factoriales !! (x + y) `div` (factoriales !! x * factoriales !! y)


factoriales :: [Integer]
factoriales = map snd aux
    where aux = iterate f (1,1) where f (x,y) = (x+1,x*y)

import Data.List

data Direccion = D | A deriving (Show, Eq)

type Camino = [Direccion]

caminos :: Int -> Int -> [Camino]

caminos x y = nub (permutations (replicate y A ++ replicate x D))

nCaminos :: Int -> Int -> Integer

nCaminos x y =

factoriales !! (x + y) `div` (factoriales !! x * factoriales !! y)

factoriales :: [Integer]

factoriales = map snd aux

where aux = iterate f (1,1) where f (x,y) = (x+1,x*y)

Responder

import Data.List

data Direccion = D | A deriving (Show, Eq)
type Camino = [Direccion]

caminos  :: Int -> Int -> [Camino]
caminos m n = busca [(0,0,[])]
  where busca :: [(Int,Int,Camino)] -> [Camino]
        busca ((a,b,xs):xss)
         | a == m && b == n = reverse xs: busca xss
         | a == m           = busca ((a,b+1,A:xs):             xss)
         |           b == n = busca (             (a+1,b,D:xs):xss)
         | otherwise        = busca ((a,b+1,A:xs):(a+1,b,D:xs):xss)
        busca [] = []

nCaminos :: Int -> Int -> Integer
nCaminos m n = product [b+1..a+b] `div` product [1..a]
  where [a,b] = map fromIntegral $ sort [n,m]

import Data.List

data Direccion = D | A deriving (Show, Eq)

type Camino = [Direccion]

caminos :: Int -> Int -> [Camino]

caminos m n = busca [(0,0,[])]

where busca :: [(Int,Int,Camino)] -> [Camino]

busca ((a,b,xs):xss)

| a == m && b == n = reverse xs: busca xss

| a == m = busca ((a,b+1,A:xs): xss)

| b == n = busca ( (a+1,b,D:xs):xss)

| otherwise = busca ((a,b+1,A:xs):(a+1,b,D:xs):xss)

busca [] = []

nCaminos :: Int -> Int -> Integer

nCaminos m n = product [b+1..a+b] `div` product [1..a]

where [a,b] = map fromIntegral $ sort [n,m]

Responder

import Data.List

data Direccion = A | D deriving (Show, Eq)
type Camino = [Direccion]

caminos :: Int -> Int -> [Camino]
caminos m n = (nub . permutations) (replicate m D ++ replicate n A)

nCaminos :: Int -> Int -> Integer
nCaminos m n = div (f (m'+n')) (f m' * f n')
               where f  = factorial 
                     n' = toInteger n
                     m' = toInteger m

factorial :: Integer -> Integer
factorial n = product [1..n]

import Data.List

data Direccion = A | D deriving (Show, Eq)

type Camino = [Direccion]

caminos :: Int -> Int -> [Camino]

caminos m n = (nub . permutations) (replicate m D ++ replicate n A)

nCaminos :: Int -> Int -> Integer

nCaminos m n = div (f (m'+n')) (f m' * f n')

where f = factorial

n' = toInteger n

m' = toInteger m

factorial :: Integer -> Integer

factorial n = product [1..n]

Responder

caminos :: Int -> Int -> [Camino]
caminos m 0 = [replicate m A]
caminos 0 n = [replicate n D]
caminos m n = map (A:) (caminos (m-1) n) ++
              map (D:) (caminos m (n-1))

-- nCaminos es idéntica a la de fracruzam
nCaminos :: Int -> Int -> Integer
nCaminos m n = product [b+1..a+b] `div` product [1..a]
  where [a,b] = map fromIntegral $ sort [n,m]

caminos :: Int -> Int -> [Camino]

caminos m 0 = [replicate m A]

caminos 0 n = [replicate n D]

caminos m n = map (A:) (caminos (m-1) n) ++

map (D:) (caminos m (n-1))

-- nCaminos es idéntica a la de fracruzam

nCaminos :: Int -> Int -> Integer

nCaminos m n = product [b+1..a+b] `div` product [1..a]

where [a,b] = map fromIntegral $ sort [n,m]

Responder

Alejandro dice:

30-mayo-2016 a las 16:39

Están intercambiadas las A y las D.

Responder

Mediante búsqueda en espacios de estados (muy parecida a la de fracruzam):

import I1M.BusquedaEnEspaciosDeEstados

data Direccion = D | A deriving (Show, Eq)
type Camino = [Direccion]

caminos  :: Int -> Int -> [Camino]
caminos m n = map fst $ buscaEE sucesores esFinal ([],(0,0))
    where sucesores (xs,(x,y)) | x == m = [(D:xs,(x,y+1))]
                               | y == n = [(A:xs,(x+1,y))]
                               | otherwise = [(D:xs,(x,y+1)),(A:xs,(x+1,y))]
          esFinal x = snd x == (m,n)

import I1M.BusquedaEnEspaciosDeEstados

data Direccion = D | A deriving (Show, Eq)

type Camino = [Direccion]

caminos :: Int -> Int -> [Camino]

caminos m n = map fst $ buscaEE sucesores esFinal ([],(0,0))

where sucesores (xs,(x,y)) | x == m = [(D:xs,(x,y+1))]

| y == n = [(A:xs,(x+1,y))]

| otherwise = [(D:xs,(x,y+1)),(A:xs,(x+1,y))]

esFinal x = snd x == (m,n)

Responder

Alejandro dice:

30-mayo-2016 a las 16:43

Están intercambiadas las A y las D.

Responder

Caminos en una retícula

Soluciones

7 Comentarios

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico

Soluciones

Se puede imprimir o compartir con

7 Comentarios

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico