type obj = Miss | Cann | Barca;;
type situazione = obj list * obj list;;
type azione= From_left of obj list|From_right of obj list;;

(* numeroObj: obj list -> int*int
   aux: int*int -> obj list -> int*int
   aux mette nel primo elemento il numero di Cannibali che trova nella lista
       nel secondo elemento il numero di Missionari che trova *)

let numeroObj riva=
    let rec aux (cann,miss)= function
        |[]-> (cann,miss)
        |Cann::rest -> aux ((cann+1),miss) rest
        |Miss::rest -> aux (cann,(miss+1)) rest
        |Barca::rest -> aux (cann,miss) rest
    in aux (0,0) riva;;

(* obj list * obj list -> bool
   confronta il numero di cannibali e missionari delle due rive
   ritorna true se in entrambi il numero dei cannibali è uguale o minore dei
   missionari *)

let safe situazione = match situazione with
        (x,y) -> let (c1,m1) = numeroObj x
             in let (c2,m2) = numeroObj y
             in if (m1>0)&&(m2>0) then ((c1<= m1)&&(c2<= m2))
                    else if m2>0 then (c2<=m2)
                 else if m1>0 then (c1<=m1)
                      else true

exception SpostamentoNonPossibile;;

let sel1 (x,_) = x;;
let sel2 (_,y) = y;;

(* remove: 'a -> 'a list -> 'a list *)
let rec remove a = function
        [] -> raise SpostamentoNonPossibile
        |x::rest -> if x = a then rest
                    else x::(remove a rest)

(* rimuoviLista: obj list -> obj list -> obj list
   rimove dalla lista data gli elementi della seconda lista
   e la barca che serve allo spostamento *)
let rec rimuoviLista l= function
    x::rest -> rimuoviLista (remove x l) rest
    |[]-> (remove Barca l);;

(* aggiungi: obj list -> int*int -> obj list
   aggiunge alla lista data gli elementi associati alla coppia Cannibali, Missionari
   più la barca utile allo spostamento *)

let rec aggiungi l x = match x with
            (0,0) -> Barca::l
            |(0,n) -> aggiungi (Miss::l) (0,(n-1))
            |(m,0) -> aggiungi (Cann::l) ((m-1), 0)
            |(m,n) -> aggiungi (Miss::Cann::l) ((m-1),(n-1));;


(* spostamento: obj list * obj list -> obj list -> int -> obj list * obj list
   l'intero mi identifica da quale riva parto, crea la nuova situazione
   rimuovendo dalla riva di partenza gli elemeneti dati, aggiungendoli all'altra riva *)

let spostamento situazione l x= if x=1 then (rimuoviLista (sel1 situazione) l, aggiungi (sel2 situazione) (numeroObj l))
                else ( aggiungi (sel1 situazione) (numeroObj l) , rimuoviLista (sel2 situazione) l );;

(* applica: obj list * obj list -> azione -> obj list * obj list
   applica gli spostamenti identificati dalla lista di azione
   lo spostamento non avviene se la situazione che si va a creare non è sicura
   o se lo spostamento non è possibile per mancanza di oggetti *)

let applica situazione azione= match azione with
    From_left x -> let coso = spostamento situazione x 1 in
                  if not(List.mem Barca (sel1 situazione)) || not(safe(coso)) then raise SpostamentoNonPossibile
                       else coso


    | From_right y -> let coso= spostamento situazione y 2 in
                  if not(List.mem Barca (sel2 situazione)) || not(safe(coso)) then raise SpostamentoNonPossibile
                       else coso;;