# 2017 LP Programming Contest

## Booth arrangement

``` ```
import planner.

main =>
Fs = \$[room(3, 3),
booths(3),
dimension(1, 2, 1),
dimension(2, 2, 1),
dimension(3, 1, 1),
position(1, 0, 1),
position(2, 1, 2),
position(3, 0, 0),
target(3, 0, 2)],
booth(Fs).

main([File]) =>
booth(Fs).

booth(Fs) =>
cl_facts(Fs),
room(RW,RH),
booths(N),
target(TB,TX,TY),
position(TB,TX0,TY0),
dimension(TB,TW,TH),
Booths = [{W,H,X,Y} : B in 1..N, dimension(B,W,H), position(B,X,Y), B !== TB].sort(),
StaticPart = {RW,RH,Booths},
best_plan_unbounded([{TW,TH,TX0,TY0,TX,TY},Booths,StaticPart],_Plan,PlanLen),
printf("moves(%w).\n",PlanLen).

final([{_TW,_TH,TX,TY,TX,TY},Booths,{_,_,Booths}]) => true.

action([{TW,TH,TX,TY,TX0,TY0},Booths,StaticPart@{RW,RH,_Booths0}],NState,Action,Cost) ?=>
move(RW,RH,TW,TH,TX,TY,Booths,TX1,TY1,Action),
NState = [{TW,TH,TX1,TY1,TX0,TY0},Booths,StaticPart],
Cost = 1.
action([Target@{TW,TH,TX,TY,_TX0,_TY0},Booths,StaticPart@{RW,RH,_Booths0}],NState,Action,Cost) =>
select(Booth,Booths,Booths1),
Booth = {W,H,X,Y},
move(RW,RH,W,H,X,Y,[{TW,TH,TX,TY}|Booths1],X1,Y1,Action),
Booths2 = Booths1.insert_ordered({W,H,X1,Y1}),
NState = [Target,Booths2,StaticPart],
Cost = 1.

move(RW,RH,W,H,X,Y,Booths,X1,Y1,Action) =>
(X1 = X-1,    X1 >= 0, Y1 = Y, Action = \$left(W,H,X,Y)
;
X1 = X+1, X1+W =< RW, Y1 = Y, Action = \$right(W,H,X,Y)
;
Y1 = Y-1, Y1 >= 0, X1 = X, Action = \$down(W,H,X,Y)
;
Y1 = Y+1, Y1+H =< RH, X1 = X, Action = \$up(W,H,X,Y)
),
once not_overlap(W,H,X1,Y1,Booths).

not_overlap(W,H,X,Y,Booths) =>
foreach ({W1,H1,X1,Y1} in Booths)
X >= X1+W1 || X1 >= X+W || Y >= Y1+H1 || Y1 >= Y+H
end.
``````

## Buffet placement

``` ```
main =>
Fs = \$[dishes(3),
separation(1),
hot(1),
table_width(4),
dish_width(1, 1),
dish_width(2, 1),
dish_width(3, 2),
demand(1, 1),
demand(2, 1),
demand(3, 1)],
buffet(Fs).

main([File]) =>
buffet(Fs).

buffet(Fs) =>
cl_facts(Fs),
dishes(N),
hot(H),
separation(D),
table_width(L),
Hs = [(W,Num) : I in 1..H, dish_width(I,W), demand(I,Num)].sort(),
Cs = [(W,Num) : I in H+1..N, dish_width(I,W), demand(I,Num)].sort(),
find(h,Hs,Cs,D,L,L,NT1),
find(c,Hs,Cs,D,L,L,NT2),
printf("table(%w).\n",min(NT1,NT2)).

table (+,+,+,+,+,+,min)
find(PreType,Hs,Cs,D,L,L0,NT) ?=>
select_plate(PreType,Hs,Cs,D,L,L1,CurType,Hs1,Cs1),
(Hs1 == [], Cs1 == [] -> NT = 1; find(CurType,Hs1,Cs1,D,L1,L0,NT)).
find(_PreType,Hs,Cs,D,_L,L0,NT) =>
find(h,Hs,Cs,D,L0,L0,NT1),
find(c,Hs,Cs,D,L0,L0,NT2),
NT = min(NT1,NT2)+1.

select_plate(PreType,Hs,Cs,D,L,L1,CurType,Hs1,Cs1) ?=>
select((W,Num),Hs,HsR),
(PreType == h -> NeededW = W; NeededW = W+D),
NeededW =< L,
L1 = L-NeededW,
Num1 = Num-1,
(Num1 == 0 -> Hs1 = HsR; Hs1 = insert_ordered(HsR,(W,Num1))),
Cs1 = Cs,
CurType = h.
select_plate(PreType,Hs,Cs,D,L,L1,CurType,Hs1,Cs1) =>
select((W,Num),Cs,CsR),
(PreType == c -> NeededW = W; NeededW = W+D),
NeededW =< L,
L1 = L-NeededW,
Num1 = Num-1,
(Num1 == 0 -> Cs1 = CsR; Cs1 = insert_ordered(CsR,(W,Num1))),
Hs1 = Hs,
CurType = c.
``````

## Pouring beer

``` ```
import planner.

main =>
Fs = \$[vessels(5),
source(1),
people(3),
capacity(1, 12),
capacity(2, 3),
capacity(3, 3),
capacity(4, 3),
capacity(5, 2),
horizon(10)],
pour(Fs).

main([File]) ?=>
pour(Fs).

