algorithms

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

main.ml (1799B)


      1 (*
      2 - given n:
      3     - create arr [1,2,...,n]
      4         - compute the sum across all digits in the elements
      5             - 11 -> 1 + 1 -> 2
      6 
      7 - hmm, could I just... precompute before even fucking asking?
      8     - nope, 64kb max size
      9 
     10 - after we read in all of our problems, we generate a table for each value from 0 -> upper bound
     11 - we then do lookups per subsequent query
     12 
     13 - alt. idea:
     14     - have a lookup table for each of our queries and be intelligent about which results to cache
     15         - nah, these can be up to 1000 while the total size is up to 10k, only 10x higher, probably fine
     16 *)
     17 
     18 let read_int () = 
     19     Scanf.scanf("%d\n") (fun x -> x) 
     20 in
     21 
     22 (* returns largest *)
     23 
     24 let readInputs arr = 
     25     let rec acc idx = 
     26         if idx >= (Array.length arr)
     27             then -1
     28         else let cn = read_int() in
     29             let () = arr.(idx) <- cn in
     30                 let pr = acc (idx + 1) in
     31                     if cn > pr then cn else pr
     32     in acc 0
     33 in
     34 
     35 let rec sumDigits idx = 
     36     let base = (idx mod 10) in
     37         if idx >= 10 then
     38             base + sumDigits (idx / 10)
     39         else
     40             base
     41 in
     42 
     43 let preComputeTo arr = 
     44     let rec acc running idx = 
     45         if idx = Array.length arr
     46             then () 
     47         else (let updated = (running + (sumDigits idx)) in arr.(idx) <- updated; acc updated (idx+1))
     48     in acc 0 0
     49 in
     50 
     51 let printAnswer cases preComp = 
     52     let rec acc idx = 
     53         if idx >= Array.length cases then () else (print_int preComp.(cases.(idx)); print_newline (); acc (idx+1))
     54     in acc 0 
     55 in
     56     
     57 
     58 let testCases = read_int () in
     59     let cases = Array.make (testCases) 0 in
     60         let maxVal = readInputs cases in
     61             let preComp = Array.make (maxVal+1) 0 in 
     62                 let () = preComputeTo preComp in 
     63                     printAnswer cases preComp