[Zk] 16.5.2008

1.) PROLOG: Hladovym algoritmom pomocou heuristiky najst minimalne ofarbenie grafu.

2.) PROLOG: Z postfixneho zapisu n-arneho stromu vytvorit n-arny strom.

napr:
(hodnota,pocet synov)
IN: postfix = [('b',0),('e',0),('f',0),('c',2),('d',0),('a',3)]
OUT: NodeN 'a' [NodeN 'b' [],NodeN 'c' [NodeN 'e' [],NodeN 'f' []],NodeN 'd' []]

3.) HASKELL: Mame zadany orientovany graf. Treba vyhodit vs.hrany (u,v), pre ktore existuje cesta dlzky 2 z u do v.

4.) HASKELL: Na vstupe mame obdlzniky(okna), mame zistit ci sa nejake prekryvaju.

type Rozmer = (Int,Int)
type Obd = (Int,Int,Rozmer) // (sur_x,sur_y,(sirka,vyska))

data Maybe a = Nothing | Just a

Ulohou bolo napisat funkciu:
prusek :: [Obd] ->Maybe (Obd,Obd) //dostane okna a vrati Kolidujucu dvojicu

5.)Vs o negacii v Prologu

mno zkouska je zamnou...ale stejne mi prijde Prolog jako takovy zly Voodoo :) Haskell mi sednul mnohem vic
a Hric je pomerne hodnej pan...nevim proc me vzdycky tak desil

pro zajimavost moje reseni 2:
(zachovava poradi)

rs([],S,S).
rs([(X,Y)|Z],S,Vysl):-
  rozdel(S,Y,SY,S2),
  rs(Z,[nt(X,SY)|S2],Vysl).

rozdel(S,0,[],S).
rozdel([S|SS],Y,SY,S2):-
  Y1 is Y-1,
  append(S1,[S],SY),
  rozdel(SS,Y1,S1,S2).  
  
spustrs:-rs([(b,0),(d,0),(e,0),(c,2),(a,2)],[],X), write(X). 

A od kolegy reseni 4:

type Rozmer = (Int, Int)
type Obd = (Int, Int, Rozmer)

prekryti :: [Obd] -> Maybe (Obd,Obd)
prekryti sObd| (seznamKolizi == []) = Nothing| otherwise = Just (head seznamKolizi)whereseznamKolizi = [(a,b) | a <- sObd, b <- (filter (/=a) sObd), prekryvajiSe a b]
prekryvajiSe :: Obd -> Obd -> Bool
prekryvajiSe (zx1,zy1,(xz1,yz1)) (zx2,zy2,(xz2,yz2)) =if ((zx1 < zx2) && (kx1 > zx2)) then  if ((zy1 < zy2) && (ky1 > zy2)) then True  else if ((zy2 < zy1) && (ky2 > zy1)) then True  else Falseelse Falsewherekx1 = zx1 + xz1ky1 = zy1 + yz2kx2 = zx2 + xz2ky2 = zy2 + yz2


-- dotaz1: prekryti [(0,0,(6,4)),(6,5,(2,2)),(7,6,(9,8))]
-- dotaz2: prekryti [(2,0,(2,5)),(0,2,(5,1))]

PROLOG: Hladovym algoritmem pomoci heuristiky najit minimalne obarbeni grafu.

 
obarvi([],_,[],_).
obarvi([(I-J)|T],Uz,[(J-N)|Z],Max):-otoc([(I-J)|T],J,OTOC),seznamMax(Max,Z),zjistiMinBarvu(J,OTOC,Uz,Z,N),dejdoUZ((J-N),Uz),maximum(Max,N,Max1),obarvi(T,Uz,Z,Max1).
zjistiMinBarvu(_,[],Z,N):-minimum(Z,N). 
zjistiMinBarvu(J,[(I-J)|T],Uz,Z,N):-member(I,UZ),barva(I,Uz,F),delete(Z,F,Z1),zjistiMinBarvu(J,T,Uz,Z1,N).

% otoc-otoci hrany tak aby koncili J
% minimum najde min ze seznamu nebo M
% seznamMax vrati seznam [1..Max]

