# 2019 LP Programming Contest

## Alien sums

``` ```
import cp.

main =>
Fs = \$[a(0,99),  a(1,117), a(2,99), a(3,100), a(4,117), a(5,99),
b(0,117), b(1,117), b(2,99), b(3,117), b(4,116), b(5,99),
c(0,117), c(1,100), c(2,99), c(3,116), c(4,99),  c(5,117)],
alien(Fs).

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

alien(Fs) =>
N = len(Fs) div 3,
A = new_array(N),
B = new_array(N),
C = new_array(N),
foreach (\$a(I,D) in Fs)
A[I+1] = D
end,
foreach (\$b(I,D) in Fs)
B[I+1] = D
end,
foreach (\$c(I,D) in Fs)
C[I+1] = D
end,
Ds = sort_remove_dups(to_list(A) ++ to_list(B) ++ to_list(C)),
Base = len(Ds),
Vs = new_list(Base),
all_different(Vs),
Vs :: 0..Base-1,
M = new_map(),
foreach ({V,D} in zip(Vs,Ds))
M.put(D,V)
end,
sum(A,Base,M,AExp),
sum(B,Base,M,BExp),
sum(C,Base,M,CExp),
AExp + BExp #= CExp,
solve(Vs),
foreach (D in Ds)
V = M.get(D),
printf("decode(%d,%d).\n",D,V)
end.

sum(A,Base,M,Exp) =>
S = 0,
P = 1,
foreach (I in 1..len(A))
V = M.get(A[I]),
S := \$(S + V*P),
P := (Base*P)
end,
Exp = S.
``````

## Fighting with the gang of Billy the Kid

``` ```
import sat.

main =>
Fs = \$[town(1),
town(2),
town(3),
town(4),
town(5),
town(6),
connected(1,4),
connected(1,2),
connected(2,3),
connected(3,4),
connected(3,5),
connected(4,5),
connected(5,6),
townsintravel(3)],
billykid(Fs).

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

