Declaratieve Talen/Oplossing Min-max

Een oplossing:

Probeer met volgend commando om bovenstaand voorbeeld te laten berekenen:

Main> berekenDoosboom (Doos 0 [Bol 1 [Doos 2 [] 1, Doos 3 [] 2] 2, Bol 4 [Doos 5 [] 3, Doos 6 [] 4] 0, Bol 7 [Doos 8 [] 5, Doos 9 [] 6] 0] 0)

Doos 0 [Bol 1 [Doos 2 [] 1,Doos 3 [] 2] 1,Bol 4 [Doos 5 [] 3,Doos 6 [] 4] 3,Bol 7 [Doos 8 [] 5,Doos 9 [] 6] 5] 5

import List

data Doosboom = Doos Int [Bolboom] Int deriving Show
data Bolboom = Bol Int [Doosboom] Int deriving Show
 
getWaardeBol :: Bolboom -> Int
getWaardeBol (Bol id [] w) = w
getWaardeBol (Bol id doosbomen w) =
        let
                (eerste:rest) = sort [getWaardeDoos d | d <- doosbomen]
        in
                eerste

getWaardeDoos :: Doosboom -> Int
getWaardeDoos (Doos id [] w) = w
getWaardeDoos (Doos id bolbomen w) =
        let
                (eerste:rest) = reverse (sort [getWaardeBol b | b <- bolbomen])
        in
                eerste

berekenDoosboom :: Doosboom -> Doosboom
berekenDoosboom (Doos id bomen w) = Doos id [(berekenBolboom b) | b <- bomen] (getWaardeDoos (Doos id bomen w))

berekenBolboom :: Bolboom -> Bolboom
berekenBolboom (Bol id bomen w) = Bol id [(berekenDoosboom d) | d <- bomen] (getWaardeBol (Bol id bomen w))

alternatieve oplossing

data Maxboom = Max Int [Minboom] Int deriving Show
data Minboom = Min Int [Maxboom] Int deriving Show

complete_max::Maxboom -> Maxboom
------------------------------
complete_max (Max id minbomen w) =
	if w /= -1
		then (Max id minbomen w)
		else let completed_minbomen = map complete_min minbomen
			 max_w = maximum [winst | (Min id maxbomen winst) <- completed_minbomen]
		     in (Max id completed_minbomen max_w)
		
complete_min::Minboom -> Minboom
--------------------------------
complete_min (Min id maxbomen (-1)) =
	let completed_maxbomen = map complete_max maxbomen
	    min_w = minimum [winst | (Max id minbomen winst) <- (map complete_max maxbomen)]
	in (Min id completed_maxbomen (minimum [winst | (Max id minbomen winst) <- (map complete_max maxbomen)]))
complete_min (Min id maxbomen w) = (Min id maxbomen w) 

Een ander alternatief:

data Doosboom = Doos Int [Bolboom] Int deriving Show
data Bolboom = Bol Int [Doosboom] Int deriving Show
doosboom = (Doos 0 [Bol 1 [Doos 2 [] 1, Doos 3 [] 2] 2, Bol 4 [Doos 5 [] 3, Doos 6 [] 4] 0, Bol 7 [Doos 8 [] 5, Doos 9 [] 6] 0] 0)

berekenDoosboom::Doosboom->Doosboom
berekenDoosboom (Doos x [] w) = Doos x [] w
berekenDoosboom (Doos x bolbomen w) = 
        let
                berekendebolbomen = [berekendeBolboom | berekendeBolboom <- map berekenBolboom bolbomen]
                max = maximum [waarde | (Bol _ _ waarde) <- berekendebolbomen]
        in (Doos x berekendebolbomen max)

berekenBolboom::Bolboom->Bolboom
berekenBolboom (Bol x [] w) = Bol x [] w
berekenBolboom (Bol x doosbomen w) =
        let
               berekendedoosbomen = [berekendeDoosboom | berekendeDoosboom <- map berekenDoosboom doosbomen]
               min = minimum [waarde | (Doos _ _ waarde) <- berekendedoosbomen]
        in (Bol x berekendedoosbomen min)

--Beau 17 jun 2006 17:34 (CEST)

Nog een ander alternatief:

data Doosboom = Doos {doosID :: Integer, bolbomen :: [Bolboom], doosWinst :: Integer} deriving (Show,Eq)
data Bolboom = Bol {bolID :: Integer, doosbomen :: [Doosboom], bolWinst :: Integer} deriving (Show,Eq)

doosboom = (Doos 0 [Bol 1 [Doos 2 [] 1, Doos 3 [] 2] 2, Bol 4 [Doos 5 [] 3, Doos 6 [] 4] 0, Bol 7 [Doos 8 [] 5, Doos 9 [] 6] 0] 0)

berekenDoosboom :: Doosboom -> Doosboom
berekenDoosboom d
	| (bolbomen d)==[] = d
	| otherwise = d{bolbomen=nbolboom,doosWinst=m}
	where 	nbolboom = map berekenBolboom (bolbomen d)
		m = maximum [(bolWinst nb) | nb<-nbolboom]

