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.