algorithms

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

main.ml (1720B)


      1 (*
      2 
      3 - n lighthouses
      4 - each night each has a different number
      5 - if a lighthouse shows x tonight, then tomorrow night it shows the sum of the squares of the decimal digits of x
      6     - 24
      7     - 2**2 + 4**2
      8 - two lighthouses i and j are in tune if there exists a night after which, forever, both of them show exactly the same number on every single night.
      9 - Kia asks: how many pairs (i,j) with i<j are in tune
     10 
     11 7 4 16 4 2
     12 
     13 steps:
     14 
     15 0 -  7  4 16  4 2
     16 1 - 49 16 37 16 4
     17 2 - 97   37 58 37 16
     18 3 - 130  58 89 58 37
     19 4 - 10 
     20 
     21 
     22 1 7 10 100
     23 
     24 4 16 37
     25 
     26 2 20 4
     27 
     28 can I just simulate these
     29 
     30 - : int -> (int -> 'a) -> 'a array = <fun>
     31 
     32 *)
     33 
     34 let readInt () = Scanf.scanf " %d" (fun x -> x)
     35 
     36 let rec nextStep num =
     37     if num = 0 then 0 else ((num mod 10)*(num mod 10)) + (nextStep (num / 10))
     38 
     39 let rec simulate arr steps = 
     40     if steps = 0 then arr else 
     41         let nxt = Array.map nextStep arr in simulate nxt (steps-1)
     42 
     43 let score arr = 
     44     let tbl = Hashtbl.create 100 in
     45         let rec acc idx running = 
     46             if idx = Array.length arr then running
     47                 else match (try Some (Hashtbl.find tbl arr.(idx)) with Not_found -> None) with
     48                     | Some x -> (Hashtbl.replace tbl arr.(idx) (x+1); acc (idx+1) (running+x))
     49                     | None -> (Hashtbl.add tbl arr.(idx) 1; acc (idx+1) (running))
     50         in acc 0 0
     51         
     52 
     53 let testCase () =
     54     let nums = readInt () in
     55     let arr = Array.init nums (fun _ -> readInt ()) 
     56     in print_int (score (simulate arr 1000)); print_newline ()
     57 
     58 let () =
     59     let testCases = readInt () in
     60     let rec acc idx = 
     61         if idx = testCases then () else (testCase (); acc (idx+1))
     62     in acc 0
     63 
     64 
     65 (* I have proven collatz conjuecture, just run a bunch of steps *)