(******************************************************************************)
(******************************************************************************)
(****                             Guião 3                                   ***)
(****                                                                       ***)
(******************************************************************************)
(******************************************************************************)

open Scanf;;


(*
funcionamento geral do scanf (e as suas variantes): 

scanf entrada formato processamento

entrada: de onde vamos retirar as leituras
formato: formato esperado das leituras
processamento: uma função que vai processar o que foi lido e extraído

bscanf ---> entrada = um buffer de "scanning" (preferir esta função a fscanf)
sscanf ---> entrada = uma string
scanf  ---> entrada é o stdin (por isso é omitida)
fscanf ---> entrada = um canal de leitura
*)





let f1 a b = (a,b);;
let f2 a b = (a+1, b/2);;
let f3 a b = a*b;;
let rec fact_fast x a = if x <1 then a else fact_fast (x-1) (x*a);; 

let st = "ola 7 tudo bem 8"


(** ler dois inteiros de st e devolvê-los na forma de um par **)
let v1 = sscanf st "ola %d tudo bem %d"  f1;;

let (u,v) = sscanf st "ola %d tudo bem %d" f1;;

(** ler dois inteiros "a" e "b" de st e devolver o par (a+1,b/2) **)
let v2 = sscanf st "ola %d tudo bem %d" f2;;

let v3 = sscanf st "ola %d tudo bem %d" f3;;

let x = sscanf "ola 5 tudo" "ola %d tudo" (fun a -> fact_fast a 1);;


(* 
PROBLEMA USUAL: misturar as variantes do scanf com outros métodos de leitura  de dados (read_int etc) dá problema
DIAGNÓSTICO: o scanf "adquire" o buffer, se houver posteriormente uma função de tipo read, esta encontrará então o EOF, mesmo se  o scanf não leu o buffer todo.
RECEITA: usar o sscanf. Um exemplo:
*)

let st = read_line () in 
let (a,b) = sscanf st "ola %d tudo bem %d" f2 in
let c = read_int () in
 (a,b,c);;




(** referências**)
(*

  Referencias são valores que representam "zonas da memória", ou seja
  são apontadores.  É a forma em Ocaml para manipular variáveis como em
  C (ou seja que podem mudar de valores)
  
  Como em OCaml tudo tem um tipo, estas também tem de seguir a regra.

  As referências são do tipo 'a ref. Por exemplo uma referencia para
  um inteiro tem por tipo int ref.

  Declaração: pela palavra chave "ref" 
  Acesso: !
  Atribuição: :=

*)

let x = ref 0;;
let li = ref [];;

li := 1:: !li;;
x  := 4 + !x;;
x := 9;;


(** Vamos agora ver uma utilização interessante dos contextos  das funções
    os "environment".
    uma função pode utilizar variáveis/valores que foram definidas foram do 
    seu alvo de definição.
    Neste caso é preciso perceber que quando isso acontece, a função grava tudo 
    localmente para não ser dependente do contexto exterior. 
    Este facto tem consequências que importa perceber e dominar.

    Vejamos o exemplo seguinte:
**)
let a  = 10 ;;

let f x = x * a + 1;; 
(* 
f grava no seu contexto o valor a=10 
ou seja, f x = x * 10 + 1 
*)

let a =5;;

f 3;;

(*
Uma utilização esotérica deste fenómeno é a técnica do fecho para
 simular o encapsulamento de dados:

Consiste no seguinte: fornecer um valor, mas não directamente. 
Queremos que esse só possa ser manipulado via as funções disponibilizadas.

Como proceder: fazer com que este valor seja um valor local a todas estas 
funções em simultaneo. Assim cada um fica com ua cópia da referencia e 
esta não é visível fora destas funções.

*)


let (init_contador, get_contador, incr_contador) =
  let contador = ref 0 in
  let i () = contador := 0 in
  let g () = !contador in
  let incr () = contador := !contador + 1 in
(i,g,incr);;

get_contador ();;
incr_contador ();;
get_contador ();;
incr_contador ();;
incr_contador ();;
get_contador ();;
init_contador ();;
get_contador ();;

(*
define um fecho para uma pilha.
As funções deverão ser: init, push, pop, is_empty 
*)


let (init, push, pop, is_empty) =
  let pilha = ref [] in
  let i () = pilha := [] in
  let pu x = pilha := x::!pilha in
  let po () = 
    match !pilha with  
	[] -> failwith "empty stack" 
      | el::li -> (pilha := li) ; el in
  let is_e () =  
    match !pilha with  
	[] -> true 
      | _ -> false 
in
    (i,pu,po,is_e)
;;


(* Vamos aqui ilustrar a utilização das estruturas, mutables, dos
vectores, dos ciclos e das strings com dois exemplos completos mais
simples
*)

 (** um exemplos simples com estruturas: os complexos **)

type complex = {re:float; im:float};;

