-module('dp16a-gy4').
-compile(export_all).
-author('patai@iit.bme.hu, hanak@iit.bme.hu, kapolnai@iit.bme.hu').
-vsn('$LastChangedDate: 2016-10-11 16:49:37 +0200 (Tue, 11 Oct 2016) $$').


% 1
seq(F, T) ->
    seq(F, T, []).

% seq(F, T, L) = F-T sorozat L elé fűzve.
seq(F, T, L) when T<F -> L;
seq(F, T, L) ->
    seq(F, T-1, [T|L]).

% 2
zip([], []) ->
    [];
zip([H1|T1], [H2|T2]) ->
    [{H1,H2}|zip(T1,T2)].
 
unzip([]) ->
    {[],[]};
unzip([{H1,H2}|T]) ->
    {T1,T2} = unzip(T),
    {[H1|T1],[H2|T2]}.

% 3
flatten([]) ->
    [];
flatten([H|T]) when is_list(H) ->
    flatten(H) ++ flatten(T);
flatten([H|T]) -> % when not is_list(H)
    [H|flatten(T)].


% szorgalmi:
flatten2(DL) -> flatten(DL, []).

% flatten(DL, Tail) = DL kilapítva a Tail lista elé fűzve.
flatten([H|T], Tail) when is_list(H) ->
    flatten(H, flatten(T, Tail));
flatten([H|T], Tail) ->
    [H|flatten(T, Tail)];
flatten([], Tail) ->
    Tail.


% 4
kozepe(M) ->
    N = length(M),
    N4 = N div 4,
    N2 = N div 2,
    [ lists:sublist(R, N4 + 1, N2) || R <- lists:sublist(M, N4 + 1, N2) ].

kozepe_2(M) ->
    N = length(M),
    Seq = lists:seq(N div 4 + 1, N div 4 + N div 2),
    [ [ lists:nth(C, lists:nth(R, M)) || C <- Seq ]
      || R <- Seq
    ].

% 5
laposkozepe(M) ->
    lists:flatten(kozepe(M)).

laposkozepe_2(M) ->
    N = length(M),
    Seq = lists:seq(N div 4 + 1, N div 4 + N div 2),
    [ lists:nth(C, lists:nth(R, M))
      || R <- Seq,
         C <- Seq
    ].

% 6
pivot(M, R, C) ->
    N = length(M),
    [ [ lists:nth(Co, lists:nth(Ro, M)) || Co <- lists:seq(1, N), Co =/= C ]
      || Ro <- lists:seq(1, N), Ro =/= R
    ].

% 7.
all_different_a([]) ->
    true;
all_different_a([H|T]) ->
    not lists:member(H, T) andalso all_different_a(T).

all_different(L) -> length(L) =:= length(lists:usort(L)).

% 8.
van2eleme([_,_|_]) -> true;
van2eleme(_) -> false.

% 9.
duplak([]) -> [];
duplak(L) ->
    [ E || {E,E} <- lists:zip(lists:sublist(L, length(L)-1), tl(L)) ].

% 10.
all(Pred, List) ->
    lists:foldl(fun erlang:'and'/2, true, lists:map(Pred, List)).

all2(Pred, [Hd|Tail]) ->
    case Pred(Hd) of
	true -> all2(Pred, Tail);
	false -> false
    end;
all2(Pred, []) when is_function(Pred, 1) ->
    true. 

% 11.
transpose([]) ->
    [];
transpose([[] | Matrix]) ->
    transpose(Matrix);
transpose(Matrix) ->
%    [lists:map(fun hd/1, Matrix) | transpose(lists:map(fun tl/1, Matrix))].
    [[H || [H|_] <- Matrix] | transpose([T || [_|T] <- Matrix])].


% +1
osszetett(K) ->
   % lists:usort
([ J || I <- lists:seq(2,K), J <- lists:seq(I*2, K*K, I)]).

% + 2
primek(K) ->
    Os = osszetett(K),
    [ X || X <- lists:seq(2,K*K), not lists:member(X,Os)].

    
test() ->
    M=[[a,b,e,f],
       [c,d,g,h],
       [i,j,m,n],
       [k,l,o,p]],
    [
     seq(10,13) =:= [10,11,12,13],
     zip([1,2,3], [a,b,c]) =:= [{1,a},{2,b},{3,c}],
     unzip([{1,a},{2,b},{3,c}]) =:= {[1,2,3], [a,b,c]},
     flatten([1,[2,3],[[[[4]]],[5,[6]]]]) =:= [1,2,3,4,5,6],
     flatten2([1,[2,3],[[[[4]]],[5,[6]]]]) =:= [1,2,3,4,5,6],
     kozepe(M) =:= [[d,g],[j,m]],
     kozepe_2(M) =:= [[d,g],[j,m]],
     laposkozepe(M) =:= [d,g,j,m],
     laposkozepe_2(M) =:= [d,g,j,m],
     pivot(M,2,3) =:= [[a,b,f],[i,j,n],[k,l,p]],
     van2eleme([]) =:= false,
     van2eleme([a]) =:= false,
     van2eleme([a,b]) =:= true,
     van2eleme([a,b,c]) =:= true,
     osszetett(5) =:= [4,6,8,10,12,14,16,18,20,22,24,6,9,12,15,18,21,24,8,12,16,20,24,10,15,20,25],
     primek(5) =:= [2,3,5,7,11,13,17,19,23],
     all_different([1,2,3,1]) =:= false,
     all_different([1,2,3]) =:= true,
     all_different_a([1,2,3,1]) =:= false,
     all_different_a([1,2,3]) =:= true,
     duplak([1,2,3]) =:= [],
     duplak([1,1,2,3,3,3]) =:= [1,3,3],
     all(fun is_atom/1, [a,b,c]) and not all(fun is_atom/1, [a,b,1]),
     all2(fun is_atom/1, [a,b,c]) and not all2(fun is_atom/1, [a,b,1]),
     transpose([[a,b],
                [c,d],
                [e,f]]) =:= [[a,c,e],
                             [b,d,f]]
    ].