billykid(Fs) =>
once member(\$townsintravel(Size),Fs),
N = max([V : \$town(V) in Fs]),
A = new_array(N),
foreach (I in 1..N)
A[I] = []
end,
foreach(\$connected(X,Y) in Fs)
A[X] := [Y|A[X]],
A[Y] := [X|A[Y]]
end,
S = new_array(N),
S :: 0..1,
sum(S) #= NSelected,
foreach (I in 1..N)
Paths = find_all(Path,\$path(I,Size,[],A,Path)),
foreach (P in Paths)
(last(P) > first(P) -> sum([S[V] : V in P]) #>= 1; true)
end
end,
solve([\$min(NSelected)],S),
printf("selected(%d).\n",NSelected).

table
path(X,1,Path0,_A,Path) => Path = [X|Path0].
path(X,Size,Path0,A,Path) =>
Neibs = A[X],
member(Neib,Neibs),
not member(Neib,Path0),
path(Neib,Size-1,[X|Path0],A,Path).
``````

## Binary four fours

``` ```
import planner.

main =>
Fs = \$[n(10)],
binfours(Fs).

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

binfours([n(N)]) =>
best_plan([4,[4,4,4],N],8,Plan,_Len),
rpn(Plan,4,R),
output(R,0).

final([G,[],G]) => true.

action([A,Fs,G],NewS,Action,Cost) ?=>
Action = [neg],
Cost = 1,
B = (-A) /\ 0xff,
NewS = [B,Fs,G].
action([A,Fs,G],NewS,Action,Cost) ?=>
Action = [not],
Cost = 1,
B = (~A) /\ 0xff,
NewS = [B,Fs,G].
action([A,[_|Fs],G],NewS,Action,Cost) ?=>
Cost = 1,
B = (4+A) /\ 0xff,
NewS = [B,Fs,G].
action([A,[_|Fs],G],NewS,Action,Cost) ?=>
Cost = 2,
B = (252+A) /\ 0xff,
NewS = [B,Fs,G].
action([A,[_|Fs],G],NewS,Action,Cost) ?=>
Cost = 2,
B = (251+A) /\ 0xff,
NewS = [B,Fs,G].
action([A,[_|Fs],G],NewS,Action,Cost) ?=>
Action = [4,mul],
Cost = 1,
B = (4*A) /\ 0xff,
NewS = [B,Fs,G].
action([A,[_|Fs],G],NewS,Action,Cost) ?=>
Action = [neg,4,mul],
Cost = 2,
B = (252*A) /\ 0xff,
NewS = [B,Fs,G].
action([A,[_|Fs],G],NewS,Action,Cost) ?=>
Action = [not,4,mul],
Cost = 2,
B = (251*A) /\ 0xff,
NewS = [B,Fs,G].

rpn([],R0,R) => R = flatten(R0).
rpn([[Op]|Plan],R0,R) =>
rpn(Plan,[R0,Op],R).
rpn([[4,Op]|Plan],R0,R) =>
rpn(Plan,[4,R0,Op],R).
rpn([[Op1,4,Op2]|Plan],R0,R) =>
rpn(Plan,[4,Op1,R0,Op2],R).

output([],_I) => true.
output([A|R],I) =>
printf("op(%d,%w).\n",I,A),
output(R,I+1).
``````

``` ```
import sat.

main =>
Fs = \$[xcoord(1),  xcoord(2),  xcoord(3),
xcoord(4),  xcoord(5),  xcoord(6),
xcoord(7),
ycoord(1),  ycoord(2),  ycoord(3),
ycoord(4),  ycoord(5),  ycoord(6),
ycoord(7),
hill(4,5),  hill(4,1),  hill(1,3),
hill(2,5),  hill(7,2),  hill(3,5),
hill(4,6),  hill(1,4),  hill(6,4),
hill(2,1),
number(4,6,0),  number(1,4,2),
number(6,4,1),  number(2,1,2)],

main([File]) =>

MaxY = max([X : \$xcoord(X) in Fs]),
MaxX = max([Y : \$xcoord(Y) in Fs]),
Laser = new_array(MaxX,MaxY),
Hill = new_array(MaxX,MaxY),
foreach (\$hill(X,Y) in Fs)
Hill[X,Y] = 1,
Laser[X,Y] = 0
end,
Laser :: 0..1,
foreach (\$number(X,Y,K) in Fs)
sum([Laser[X1,Y1] : (Dx,Dy) in [(-1,0),(1,0),(0,-1),(0,1)], X1 = X+Dx, Y1 = Y+Dy, X1 >= 1, X1 =< MaxX, Y1 >= 1, Y1 =< MaxY]) #= K
end,
foreach (X in 1..MaxX, Y in 1..MaxY)
(Hill[X,Y] == 1 ->
;
attacked_positions(Hill,X,Y,MaxX,MaxY,AttackedPs),
sum([Laser[X1,Y1] : (X1,Y1) in [(X,Y)|AttackedPs]]) #= 0 #=> Road[X,Y],
foreach ((X1,Y1) in AttackedPs)
Laser[X,Y] #=> #~Laser[X1,Y1]
end
)
end,
NOneCells #= sum([Road[X,Y] : X in 1..MaxX, Y in 1..MaxY]),
subcircuit_grid(Road,NOneCells),   % a new built-in in version 2.7b16
printf("safecircuitlen(%d).\n",NOneCells).

attacked_positions(Hill,X,Y,MaxX,MaxY,AttackedPs) =>
attacked_positions(Hill,X-1,Y,-1,0,MaxX,MaxY,AttackedPs,AttackedPs1),
attacked_positions(Hill,X+1,Y,1,0,MaxX,MaxY,AttackedPs1,AttackedPs2),
attacked_positions(Hill,X,Y-1,0,-1,MaxX,MaxY,AttackedPs2,AttackedPs3),
attacked_positions(Hill,X,Y+1,0,1,MaxX,MaxY,AttackedPs3,[]).

attacked_positions(Hill,X,Y,Dx,Dy,MaxX,MaxY,AttackedPs,AttackedPsR),
X >= 1, X =< MaxX,
Y >= 1, Y =< MaxY
=>
(Hill[X,Y]==1 ->
AttackedPs = AttackedPsR
;
AttackedPs = [(X,Y)|AttackedPs1],
attacked_positions(Hill,X+Dx,Y+Dy,Dx,Dy,MaxX,MaxY,AttackedPs1,AttackedPsR)
).
attacked_positions(_Hill,_X,_Y,_Dx,_Dy,_MaxX,_MaxY,AttackedPs,AttackedPsR) =>
AttackedPs = AttackedPsR.
``````

## Organizing a visit to White Sands

``` ```
import sat.

main =>
Fs = \$[offer(1,1,1,1),     offer(2,1,3,2),     offer(3,1,1,3),
offer(1,1,3,1),     price(2,1,3),       offer(3,1,2,1),
offer(1,1,4,1),     offer(3,1,3,2),
price(1,1,7),       offer(2,2,1,2),     price(3,1,5),
offer(2,2,2,1),
offer(1,2,2,2),     offer(2,2,3,2),     offer(3,2,2,2),
offer(1,2,5,1),     offer(2,2,5,2),     offer(3,2,4,2),
price(1,2,7),       price(2,2,9),       price(3,2,5),
offer(2,3,4,2),
price(2,3,4),
maxacceptedoffer(2),
need(1,3), need(2,2), need(3,4), need(4,1), need(5,3)],
whitesand(Fs).

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

whitesand(Fs) =>
Prices = [F : F in Fs, F = \$price(T,O,P)].sort(),
Ts = [T : \$price(T,O,P) in Prices].sort_remove_dups(),
member(\$maxacceptedoffer(K),Fs),
M = len(Prices),
Vs = new_list(M),
Vs :: 0..1,
foreach (\$need(A,NeededU) in Fs)
BuyUList = [\$(V*U) : {\$price(T,O,_), V} in zip(Prices,Vs), (member(\$offer(T,O,A,U), Fs) -> true; U = 0)],