Dit topic gaat nergens over...

dinsdag 5 november 2002 @ 22:05:41 #1

Ramonkey

[Dit bericht is gewijzigd door Ramonkey op 05-11-2002 22:06]

dinsdag 5 november 2002 @ 22:05:53 #2

Roonaan

Strictly

code:
||-------------------------------------------||
|| Structuur van Programmeertalen            ||
||                                           ||
||                                           ||
||                                           ||
||                                           ||
||                                           ||
||-------------------------------------------||
||zonder driehoeken
run::[(num,[char])]
run = quickSeekCalc 25
||met driehoeken
run3::num->[[char]]
run3 capaciteit = map optimaal2string (collapse (map verander (run3b capaciteit)))
run3b::num->[[char]]
run3b capaciteit
= [pad | (dist,pad)<-mogelijkePaden]
  where
    mogelijkePaden = filter (isMogelijk capaciteit) (gevondenPaden3)
    gevondenPaden3  = map verander ([pad | (dist,pad)<-gevondenPaden])
    gevondenPaden   = (zoekPaden capaciteit allePunten)
allePunten = "abcx"
locatie::char->(num,num)
locatie n  = (  0,  0), if n='a'
            = (  7,  0), if n='b'
            = (  7, 11), if n='c'
            = (  7, 26), if n='x'
            = (118,101), if n='b'
            = ( 57,136), if n='c'
            = ( 99, 63), if n='d'
            = ( 47,156), if n='e'
            = ( 90, 89), if n='f'
            = ( 40,187), if n='g'
            = ( 92,178), if n='h'
            = ( 26, 80), if n='i'
            = ( 10, 77), if n='j'
            = ( 20, 20), if n='x'
            = ( 10,  0), if n='p'
            = ( 10, 10), if n='q'
            = ( 20, 10), if n='r'
            = (  0,  0), otherwise
afstand::char->char->num
afstand a b = round (sqrt((x1-x2)^2 + (y1-y2)^2))
          where (x1,y1) = locatie a
                (x2,y2) = locatie b
zoekPaden::num->[char]->[(num,[char])]
zoekPaden capaciteit [] = []
zoekPaden capaciteit points
      = goDeeper ++ (zoekPaden capaciteit xs), if (afstand 'x' x) < capaciteit
      = zoekPaden capaciteit xs, otherwise
       where
        (x:xs)     = points
        track      = subpaths nextPoints x "x" capaciteit 1
        goDeeper   = subpaths nextPoints x (x:basePath) capaciteit (level+1)
        nextPoints = (mextract allePunten "x"++[x])
        basePath   = "x"
        level      = 0
subpaths::[char]->char->[char]->num->num->[(num,[char])]
subpaths points startPoint basePath capaciteit level
     = [(level, basePath)]  , if startPoint = 'a'
     = []                   , if points = []
     = doNext               , if member basePath x
     = doNext               , if startPoint = x
     = goDeeper ++ doNext   , if capaciteit - 2 * (afstand x startPoint) > 0
     = doNext               , otherwise
      where
        nextPoints = (mextract allePunten basePath)
        goDeeper   = subpaths nextPoints x (x:basePath) capaciteit (level+1)
        doNext   = subpaths xs startPoint basePath capaciteit level
        (x:xs)     = points
mextract::[char]->[char]->[char]
mextract [] [] = []
mextract [] ys = []
mextract xs [] = xs
mextract (x:xs) ys = mextract xs ys     , if member ys x
                    = x:(mextract xs ys) , otherwise

invert::[char]->[char]->[char]
invert[] ys = ys
invert (x:xs) ys = (invert xs ys) ++[x]
quickSeek::num->[(num,[char])]
quickSeek capaciteit = zoekPaden capaciteit allePunten
quickSeekCalc::num->[(num,[char])]
quickSeekCalc capaciteit
= [], if paden = []
= quickCalcPaths capaciteit paden, otherwise
  where paden = (zoekPaden capaciteit allePunten)
quickCalcPaths::num->[(num,[char])]->[(num,[char])]
quickCalcPaths capaciteit (thisItem:rest)
  = [dezeBerekend], if rest = []
  = dezeBerekend:(quickCalcPaths capaciteit rest), otherwise
    where
      dezeBerekend = ((quickCalc capaciteit thisPath), thisPath)
      (thisPointCount,thisPath) = thisItem

