Declaratieve Talen/oplossingWinkelen

--Data type voor Section
data Section = Section Int Int Int deriving (Show)
--Je zou ook een type declaratie kunnen maken voor de hele weg : type Kaart = [Section]


help_jan::[Section]->[(Char,Int)]
help_jan kaart = let
		   (bestApath, bestBpath) = zoekPaden kaart ([],[]) --je berkent de beste paden die je vanboven doen uit komen (de A kant) en voor beneden (B kant)
		  in
                    if((sum[x|(a,x)<-bestApath]) < (sum[x|(a,x)<-bestBpath]))
			then reverse bestApath -- want we hebben het pad achterstevoeren opgebouwd
		    else
			reverse bestBpath


zoekPaden::[Section]->([(Char,Int)],[(Char,Int)])->([(Char,Int)],[(Char,Int)])
zoekPaden [] (pathA ,pathB) = (pathA ,pathB) --Je bent aangekomen in je eindpunt
zoekPaden ( (Section n z b ):xs) (pathA,pathB) =  let 
						   forwardA = (n + (sum[x|(a,x)<-pathA]))	 -- je bevindt je aan de A kant en je gaat gewoon rechtdoor
						   crossOverA = (b + (z + (sum[x|(a,x)<-pathB])))-- je bevindt je aan de B kant en je gaat eerst over de brug en dan aan de A kan naar voor
						   forwardB = (z + (sum[x|(a,x)<-pathB]))	 -- idem
						   crossOverB = ( b+ (n + (sum[x|(a,x)<-pathA])))--idem
						   newA |(forwardA<crossOverA) = ([('N',n)]++pathA)--kies het korste pad naar de nieuwe knoop aan de A kant
						  	|otherwise  = ([('B',b),('Z',z)]++pathB)
						   newB |(forwardB<crossOverB) =([('Z',z)]++pathB)
						  	|otherwise =([('B',b),('N',n)]++pathA)
						in zoekPaden xs (newA,newB) -- Doe de volgende stap

--Greet

--Data type voor Section
data Section a= Section Int Int Int


helpJan::[Section Int]->[([Char],Int)]
helpJan ((Section n z b):xs)|z<n = [("Z",z)] ++ (helpJan2 [("Z",z)] b 2 xs)
			    |otherwise = [("N",n)] ++ (helpJan2 [("N",n)] b 1 xs)

helpJan2::[([Char],Int)]->Int->Int->[Section Int]->[([Char],Int)]
helpJan2 xs b i [] = []
helpJan2 xs b1 i ((Section n z b2):ys) = if (and [(i==1),(n <= (b1+z))]) then [("N",n)] ++ (helpJan2 (xs++[("B",b1),("N",n)]) b2 1 ys)
					 else if (and [(i==1),(n > (b1+z))]) then [("B",b1),("Z",z)] ++ (helpJan2 (xs++[("B",b1),("Z",z)]) b2 2 ys)
					 else if (and [(i==2),(z <= (b1+n))]) then [("Z",z)] ++ (helpJan2 (xs++[("Z",z)]) b2 2 ys)
					 else [("B",b1),("N",n)] ++ (helpJan2 ([("B",b1),("N",n)]) b2 1 ys)

--eerste geval: je zit in noord en de kortste weg is verder via noord
--tweede geval: je zit in noord en de kortste weg is verder via zuid
--derde geval: je zit in zuid en de kortste weg is verder via zuid
--vierde geval: je zit in zuid en de kortste weg is verder via noord

--Lynn 17 jan 2011 10:35 (UTC)

import Data.List
import Data.Ord

data Section = Section Int Int Int
data Direction = N | Z | B
	deriving (Show)

helpJan :: [Section] -> [(Direction,Int)]
helpJan xs = reverse $ minimumBy (comparing evaluate) (foldl f ([[],[]]) xs)
				where
					f :: [[(Direction,Int)]] -> Section -> [[(Direction,Int)]]						
					f [xs,ys] (Section a b c) = [newxs,newys]
						where
							newxs = minimumBy (comparing evaluate) [path1,path2] -- kortste pad naar noordkant
							newys = minimumBy (comparing evaluate) [path3,path4] -- kortste pad naar zuidkant
							path1 = (N,a) : xs			-- N -> N
							path2 = (B,c) : (Z,b) : ys		-- Z -> N
							path3 = (Z,b) : ys			-- Z -> Z
							path4 = (B,c) : (N,a) : xs		-- N -> Z

evaluate ::  [(Direction,Int)] -> Int 
evaluate = sum . map snd -- berekent totale afstand van pad

--Jeroen

data Section = Section Int Int Int
data Rhumb   = N | Z | B deriving (Show)

runProgram :: [Section] -> [(Rhumb,Int)]
runProgram sections =
    shortestPath northPath southPath
    where (north,south) = traverse sections [] []
          northPath     = reverse north
          southPath     = reverse south

shortestPath :: [(Rhumb,Int)] -> [(Rhumb,Int)] -> [(Rhumb,Int)]
shortestPath pathA pathB | (pathLength pathA) >= (pathLength pathB) = pathA
                         | otherwise                                = pathB
                         where pathLength p = sum $ [ x | (_,x) <- p]

traverse :: [Section] -> [(Rhumb,Int)] -> [(Rhumb,Int)] -> ([(Rhumb,Int)],[(Rhumb,Int)])
traverse [] north south                   = (north,south)
traverse ((Section n z b):xs) north south = let 
                                             northStraight = n
                                             southStraight = z
                                             crossNorth    = z + b
                                             crossSouth    = n + b
                                             newNorth | northStraight <= crossNorth = (N,n) : north
                                                      | otherwise                   = (B,b) : (Z,z) : south
                                             newSouth | southStraight <= crossSouth = (Z,z) : south
                                                      | otherwise                   = (B,b) : (N,n) : north
                                            in traverse xs newNorth newSouth

--Mathieu Cruts

Een tweede kortere versie

{--
    Example usage:
    
        run [Section 10 5 3, Section 20 30 2, Section 30 15 3, Section 10 8 0]
        [('S',5),('B',3),('N',20),('B',2),('S',15),('S',8),('B',0)]
--}

data Section = Section Int Int Int
type Path    = [(Char,Int)]

run :: [Section] -> Path
run = path [] []

path :: Path -> Path -> [Section] -> Path
path n s [] | costN <= costS = n
            | otherwise      = s
              where costN    = costPath n
                    costS    = costPath s
path w1 w2 ((Section n s b):xs) = let
                                     north | n <= s+b = w1++[('N',n)]
                                           | n >  s+b = w2++[('S',s),('B',b)]
                                     south | s <= n+b = w2++[('S',s)]
                                           | s >  n+b = w1++[('N',n),('B',b)]
                                  in path north south xs

costPath :: Path -> Int
costPath = sum . map snd

--Mathieu Cruts