Zdroj
/*
Řešte následující (zobecněnou) hádanku.
Skupina osob potřebuje překonat most.
Ten ale unese nejvýše dvě osoby najednou.
Navíc je tma, takže je potřeba překračovat se světlem,
které je jen jedno a už moc dlouho nevydrží svítit.
(Tedy pravidla podobná překonávání řeky v loďce.)
Různým osobám trvá přechod různě dlouho
a dvojice musí jít rychlostí toho pomalejšího.
Vstup: seznam osob, kde každá je pro zjednodušení
reprezentována pouze číslem - svou dobou přechodu mostu.
Výstup - řešení: seznam kroků, kde krok je prostý seznam
osob překračujících most (směr se stejně musí střídat).
Bodování:
(rychlost zkouším na prvních dvou příkladech níže)
- max. 2.4 za nalezení všech řešení ve zlomku vteřiny,
- 2 body pokud to bude pomalejší (max. desítky vteřin),
- 1.5 bodu za nevracení nekorektních řešení
a nalezení nějakého do 1-2 minut (nebo false).
Rozumnou funkčnost budu zkoušet i na jiných vstupech
než těch co jsou uvedené v době zadání ;-)
*/
% most(+SeznamČasůNaPřekročení, +ČasovýLimit, -NějakéŘešení)
% krok(+StavPřed, -SeznamKdoPřejde, -ČasKroku, -StavPo)
krok(s(Strana0,Leva0,Prava0), Kdo, Cas, s(Strana,Leva,Prava))
:-
% Nejprve symetrie: Leva*, Prava* => Prvni*, Druha*
( Strana0=leva, Strana=prava,
Prvni0=Leva0, Prvni=Leva, Druha0=Prava0, Druha=Prava
; Strana0=prava, Strana=leva,
Prvni0=Prava0, Prvni=Prava, Druha0=Leva0, Druha=Leva
),
% Vybereme kdo přejde: Kdo1 a případně i Kdo2
select(Kdo1, Prvni0, Prvni0_bez1),
( Kdo = [Kdo1, Kdo2],
select(Kdo2, Prvni0_bez1, Prvni),
Kdo2 >= Kdo1,
Cas is max(Kdo1,Kdo2)
; Kdo = [Kdo1],
Prvni = Prvni0_bez1,
Cas is Kdo1
),
append(Kdo, Druha0, Druha).
% Převážejme zleva doprava:
% na začátku všichni vlevo, na konci nikdo vlevo.
most(Leva, Limit, Kroky) :-
hledej(s(leva,Leva,[]), Limit, Kroky).
hledej(s(_,[],_), Limit, []) :- Limit >= 0.
hledej(Stav, Limit, Kroky) :-
krok(Stav, Kdo, Cas, Stav2),
Limit2 is Limit-Cas, Limit2 >= 0,
Kroky = [Kdo|DalsiKroky],
hledej(Stav2, Limit2, DalsiKroky).
Dotazy
% Vstup z flashové hry na http://plastelina.net/game3.html
?- most([1,3,6,8,12], 28, R).
false.
?- most([1,3,6,8,12], 30, R).
R = [[1, 3], [1], [8, 12], [3], [1, 6], [1], [1, 3]] ;
R = [[1, 3], [1], [8, 12], [3], [1, 3], [1], [1, 6]] ;
R = [[1, 3], [1], [1, 6], [3], [8, 12], [1], [1, 3]] ;
R = [[1, 3], [1], [1, 6], [1], [8, 12], [3], [1, 3]] ;
R = [[1, 3], [3], [8, 12], [1], [1, 6], [1], [1, 3]] ;
R = [[1, 3], [3], [8, 12], [1], [1, 3], [1], [1, 6]] ;
R = [[1, 6], [1], [1, 3], [1], [8, 12], [3], [1, 3]] ;
R = [[1, 6], [1], [1, 3], [3], [8, 12], [1], [1, 3]] ;
false.
?- most([5,10,20,25], 59, R).
false.
?- most([5,10,20,25], 60, R).
R = [[5, 10], [5], [20, 25], [10], [5, 10]] ;
R = [[5, 10], [10], [20, 25], [5], [5, 10]] ;
false.
?- most([2], 10, R).
R = [[2]] ;
R = [[2], [2], [2]] ;
R = [[2], [2], [2], [2], [2]] ;
false.