# 2016 LP Programming Contest

## Teaching Brackets

``` ```
main =>
As = \$[bracket(0,1),
bracket(1,1),
bracket(2,1),
bracket(3,-1),
bracket(4,-1),
bracket(5,-1)],
breackets(As).

main([File]) =>
breackets(As).

breackets(As) =>
s(As,[],Rs),
area(Rs) = A,
printf("black_squares(%w).\n",A).

s([bracket(_,1),bracket(_,-1)|S],Sr,Rs) =>
Rs = [\$r(1,1,[])|Rs1],
s(S,Sr,Rs1).
s([bracket(_,1)|S],Sr,Rs) =>
Rs = [\$r(W,H,Cs)|Rs1],
s(S,S1,Cs),
wh(Cs) = (N,W1,H1),
W = W1+N+1,
H = H1+1,
S1 = [\$bracket(_,-1)|S2],
s(S2,Sr,Rs1).
s(S,Sr,Rs) => Sr = S, Rs = [].

wh(Rs) = (N,TW,TH) =>
N = len(Rs),
TW = sum([W : \$r(W,_,_) in Rs]),
TH = max([H : \$r(_,H,_) in Rs]).

area([]) = 0.
area([r(W,H,Cs)|Rs]) = W*H - area(Cs) + area(Rs).
``````

## Empire State Building Elevators

``` ```
main =>
As = \$[top(10),
elevators(4),
elevator(1,0,5),
elevator(2,5,10),
elevator(3,5,7),
elevator(4,7,10)],
elevator(As).

main([File]) =>
elevator(As).

elevator(As) =>
once member(\$top(K),As),
once member(\$elevators(N),As),
Es = [\$e(I,F,F,T,1) : I in 1..N, member(\$elevator(I,F,T),As)],
simulate(0,K,sort(Es),T),
printf("min_time(%w).\n",T).

table(+,+,+,min)
simulate(K,K,_,T) => T = 0.
simulate(F,K,Es,T) ?=>
update0(Es,Es1),
simulate(F,K,Es1,T1),
T = T1+1.
simulate(F,K,Es,T) ?=>
member(\$e(_,F,_,_,D),Es),
update0(Es,Es1),
simulate(F+D,K,Es1,T1),
T = T1+1.

update0(Es0,Es) =>
Es = [E : E0 in Es0, update(E0,E)].

update(e(I,F,LF,T,D),E) =>
F1 = F+D,
update1(\$e(I,F1,LF,T,D),E).

update1(e(I,F,LF,T,_D),E), F > T =>
F1 = T-1, D1 = -1,
E = \$e(I,F1,LF,T,D1).
update1(e(I,F,LF,T,_D),E), F == LF-1 =>
F1 = LF+1, D1 = 1,
E = \$e(I,F1,LF,T,D1).
update1(E0,E) => E = E0.
``````

## New York Subway Ticket Swapping

``` ```
main =>
Ps = \$[passenger(mike, 1, 4),
passenger(anna, 2, 6),
passenger(susan, 4, 5),
passenger(steve, 6, 7)],
ticket(Ps).

main([File]) =>
ticket(Ps).

ticket(Ps) =>
Ps1 = [(S,E) : \$passenger(_,S,E) in Ps],
mta(sort(Ps1),Cost),
printf("loss(%w).",cost(Ps1)-Cost).

table (+,min)
mta(Ps,Cost) ?=>
cost(Ps) = Cost.
mta(Ps,Cost) =>
select(P1,Ps,Ps1),
select(P2,Ps1,Ps2),
overlap(P1,P2),
swap(P1,P2,P11,P22),
mta(Ps2.insert_ordered(P11).insert_ordered(P22),Cost).

overlap((S1,_E1), (S2,E2)), S1 >= S2, S1 =< E2 => true.
overlap((S1,E1), (S2,_E2)), S2 >= S1, S2 =< E1 => true.

swap((S1,E1),(S2,E2),P1,P2) =>
P1 = (S2,E1),
P2 = (S1,E2),
S2 =< E1,
S1 =< E2.

cost(Ps) = sum([C : (S,E) in Ps, cost_p(S,E,0,C,10)]).

cost_p(E,E,C0,C,_D) => C=C0.
cost_p(_,_,C0,C,0) => C=C0.
cost_p(S,E,C0,C,D) => cost_p(S+1,E,C0+D/10,C,D-1).
``````

## New York Stock Exchange Short Position

``` ```
main =>
Stocks = \$[stock(vandelayIndustries, [0, 0, 1, 1, 2, 2, 1, 1, 0, 1, 2, 0]),
stock(kramerica, [0, 1, 2, 4, 3, 1, 3, 4, 5, 2, 1, 0]),
stock(sunshineCarpetCleaners, [0, 1, 2, 4, 4, 1, 0, 2, 4, 1, 0, 0]),
stock(tylerChicken, [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 0])],
sposition(Stocks).

main([File]) =>
sposition(Stocks).

sposition(Stocks) =>
islands(Stocks,Name,Count),
printf("short_position(%w, %w).\n",Name,Count).

table (+,-,max)
islands(Stocks,Name,Count) =>
member(\$stock(Name,Seq),Stocks),
Seq = [Pre|Seq1],
count_islands(Pre,Seq1,[],0,Count).

count_islands(_Pre,[],_Is,C0,C) => C=C0.
count_islands(X,[X|L],Is,C0,C) =>
count_islands(X,L,Is,C0,C).
count_islands(Pre,[X|L],Is,C0,C) =>
update(X,Is,Is1,C0,C1),
(Pre<X -> Is2=[(Pre,X)|Is1]; Is2=Is1),
count_islands(X,L,Is2,C1,C).

update(_,[],NIs,C0,C) => NIs=[], C=C0.
update(X,[I|Is],NIs,C0,C), I=(Pre,Min), Min>X =>
(X > Pre -> NIs = [(Pre,X)|NIs1]; NIs=NIs1),
update(X,Is,NIs1,C0+1,C).
update(X,[I|Is],NIs,C0,C), I=(Pre,Min) =>
(X > Pre -> NIs = [(Pre,Min)|NIs1]; NIs=NIs1),
update(X,Is,NIs1,C0,C).
``````

## Making Friends

``` ```
import sat.

main =>
As = \$[people(4),
host_protocol(1,0,0),
host_protocol(2,1,1),
host_protocol(3,2,0),
confidence(0,50),
confidence(1,25),
confidence(2,25),
confidence(3,10)],
friend(As).

main([File]) =>
friend(As).

friend(As) =>
cl_facts(As, \$[people(-),host_protocol(+,-,-),confidence(+,-)]),
people(N),
G = new_map(),
foreach(I in 0..N-1)
G.put(I,[])
end,
foreach(I in 1..N-1)
host_protocol(I,H,P),
end,
foreach (I in 0..N-1)
printf("%w: %w\n",I,G.get(I))
end,
S = new_list(N),
S :: 0..1,
foreach (I in 1..N-1, J in I+1..N)
(edge(I-1,J-1,G) -> #~S[I] #\/ #~S[J]; true)
end,
T #= sum([S[I]*C : I in 1..N, confidence(I-1,C)]),
solve(\$[max(T)],S),
printf("max_confidence(%w).\n",T).

FsH = G.get(H),
G.put(H,[I|FsH]),
G.put(I,[H]).
FsH = G.get(H),
foreach (F in FsH)
FFs = G.get(F),
G.put(F,[I|FFs])
end,
G.put(I,FsH).