F# で Project Euler Problem 14
今回は、Scala 版とは違って、辞書にコラッツ数列そのものを格納するのではなく、
次の数だけ格納してみる。
> let rec collatz_list(n:int64): List<int64> = - if (n = 1L) then [1L] - elif (n % 2L = 0L) then n::collatz_list(n / 2L) - else n::collatz_list(3L * n + 1L) - ;; val collatz_list : int64 -> List<int64>
> collatz_list 1L;; val it : List<int64> = [1L]
> collatz_list 9L;; val it : List<int64> = [9L; 28L; 14L; 7L; 22L; 11L; 34L; 17L; 52L; 26L; 13L; 40L; 20L; 10L; 5L; 16L; 8L; 4L; 2L; 1L]
> let rec add_map(lst:List<int64>, map:Map<int64, int64> byref) = - if not (List.isEmpty lst) then - if lst.Head <> 1L then - if not (Map.containsKey lst.Head map) then - map <- map |> Map.add lst.Head lst.Tail.Head - add_map(lst.Tail, &map) - ;; val add_map : List<int64> * byref<Map<int64,int64>> -> unit
> let rec collatz_list(n:int64, map:Map<int64, int64>): List<int64> = - if (n = 1L) then [1L] - else - if (Map.containsKey n map) then - n::collatz_list(map.[n], map) - else - if (n % 2L = 0L) then n::collatz_list(n / 2L, map) - else n::collatz_list(3L * n + 1L, map) - ;; val collatz_list : int64 * Map<int64,int64> -> List<int64>
> let mutable map:Map<int64, int64> = Map.empty;; val mutable map : Map<int64,int64> = map [] > let lst = collatz_list(1L, map);; val lst : List<int64> = [1L] > add_map(lst, &map);; val it : unit = () > map;; val it : Map<int64,int64> = map []
> - let lst = collatz_list(2L, map);; val lst : List<int64> = [2L; 1L] > add_map(lst, &map);; val it : unit = () > map;; val it : Map<int64,int64> = map [(2L, 1L)]
>
- let lst = collatz_list(3L, map);;
val lst : List<int64> = [3L; 10L; 5L; 16L; 8L; 4L; 2L; 1L]
> add_map(lst, &map);;
val it : unit = ()
> map;;
val it : Map<int64,int64> =
map
[(2L, 1L); (3L, 10L); (4L, 2L); (5L, 16L); (8L, 4L); (10L, 5L); (16L, 8L)]> let mutable map:Map<int64, int64> = Map.empty;; val mutable map : Map<int64,int64> = map [] > for i in [1L..9L] do - let lst = collatz_list(i, map) - printf "%d\n" (List.length lst) - add_map(lst, &map) - ;; 1 2 8 3 6 9 17 4 20 val it : unit = ()
> let mutable map:Map<int64, int64> = Map.empty;; val mutable map : Map<int64,int64> = map [] > let mutable max_num = 0;; val mutable max_num : int = 0 > let mutable max_idx = 0L;; val mutable max_idx : int64 = 0L > for i in [1L..99L] do - let lst = collatz_list(i, map) - if (List.length lst) > max_num then - max_num <- (List.length lst) - max_idx <- i - add_map(lst, &map) - ;; val it : unit = () > printf "%d:%d\n" max_idx max_num;; 97:119 val it : unit = ()
> - let mutable map:Map<int64, int64> = Map.empty;; val mutable map : Map<int64,int64> = map [] > let mutable max_num = 0;; val mutable max_num : int = 0 > let mutable max_idx = 0L;; val mutable max_idx : int64 = 0L > for i in [1L..9999L] do - let lst = collatz_list(i, map) - if (List.length lst) > max_num then - max_num <- (List.length lst) - max_idx <- i - add_map(lst, &map) - ;; val it : unit = () > printf "%d:%d\n" max_idx max_num;; 6171:262 val it : unit = ()
> - let mutable map:Map<int64, int64> = Map.empty;; val mutable map : Map<int64,int64> = map [] > let mutable max_num = 0;; val mutable max_num : int = 0 > let mutable max_idx = 0L;; val mutable max_idx : int64 = 0L > for i in [1L..999999L] do - let lst = collatz_list(i, map) - if (List.length lst) > max_num then - max_num <- (List.length lst) - max_idx <- i - add_map(lst, &map) - ;; val it : unit = () > printf "%d:%d\n" max_idx max_num;; 837799:525 val it : unit = ()
だめだ
めちゃ遅くて話にならない
