1 files changed, 58 insertions, 27 deletions

diff --git a/calculette_aoo/lib/roll.ml b/calculette_aoo/lib/roll.ml
index 00d8465..14488e6 100644
--- a/calculette_aoo/lib/roll.ml
+++ b/calculette_aoo/lib/roll.ml
@@ -1,24 +1,52 @@
 open StdLabels
 
-(** Evaluate the coefficient for the product of two polynamials *)
-let mul p1 p2 =
-  let n1 = Array.length p1 and n2 = Array.length p2 in
-  let n = n1 + n2 in
-  let res = Array.make n 0 in
-  for i = 0 to n1 - 1 do
-    for j = 0 to n2 - 1 do
-      res.(i + j + 1) <- res.(i + j + 1) + (p1.(i) * p2.(j))
-    done
-  done;
-  res
+(** Build the frequencies table for the given number of dices to roll. The
+    function return a table with the number of occurences for the each index.
+
+    Example : 
+        table[2] = 1
+        table[3] = 4
+
+    Tell us than there the probabily to get the value 3 is 4× higher to get the
+    value 2.
+    *)
+let build_frequencies n =
+  let length = n * 3 in
+
+  let arr_source = Array.init length ~f:(fun i -> if i < 3 then 1 else 0) in
+
+  (* Recursive function, evaluate the odd by adding a new dice to the previous
+     distribution.
+
+     The probabily to get the value V with N dice is equal to :
+     - The probabilyt to get the value V - 1 with N - 1 dices and having 1 with
+       the new dice
+     - The probabilyt to get the value V - 2 with N - 1 dices and having 2 with
+       the new dice
+     - The probabilyt to get the value V - 3 with N - 1 dices and having 3 with
+       the new dice
 
-(** Apply a power function over a polynomial *)
-let pow p1 n =
-  let result = ref p1 in
-  for _ = 1 to n - 1 do
-    result := mul !result p1
-  done;
-  !result
+     As the dice is fair, the probability to get the new value is equal in each
+     case, and we can just ignore this part.
+
+     This give us this formula :
+
+     P(V)_N = P(V - 1)_(N-1) + P(V - 2)_(N-1) + P(V - 3)_(N-1)
+  *)
+  let rec apply level arr_source =
+    match level with
+    | 0 -> arr_source
+    | _ ->
+        let arr_target = Array.init length ~f:(fun _ -> 0) in
+        let depth = n - level + 1 in
+        for index = max 1 (depth - 1) to (3 * depth) - 1 do
+          for j = max 0 (index - 3) to index - 1 do
+            arr_target.(index) <- arr_target.(index) + arr_source.(j)
+          done
+        done;
+        apply (level - 1) arr_target
+  in
+  apply (n - 1) arr_source
 
 (** Evaluate the odd to win agains a give difficulty *)
 let against : int -> int array -> Q.t array =
@@ -26,18 +54,19 @@ let against : int -> int array -> Q.t array =
   match n with
   | 0 -> Array.map ~f:(fun _ -> Q.zero) difficulties
   | _ ->
-      (* Create the polynomial with the odd ratio for the given caracteristic *)
-      let arr = Array.make 3 1 in
-      let frequencies = pow arr n in
+      (* Create the polynomial with the odd ratio for the given
+         caracteristic *)
+      let frequencies = build_frequencies n in
       let ratio = Z.(of_int 3 ** n) in
 
       let get_chances difficulty =
         (* Evaluate the ratio to win the roll *)
         let chances = ref Z.zero in
         for i = difficulty - 1 to Array.length frequencies - 1 do
-          (* The index in the table is the odd to get exactly this value in the roll.
-             Here, we just add every value in the array from the index strarting from
-             the given difficulty. *)
+          (* The index in the table is the odd to get exactly this value in the
+             roll.
+             Here, we just add every value in the array from the index
+             strarting from the given difficulty. *)
           chances := Z.(!chances + of_int frequencies.(i))
         done;
         Q.make !chances ratio
@@ -51,7 +80,6 @@ let against : int -> int array -> Q.t array =
     In case of equality, the win is given to [v1] *)
 let compare : int -> int -> Q.t =
  fun carac1 carac2 ->
-  let arr = Array.make 3 1 in
   let z3 = Z.of_int 3 in
 
   let ordinal1 = Z.(z3 ** carac1)
@@ -63,8 +91,11 @@ let compare : int -> int -> Q.t =
   (* The number of iterations to do is elements1 × elements2. For every iteration of elements2, we have ordinal1 points to get.  *)
   let cases = Z.(ordinal1 * ordinal2) in
 
-  let frequencies_1 = pow arr carac1 |> Array.map ~f:(fun v -> Z.(of_int v))
-  and frequencies_2 = pow arr carac2 |> Array.map ~f:(fun v -> Z.(of_int v)) in
+  let frequencies_1 =
+    build_frequencies carac1 |> Array.map ~f:(fun v -> Z.(of_int v))
+  and frequencies_2 =
+    build_frequencies carac2 |> Array.map ~f:(fun v -> Z.(of_int v))
+  in
 
   (* Now, compare for each values the probabily to win *)
   let res = ref Z.zero in