let new_account p =
  let password = ref p in
  let pass_fail = ref 0 in
  let balance = ref 0 in
  {
    update_passwd = (fun old new_pass -> if old = !password then
                        (password := new_pass; pass_fail := 0)
                      else
                        (pass_fail := !pass_fail + 1; raise wrong_pass)

                    );

    retrieve = (fun pass amt -> if !pass_fail < 3 then
                   if pass = !password then
                     (pass_fail := 0;
                      if !balance < amt then
                        raise no_money
                      else
                        balance := !balance - amt)
                   else
                     (pass_fail := !pass_fail + 1; raise wrong_pass)
                 else
                   raise too_many_attempts
               );

    deposit = (fun pass amt -> if !pass_fail < 3 then
                  if pass = !password then
                    (pass_fail := 0;
                     balance := !balance + amt)
                  else
                    (pass_fail := !pass_fail + 1; raise wrong_pass)
                else
                  raise too_many_attempts
              );

    print_balance = (fun pass -> if !pass_fail < 3 then
                        if pass = !password then
                          (pass_fail := 0;
                           !balance)
                        else
                          (pass_fail := !pass_fail + 1; raise wrong_pass)
                      else
                        raise too_many_attempts
                    );
  }
;;

let rec catalan_I n =
  let final = ref {num_rec = 1; result = 0} in
  let rec sum f i = match i with
    | 0 -> f 0
    | i -> (final := {num_rec = !final.num_rec + 2; result = !final.result};
            f i + sum f (i - 1))
  in
  let rec catalan n = match n with
    | 0 -> 1
    | 1 -> 1
    | n ->(final := {num_rec = !final.num_rec + 2; result = !final.result};
           sum (fun i -> catalan i * catalan (n - 1 - i)) (n - 1))

  in
  let final = ref {num_rec = !final.num_rec; result = catalan n}
  in
  !final
;;

let rec catalan_memo n =
  let rec catalan n = match n with
    | 0 -> 1
    | n -> match Hashtbl.find_opt store n with
      | None ->
          let x = sum (fun i -> catalan i * catalan (n - 1 - i)) (n - 1) in
          Hashtbl.add store n x;
          x
      |Some x -> x
  in
  catalan n
;;

let memo f stats =
  let store = Hashtbl.create 1000 in
  let rec funct n  = match Hashtbl.find_opt store n with
    |None -> (stats.entries := !(stats.entries) + 1;
              let x = f funct n in
              Hashtbl.add store n x;
              x)
    |Some x -> stats.lkp := !(stats.lkp) + 1; x
  in funct



;;


let hofstadter_Q  =
  let stats = {entries = ref 0; lkp = ref 0} in
  let rec func g n = match n with
    |1 -> 1
    |2 -> 1
    |n -> g (n - g (n - 1)) + g (n - g(n - 2)) in
  let hofs = memo func stats
  in
  (fun n -> hofs n, stats)
;;