quickCalc::num->[char]->num
quickCalc capaciteit (startpoint:path) = qCalc capaciteit 0 startpoint path
qCalc::num->num->char->[char]->num
qCalc capaciteit nodig p1 (p2:rest)
= 0, if [p2] = []
= thisNeeds, if rest = []
= qCalc capaciteit thisNeeds p2 rest, otherwise
   where thisNeeds = qCalc1 (afstand p1 p2) nodig capaciteit
qCalc1::num->num->num->num
qCalc1 distance nodig carry
= nodig + (fulltrips*2+1)*distance
  where
   fulltrips = ceil((nodig-(carry-distance))/qOverflow)
    qOverflow = carry - 2* distance, if carry - 2* distance > 0
              = 1, otherwise

ceil::num->num
ceil a = ceil2 a, if ceil2 a > 0
       = 0, otherwise
ceil2::num->num
ceil2 a
  = round(a+1), if round(a) ~= a
  = a, otherwise
overflow::num->num->num
overflow carry distance = carry - 2 * distance
modulus::num->num->num
modulus a b
  = a - b, if a < b
  = modulus (a-b) b, otherwise
||********************************************************||
||* Hier komen de methodes die rekening houden met        ||
||* driehoeken                                            ||
||********************************************************||
optimaalPad::=Recht char optimaalPad | Driehoek char char char optimaalPad | Eind
|| optimaal2string: Methode die bij een gegeven optimaalPad een string-
|| representatie creeert van het gevonden pad.
optimaal2string::optimaalPad->[char]
optimaal2string (Recht c n) = c:(optimaal2string n)
optimaal2string (Driehoek a b c n) = '(':a:b:c:')':(optimaal2string n)
optimaal2string (Eind) = []
||Creert van een [char] alle mogelijke optimaalPad's
verander::[char]->[optimaalPad]
verander punten
= [Eind], if #punten = 0
= [Recht p11 (Eind)], if #punten = 1
= [Recht p21 (Recht p22 (Eind))], if #punten = 2
= extend ++ normal, otherwise
  where
   normal              = plak_recht p11 (verander p1Overig)
   extend       = plak_driehoek p31 p32 p33 (verander p3Overig)
    (p11:p1Overig)     = punten
    (p21:p22:p2Overig) = punten
    (p31:p32:p33:p3x)  = punten
    p3Overig       = (p33:p3x)

plak_recht::char->[optimaalPad]->[optimaalPad]
plak_recht a []     = []
plak_recht a (x:xs) = [Recht a (x)] ++ plak_recht a xs
plak_driehoek::char->char->char->[optimaalPad]->[optimaalPad]
plak_driehoek a b c []     = []
plak_driehoek a b c (x:xs) = [Driehoek a b c (x)] ++ (plak_driehoek a b c xs)
|| Collapse zorgt ervoor dat er een rij van optimaalPads gemaakt
|| kan worden van de rij van rijen van optimaalPads
collapse::[[optimaalPad]]->[optimaalPad]
collapse [] = []
collapse (a:ax) = merge a (collapse ax)
|| Een pad is direct als er geen driehoekjes inzitten
isIndirect::optimaalPad->bool
isIndirect (Recht pA pB) = isIndirect pB
isIndirect (Driehoek pA pB pC (x)) = True
isIndirect Eind = False

||Een pad is mogelijk als alle driehoeken ABC in het pad
|| voldoen aan een aantal eisen.
isMogelijk::num->optimaalPad->bool
isMogelijk capaciteit (Eind) = True
isMogelijk capaciteit (Recht pA n)
= and [(isMogelijk capaciteit n), ((afstand pA (getEerste n)) <= capaciteit)]
isMogelijk capaciteit (Driehoek pA pB pC n)
= and[controleer3,  (isMogelijk capaciteit n)]
   where
   controleer3 = and [eis1,eis2,eis3,eis4]
          eis1 = True, if (capaciteit - (afstand pB pC)) > (afstand pC pA)
               = False, otherwise
          eis2 = True, if (afstand pB pC) > (afstand pC pA)
               = False, otherwise
          eis3 = True
          eis4 = True
getEerste::optimaalPad->char
getEerste (Eind) = '!'
getEerste (Recht pA n) = pA
getEerste (Driehoek pA pB pC n) = pA
rekenuit::[optimaalPad]->[optimaalPad]
rekenuit a = a