pour(Fs) ?=>
cl_facts(Fs),
source(SV),
capacity(SV,SK),
findall((0,K),(capacity(V,K),V !== SV)) = Pairs0,
sort_down([(SK,SK)|Pairs0]) = Pairs,
horizon(L),
people(M),
SK div M = Share,
Share*M = SK,
Shares = [Share : _ in 1..M],
plan({Pairs,Shares},L,_Plan,_Len),
println("split(yes).\n").
pour(Fs) =>
println("split(no).\n").

final({Pairs,Shares}) =>
equal_shares(Pairs,Shares).

equal_shares(_,[]) => true.
equal_shares([(Amount,_)|Pairs],[Amount|Shares]) =>
equal_shares(Pairs,Shares).
equal_shares([(Amount,_)|Pairs],[Share|_]), Amount > Share => fail.
equal_shares([(Amount,_)|Pairs],[Share|Shares]) =>
find_division(Pairs,Pairs1,Share-Amount),
equal_shares(Pairs1,Shares).

find_division(Pairs,PairsR,0) => PairsR = Pairs.
find_division(Pairs,PairsR,Share) =>
select((Amount,_),Pairs,Pairs1),
Amount =< Share,
find_division(Pairs1,PairsR,Share-Amount).

action({Pairs,Shares},NState,Action,Cost) ?=>
select((Amount1,K1),Pairs,Pairs1),
Amount1 > 0,
select((Amount2,K2),Pairs1,Pairs2),
Amount2 < K2,
(Amount1+Amount2 >= K2 ->
NAmount1 = Amount1-(K2-Amount2),
NAmount2 = K2
;
NAmount1 = 0,
NAmount2 = Amount1+Amount2
),
NPairs = Pairs2.insert_ordered_down((NAmount1,K1)).insert_ordered_down((NAmount2,K2)),
NState = {NPairs,Shares},
Action = pour,
Cost = 1.
``````

## Tourism 1

``` ```
import cp.

main =>
Fs = \$[people(2),
places(3),
preferences(4),
order(1, 1, 2),
order(1, 2, 3),
order(2, 3, 2),
order(2, 2, 1)],
pour(Fs).

main([File]) =>
pour(Fs).

pour(Fs) =>
cl_facts(Fs, \$[order(+,+,+)]),
people(N),
places(M),
Order = new_array(N,M,M),
foreach (P in 1..N, Loc1 in 1..M, Loc2 in 1..M)
(order(P,Loc1,Loc2) -> Order[P,Loc1,Loc2] = 1; true)
end,
transitive_closure(N,M,Order),
Tour = new_array(M),
Tour :: 1..M,
all_different(Tour),
Violations = new_array(N,M,M),
Violations :: 0..1,
foreach (P in 1..N, Loc1 in 1..M, Loc2 in 1..M)
(Order[P,Loc1,Loc2] == 1 ->
element(I1,Tour,Loc1),
element(I2,Tour,Loc2),
I1 #> I2 #<=> Violations[P,Loc1,Loc2]
;
true
)
end,
Total #= sum([Violations[P,Loc1,Loc2] : P in 1..N, Loc1 in 1..M, Loc2 in 1..M]),
solve(\$[min(Total)],(Tour,Violations)),
printf("violations(%w).\n",Total).

% transitive closure
transitive_closure(N,M,Order) =>
foreach (P in 1..N, K in 1..M, I in 1..M, J in 1..M)
(Order[P,I,K] == 1, Order[P,K,J] == 1 -> Order[P,I,J] = 1; true)
end.
``````

## Tourism 2

``` ```
import sat.

main =>
Fs = \$[people(3),
places(4),
preferences(4),
place(1, 2, 9, 12),
place(2, 1, 9, 12),
place(3, 3, 9, 15),
place(4, 6, 12, 18),
prefer(1, 1),
prefer(1, 2),
prefer(2, 3),
prefer(2, 4)],
tour(Fs).

main([File]) =>
tour(Fs).

tour(Fs) =>
cl_facts(Fs),
people(N),
places(M),
Tour = new_array(M),
Tour :: 0..M,   % 0 means skip this place
all_different_except_0(Tour),
foreach (I in 1..M-1)
Tour[I] #= 0 #=> Tour[I+1] #= 0
end,
Visited = new_array(M),
Visited :: 0..1,
foreach (Loc in 1..M)
Visited[Loc] #= max([Tour[I] #= Loc : I in 1..M])
end,
Start = new_array(M),
End = new_array(M),
MaxC = max([C : Loc in 1..M, place(Loc,_,_,C)]),
Start :: 0..MaxC,
End :: 0..MaxC,
foreach (Loc in 1..M)
place(Loc,D,O,C),
foreach (I in 1..M)
Tour[I] #= Loc #=> Start[I] #>= O #/\ End[I] #= Start[I]+D #/\ End[I] #=< C
end
end,
foreach (I in 2..M)
Tour[I] #!= 0 #=> Start[I] #>= End[I-1]
end,
Satis = new_list(N),
foreach (P in 1..N)
Count = count_all(prefer(P,_)),
SatisP #= sum([Visited[Loc] : Loc in 1..M, prefer(P,Loc)]),
Satis[P] #= cond(SatisP #= Count, M, SatisP)
end,
Obj #= min(Satis),
solve(\$[max(Obj)],(Tour,Satis,Visited)),
printf("satisfaction(%w).\n",Obj).

``````