Permalink
Switch branches/tags
Nothing to show
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
31 lines (24 sloc) 737 Bytes
open Core.Std
type t = int String.Map.t
let empty = String.Map.empty
let to_list t = Map.to_alist t
let touch t s =
let count =
match Map.find t s with
| None -> 0
| Some x -> x
in
Map.add t ~key:s ~data:(count + 1)
(* part 1 *)
type median = | Median of string
| Before_and_after of string * string
let median t =
let sorted_strings = List.sort (Map.to_alist t)
~cmp:(fun (_,x) (_,y) -> Int.descending x y)
in
let len = List.length sorted_strings in
if len = 0 then failwith "median: empty frequency count";
let nth n = fst (List.nth_exn sorted_strings n) in
if len mod 2 = 1
then Median (nth (len/2))
else Before_and_after (nth (len/2 - 1), nth (len/2));;