-module(dp11a_gy4). -compile(export_all). -author('patai@iit.bme.hu, hanak@iit.bme.hu, kapolnai@iit.bme.hu'). -vsn('2011-10-28 ($LastChangedDate: 2012-09-15 17:47:13 +0200 (Sat, 15 Sep 2012) $$'). test() -> 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, rendezett_fa(T1) =:= rendezett_fa_2(T1), rendezett_fa(T2) =:= rendezett_fa_2(T2), rendezett_fa(T3) =:= rendezett_fa_2(T3), rendezett_fa(T1) =:= rendezett_fa_3(T1), rendezett_fa(T2) =:= rendezett_fa_3(T2), rendezett_fa(T3) =:= rendezett_fa_3(T3), 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), ok =:= ok ] % ) . % 1. fa_noveltje(level) -> level; fa_noveltje({C,Bfa,Jfa}) -> {C+1, fa_noveltje(Bfa), fa_noveltje(Jfa)}. % 2. fa_tukorkepe(level) -> level; fa_tukorkepe({C,Bfa,Jfa}) -> {C, fa_tukorkepe(Jfa), fa_tukorkepe(Bfa)}. % 3. a) fa_balerteke(level) -> error; fa_balerteke({C,level,_}) -> {ok, C}; fa_balerteke({_,Bfa,_}) -> fa_balerteke(Bfa). % 3. b) fa_jobberteke(level) -> error; fa_jobberteke({C,_,level}) -> {ok, C}; fa_jobberteke({_,_,Jfa}) -> fa_jobberteke(Jfa). % 4. 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). % 4. hatékonyabban (bonyolult, ráadásul lehetne még javítani) rendezett_fa_2(level) -> true; rendezett_fa_2({C,Bfa,Jfa}=F) -> Also = case fa_balerteke(Bfa) of {ok, AE} -> AE; error -> C end, Felso = case fa_jobberteke(Jfa) of {ok, FE} -> FE; error -> C end, rendezett_fa_2_kozott(Also,Felso,F). % rendezett_fa_2_kozott(Also::term(), Felso::term(), F::fa()) -> B::bool() % B igaz, ha az F fa rendezett ÉS minden C címkéjére Also =< C andalso C =< Felso, % ahol az = csak akkor megengedett, ha C balérték (Also=C) vagy jobbérték (C=Felso). rendezett_fa_2_kozott(Also, Felso, {C,level,level}) -> Also =< C andalso C =< Felso; rendezett_fa_2_kozott(Also, Felso, {C,Bfa,level}) -> Also < C andalso C =< Felso andalso rendezett_fa_2_kozott(Also,C,Bfa); rendezett_fa_2_kozott(Also, Felso, {C,level,Jfa}) -> Also =< C andalso C < Felso andalso rendezett_fa_2_kozott(C,Felso,Jfa); rendezett_fa_2_kozott(Also, Felso, {C,Bfa,Jfa}) -> Also < C andalso C < Felso andalso rendezett_fa_2_kozott(Also,C,Bfa) andalso rendezett_fa_2_kozott(C,Felso,Jfa). % 4. még hatékonyabban (csak egyszer járja be). rendezett_fa_3(Fa) -> case mmrendezett(Fa) of {_,_,R} -> R; R -> R end. %% @spec mmrendezett(F::fa()) -> %% {Min::term(), Max::term(), Rendezett::bool()} | Rendezett::bool(). %% Az F fa balértéke Min, jobbértéke Max, és rendezettsége Rendezett, %% de olykor Min és Max nem kerül meghatározásra; %% ezen esetek: üres fa, bizonyos nem rendezett fák. mmrendezett(level) -> true; mmrendezett({C,Bfa,Jfa}) -> % Első case-ben a bal fa rendezettségét vizsgáljuk, % ezután BR a bal fa rendezettsége, Min a balérték, % CBR a jobb fa elhagyásával keletkező fa, vagyis {C,Bfa,level} rendezettsége. CBR = case mmrendezett(Bfa) of {BMin,BMax,BR} -> Min=BMin, BR andalso BMax < C; % CBR a case értéke BR -> Min=C, BR % CBR a case értéke end, %% Második case-ben a jobb fa rendezettségét vizsgáljuk, és azt, hogy a %% teljes fa rendezett-e (a case-ben tudjuk, hogy {C,Bfa,level} fa rendezett). if CBR -> case mmrendezett(Jfa) of {JMin,JMax,JR} -> {Min,JMax,JR andalso C < JMin}; % eredmény JR -> {Min,C,JR} % eredmény end; true -> false % eredmény (CBR=:=false, tehát nem rendezett) end. % 5. tartalmaz(_, level) -> false; tartalmaz(C, {C,_,_}) -> true; tartalmaz(C, {_,Bfa,Jfa}) -> tartalmaz(C, Bfa) orelse tartalmaz(C, Jfa). % 6. elofordul(_, level) -> 0; elofordul(C, {R,Bfa,Jfa}) -> if C =:= R -> 1; true -> 0 end + elofordul(C, Bfa) + elofordul(C, Jfa). % 7. 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). % 8. a) cutak_a(C, Fa) -> [CU || {C0,_} = CU <- utak(Fa), C0 =:= C]. % 8. b) 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. %--------------------------------------------------------------------------- % 8 VEZÉR A SAKKTÁBLÁN %--------------------------------------------------------------------------- test(8) -> [ 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]}, 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), 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] ]. % 9. zip([], []) -> []; zip([H1|T1], [H2|T2]) -> [{H1,H2}|zip(T1,T2)]. unzip([]) -> {[],[]}; unzip([{H1,H2}|T]) -> {T1,T2} = unzip(T), {[H1|T1],[H2|T2]}. % 10. atlok(L) -> [{X+Y,X-Y} || {X,Y} <- L]. % 11. all_different(L) -> length(L) =:= length(lists:usort(L)). nem_utik_egymast(J) -> {AtlokBalrol,AtlokJobbrol} = unzip(atlok(zip(lists:seq(1, length(J)), J))), all_different(AtlokBalrol) andalso all_different(AtlokJobbrol). % 12. 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] ]. % 12. 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]) ]. % 13. vezerek8_1() -> [ J || J <- perms_1(), nem_utik_egymast(J) ]. % 14. 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]) ]. % 15. vezerek_1(N) -> [J || J <- perms_2(lists:seq(1,N)), nem_utik_egymast(J) ]. % 16. 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) ].