Difference between revisions of "99 questions/80 to 89"
RossPaterson (talk | contribs) m (new URL) |
|||
| Line 29: | Line 29: | ||
== Problem 81 == |
== Problem 81 == |
||
| + | Path from one node to another one |
||
| − | <Problem description> |
||
| + | Write a function that, given two nodes a and b in a graph, returns all the acyclic paths from a to b. |
||
| − | |||
<pre> |
<pre> |
||
Example: |
Example: |
||
| Line 36: | Line 36: | ||
Example in Haskell: |
Example in Haskell: |
||
| + | paths 1 4 [(1,2),(2,3),(1,3),(3,4),(4,2),(5,6)] |
||
| − | <example in Haskell> |
||
| + | [[1,2,3,4],[1,3,4]] |
||
| + | paths 2 6 [(1,2),(2,3),(1,3),(3,4),(4,2),(5,6)] |
||
| + | [] |
||
</pre> |
</pre> |
||
Solution: |
Solution: |
||
<haskell> |
<haskell> |
||
| + | import List (nub, elem) |
||
| − | <solution in haskell> |
||
| + | |||
| + | data Graph a = [(a,a)] |
||
| + | |||
| + | paths :: Eq a => a -> a -> [(a,a)] -> [[a]] |
||
| + | paths a b g = paths1 a b g [] |
||
| + | |||
| + | paths1 :: Eq a => a -> a -> [(a,a)] -> [a] -> [[a]] |
||
| + | paths1 a b g c = paths2 a b g c [ y | (x,y) <- g, x == a ] |
||
| + | |||
| + | paths2 :: Eq a => a -> a -> [(a,a)] -> [a] -> [a] -> [[a]] |
||
| + | paths2 a b g c [] | a == b = [c++[b]] |
||
| + | | otherwise = [] |
||
| + | paths2 a b g c (x:xs) | a == b = [c++[b]] |
||
| + | | elem a c = [] |
||
| + | | otherwise = (paths1 x b g (c++[a])) ++ (paths2 a b g c xs) |
||
</haskell> |
</haskell> |
||
| + | This solution uses a representation of a (directed) graph as a list of arcs (a,b). |
||
| − | <description of implementation> |
||
== Problem 82 == |
== Problem 82 == |
||
Revision as of 10:10, 7 December 2007
This is part of Ninety-Nine Haskell Problems, based on Ninety-Nine Prolog Problems.
If you want to work on one of these, put your name in the block so we know someone's working on it. Then, change n in your block to the appropriate problem number, and fill in the <Problem description>,<example in lisp>,<example in Haskell>,<solution in haskell> and <description of implementation> fields.
Graphs
Problem 80
<Problem description>
Example: <example in lisp> Example in Haskell: <example in Haskell>
Solution:
<solution in haskell>
<description of implementation>
Problem 81
Path from one node to another one
Write a function that, given two nodes a and b in a graph, returns all the acyclic paths from a to b.
Example: <example in lisp> Example in Haskell: paths 1 4 [(1,2),(2,3),(1,3),(3,4),(4,2),(5,6)] [[1,2,3,4],[1,3,4]] paths 2 6 [(1,2),(2,3),(1,3),(3,4),(4,2),(5,6)] []
Solution:
import List (nub, elem)
data Graph a = [(a,a)]
paths :: Eq a => a -> a -> [(a,a)] -> [[a]]
paths a b g = paths1 a b g []
paths1 :: Eq a => a -> a -> [(a,a)] -> [a] -> [[a]]
paths1 a b g c = paths2 a b g c [ y | (x,y) <- g, x == a ]
paths2 :: Eq a => a -> a -> [(a,a)] -> [a] -> [a] -> [[a]]
paths2 a b g c [] | a == b = [c++[b]]
| otherwise = []
paths2 a b g c (x:xs) | a == b = [c++[b]]
| elem a c = []
| otherwise = (paths1 x b g (c++[a])) ++ (paths2 a b g c xs)
This solution uses a representation of a (directed) graph as a list of arcs (a,b).
Problem 82
<Problem description>
Example: <example in lisp> Example in Haskell: <example in Haskell>
Solution:
<solution in haskell>
<description of implementation>
Problem 83
<Problem description>
Example: <example in lisp> Example in Haskell: <example in Haskell>
Solution:
<solution in haskell>
<description of implementation>
Problem 84
<Problem description>
Example: <example in lisp> Example in Haskell: <example in Haskell>
Solution:
<solution in haskell>
<description of implementation>
Problem 85
<Problem description>
Example: <example in lisp> Example in Haskell: <example in Haskell>
Solution:
<solution in haskell>
<description of implementation>
Problem 86
<Problem description>
Example: <example in lisp> Example in Haskell: <example in Haskell>
Solution:
<solution in haskell>
<description of implementation>
Problem 87
<Problem description>
Example: <example in lisp> Example in Haskell: <example in Haskell>
Solution:
<solution in haskell>
<description of implementation>
Problem 88
<Problem description>
Example: <example in lisp> Example in Haskell: <example in Haskell>
Solution:
<solution in haskell>
<description of implementation>
Problem 89
<Problem description>
Example: <example in lisp> Example in Haskell: <example in Haskell>
Solution:
<solution in haskell>
<description of implementation>