type complexo = float * float;;

let c = {re=2.;im=3.} ;;

let cc = {im=9.2;re=5.9};;

let d = {c with im = c.im +. 8.};; 

let e = {im=7. ; re=9.};;

let add_complex c1 c2 =  {re = c1.re +. c2.re; im = c1.im +. c2.im};;


let mult_complex c1 c2 = 
  let {re=x1;im=y1} = c1 in
  let {re=x2;im=y2} = c2 in
     {re=x1*.x2-.y1*.y2;im=x1*.y2+.x2*.y1} ;;

let g = mult_complex c c ;;


(** desta vez com um campo mutable (---->alterável)**)
type conta = {dono : string; mutable  saldo : float};;

exception Operacao_Invalida;;

let create_account name = {dono=name; saldo=0.0};;
let get_owner x = x.dono;;
let get_balance x = x.saldo;;
let inc_account x v = x.saldo <- x.saldo +. v;;
let decr_account x v= 
  if x.saldo -. v < 0.0 
  then raise Operacao_Invalida
  else x.saldo  <- x.saldo -. v;;

(**Podemos assim revelar o segredo das referências....**)
type 'a ref = {mutable contents:'a};;

type 'a caixa = {mutable dentro: 'a};;

let x = {dentro= 9};;


(***Utilização básica de vectores (array em OCaml)***)
let v = [| 3.14; 6.28; 9.42 |] ;; 

let v = Array.make 10  3.14;;

let w = Array.init 10 (fun i -> i * 2);;

v.(1) ;;
v.(0) <- 100.0 ;;
v ;;

(**erro!**)
v.(-1) +. 4.0;;


(** partilha de valores: Perigoso (partilha-se referencias!!!!) **)
let v = Array.make 3 0;;
let m = Array.make 3 v;;
v.(0) <- 1;;
m;;

let w = v ;;

let t = [| 
           [|1|];
           [|1; 1|];
           [|1; 2; 1|];
           [|1; 3; 3; 1|];
           [|1; 4; 6; 4; 1|];
           [|1; 5; 10; 10; 5; 1|]
         |] ;;

(**cópia (sem partilha)**)
let v2 = Array.copy v ;;

(** concatenação **)
let mm = Array.append m m ;;
Array.length mm ;;
m.(0) <- Array.make 3 0 ;;
m ;;
mm;;
v.(1)<- 5;;
mm ;;



(**** um exemplo ilustrativo ****)
open Scanf;;
open Printf;;
open Array;;

(** um conjunto de funções que inicializam uma matriz n x n com valores
lidos dum ficheiro e devolve a soma das linhas e colunas **)

let calcula name =
  let fich = open_in name in
    (**  criação dum buffer para scanf (melhor no caso de scanf repetidos como vai ser o caso)**)
  let sb = Scanning.from_channel fich in  
    (* leitura do tamanho da matriz *)
  let n = int_of_string (input_line fich) in
    (** função auxiliar que lê uma linha de n valores e devolve um vector
	de n+1 posição com os valores lidos mais o 0 final **)
  let fill i = 
    if i<n 
    then 
      Array.init (n+1)
	(fun j -> 
	   if j < n then bscanf sb " %d" (fun a -> a) 
	   else 0)
    else Array.make (n+1) 0 
  in
    (** Inicializar a grelha **)
  let grelha = Array.init (n+1) fill in

(** calculo da coluna da direita  **)
  let  _ =
    for i = 0 to n-1 do
    let acc = ref 0 in
      for j = 0 to n-1 do
	acc := !acc + grelha.(i).(j)
      done;
      grelha.(i).(n) <- !acc
    done in   

(** calculo da linha final **)
  let  _ =
    for j = 0 to n-1 do
    let acc = ref 0 in
      for i = 0 to n-1 do
	acc := !acc + grelha.(i).(j)
      done;
      grelha.(n).(j) <- !acc
    done in  

(** calculo do valor extremo grelha.(n).(n) **)
  let _ =
    let i = ref 0 in
    let acc = ref 0 in  
      while (!i <= n) do
	acc := !acc + grelha.(!i).(n);
	i:= !i + 1
      done; grelha.(n).(n)<- !acc 
  in
    (** visualização**)
    for i = 0 to n do
      for j = 0 to n do
	printf "   %3d"  grelha.(i).(j)
      done;
      print_newline ()
    done
;;

(****
test.txt=
4
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
*****)

calcula "test.txt";;


(****EXERCICIO****)
(***Totoloto: 
1) codificar a grelha como uma matriz 7x7 de inteiros e 
2) definir uma função que preencha a grelha a partir duma  lista de 7 números distintos 
3) definir uma função que dado um sorteio (lista de 6 números, e um inteiro: o complementar) 
   diz em quantos números se acertou 
*)



