-module('dp15a-gy7').
-compile(export_all).
-author('patai@iit.bme.hu, hanak@iit.bme.hu, kapolnai@iit.bme.hu').
-vsn('2011-10-28 ($LastChangedDate: 2015-10-28 15:04:33 +0100 (Wed, 28 Oct 2015) $$').


% 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
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
    ].

% 3
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
    ].

% 4
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
    ].

% 5.
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)).

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

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

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

% 9.
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)].

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

    

%---------------------------------------------------------------------------
%                           II. RÉSZ: FÁK
%---------------------------------------------------------------------------

% 10.
fa_noveltje(level) ->
    level;
fa_noveltje({C,Bfa,Jfa}) ->
    {C+1, fa_noveltje(Bfa), fa_noveltje(Jfa)}.

% 11.
fa_tukorkepe(level) ->
    level;
fa_tukorkepe({C,Bfa,Jfa}) ->
    {C, fa_tukorkepe(Jfa), fa_tukorkepe(Bfa)}.

% 12.
fa_balerteke(level) ->
    error;
fa_balerteke({C,level,_}) ->
    {ok, C};
fa_balerteke({_,Bfa,_}) ->
    fa_balerteke(Bfa).

fa_jobberteke(level) ->
    error;
fa_jobberteke({C,_,level}) ->
    {ok, C};
fa_jobberteke({_,_,Jfa}) ->
    fa_jobberteke(Jfa).

% 13.
rendezett_fa(level) ->
    true;
rendezett_fa({C,Bfa,Jfa}) ->
    case fa_jobberteke(Bfa) of
        error  -> true;
        {ok,J} -> J < C
    end andalso
        rendezett_fa(Bfa) andalso
    case fa_balerteke(Jfa) of
        error  -> true;
        {ok,B} -> C < B
    end andalso
        rendezett_fa(Jfa).

% 14.
tartalmaz(_, level) ->
    false;
tartalmaz(C, {C,_,_}) ->
    true;
tartalmaz(C, {_,Bfa,Jfa}) ->
    tartalmaz(C, Bfa) orelse tartalmaz(C, Jfa).

% 15.
elofordul(_, level) ->
    0;
elofordul(C, {R,Bfa,Jfa}) ->
    if C =:= R -> 1;
       true    -> 0
    end
        + elofordul(C, Bfa) + elofordul(C, Jfa).

% 16.
utak(Fa) -> utak(Fa, []).

% @spec utak(F::fa(), Eddigi::ut()) -> CimkezettUtak::[{C::term(), U::ut()}].
% A CimkezettUtak lista az F fa minden csomópontjához egy kételemű ennest
% társít, amelynek első eleme (C) a csp. címkéje, második eleme (U) az
% Eddigi útvonal és a csp. útvonala összefűzve.
utak(level, _) ->
    [];
utak({C,Bfa,Jfa}, Eddigi) ->
    Eddigi1 = Eddigi ++ [C], % Költséges művelet!
    [{C, Eddigi} | utak(Bfa, Eddigi1)] ++ utak(Jfa, Eddigi1).

% 17.
cutak_a(C, Fa) ->
    [CU || {C0,_} = CU <- utak(Fa), C0 =:= C].

cutak_b(C, Fa) -> cutak(C, Fa, []).

% @spec ut(C::term(), F::fa(), Eddigi::ut()) ->
%               CimkezettUtak::[{C::term(), U::ut()}].
% A CimkezettUtak lista az F fa minden C címkéjű csomópontjához egy kételemű
% ennest társít, amelynek első eleme C, második eleme az Eddigi útvonal és
% és a csp. útvonala összefűzve.
cutak(_, level, _) ->
    [];
cutak(C, {R,Bfa,Jfa}, Eddigi) ->
    Eddigi1 = Eddigi ++ [R],
    Cutak = cutak(C, Bfa, Eddigi1) ++ cutak(C, Jfa, Eddigi1),
    if R =:= C -> [{C, Eddigi} | Cutak];
       true    -> Cutak
    end.

% 18.
cimkek(Fa) -> cimkek(Fa, []).

cimkek(level, L) ->
    L;
cimkek({R,Bfa,Jfa}, L) ->
    cimkek(Bfa, [R|cimkek(Jfa, L)]).


test(lista) ->
    M=[[a,b,e,f],
       [c,d,g,h],
       [i,j,m,n],
       [k,l,o,p]],
    [
     seq(10,13) =:= [10,11,12,13],
%     flatten([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,
     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]},
     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]),
     transpose([[a,b],
                [c,d],
                [e,f]]) =:= [[a,c,e],
                             [b,d,f]]
    ]
;

test(fa) ->
    T1 = {4,
          {3,level,level},
          {6,
           {5,level,level},
           {7,level,level}}},
    T2 = {a,
          {b, {x,level,level}, level},
          {c,
           level,
           {d,
            {x,{e,level,level},level},
            {a, {x,level,level},{x,level,level}}}}},
    T3 = {4,
          {3,
           {2,level,level},
           {1,level,level}},
          {6,
           {5,level,level},
           {7,level,level}}},
%    lists:foldl(fun erlang:'and'/2, true,
    [fa_noveltje(T1) =:= {5,{4,level,level},{7,{6,level,level},{8,level,level}}},
     fa_tukorkepe(T1) =:= {4,{6,{7,level,level},{5,level,level}},{3,level,level}},
     fa_balerteke(T1) =:= {ok, 3},
     fa_balerteke(level) =:= error,
     fa_balerteke(T2) =:= {ok, x},
     fa_jobberteke(T1) =:= {ok, 7},
     rendezett_fa(T1) =:= true,
     rendezett_fa(T2) =:= false,
     rendezett_fa(T3) =:= false,
     tartalmaz(x, T1) =:= false,
     tartalmaz(x, T2) =:= true,
     elofordul(x, T1) =:= 0,
     elofordul(x, T2) =:= 4,
     utak(T1) =:= [{4,[]},{3,[4]},{6,[4]},{5,[4,6]},{7,[4,6]}],
     utak(T2) =:= [{a,[]},{b,[a]},{x,[a,b]},{c,[a]},{d,[a,c]},{x,[a,c,d]},
                   {e,[a,c,d,x]},{a,[a,c,d]},{x,[a,c,d,a]},{x,[a,c,d,a]}],
     cutak_a(x,T1) =:= [],
     cutak_a(x,T2) =:= [{x,[a,b]},{x,[a,c,d]},{x,[a,c,d,a]},{x,[a,c,d,a]}],
     cutak_a(x,T1) =:= cutak_b(x,T1),
     cutak_a(x,T2) =:= cutak_b(x,T2),
     cimkek(T1) =:= [3,4,5,6,7]
    ]
%	       )
.