2015 LP Programming Contest

Games

``` ```
import cp.

main =>
Facts = \$[num(4),
cap(5),
refill(2),
fun(1,4),
fun(2,1),
fun(3,2),
fun(4,3)],
games(Facts).

main([File]) =>
games(Facts).

games(Facts) =>
cl_facts(Facts),
num(N),
VArr = {V : I in 1..N, fun(I,V)},
cap(T),
refill(K),
IArr = new_array(N),      % IArr[I]: number of tokens before game I
IArr :: 1..T,
IArr[1] = T,
OArr = new_array(N),      % OArr[I]: number of tokens after game I
OArr :: 0..T-1,
SArr = new_array(N),      % SArr[I]: number of tokens spent on game I
SArr :: 1..T,
foreach (I in 1..N)
if I<N then
IArr[I+1] #= min(OArr[I]+K, T)
end,
SArr[I] #= IArr[I] - OArr[I]
end,
TotalFun #= sum([SArr[I]*VArr[I] : I in 1..N]),
solve([\$max(TotalFun)], (IArr,OArr,SArr)),
printf("total_fun(%w). \n",TotalFun).
``````

Fix Queens

``` ```
import planner.

main =>
Facts = \$[board_size(4),pos(2,1), pos(1,2), pos(4,2), pos(1,3)],
fqueens(Facts).

main([File]) =>
fqueens(Facts).

fqueens(Facts) =>
cl_facts(Facts),
find_all((R,C),pos(R,C)).sort() = Config,
best_plan(Config,Plan,Cost),
printf("moves(%w). ",Cost).
%    println(Plan).

final(Config) =>
not_attack(Config).

not_attack([_]) => true.
not_attack([(R,C)|L]) =>
not_attack(R,C,L),
not_attack(L).

not_attack(_R,_C,[]) => true.
not_attack(R,C,[(R1,C1)|L]) =>
R !== R1,
C !== C1,
R - C != R1 - C1,
R+C !== R1+C1,
not_attack(R,C,L).

action(Config,NConfig,Action,Cost) =>
Cost = 1,
Action = \$move(R,C,R1,C1),
board_size(N),
select((R,C),Config,ConfigR),
move(N,R,C,R1,C1,ConfigR),
NConfig = insert_ordered(ConfigR,(R1,C1)).

move(N,R,C,R1,C1,Qs) ?=>
C1 = C,
between(1,N,R1),
R1 !== R,
not (between(min(R1,R),max(R1,R),R2), member((R2,C),Qs)).
move(N,R,C,R1,C1,Qs) ?=>
R1 = R,
between(1,N,C1),
C1 !== C,
not (between(min(C1,C),max(C1,C),C2), member((R,C2),Qs)).
move(N,R,C,R1,C1,Qs) ?=>
K = R-C,
between(1,N,R1),
C1 = R1-K,
between(1,N,C1),
(R,C) != (R1,C1),
not (between(min(R1,R),max(R1,R),R2), C2 = R2-K, member((R2,C2),Qs)).
move(N,R,C,R1,C1,Qs) =>
K = R+C,
between(1,N,R1),
C1 = K-R1,
between(1,N,C1),
(R,C) != (R1,C1),
not (between(min(R1,R),max(R1,R),R2), C2=K-R2, member((R2,C2),Qs)).
``````

Logistics

``` ```
main =>
Facts = \$[graph_size(6),
start(1),
dest(6),
edge(1,2,4),
edge(1,3,2),
edge(2,3,5),
edge(2,4,10),
edge(3,5,3),
edge(4,5,4),
edge(4,6,11)],
logistics(Facts).

main([File]) =>
logistics(Facts).

logistics(Facts) =>
IEdges = [\$edge(Y,X,C) : \$edge(X,Y,C) in Facts],
cl_facts(IEdges++Facts, \$[edge(+,-,-)]),
Dests = find_all(V,dest(V)).sort(),
start(V0),
find_tree([V0],Dests,Tree,Cost),
writeln(Tree),
printf("cost(%w).\n",Cost).

table (+,+,-,min)
find_tree(_FrontVs,[],Tree,Cost) => Cost=0, Tree=[].
find_tree(FrontVs,Dests,Tree,Cost) =>
member(V,FrontVs),
edge(V,NextV,W),
not member(NextV,FrontVs),
(member(NextV,Dests) -> Dests1 = delete(Dests,NextV); Dests1 = Dests),
Tree = [(V,NextV,W)|TreeR],
find_tree(insert_ordered(FrontVs,NextV),Dests1,TreeR,Cost1),
Cost = Cost1+W.
``````

Packing

``` ```
import cp.

main =>
Facts = \$[r(2),
s(2),
l(0),
t(0)],
packing(Facts).

main([File]) =>
packing(Facts).

packing(Facts) =>
Board = new_array(4,4),
pack_board(Facts,Board).

pack_board(Ps,Board),
pack_ps(Ps,Board)
=>
printf("yes.\n").
pack_board(_Ps,_Board) =>
printf("no.\n").

pack_ps([],_Board) => true.
pack_ps([P|Ps],Board) =>
pack_p(P,Board),
pack_ps(Ps,Board).

pack_p(P,_Board),P[1]==0 => true.
pack_p(r(N),Board) =>
place_r(Board),
N1 = N-1,
pack_p(\$r(N1),Board).
pack_p(l(N),Board) =>
place_l(Board),
N1 = N-1,
pack_p(\$l(N1),Board).
pack_p(s(N),Board) =>
place_s(Board),
N1 = N-1,
pack_p(\$s(N1),Board).
pack_p(t(N),Board) =>
place_t(Board),
N1 = N-1,
pack_p(\$t(N1),Board).

