/*
Fantasy OR in Picat.
Problem and XPress Mosel model from
Martin J Chlond "Fantasy OR"
http://archive.ite.journal.informs.org/Vol4No3/Chlond/index.php
"""
An interesting article by J.R. Partington investigating puzzles of a mathematical
nature to be found embedded within computer fantasy games may be found at
Mathematical Puzzles in Fantasy Games.
[http://www1.maths.leeds.ac.uk/~pmt6jrp/personal/tms.html ]
The following is an example of the whimsical delights to be found therein.
A Scheduling Problem from Sangraal
When the Sangraal (Holy Grail) is almost won you arrive at the castle
where the Foul Fiend has imprisoned 8 knights. These are as follows:
Agravain - lightly bound - badly wounded
Bors - lightly bound - scratched
Caradoc - bound a bit more - badly wounded
Dagonet - bound as C - scratched
Ector - bound and gagged - somewhat wounded
Feirefiz - in chains - badly wounded
Gareth - in chains and gagged - somewhat wounded
Harry - bound really tight in chains (poor chap) - scratched
Here the state of binding means that it will take 1, 1, 2, 2, 3, 4, 5 and 6 minutes
(respectively) to free them: a freed knight then goes away to wash and recover himself
physically in time for the Sangraal's arrival. The time he takes for this second stage
is 5, 10 or 15 minutes, according to injury. In twenty minutes' time the sun will
set and the Sangraal will arrive. How many knights can you bring? We see, for example
that if you want F, you must free him almost at once, as he can only be ready in
19 minutes at the earliest. Freeing Harry, though it takes 6 minutes, is not urgent,
as he only needs to be freed by the 15th minute.
"""
Note in the original XPress Mosel model
Filename : sangraal.mos
Written by : Martin J Chlond
Date written: 10-April-2002
Source : http://www.amsta.leeds.ac.uk/~pmt6jrp/personal/tms.html
This model also contain a - slightly faster - CP version (go2/0).
This Picat model was created by Hakan Kjellerstrand, hakank@gmail.com
See also my Picat page: http://www.hakank.org/picat/
*/
import cp. % 0.09s / 4761 backtracks (go2: 0.0s / 0 backtracks)
% import sat. % 1.62s (go2: 0.49s)
% import mip. % 5.1s (go2: >1min )
main => go.
%
% IP version, based on Chlond's XPress Mosel model
%
go =>
% time to free each knight
Free = [1, 1, 2,2, 3, 4, 5,6],
% time to prepare each knight
Prep = [15,5,15,5,10,15,10,5],
K = Free.length,
% x(i,j)=1 if knight i in position j, 0 otherwise
X = new_array(K,K),
X :: 0..1,
% d(j)=1 if position j finished within 20 minutes, 0 otherwise
D = new_list(K),
D :: 0..1,
% finish time for each position
T = new_list(K),
% maximise number of positions finished within 20 minutes
MaxK #= sum(D),
% each knight in one position
foreach(I in 1..K)
sum([X[I,J] : J in 1..K]) #= 1
end,
% each position has one knight
foreach(J in 1..K)
sum([X[I,J] : I in 1..K]) #= 1
end,
% compute finish time for each position
foreach(J in 1..K)
sum([Free[I]*X[I,L] : I in 1..K, L in 1..J-1]) +
sum([(Free[I]+Prep[I])*X[I,J] : I in 1..K]) #= T[J]
end,
% d(j) = 1 if knight in position j is freed and prepared within 20 minutes
foreach(J in 1..K)
T[J] #>= 21-15*D[J],
T[J] #<= 53-33*D[J]
end,
Vars = X.vars() ++ D ++ T,
solve($[ffc,updown,max(MaxK)], Vars),
println('MaxK'=MaxK),
println("X:"),
foreach(Row in X) println(Row.to_list()) end,
println('T'=T),
println('D'=D),
nl.
%
% CP version, using cumulative/4.
% This is faster than go/0, and - in my view - simpler.
%
go2 =>
% time to free each knight
Free = [1, 1, 2,2, 3, 4, 5,6],
% time to prepare each knight
Prep = [15,5,15,5,10,15,10,5],
Limit = 20, % time limit for rescuing
K = Free.length,
% start times
Start = new_list(K),
Start :: 0..20,
% finishing time
End = new_list(K),
% The knights that will be rescued.
Rescued = new_list(K),
Rescued :: 0..1,
foreach(I in 1..K)
End[I] #= Start[I] + Free[I] + Prep[I],
End[I] #<= Limit #<=> Rescued[I] #= 1
end,
Z #= sum(Rescued),
cumulative(Start,Free,[1 :_ in 1..K], 1),
% with 2 persons doing the rescue, we can rescue all knights
% cumulative(Start,Free,[1 :_ in 1..K], 2),
Vars = Start ++ End ++ Rescued,
solve($[ffc,split,max(Z)],Vars),
println(z=Z),
print_list('Free ', Free),
print_list('Prep ', Prep),
print_list('Start ', Start),
print_list('End ', End),
print_list('Rescued ', Rescued),
nl.
print_list(Name,List) =>
printf("%w: ", Name),
println([to_fstring("%2d", E) : E in List]).