-module('dp18a-gy4').
-compile(export_all).
-author('patai@iit.bme.hu, hanak@iit.bme.hu, kapolnai@iit.bme.hu').
-vsn('$LastChangedDate: 2018-11-12 23:31:43 +0100 (Mon, 12 Nov 2018) $$').

% 1.
-spec seq(F::integer(), T::integer()) -> S::[integer()].
%% S = [F, F+1, ..., T].
seq(F, T) ->
    seq(F, T, []).

-spec seq(F::integer(), T::integer(), L::[integer()]) -> S::[integer()].
%% 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.
-spec all_different(Xs::[any()]) -> B::boolean().
%% B igaz, ha az L listában csupa különböző értékű elem van.
all_different([]) ->
    true;
all_different([H|T]) ->
    not lists:member(H, T) andalso all_different(T).

-spec all_different_2(Xs::[any()]) -> B::boolean().
all_different_2(L) -> length(L) =:= length(lists:usort(L)).

% 3.
-spec van2eleme(L::list()) -> R::boolean().
%% R =:= length(L) >= 2.
van2eleme([_,_|_]) -> true;
van2eleme(_) -> false.

% 4.
-spec duplak(Xs::[any()]) -> Ys::[any()].
%% Ys az Xs azon elemeinek listája, melyek azonosak az őket követő elemmel.
duplak([]) -> [];
duplak(L) ->
    [ E || {E,E} <- lists:zip(lists:sublist(L, length(L)-1), tl(L)) ].

% 5.
-spec all(Pred::fun((T::any()) -> boolean()), L::[T::any()]) -> B::boolean().
all(Pred, L) ->
    lists:foldl(fun(X,E) -> X andalso E end, true, lists:map(Pred, L)).

-spec all_2(Pred::fun((T::any()) -> boolean()), L::[T::any()]) ->
		   B::boolean().
%% B akkor és csak akkor igaz, ha Pred teljesül az L minden elemére.
all_2(Pred, [Hd|Tail]) ->
    case Pred(Hd) of
	true -> all_2(Pred, Tail);
	false -> false
    end;
all_2(Pred, []) when is_function(Pred, 1) ->
    true.

% 6.
-spec platok_hossza(Xs::[any()]) -> PHs::[{P::any, H::integer()}].
%% Platónak nevezzük az egyenlő értékű elemek sorozatát egy listában.
%% PHs olyan {P, H} párok listája, amelyekben P a platót képező
%% érték, H pedig e plató hossza (= azonos értékű elemeinek száma).
platok_hossza([])->
    [];
platok_hossza(Xs) ->
    {[P|_Ps] = PPs, Ss} = plato(Xs),
    [ {P, length(PPs)} | platok_hossza(Ss) ].

-spec plato(Xs::[any()]) -> PsMs::{Ps::[any()], Ms::[any()]}.
%% PsMs egy olyan {Ps, Ms} pár, amelyben Ps az Xs lista azonos értékű
%% elemekből álló, tovább már nem bővíthető prefixuma, Ms pedig az Xs
%% további elemeinek listája.
plato([X|[X|_Ys] = XYs]) ->
    {Ps, Ms} = plato(XYs),
    {[X|Ps], Ms};
plato([X|[_Y|_Ys] = YYs]) ->
    {[X], YYs};
plato(Xs) ->
    {Xs, []}.

% 7.
-spec sublist(L0::[any()], S::integer(), N::integer()) -> L::[any()].
%% Az L0 lista S-edik elemétől kezdődő és N hosszú részlistája az L lista.
sublist(L, S, N) ->
    [lists:nth(I, L) || I <- lists:seq(S, S+N-1)].

% 8.
-spec kozepe(M::list([any()])) -> M1::list([any()]).
%% M1 az M n*n-es négyzetes mátrix olyan (n/2)*(n/2) méretű részmátrixa,
%% mely az n/4+1. sor n/4+1. oszlopának elemétől kezdődik.
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) ].

-spec kozepe_2(M::list([any()])) -> M1::list([any()]).
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
    ].

% 9.
-spec laposkozepe(M::list([any()])) -> L::[any()].
%% Az L lista az M mátrix közepe elemeinek listája.
laposkozepe(M) ->
    lists:flatten(kozepe(M)).

-spec laposkozepe_2(M::list([any()])) -> L::[any()].
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
    ].

% 10.
-spec pivot(M::list([any()]),R::integer(),C::integer()) -> M1::list([any()]).
%% M1 az M mátrix R-edik sorának és C-edik oszlopának elhagyásával áll elő.
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
    ].

% 11.
-spec transpose(M::list([any()])) -> MT::list([any()]).
%% M transzponáltja MT.
transpose([]) ->
    [];
transpose([[] | Matrix]) ->
    transpose(Matrix);
transpose(Matrix) ->
    [[H || [H|_] <- Matrix] | transpose([T || [_|T] <- Matrix])].