berekenBolboom :: Bolboom -> Bolboom
berekenBolboom b
	| (doosbomen b)==[] = b
	| otherwise = b{doosbomen=ndoosboom,bolWinst=m}
	where	ndoosboom = map berekenDoosboom (doosbomen b)
		m = minimum [(doosWinst nd) | nd<-ndoosboom]

Nog een ander alternatief:

Elfangor

import List
       
data Boom = Boom Int [Boom] (Maybe Int) ([Int] -> Int)
      
instance Show Boom  where
       show (Boom a y k f) = concat $ intersperse " " ["Boom: ",show a, show y, show k ]
          
maxboom :: Int -> [Boom] -> Maybe Int ->  Boom
maxboom i y mi = Boom i y mi maximum
           
minboom :: Int -> [Boom] -> Maybe Int -> Boom
minboom i y  mi= Boom i y mi minimum
          
getWaarde :: Boom -> Int
getWaarde (Boom _ [] Nothing _ ) = error ""
getWaarde (Boom _ _ (Just w) _) = w
getWaarde (Boom _ y Nothing f) = f $ map getWaarde y
        
adjustBoom :: Boom -> Boom
adjustBoom (Boom _ [] Nothing _ ) = error ""
adjustBoom b@(Boom _ _ (Just z) _ ) = b
adjustBoom (Boom id rij Nothing f) = let adjustedRij = map adjustBoom rij
                                      in Boom id adjustedRij (Just (f ( map getWaarde adjustedRij)))   f
     
     
boompje :: Boom
boompje = maxboom 0 [minboom 1 [maxboom 3 [] (Just 1), maxboom 4 [] (Just 2)] Nothing, minboom 5 [maxboom 6 [] (Just 3), maxboom 7 [] (Just 4 )] Nothing, minboom 8 [maxboom 9 [] (Just 5), maxboom 10 [] (Just 6)] Nothing] Nothing
  
   
findPathID :: Boom -> [Int]
findPathID (Boom id [] _ _) = [id]
findPathID boom = let (Boom id rij (Just w) _) = adjustBoom boom
                in id: ( findPathID ( head ( filter (\a -> w == getWaarde a) rij)))

Nog eentje voor et af te leren

data DoosBoom = Doos Int [BolBoom] Int deriving Show
data BolBoom = Bol Int [DoosBoom] Int deriving Show

berekenDoosBoom :: DoosBoom -> DoosBoom
berekenDoosBoom a@(Doos _ [] _ )	= a
berekenDoosBoom (Doos id b _) 		= (Doos id bb m)
					where 
						bb = map berekenBolBoom b
						m = maximum [w| (Bol _ _ w) <- bb]
									 
berekenBolBoom :: BolBoom -> BolBoom
berekenBolBoom a@(Bol _ [] _ ) 	= a
berekenBolBoom (Bol id d _) 		= (Bol id db m)
					where
						db = map berekenDoosBoom d
						m = minimum [w| (Doos _ _ w) <- db]

zoekpadDBoom :: DoosBoom -> [Int]
zoekpadDBoom (Doos id [] _)	= [id]
zoekpadDBoom (Doos id bb w)	= (id : zoekpadBBoom b)
					where b = head [a| a@(Bol _ _ v) <- bb, v==w] 

zoekpadBBoom :: BolBoom -> [Int]
zoekpadBBoom (Bol id [] _)	= [id]
zoekpadBBoom (Bol id db w)	= (id : zoekpadDBoom d)
					where d = head [a| a@(Doos _ _ v) <- db, v==w]

Oplossing mbv ingebouwde ordening

data Spelboom = Doos Int [Spelboom] Int | Bol Int [Spelboom] Int deriving (Show, Eq)
instance Ord Spelboom where
    (Doos _ _ x) <= (Doos _ _ y) = x <= y
    (Bol  _ _ x) <= (Bol  _ _ y) = x <= y

------------------------------
beslis :: Spelboom -> Spelboom
beslis (Doos id [] w)   = Doos id [] w
beslis (Bol  id [] w)   = Bol  id [] w
beslis (Doos id deel _) = let deel2 = map beslis deel
                          in Doos id deel2 (winst $ maximum deel2)
beslis (Bol  id deel _) = let deel2 = map beslis deel
                          in Bol  id deel2 (winst $ minimum deel2)

------------------------
winst :: Spelboom -> Int
winst (Doos _ _ w) = w
winst (Bol  _ _ w) = w


--------------------------------
optimaalPad :: Spelboom -> [Int]
optimaalPad boom = optimum (beslis boom) where
    optimum (Doos id []   _) = [id]
    optimum (Bol  id []   _) = [id]
    optimum (Doos id deel _) = id : (optimum $ maximum deel)
    optimum (Bol  id deel _) = id : (optimum $ minimum deel)