algorithms

Algorithm implementations
git clone git://git.laack.co/algorithms.git
Log | Files | Refs | README

naive.ml (1138B)


      1 let readInt () = 
      2     Scanf.scanf " %d" (fun x->x)
      3 
      4 let readString () = 
      5     Scanf.scanf " %s" (fun x->x)
      6 
      7 let compress s = 
      8     let buf = Buffer.create (String.length s) in
      9     String.iteri (fun i c -> if i = 0 || s.[i-1] <> c then Buffer.add_char buf c) s;
     10     Buffer.contents buf
     11 
     12 let allFlips s = 
     13 
     14     let compressedTbl = Hashtbl.create 10 in
     15     let () = Hashtbl.replace compressedTbl (compress s) () in
     16 
     17     let rec acc idx = 
     18         if idx == String.length s - 1 then
     19             ()
     20         else
     21             let oldChar = s.[idx] in
     22             let newChar = (if oldChar = '0' then '1' else '0') in
     23             let swapped = String.mapi (fun i c -> if i = idx then newChar else c) s in
     24                 Hashtbl.replace compressedTbl (compress swapped) ();
     25             acc (idx+1)
     26         in
     27     acc 1; Hashtbl.length compressedTbl
     28 
     29 let handleTestCase () =
     30     let st = readString ()
     31         in
     32     allFlips st
     33     
     34 let () = 
     35     let testCases = readInt () in
     36         let rec acc idx = 
     37             if idx = testCases then ()
     38                 else (print_int (handleTestCase ()); print_newline (); acc (idx+1))
     39         in
     40     acc 0