:-use_module(library(clpfd)).
:-use_module(library(lists)).

toast(N,Pairs):-
        statistics(runtime, [T1,_]), 
        
        MaxL is 2*N,
        length(Left,N), domain(Left,1,MaxL),
        length(Right,N), domain(Right,1,MaxL),
        pairs(Left ,Right,Pairs,All),
        lex_chain(Pairs),
        shift(Left),
        
        N1 is (N//2) * 2,
        incList(1,N1, ValsMust), length(Rep1,N1), domain(Rep1,2,2),
        N2 is N1+1,
        incList(N2,MaxL, ValsCan), Diff is MaxL-N2+1, length(Rep2,Diff), domain(Rep2,0,2),
        keys_and_values(Keys1,ValsMust,Rep1),
        keys_and_values(Keys2,ValsCan,Rep2),
        append(Keys1,Keys2,Keys),
        
/*        incList(1,MaxL, Vals),
        length(Rep,MaxL), domain(Rep,0,2),
        keys_and_values(Keys,Vals,Rep),*/
        
        global_cardinality(All,Keys),

        maximum(MaxSlot,All),
        MaxSlot #>= N,
        
        labeling([minimize(MaxSlot)],All),
        
        statistics(runtime, [T2,_]),
        Time is T2-T1, write(time=Time),nl.

pairs([],[],[],[]).
pairs([L|LT],[R|RT], [[L,R]|T], [L,R|TT]):-
 %       L #\= R,!,
        L #< R,!,
        pairs(LT,RT,T,TT).

shift([]).
shift([A|T]):-
        (T=[_,B|_] ->
           A #< B,!,
           shift(T)
        ;
           true
        ).
        
incList(N,N,[N]).
incList(I,N,[I|T]):-
        I<N, NextI is I+1,
        incList(NextI,N,T).