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]]