Declaratieve Talen/oplossingBallen

Een oplossing voor het eerste deel:

import Data.List

-- Bereken alle mogelijke mappings tussen twee foto's, gegeven de tijdspanne
-- tussen deze foto's.
berekenMappings :: [Int] -> [Int] -> Int -> [[(Int,Int)]]
berekenMappings f1 f2 t = filterMappings ( combinations f1 (allMappings f1 f2 t))

-- Zoek alle mogelijke combinaties van een positie uit Foto1 met een positie uit Foto2.
-- Een combinatie is mogelijk als: abs(oude_positie - nieuwe_positie) = Tijd
-- Main> allMappings [10,12] [9,11,14] 1
-- [(10,9), (10,11), (12,11)]
allMappings :: [Int] -> [Int] -> Int -> [(Int,Int)]
allMappings f1 f2 t = 
    [(old_pos, new_pos) | old_pos <- f1,
                          new_pos <- f2, 
                          abs (old_pos - new_pos) == t]

-- Groepeer allMappings.
-- Main> combinations [10,12] [(10,9), (10,11), (12,11)]
-- [ [(10,9), (12,11)] , [(10,11), (12,11)] ]
combinations :: [Int] -> [(Int,Int)] -> [[(Int,Int)]]
combinations [] _  = [ [] ]
combinations (oldPosition:oldPositions) mappings = 
    [ (o,n):ys | (o,n):mappings' <- tails mappings,
                 o == oldPosition,
                 ys <- combinations oldPositions mappings'] 

-- Filter ongeldige mappings.
-- Mappings genre [(10,11), (12,11)] moeten nog weggefilterd worden.
-- Main> filterMappings [ [(10,9), (12,11)] , [(10,11), (12,11)] ]
-- [ [(10,9), (12,11)] ]
filterMappings :: [[(Int,Int)]] -> [[(Int,Int)]]
filterMappings [] = []
filterMappings (m:ms) 
    | ok        = m:filterMappings ms
    | otherwise = filterMappings ms
    where ok = noDoubles newPos
          noDoubles xs = (length xs == length (nub xs))
          newPos = map snd m

--Pieter 14 jan 2014 23:18 (UTC)

import Data.List

berekenMappings :: [Int] -> [Int] -> Int -> [[(Int,Int)]]
berekenMappings xs ys n = filter correct arr --volgorde antwoorden kan verschillen van opgave
					where
						arr = filter different . sequence . map genPos $ xs -- lijst met alle mogelijkheden voor overgang naar foto 2
						genPos :: Int -> [(Int,Int)]
						genPos x = [(x,x-n),(x,x+n)] -- alle mogelijkheden voor een positie in foto 2 van een bepaalde positie in foto 1
						different :: [(Int,Int)] -> Bool
						different xs = map snd xs == nub (map snd xs) --alle tweede elementen moeten verschillend zijn
						correct :: [(Int,Int)] -> Bool
						correct zs = all (`elem` ys) (map snd zs) --alle tweede elementen moeten in foto 2 zitten

--Jeroen

Gelijkaardig aan vorige oplossingen, maar (naar mijn mening) overzichtelijker voor wie moeite heeft met bovenstaande oplossingen:


-- Main call for starting the program:
--      
--     Collect all possible results between start- and endstate for given time span
--     Sequence all combinations of possibilities (Monad)
--     Filter on the valid ones (being without collisions)
--
runProgram startState endState n =
    filter (\x -> noCollision x) $ sequence $ possibleResults startState endState n


-- Makes sure no two balls have the same 2nd tuple value (meaning they would have
-- collided with each other)
noCollision tupleList =
    length seconds == (length $ nub $ seconds)
    where seconds = map snd tupleList
                

-- Collects all possible results between start- and endstate for the given time span
possibleResults :: (Ord a, Num a) => [a] -> [a] -> a -> [[(a, a)]]
possibleResults [] _ _         = []
possibleResults (x:xs) list n  =
    [validTuples x list n] ++ possibleResults xs list n


-- Does the actual checkings for the movements in function of the passed time span
validTuples :: (Ord a, Num a) => a -> [a] -> a -> [(a,a)]
validTuples _ [] _ = []
validTuples a (x:xs) n | valid a x     = (a,x) : validTuples a xs n
                       | otherwise     = validTuples a xs n
                       where valid a x = (==n) $ abs $ subtract a x

--Mathieu Cruts