cryptopangrams.ml

let string_of_chars chars = 
  let buf = Buffer.create 16 in
  List.iter (Buffer.add_char buf) chars;
  Buffer.contents buf

module type Integer = sig
    type t
    val of_string : string -> t
    val to_string : t -> string
    val subtract : t -> t -> t
    val add : t -> t -> t
    val lshift : t -> int -> t
    val rshift : t -> int -> t
    val unit : t
    val zero : t
    val msb : t -> int
    val compare : t -> t -> int
 end

module SmallInt : Integer = struct
    type t = int
    let of_string = int_of_string
    let to_string = string_of_int
    let subtract = (-)
    let add = (+)
    let lshift = (lsl)
    let rshift = (lsr)
    let unit = 1
    let zero = 0
    let msb n =
        let rec loop n c = 
            if compare n zero = 0 then 
                c
            else loop (rshift n 1) (c + 1) in
        loop n 0
    let compare = compare
end

module BigInt : Integer = struct
    type t = int list
    let of_string s = failwith "To be implemented"
    let to_string n = failwith "To be implemented"
    let subtract a b = failwith "To be implemented"
    let add a b = failwith "To be implemented"
    let lshift a n = failwith "To be implemented"
    let rshift a n = failwith "To be implemented"
    let unit = [1]
    let zero = [0]
    let msb n = failwith "To be implemented"
    let compare a b = failwith "To be implemented"
end

module Decrypter(M : Integer) = struct
    module MMap = Map.Make(M)
    let lt a b = M.compare a b  < 0
    let eq a b = M.compare a b = 0

   let rec subtraction_div n d = 
        if lt n d then
            (M.zero, n)
        else
            let (q, r) = subtraction_div (M.subtract n d) d in
            M.add M.unit q, r

    let calcx n d = 
        let mn = M.msb n in
        let md = M.msb d in
        assert (md <= mn);
        let shift = mn - md in
        let a = M.lshift d shift in
        if lt n a then
            shift - 1
        else 
            shift

    let rec slow_div n d =
        if lt n d then
            (M.zero, n)
        else
            let x = calcx n d in
            let q, r = slow_div (M.subtract n (M.lshift d x)) d in
            M.add (M.lshift M.unit x) q, r

    let divide = slow_div
    let rec gcd a b = 
        let a_, b_ = if lt a b then a, b else b, a in
        if eq a_ M.zero then
            b_
        else 
            let q, r = divide b_ a_ in
            gcd a_ r

    let chars = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"

    let decrypt l =
        let nums = List.map M.of_string l in
        let a = List.hd nums in
        let b = List.hd (List.tl nums) in
        let c = gcd a b in
        let n1 = fst (divide a c) in
        let l = List.fold_left (fun l a -> 
                let n1 = List.hd l in
                let (n2, r) = (divide a n1) in
                assert (eq r M.zero);
                n2::l
            ) [n1] nums |> List.rev in
        let unique =  (List.sort_uniq M.compare l) in
        assert (List.length unique = 26);
        let mapping = MMap.of_seq (List.to_seq (List.mapi (fun i a -> (a, i)) unique)) in
        let ints = List.map (fun k -> MMap.find k mapping) l in
        let chars = List.map (fun i -> String.get chars i) ints in
        string_of_chars chars
end

module SmallIntDecrypter = Decrypter(SmallInt)

let _ = 
    let read_n n = 
        let line = read_line () in
        String.split_on_char ' ' line in
    let test count = 
        let line = read_line () in
        let n, l = Scanf.sscanf line "%d %d" (fun n l -> n, l) in
        let nums = read_n n in
        let res = SmallIntDecrypter.decrypt nums in
        Printf.printf "Case #%d: %s\n" count res in
    let count = read_int () in
    for i = 1 to count do
        test i
    done