(* Compter le nombre de façons de construire un mur de briques
   de longueur 32 et de hauteur 10, avec des briques de longueur 2 et 3 *)

let width = 32
let height = 10

let add2 r = (r lsl 2) lor 0b10
let add3 r = (r lsl 3) lor 0b100

let rows = ref []

let rec fill w r =
  if w = width then rows := r :: !rows
  else if w < width then begin fill (w + 2) (add2 r); fill (w + 3) (add3 r) end

let () = fill 2 0; fill 3 0
let () = Printf.printf "%d rangées\n" (List.length !rows)

let rec sum f = function
  | [] -> 0
  | x :: r -> f x + sum f r

let size = 1 lsl 16
let table = Array.make size []

let hash (x,y) = x lxor (x lsr 16) + 5003 * y
let bucket k = (hash k) land (size - 1)

let add k v =
  let i = bucket k in
  table.(i) <- (k, v) :: table.(i)

let find k =
  let rec lookup = function
    | [] -> raise Not_found
    | (k', v) :: r -> if k' = k then v else lookup r
  in
  lookup table.(bucket k)

let rec count r h =
  if h = 1 then
    1
  else
    sum (fun r' -> if r land r' = 0 then memo_count r' (h-1) else 0) !rows

and memo_count r h =
  try  find (r,h)
  with Not_found -> let v = count r h in add (r,h) v; v

let sol = sum (fun r -> count r height) !rows
let () = Printf.printf "solution = %d\n" sol

(*
Local Variables:
compile-command: "ocamlopt -o wall wall.ml && time ./wall"
End:
*)


This document was generated using caml2html