Pozn.: Neni to uplne hladovy algoritmus, najdem vsechny barvy kteryma muzeme barvit a vyberem tu nejmensi, ale hricovi to nevadilo

Druhe reseni vic hladovejsi

zjistiBarvu(S,T,X,X):-jde(S,T,X).
zjistiBarvu(S,T,X,N):- X1 is X+1, zjistiBarvu(S,T,X1,N).

jde([],_,_).
jde([S|Z],T,X):-notmenber((S-X),T), jde(Z,T,X).

barvy([],X,X).
barvy([[V|ZS]|Z],T,X):-zjistiBarvu(ZS,T,1,N),barvy(Z,[(V-N)|T],X).

Prolog 2: Z postfixneho zapisu n-arniho stromu rekonstruovat n-arny strom. Vstup [B-0,E-0,F-0,C-2,D-0,A-3]

rekonstrukce(Vstup,Strom):-reverse(Vstup,Vystup), makeTree(Vystup,_,Strom).

makeTree ( [ Val-0|T], T, t(Val,[]) ).
makeTree ( [Val-N|T], Z, t(Val, Childs) ) :- makeChild ( T, N, Z, Childs ).

makeChild ( T, 0, T, [] ).
makeChild ( T, N, Z, [C|Childs] ) :- makeTree ( T, Zb, C ),N1 = N – 1,
makeChild ( Zb, N1, Z, Childs).

Pozn.: Celkem ok ale drobnost nezachovava poradi synu!!

Haskell 3: V orientovanem acyklickem grafu vyskrtat hrany[u,v] pokud mezi vrcholy u a v existuje cesta delky 2.
vstup je seznam hran. Hrana je dvojprvkovy seznam napr [[1,4],[2,3],[3,4],[4,5]]

proskrtej hrany = gen hrany hrany

gen [] _ = []
gen (x:xs) hrany| projdi x vrcholy hrany = gen xs hrany| otherwise = x: g xs hrany
projdi _ []  _  = False
projdi [x,y] [a:as] hrany| (member [x,a] hrany) && (member [a,y] hrany) = True| otherwise = projdi [x,y] as hrany


	  

Pozn.: neefektivni protoze se porad prochazeji hrany - lepsi reseni nagenerovat seznam naseledniku a predchudcu pro vsechny vrcholy

Haskell 4: Na vstupu mame obdelniky(okna), mame zistit jestli nejake prekryvaji.

type Rozmer = (Int,Int)
type Obd = (Int,Int,Rozmer)

data Maybe a = Nothing | Just a

Ulohou bylo napsat funkci:
prekryvaji :: [Obd] ->Maybe (Obd,Obd) //dostane okna a vrati kolidujici dvojci

Nevedel sem co je Maybe tak sem generoval seznam -> 4body

prekryvaji [] = []
prekryvaji [x] = []
prekryvaji (x:xs) = (p x xs) ++ prekryvaji xs

--vrati seznam oken ktere se prekryvaji
p _ [] = []
p (a,b,(ar,br)) ((x,y(xr,yr)):zbytek)| ((x>a)&&(x<(a+ax))&&(y>b)&&(y<(b+bx))) || () || () || () = ( (a,b,(ar,br)), ((x,y(xr,yr)))) :p (a,b,(ar,br)) zbytek| otherwise = p (a,b,(ar,br)) zbytek

hezky reseni...
jenom otazka na 4 "|| () || () || ()" to jsou nejaky specialni haskellovsky kouzla nebo se ti nechtelo psat s podminkama? :)

za || () || () .... se doplni podminky pro ostatni rohy, to je test jestli nejaky roh je v tom druhem a obdelnik ma 4 rohy -> dalsi 3 testy

jo no ale to nepokreje pripad pro tyhle dva obdelniky:

   +-+
+--|-|--+
|  | |  |
+--|-|--+
   +-+

reseni co jsem posilal ja by to snad melo zvladat...

My way:

3.) zmaz g = setDiff g [(u,v) | (u,v)<-g,(a,x)<-g,(y,b)<-g,u==a,x==y,b==v]

4.) na styri porovnania: (kx1 < zx2) || (ky1 < zy2) || (kx2 < zx1) || (ky2 < zy1)