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]) =>
    Fs = read_file_terms(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]) =>
    Fs = read_file_terms(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]) =>
    Fs = read_file_terms(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) ?=>
    Action = [4,add],
    Cost = 1,
    B = (4+A) /\ 0xff,
    NewS = [B,Fs,G].
action([A,[_|Fs],G],NewS,Action,Cost) ?=>
    Action = [neg,4,add],
    Cost = 2,
    B = (252+A) /\ 0xff,
    NewS = [B,Fs,G].
action([A,[_|Fs],G],NewS,Action,Cost) ?=>
    Action = [not,4,add],
    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).


Smarty Road Runner

 
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)],
    roadrunner(Fs).          

main([File]) =>
    Fs = read_file_terms(File),
    roadrunner(Fs).

roadrunner(Fs) =>
    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,
    Road = new_array(MaxX,MaxY),
    Road :: 0..1,
    foreach (X in 1..MaxX, Y in 1..MaxY)
        (Hill[X,Y] == 1 ->
            Road[X,Y] = 0
        ; 
            attacked_positions(Hill,X,Y,MaxX,MaxY,AttackedPs),
            sum([Laser[X1,Y1] : (X1,Y1) in [(X,Y)|AttackedPs]]) #= 0 #=> Road[X,Y],
            Laser[X,Y] #=> #~Road[X,Y],
            foreach ((X1,Y1) in AttackedPs)
                Laser[X,Y] #=> #~Road[X1,Y1],
                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 
    solve([$max(NOneCells)],(Laser,Road)),
    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]) =>
    Fs = read_file_terms(File),
    whitesand(Fs).

whitesand(Fs) =>
    Needs = [{A,U} : $need(A,U) in Fs],
    Offers = [{T,O,A,U} : $offer(T,O,A,U) in Fs].sort(),
    Prices = [{T,O,P} : $price(T,O,P) in Fs].sort(),
    member($maxacceptedoffer(K),Fs),
    M = len(Prices),
    Vs = new_list(M),
    Vs :: 0..1,
    foreach ({A,NeededU} in Needs)
        BuyUList = [$(V*U) : {{T,O,_}, V} in zip(Prices,Vs), (member({T,O,A,U},Offers) ->true; U = 0)],
        sum(BuyUList) #>= NeededU
    end,
    constr_count(Prices,Vs,0,0,K),
    TotalPrice #= sum([V*P : {{_,_,P}, V} in zip(Prices,Vs)]),
    solve([$min(TotalPrice)],Vs),
    printf("totalcost(%d).\n",TotalPrice).

constr_count([],_,_,S,K) => S #=< K.
constr_count([{T,_,_}|Prices],[V|Vs],T,S,K) =>
    constr_count(Prices,Vs,T,$(S+V),K).
constr_count([{T,_,_}|Prices],[V|Vs],_T,S,K) =>
    S #=< K,
    constr_count(Prices,Vs,T,V,K).