Project Euler #74

gistfile1.ml

open List;;
open Printf;;

let rec dfact n = 
  match n with
      0 -> 1
    | 1 -> 1
    | 2 -> 2
    | 3 -> 6
    | 4 -> 24
    | 5 -> 120
    | 6 -> 720
    | 7 -> 5040
    | 8 -> 40320
    | 9 -> 362880
    | _ -> raise (Failure "Not a digit");;

let digit_list n =
  let rec i_dlist m acc =
    match m with
        0 -> acc
      | k -> i_dlist (k / 10) (rev_append acc [k mod 10])
  in
    i_dlist n [];;

let dfs n = fold_left (+) 0 (rev_map dfact (digit_list n));;

let dfs_chain n = 
  let rec i_dfs_chain acc m k=
    try
      find (fun x -> x = m) acc; k
    with Not_found ->
      i_dfs_chain (rev_append acc [m]) (dfs m) (k + 1)
  in
    i_dfs_chain [n] (dfs n) 1;;

let rec solution n k =
  match n with
      0 -> printf "Total number of chains: %d\n" k
    | l -> 
        let chain_length = dfs_chain l
        in
          if chain_length >= 60 then
            begin
              printf "%d -> %d\n" k chain_length; 
              solution (l - 1) (k + 1)
            end
          else
            solution (l - 1) k;;

solution 1000000 0;