place_r(Board) ?=>
Cells = [(R,C1),(R,C2),(R,C3),(R,C4)],
available_c(Board,R,C1),
C2 = C1+1, C3 = C2+1, C4 = C3+1,
place_cs(Board,Cells).
place_r(Board) =>
Cells = [(R1,C),(R2,C),(R3,C),(R4,C)],
available_c(Board,R1,C),
R2 = R1+1, R3 = R2+1, R4 = R3+1,
place_cs(Board,Cells).

place_s(Board) =>
Cells = [(R1,C1),(R1,C2),(R2,C1),(R2,C2)],
available_c(Board,R1,C1),
C2 = C1+1, R2 = R1+1,
place_cs(Board,Cells).

place_l(Board) ?=>
Cells = [(R1,C1),(R2,C1),(R2,C2),(R2,C3)],
available_c(Board,R1,C1),
R2 = R1+1, C2 = C1+1, C3 = C2+1,
place_cs(Board,Cells).
place_l(Board) ?=>
Cells = [(R1,C3),(R2,C1),(R2,C2),(R2,C3)],
available_c(Board,R1,C3),
R2 = R1+1, C2 = C3-1, C1 = C2-1,
place_cs(Board,Cells).
place_l(Board) ?=>
Cells = [(R2,C1),(R1,C1),(R1,C2),(R1,C3)],
available_c(Board,R2,C1),
R1 = R2-1, C2 = C1+1, C3 = C2+1,
place_cs(Board,Cells).
place_l(Board) ?=>
Cells = [(R2,C3),(R1,C1),(R1,C2),(R1,C3)],
available_c(Board,R2,C3),
R1 = R2-1, C2 = C3-1, C1 = C2-1,
place_cs(Board,Cells).
place_l(Board) ?=>
Cells = [(R1,C1),(R1,C2),(R2,C2),(R3,C2)],
available_c(Board,R1,C1),
R2 = R1+1, R3 = R2+1, C2 = C1+1,
place_cs(Board,Cells).
place_l(Board) ?=>
Cells = [(R1,C2),(R1,C1),(R2,C1),(R3,C1)],
available_c(Board,R1,C2),
R2 = R1+1, R3 = R2+1, C1 = C2-1,
place_cs(Board,Cells).
place_l(Board) ?=>
Cells = [(R3,C1),(R1,C2),(R2,C2),(R3,C2)],
available_c(Board,R3,C1),
R2 = R3-1, R1 = R2-1, C2 = C1+1,
place_cs(Board,Cells).
place_l(Board) =>
Cells = [(R3,C2),(R1,C1),(R2,C1),(R3,C1)],
available_c(Board,R3,C2),
R2 = R3-1, R1 = R2-1, C1 = C2-1,
place_cs(Board,Cells).

place_t(Board) ?=>
Cells = [(R1,C2),(R2,C1),(R2,C2),(R2,C3)],
available_c(Board,R1,C2),
R2 = R1+1, C1 = C2-1, C3 = C2+1,
place_cs(Board,Cells).
place_t(Board) ?=>
Cells = [(R2,C2),(R1,C1),(R1,C2),(R1,C3)],
available_c(Board,R2,C2),
R1 = R2-1, C1 = C2-1, C3 = C2+1,
place_cs(Board,Cells).
place_t(Board) ?=>
Cells = [(R2,C2),(R1,C1),(R2,C1),(R3,C1)],
available_c(Board,R2,C2),
R1 = R2-1, R3 = R2+1, C1 = C2-1,
place_cs(Board,Cells).
place_t(Board) =>
Cells = [(R2,C1),(R1,C2),(R2,C2),(R3,C2)],
available_c(Board,R2,C1),
R1 = R2-1, R3 = R2+1, C2 = C1+1,
place_cs(Board,Cells).

place_cs(Board,Cells) =>
foreach((R,C) in Cells)
available_c(Board,R,C),
Board[R,C] = 1
end.

available_c(Board,R,C) =>
R #>= 1, R #=< 4,
C #>= 1, C #=< 4,
nth(R,Board,Row),
nth(C,Row,Cell),
var(Cell).
``````

Pizza

``` ```
import sat.

main =>
Facts = \$[n_pizzas(4),
pizza(1,10),
pizza(2,5),
pizza(3,20),
pizza(4,15),
n_vouchers(2),
voucher(1,1,1),
voucher(2,2,1)],
pizza(Facts).

main([File]) =>
pizza(Facts).

pizza(Facts) =>
cl_facts(Facts),
n_pizzas(N),
Prices = new_array(N),
foreach (I in 1..N)
pizza(I,C),
Prices[I] = C
end,
n_vouchers(M),
Free = new_array(M),
foreach (I in 1..M)
voucher(I,B,F),
Free[I] = F
end,

How = new_array(N),
How :: -M..M,    % -I buy using voucher I, I free from voucher I, 0 obtained without using a voucher

Used = new_array(M),
Used :: 0..1,

% assign right number of pizzas to buy order
foreach(V in 1..M)
Used[V] #<=> sum([How[P] #= -V : P in 1..N]) #>= Buy[V]
end,

% assign not too many pizzas to free order
foreach(V in 1..M)
sum([How[P] #= V : P in 1..N]) #=< Used[V]*Free[V]
end,

% pizzas assigned to free are cheaper than pizzas assigned to buy
foreach (P1 in 1..N, P2 in 1..N)
How[P1] #<0 #/\ How[P1] #= -How[P2] #=> Prices[P2] #=< Prices[P1]
end,

Cost #= sum([(How[P] #=< 0)*Prices[P] : P in 1..N]),

solve([\$min(Cost)],How),
printf("cost(%w).\n",Cost).
``````