Cílem 1. části práce je úplně prohledat 2D prostor (samozře pomocí metody prohledávání stavového prostoru) prostřednictvím robota. Prostor je rozdělen pomocí pravoúhlé mřížky. Robot v prstoru může:

• udělat krok vpřed
• krok vzad
• zjistit, zda se před ním nachází zeď
• otočit se vlevo o 90°
• otočit se vpravo o 90°
• zjistit svou absolutní orientaci
• zjistit své absolutní souřadnice

Jak zacházet s robotem zjistíte z cast1.scm z balíčku. Balíček si rozbalte a v prostředí PLT DrScheme otevřete soubor cast1.scm, který můžete rovnou editovat.

Zde je tentýž balíček, ale s větším bludištěm.

V první fázi máte k dispozici pouze jeden pár bludišť a 2 roboty. Cílem je zjistit, zda jsou dvě 2D bludiště stejná. Bludiště jsou stejná i případě, že jsou vůči sobě otočená. Stáhněte si balíček pro 2. část práce. Nyní již nelze zjišťovat absolutní souřadnice a absolutní orientaci robotů.

Ve druhé fázi máte 100 párů bludišť. Na cvičení budeme kontrolovat prvních n výsledků porovnání. Zároveň budeme sledovat hodnotu proměnné operations, která obsahuje počet sledovaných operací (tedy počet kroků a otočení) od spuštění programu. V této verzi již pro přehlednost a rychlost nevypisujeme elementární operace robota.

Zadání je shodné se zadáním 2. části, ale roboti se pohybují ve 3D. Hodnotit budeme i celkový počet operací. Práce se bude odevzdávat na cvičení 24.3. a e-mailem. Stáhněte si balíček ke 3. části s jedním párem malých bludišť.

Bludiště jsou shodná a vypadají, jak je nakresleno výše.

Pak zde máme další balíček se stem párů malých 3D bludišť i s výsledky.

Dále pak sto párů testovacích malých bludišť a sto párů větších bludišť.

A čistě pro zajímavost tu máme sto párů velkých bludišť.

Puristické řešení, však méně efektivní

(define (rev-app lst)
  (if (empty? lst)
      '()
      (append (rev-app (cdr lst)) (list (car lst)))
  )
)

Efektivnější řešení s akumulátorem

(define (rev-acc lst acc)
  (if (empty? lst)
      acc
      (rev-acc (cdr lst) (cons (car lst) acc))
  )
)
 
(define (rev lst)
  (rev-acc lst '())
)

(define (merge-sort ls)
  (cond
    ((null? ls) ls)
    ((null? (cdr ls)) ls)
    (else (let ((s (split ls)))
              (merge (merge-sort (car s)) (merge-sort (cdr s)))
            )
          )
  ) 
) 
 
(define (split ls)
  (begin
      (define (split-acc as bs cs)
         (if (null? as)
             (cons bs cs)
             (split-acc (cdr as) 
                        (cons (car as) cs) 
                        bs)
             )
         )
       (split-acc ls '() '())
       )
 
  )
 
(define (merge as bs)
  (cond
      ((null? as) bs)
      ((null? bs) as)
      ((<= (car as) (car bs)) (cons (car as) (merge (cdr as) bs)))
      (else (merge bs as))
   )
 ) 
 

(define match?
        (lambda (p n)
          (cond 
              ((and (not (list? p)) (not (list? n)))
                 (equal? p n))
              ((and (null? p) (null? n)) 
                   '#t)
              ((null? p) 
                   '#f)
              ((equal? (car p) '*) 
                   (if (match? (cdr p) n) 
                         '#t
                         (if (null? n)
                             '#f
                             (match? p (cdr n))
                          )   
                     ))
              ((null? n) '#f)
              ((equal? (car p) '?) 
                   (match? (cdr p) (cdr n))) 
              (else (and (match? (car p) (car n)) 
                   (match? (cdr p) (cdr n)))))))

(define mapuj
   (lambda (f ls)
     (if (null? ls)
         ls
         (cons (f (car ls)) (mapuj f (cdr ls))))))

faktorial :: Integer -> Integer
faktorial 0 = 1
faktorial n = n * (faktorial (n - 1))

faktorial n | (n==0) = 1 
            | otherwise = n * (faktorial (n-1))

car (x:_) = x -- v haskellu head
 
cdr (_:xs) = xs -- v haskellu tail
 
cons x xs = x : xs -- v haskellu operator :

-- v haskellu infixovy operator ++
append [] xs = xs 
append xs [] = xs
append (x:xs) ys = (x: (append xs ys))

quicksort [] = []
quicksort (x:xs) = (quicksort [y|y<-xs,y<=x]) ++ [x] ++ 
                   (quicksort [y|y<-xs,y>x])

is_odd 0 = False
is_odd 1 = True
is_odd n = is_odd (n - 2)
 
list_odd xs = [x | x<-xs,is_odd x]

(x:_) `nth` 0 = x  -- v haskellu infixovy operator: !!
(_:xs) `nth` n = nth xs (n-1)

take' 0 _ = []
take' n (x:xs) = x: take' (n-1) xs

zip' [] _ = []
zip' _ [] = []
zip' (x:xs) (y:ys) = (x,y) : zip' xs ys

zipWith' _ [] _ = []
zipWith' _ _ [] = []
zipWith' f (x:xs) (y:ys) = (f x y) : zipWith' f xs ys

map' _ [] = []
map' f (x:xs) = (f x) : map' f xs

pretoc f x y z = f z y x

data BinStrom a = List a | 
                  Uzel a (BinStrom a) (BinStrom a) deriving Show
 
rotaceBinStromu (List x) = List x
rotaceBinStromu (Uzel x lS rS) = (Uzel x (rotaceBinStromu rS) (rotaceBinStromu lS))

data Strom a = L a | U a [Strom a] deriving Show
 
rotaceStromu :: Strom a -> Strom a
rotaceStromu (L x) = (L x)
rotaceStromu (U x ss) = (U x (rotate [(rotaceStromu y) | y<-ss])) where
	rotate [] = []
	rotate (x:ys) = (rotate ys) ++ [x]

mergeSort [] = []
mergeSort [x] = [x]
mergeSort xs = merge (mergeSort ls) (mergeSort ps) where
	(ls,ps) = split xs where
		split [] = ([],[])
		split [x] = ([x],[])
		split (x : y : zs) = ((x : ls), (y : ps)) where
			(ls,ps) = split zs
	merge [] xs = xs
	merge xs [] = xs
	merge q@(x:xs) z@(y:ys) | x<=y = (x : (merge xs z))
		                    | otherwise = merge z q

match [] [] = True
match "*" _ = True
match q@(x : xs) z@(y : ys) | x == '?' = match xs ys
	                        | x == '*' = (match xs z) || (match q ys)
	                        | x == y   = match xs ys
match _ _ = False