maze_utils.ml

type ordinals = Left | Right | Up | Down;; 

let concat x y = x::y ;;

let rec map f l = match l with
    | [] -> []
    | a::b -> f(a)::(map f b)
;;

let rec filter f l = match l with
    | [] -> []
    | a::b -> if f a then a::filter f b else filter f b
;;

(*Check if there is a way in the given configuration 
  starting from cell (x, y) in the ord direction*)
let rec passage configuration m n x y ord = match ord, x, y with
    | Left, 0, _                    -> false
    | Up, _, 0                      -> false
    | Right, a, _ when a = (m-1)    -> false
    | Down, _, b when b = (n-1)     -> false

    | Right, _, _   -> passage configuration m n (x+1) y Left
    | Down, _, _    -> passage configuration m n x (y+1) Up

    | Left, _, _    -> configuration.(y*(m-2) + x)
    | Up, _, _      -> configuration.((m-2) * (n-2) + x*(n-2) + y)
;;

(*Check whether a given configuration is a maze*)
let sanity_check m n configuration = 
    let maze = Array.make_matrix m n false
    in
    let counter = ref 0
    in
    let rec search x y = if maze.(x).(y) = false then 
        (
            maze.(x).(y) <- true;
            counter.contents <- counter.contents + 1 ;
            if passage configuration m n x y Left   then search (x-1) y ;
            if passage configuration m n x y Right  then search (x+1) y ;
            if passage configuration m n x y Up     then search x (y-1) ;
            if passage configuration m n x y Down   then search x (y+1) ;
        )
    in
    search 0 0;
    counter.contents = m*n
;;