type build = {
    a : Carac.t
  ; m : Carac.t
  ; rm : Carac.t
  ; pm : Carac.t
  ; fm : Carac.t
}

type env = {
    cout_sort : int
  ; degat_sort : int
  ; max_tours : int
  ; fm_oponent : int
  ; cost_max : int
  ; frequencies : (int * float) list
}

let get_chance : env -> int -> float =
 fun env delta ->
  match List.assoc_opt delta env.frequencies with
  | None -> 1.
  | Some v -> v

(** Build a list with the differents percentages to hit *)
let buil_freq_table from thresold =
  List.init 10 (fun i ->
      (from + i, Roll.compare (from + i) thresold |> Q.to_float))

let eval : build -> env -> float * int =
 fun { a; m; rm; pm; fm } env ->
  let mp_available = Carac.value pm + ((env.max_tours - 1) * Carac.value rm) in

  (* How many attacks can be done using this cost ? (rounded down) *)
  let nb_attacks =
    min (env.max_tours * Carac.value a) (mp_available / env.cout_sort)
  in

  let degats =
    float (nb_attacks * (env.degat_sort + Carac.value m - 5))
    *. get_chance env (Carac.value fm)
  in
  (degats, nb_attacks)

let repr_degats : env -> Format.formatter -> build -> unit =
 fun env out build ->
  let delta = get_chance env (Carac.value build.fm) in
  Format.fprintf out "%d A × (%d du sorts + %d M - %d M) × %.2f %%"
    (Carac.value build.a) env.degat_sort (Carac.value build.m) 5 (delta *. 100.);
  let sum = env.degat_sort + Carac.value build.m - 5 in
  let prod = Carac.value build.a * sum in
  Format.fprintf out "@;%d A × %d = %d@;" (Carac.value build.a) sum prod;
  Format.fprintf out "%d × %.2f = %.2f" prod delta (delta *. float prod);
  ()

let cost : build -> int =
 fun { a; m; rm; pm; fm } ->
  Carac.(cout a + cout m + cout rm + cout pm + cout fm)

let repr : env -> Format.formatter -> build -> unit =
 fun env formatter build ->
  let degats, nb_attacks = eval build env in

  Format.fprintf formatter
    {|Caractéristiques retenues :
- A : %a
- M : %a
- FM: %a
- RM: %a
- PM: %a
|}
    Carac.repr build.a Carac.repr build.m Carac.repr build.fm Carac.repr
    build.rm Carac.repr build.pm;
  Format.fprintf formatter
    "@[Le magicien fera %.2f degats par attaque pour un total de %.2f (via %d \
     attaques)@;\
     (@[<v 2>%a@])@;"
    (degats /. float_of_int nb_attacks)
    degats nb_attacks (repr_degats env) build;
  Format.fprintf formatter "Le cout de ce build est de %d@]@." (cost build)

let score : env -> build -> float =
 fun env build ->
  let d, _ = eval build env in
  d

(* Upgrade each caracteristic and keep only the values in range *)
let upgrade : env -> build -> build list =
 fun env build ->
  [
    { build with a = Carac.incr build.a }
  ; { build with m = Carac.incr build.m }
  ; { build with rm = Carac.incr build.rm }
  ; { build with pm = Carac.incr build.pm }
  ; { build with pm = Carac.incr ~step:3 build.pm }
  ; { build with pm = Carac.incr ~step:10 build.pm }
  ; { build with fm = Carac.incr build.fm }
  ]
  |> List.filter (fun f -> cost f <= env.cost_max)

let rec traverse env (last_cost, last_score) = function
  | [] -> failwith "Invalid data"
  | hd :: [] -> hd
  | hd :: tl ->
      let score' = score env hd and cost' = cost hd in
      if cost' > last_cost && score' < last_score then
        traverse env (last_cost, last_score) tl
      else
        (* Get the new elements to add and filter them if they do not provide
           anything better *)
        let new_builds =
          upgrade env hd
          |> List.filter (fun build ->
                 List.for_all
                   (fun element -> score env build > score env element)
                   tl)
        in

        (* For each new element, remove all the obsolete builds *)
        traverse env (cost', score') (List.rev_append tl new_builds)