%---------------------------------------------------------------------------
%                           8 VEZÉR A SAKKTÁBLÁN
%---------------------------------------------------------------------------

atlok(L) ->
    [{X+Y,X-Y} || {X,Y} <- L].


nem_utik_egymast(J) ->
    {AtlokBalrol,AtlokJobbrol}
        = unzip(atlok(zip(seq(1, length(J)), J))),
    all_different(AtlokBalrol) andalso all_different(AtlokJobbrol).

% Kevésbé rugalmas megoldás:
perms_1() ->
    Ds = lists:seq(1,8),
    [ [A,B,C,D,E,F,G,H] || A <- Ds,
                           B <- Ds -- [A],
                           C <- Ds -- [A,B],
                           D <- Ds -- [A,B,C],
                           E <- Ds -- [A,B,C,D],
                           F <- Ds -- [A,B,C,D,E],
                           G <- Ds -- [A,B,C,D,E,F],
                           H <- Ds -- [A,B,C,D,E,F,G]
    ].
                           
% Rugalmasabb megoldás:
perms_2() ->
    perms_2(lists:seq(1,8)).
    
% perms_2(L) az L lista elemeinek permutációit tartalmazó lista.
% Hátulról épít.
perms_2([X]) ->
    [[X]];
perms_2(L) ->
    [ [H|T] || H <- L, T <- perms_2(L--[H]) ].

perms_3() -> perms_3(lists:seq(1,8), []).

% perms_3(L) az L lista elemeinek permutációit tartalmazó,
% Prefix mögé fűzött lista. Elölről épít.
perms_3([], Prefix) ->
    [Prefix];
perms_3(L, Prefix) ->
    [ T || H <- L, T <- perms_3(L--[H], Prefix ++ [H]) ].

% 15.
vezerek8_1() ->
    [ J || J <- perms_1(), nem_utik_egymast(J) ].

% 16.
vezerek8_2() ->
    Ds = lists:seq(1,8),
    [ [A,B,C,D,E,F,G,H] || A <- Ds,
                           B <- Ds -- [A],
                           C <- Ds -- [A,B],
                           nem_utik_egymast([A,B,C]),
                           D <- Ds -- [A,B,C],
                           nem_utik_egymast([A,B,C,D]),
                           E <- Ds -- [A,B,C,D],
                           nem_utik_egymast([A,B,C,D,E]),
                           F <- Ds -- [A,B,C,D,E],
                           nem_utik_egymast([A,B,C,D,E,F]),
                           G <- Ds -- [A,B,C,D,E,F],
                           nem_utik_egymast([A,B,C,D,E,F,G]),
                           H <- Ds -- [A,B,C,D,E,F,G],
                           nem_utik_egymast([A,B,C,D,E,F,G,H])
    ].

% 17.
vezerek_1(N) ->
    [J || J <- perms_2(lists:seq(1,N)),
          nem_utik_egymast(J) ].

% 18. vö perms_3(L)
vezerek_2(N) ->
    vezerek_2(lists:seq(1,N), []).

% @spec vezerek_2(SzabadOszlopok::[oszlop()], Jelolt::jelolt()) -> [jelolt()].
% Olyan megoldások listája, melyek Jeloltből építhetőek,
% ahol Jeloltben nem foglaltak SzabadOszlopok (ami Jelolt komplementere).
vezerek_2([], Jelolt) ->
    [Jelolt];
vezerek_2(L, Jelolt) ->
    [ T || H <- L,
           begin Jelolt1 = Jelolt ++ [H], nem_utik_egymast(Jelolt1) end,
           T <- vezerek_2(L--[H], Jelolt1) ].



test(8) ->
    [
     atlok([{1,1}, {2,3}]) =:= [{2,0}, {5,-1}],
     nem_utik_egymast([1,3,5]) =:= true,
     nem_utik_egymast([1,5,3]) =:= false,
     length(perms_1()) =:= 40320,
     length(perms_2()) =:= 40320,
     length(perms_3()) =:= 40320,
     length(vezerek8_1()) =:= 92,
     length(vezerek8_2()) =:= 92,
     length(vezerek_1(8)) =:= 92,
     length(vezerek_2(8)) =:= 92,
     begin
         _ = statistics(runtime),
         V1 = vezerek8_1(),
         {_,Time1} = statistics(runtime),
         V2 = vezerek8_2(),
         {_,Time2} = statistics(runtime),
         io:write({Time1,Time2}),
         lists:sort(V1) =:= lists:sort(V2)
             andalso Time2 < Time1
     end,
     [ length(vezerek_2(N)) || N <- lists:seq(1,10) ] =:=
         [1,0,0,2,10,4,40,92,352,724]
    ].