-spec transpose_2(M::list([any()])) -> MT::list([any()]).
transpose_2([]) ->
    [];
transpose_2([[] | Matrix]) ->
    transpose_2(Matrix);
transpose_2(Matrix) ->
    [lists:map(fun hd/1, Matrix) | transpose_2(lists:map(fun tl/1, Matrix))].

% +1.
-spec osszetett(K::integer()) -> L::[integer()].
%% L tartalmazza az összetett számokat 4..K*K között, ismétlődés lehet.
osszetett(K) ->
   % lists:usort
([ J || I <- lists:seq(2,K), J <- lists:seq(I*2, K*K, I)]).

% +2.
-spec primek(K::integer()) -> L::[integer()].
%% L tartalmazza a prímszámokat 2..K*K között.
primek(K) ->
    Os = osszetett(K),
    [ X || X <- lists:seq(2,K*K), not lists:member(X,Os)].

% +3.
-spec zip(Xs::[any()], Ys::[any()]) -> XYs::[{any(), any()}].
%% XYs olyan párok listája, amelyek első eleme az Xs, második eleme
%% az Ys lista azonos pozíciójú eleme.
zip([], []) ->
    [];
zip([H1|T1], [H2|T2]) ->
    [{H1,H2}|zip(T1,T2)].

-spec unzip(XYs::[{any(), any()}]) -> {Xs::[any()], Ys::[any()]}.
%% XYs olyan párok listája, amelyek első eleme az Xs, második eleme
%% az Ys lista azonos pozíciójú eleme.
unzip([]) ->
    {[],[]};
unzip([{H1,H2}|T]) ->
    {T1,T2} = unzip(T),
    {[H1|T1],[H2|T2]}.

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

-type fa()      :: level | {any(),fa(),fa()}.
-type egeszfa() :: level | {integer(),egeszfa(),egeszfa()}.

% 12.
-spec fa_noveltje(F0::egeszfa()) -> F::egeszfa().
%% Az F fa minden címkéje eggyel nagyobb az F0 azonos helyen lévő címkéjénél.
fa_noveltje(level) ->
    level;
fa_noveltje({C,Bfa,Jfa}) ->
    {C+1, fa_noveltje(Bfa), fa_noveltje(Jfa)}.

% 13.
-spec fa_tukorkepe(F0::fa()) -> F::fa().
%% F az F0 fa tükörképe.
fa_tukorkepe(level) ->
    level;
fa_tukorkepe({C,Bfa,Jfa}) ->
    {C, fa_tukorkepe(Jfa), fa_tukorkepe(Bfa)}.

%14.
-spec inorder(F::fa()) -> L::list().
%% L az F fa elemeinek a fa inorder bejárásával létrejövő listája.
inorder(level) ->
    [];
inorder({C,Bfa,Jfa}) ->
    inorder(Bfa) ++ [C | inorder(Jfa)].

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

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

% 17.
-spec cimkek(F::fa()) -> L::[any()].
%% L az F címkéinek listája inorder sorrendben.
cimkek(Fa) -> cimkek(Fa, []).

-spec cimkek(F::fa(), L0::[any()]) -> L::[any()].
%% L az F címkéinek listája inorder sorrendben L0 elé fűzve.
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],
     all_different([1,2,3,1]) =:= false,
     all_different([1,2,3]) =:= true,
     all_different_2([1,2,3,1]) =:= false,
     all_different_2([1,2,3]) =:= true,
     van2eleme([]) =:= false,
     van2eleme([a]) =:= false,
     van2eleme([a,b]) =:= true,
     van2eleme([a,b,c]) =:= 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]),
     all_2(fun is_atom/1, [a,b,c]) and not all(fun is_atom/1, [a,b,1]),
     platok_hossza([a,a,a,b,b,c,c,c,c,d,e,f,f,f,g,h]) =:=
	 [{a,3},{b,2},{c,4},{d,1},{e,1},{f,3},{g,1},{h,1}],
     platok_hossza([a,a,a,b,b,d,f,f,h]) =:= [{a,3},{b,2},{d,1},{f,2},{h,1}],
     sublist([1,2,3,4],2,2) =:= [2,3],
     sublist([1,2,3,4],2,3) =:= [2,3,4],
     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]],
     transpose([[a,b],
                [c,d],
                [e,f]]) =:= [[a,c,e],
                             [b,d,f]],
     transpose_2([[a,b],
                  [c,d],
                  [e,f]]) =:= [[a,c,e],
                               [b,d,f]],
     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],
     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]}
    ]
;

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}}}}},
%    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}},
     inorder(T1) =:= [3,4,5,6,7],
     tartalmaz(x, T1) =:= false,
     tartalmaz(x, T2) =:= true,
     elofordul(x, T1) =:= 0,
     elofordul(x, T2) =:= 4,
     cimkek(T1) =:= [3,4,5,6,7]
    ]
%	       )
.