Personal tools

99 questions/80 to 89

From HaskellWiki

< 99 questions(Difference between revisions)
Jump to: navigation, search
m (new URL)
Line 29: Line 29:
 
== Problem 81 ==
 
== Problem 81 ==
   
<Problem description>
+
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.
 
<pre>
 
<pre>
 
Example:
 
Example:
Line 36: Line 36:
   
 
Example in Haskell:
 
Example in Haskell:
<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)]
  +
[]
 
</pre>
 
</pre>
   
 
Solution:
 
Solution:
 
<haskell>
 
<haskell>
<solution in haskell>
+
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)
 
</haskell>
 
</haskell>
   
<description of implementation>
+
This solution uses a representation of a (directed) graph as a list of arcs (a,b).
 
 
 
== 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.

1 Graphs

2 Problem 80

<Problem description>

Example:
<example in lisp>

Example in Haskell:
<example in Haskell>

Solution:

<solution in haskell>

<description of implementation>


3 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).

4 Problem 82

<Problem description>

Example:
<example in lisp>

Example in Haskell:
<example in Haskell>

Solution:

<solution in haskell>

<description of implementation>

5 Problem 83

<Problem description>

Example:
<example in lisp>

Example in Haskell:
<example in Haskell>

Solution:

<solution in haskell>

<description of implementation>

6 Problem 84

<Problem description>

Example:
<example in lisp>

Example in Haskell:
<example in Haskell>

Solution:

<solution in haskell>

<description of implementation>

7 Problem 85

<Problem description>

Example:
<example in lisp>

Example in Haskell:
<example in Haskell>

Solution:

<solution in haskell>

<description of implementation>

8 Problem 86

<Problem description>

Example:
<example in lisp>

Example in Haskell:
<example in Haskell>

Solution:

<solution in haskell>

<description of implementation>

9 Problem 87

<Problem description>

Example:
<example in lisp>

Example in Haskell:
<example in Haskell>

Solution:

<solution in haskell>

<description of implementation>

10 Problem 88

<Problem description>

Example:
<example in lisp>

Example in Haskell:
<example in Haskell>

Solution:

<solution in haskell>

<description of implementation>

11 Problem 89

<Problem description>

Example:
<example in lisp>

Example in Haskell:
<example in Haskell>

Solution:

<solution in haskell>

<description of implementation>