Ir al contenido principal

Bosque de recorridos del autobús

En la librería Data.Tree se definen los árboles y los bosques como sigue

data Tree a   = Node a (Forest a)
type Forest a = [Tree a]

Se pueden definir árboles. Por ejemplo,

ejArbol1 = Node 3 [Node 5 [Node 9 []], Node 7 []]
ejArbol2 = Node 8 [Node 4 []]

También se pueden definir bosques. Por ejemplo,

ejBosque = [ejArbol1, ejArbol2]

Se pueden dibujar los bosques con la función drawForest. Por ejemplo,

λ> putStrLn (drawForest (map (fmap show) ejBosque))
3
|
+- 5
|  |
|  `- 9
|
`- 7

8
|
`- 4

Usando la notación de los ejercicios anteriores para las subidas y bajadas en el autobús, definir la función

bosqueRecorridos :: Int -> Int -> Forest (Int,Int)

tal que (bosqueRecorridos n m) es el bosque cuyas ramas son los recorridos correctos en un autobús de capacidad n y usando m paradas. Por ejemplo,

λ> putStrLn (drawForest (map (fmap show) (bosqueRecorridos 2 3)))
(0,0)
|
+- (0,0)
|  |
|  +- (0,0)
|  |
|  +- (1,0)
|  |
|  `- (2,0)
|
+- (1,0)
|  |
|  +- (0,0)
|  |
|  +- (0,1)
|  |
|  +- (1,0)
|  |
|  `- (1,1)
|
`- (2,0)
   |
   +- (0,0)
   |
   +- (0,1)
   |
   `- (0,2)

(1,0)
|
+- (0,0)
|  |
|  +- (0,0)
|  |
|  +- (0,1)
|  |
|  +- (1,0)
|  |
|  `- (1,1)
|
+- (0,1)
|  |
|  +- (0,0)
|  |
|  +- (1,0)
|  |
|  `- (2,0)
|
+- (1,0)
|  |
|  +- (0,0)
|  |
|  +- (0,1)
|  |
|  `- (0,2)
|
`- (1,1)
   |
   +- (0,0)
   |
   +- (0,1)
   |
   +- (1,0)
   |
   `- (1,1)

(2,0)
|
+- (0,0)
|  |
|  +- (0,0)
|  |
|  +- (0,1)
|  |
|  `- (0,2)
|
+- (0,1)
|  |
|  +- (0,0)
|  |
|  +- (0,1)
|  |
|  +- (1,0)
|  |
|  `- (1,1)
|
`- (0,2)
   |
   +- (0,0)
   |
   +- (1,0)
   |
   `- (2,0)

en donde la última rama representa el recorrido [(2,0),(0,2),(2,0)].


Soluciones

import Data.Tree

bosqueRecorridos :: Int -> Int -> Forest (Int,Int)
bosqueRecorridos n m = [Node (a,0) (siguientes a 1) | a <- [0..n]]
  where siguientes k p | p == m    = []
                       | otherwise = [Node (a,b) (siguientes (k+a-b) (p+1))
                                     | a <- [0..n-k]
                                     , b <- [0..k]]