(****************SUDOKU em OCAML*********************

  Solução original de Jon Harrop retirada de
  http://www.ffconsultancy.com/free/sudoku/

**********************************************)


(*

  leitura do tabuleiro: 9 linhas de texto de 9 caracteres obtidas do
  stdin que vão para um vector: m.


*)
let m = Array.init 9 (fun _ -> input_line stdin);;

(*

  Mostrar o conteúdo de m: imprimir cada linha l de m com a ajuda de
  print_endline l

*)

let print() = Array.iter print_endline m;;

(*

  Esta função testa a validade dum tabuleiro a custa dum percurso
  deste (por recursão) com i=0..8. Dito de outra forma: procura-se
  saber de é válido ter n na posição (y,x)?  Isto é, Se existe no
  alcance da posição (y,x) uma célula com o valor n.

  Para tal são testados simultaneamente um elemento da linha, um
  elemento da coluna e um elemento do quadrado 3x3 que contem a
  coordenada explorada. No final do percurso estes três componentes do
  tabuleiro (linha, coluna e quadrado foram explorados).

  Repare na declaração e no uso do parâmetro i. Este é
  opcional. Quando omitido este vale por defeito 0.

*)
let rec invalid ?(i=0) x y n =
  i<9 && 
    ( 
      m.(y).[i] = n || 
      m.(i).[x] = n ||
      m.(y/3*3 + i/3).[x/3*3 + i mod 3] = n || 
      invalid ~i:(i+1) x y n
    )
;;


(*

  A aplicação duma função f sobre um intervalo [l..u) é factorizada a
  custa duma função fold de ordem superior:

  fold f accu l u = (f ... (f (f (f accu l) (l+1)) (l+2)) ... (u-1))

*)
let rec fold f accu l u = 
  if l=u then accu else fold f (f accu l) (l+1) u
;;


(*

  A função de procura de solução examina simplesmente cada posição no
  tabuleiro e tenta para tentando cada uma das células vazias os
  números de 1 a 9.

  Note que esta função é igualmente uma função fold (iterador) de
  ordem superior que acumula o valor accu aplicando-lhe a função dada
  f de cada vez que uma solução m é encontrada.

  x e y são argumentos opcionais cujo valor por defeito é 0.

*)
let rec search ?(x=0) ?(y=0) f accu = match x, y with
    9, y -> search ~x:0 ~y:(y+1) f accu (* o passo seguinte: explorar 
                                           a linha seguinte *)
  | 0, 9 -> f accu                      (* Uma solução foi encontrada *)
  |  _   ->                             (* Se não estivermos em nenhum 
                                           dos outros casos *) 
       if m.(y).[x] <> '0'              (* A célula explorada 
                                            está preenchida? *) 
       then search ~x:(x+1) ~y f accu   (* Então ver a célula seguinte *)
       else                             (* Senão para n em [1 10) aplicar 
                                           g a começando de accu *)
                                        (* g accu n =  *)
         fold (fun accu n ->
                 let n = Char.chr (n + 48) in             (* redefinir o inteiro n 
                                                             como um caracter *)
                   if invalid x y n then accu             (* se n na posição x,y 
                                                             tornar o tabuleiro inválido
                                                             então esquecer e tentar com
                                                             o valor seguinte *) 
                   else (m.(y).[x] <- n;                  (* senão colocar o n nesta célula *)
                      let accu = search ~x:(x+1) ~y f accu in  (* e preencher  as células *)
			m.(y).[x] <- '0';                      (* seguintes.  Após este passo *)
			accu)) accu 1 10                       (* tentar  outro valor (i.e. n+1) *)
                                                               (*  para a posição (x,y) *)
;;

(*  

    O programa principal utiliza a função search para acumular o
    número total de solução (f = (função sobre i que mostra m e
    incrementa i) e accu começa em 0).

*)

let () = Printf.printf "%d solutions\n" (search (fun i -> print(); i+1) 0)
;;




(** Algoritmo Knuth Morris Pratt para a procura de substrings em strings**)
let init_next p =
    let m = String.length p in
    let next = Array.make m 0 in
    let i = ref 1 and j = ref 0 in
    while !i < m - 1 do
      if p.[!i] = p.[!j] then begin incr i; incr j; next.(!i) <- !j end  else
      if !j = 0 then begin incr i; next.(!i) <- 0 end else j := next.(!j)
    done;
    next;;

let kmp p =
    let next = init_next p and m = String.length p in
    function s ->
      let n = String.length s and i = ref 0 and j = ref 0 in
      while !j < m && !i < n do
        if s.[!i] = p.[!j] then begin incr i; incr j end else
        if !j = 0 then incr i else j := next.(!j)
      done;
      if !j >= m then !i - m else raise Not_found;;

 kmp "xxw" "fnflxxjpqmjsxxwmecçamscxhep284ufwcm4rhfwxexw";;
(*** - : int = 12 **)