Brückenrätsel mit Haskell lösen
Bei Nacht wollen vier Personen eine Rheinbrücke überqueren.
Dazu steht ihnen aber nur eine einzige Taschenlampe zur Verfügung, deren Batterien gerade noch für 60 Minuten reichen, um die Taschenlampe zum Leuchten zu bringen. Über die Brücke dürfen gleichzeitig höchstens zwei Personen gehen und sobald eine Person sich auf der Brücke befindet, muß die Taschenlampe eingeschaltet sein!
Die vier Personen sind unterschiedlich gut zu Fuß. Anton braucht nur 5 Minute über die Brücke, Maria braucht 10 Minuten, Karl braucht 20 Minuten und Alfred braucht 25 Minuten. Da vier Personen über die Brücke gebracht werden müssen, können also nicht alle gleichzeitig über die Brücke gehen. Wenn zwei Personen mit eingeschalteter Taschenlampe über die Brücke gehen, muss also einer bei eingeschalteter Taschenlampe wieder zurückgehen, damit die Taschenlampe wieder zu den wartenden Personen kommt!
Wie müssen die Personen über die Brücke gehen, damit nach 60 Minuten Leuchten der Taschenlampe alle vier Personen am Ziel über die Brücke sind? Ist es möglich?
Bei Nacht wollen vier Personen eine Rheinbrücke überqueren.
Dazu steht ihnen aber nur eine einzige Taschenlampe zur Verfügung, deren Batterien gerade noch für 60 Minuten reichen, um die Taschenlampe zum Leuchten zu bringen. Über die Brücke dürfen gleichzeitig höchstens zwei Personen gehen und sobald eine Person sich auf der Brücke befindet, muß die Taschenlampe eingeschaltet sein!
Die vier Personen sind unterschiedlich gut zu Fuß. Anton braucht nur 5 Minute über die Brücke, Maria braucht 10 Minuten, Karl braucht 20 Minuten und Alfred braucht 25 Minuten. Da vier Personen über die Brücke gebracht werden müssen, können also nicht alle gleichzeitig über die Brücke gehen. Wenn zwei Personen mit eingeschalteter Taschenlampe über die Brücke gehen, muss also einer bei eingeschalteter Taschenlampe wieder zurückgehen, damit die Taschenlampe wieder zu den wartenden Personen kommt!
Wie müssen die Personen über die Brücke gehen, damit nach 60 Minuten Leuchten der Taschenlampe alle vier Personen am Ziel über die Brücke sind? Ist es möglich?
import ListUtils
-- Randbedingung
persons :: [Int]
persons = [5,10,20,25]
-- Jeden eindeutig machen, d.h. numerieren ('select2' wird dadurch einfacher)
numberedPersons :: [(Int, Int)]
numberedPersons = zip [1..] persons
-- Alle Kombinationsmoeglichkeiten
allCombinations = vonAnachB numberedPersons []
bestTime = minimum times
worstTime = maximum times
timeCombinations = zip times allCombinations
bestCombinations = [(a,b)|(a,b)<-timeCombinations, a==bestTime]
worstCombinations = [(a,b)|(a,b)<-timeCombinations, a==worstTime]
solution = head bestCombinations
-- Die Zeit, fuer jede Kombination
times :: [Int]
times = map (\ass->sum (map (\as->maximum (map snd as)) ass)) allCombinations
vonAnachB :: [(Int,Int)] -> [(Int,Int)] -> [[[(Int,Int)]]]
vonAnachB (a:b:[]) _ = [[[a,b]]]
vonAnachB as bs = concat (map f options)
where options = select2 as
f a = map (\q->a:q) (vonBnachA (minus as a) (a++bs))
vonBnachA :: [(Int,Int)] -> [(Int,Int)] -> [[[(Int,Int)]]]
vonBnachA as bs = concat (map f options)
where options = map (\a->[a]) bs
f a = map (\q->a:q) (vonAnachB (a++as) (minus bs a))
-- Liefere die Menge aller Zweiermengen
select2 :: Ord a => [(a,b)] -> [[(a,b)]]
select2 ls = [[(i,a),(j,b)] | (i,a)<-ls,
(j,b)<-ls,
i<j
]
-- Entferne aus 'as' alle Elemente von 'bs'
minus :: Eq a => [a] -> [a] -> [a]
minus as bs = [a|a<-as, notElem a bs]