algorithms

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

commit d9681d12ff8ecd672635f0bf5adacc1b54c2e2ee
parent 0973b5639e3a817629062f6d57feb90a907ea50d
Author: Andrew Laack <andrew@laack.co>
Date:   Tue, 10 Nov 2026 23:34:15 -0600

Iterative (recursive) precomputation problem in ocaml

Diffstat:
Acomp/vlad-and-a-sum-of-digits/ex1.in | 8++++++++
Acomp/vlad-and-a-sum-of-digits/ex2.in | 1001+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Acomp/vlad-and-a-sum-of-digits/main.ml | 63+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
3 files changed, 1072 insertions(+), 0 deletions(-)

diff --git a/comp/vlad-and-a-sum-of-digits/ex1.in b/comp/vlad-and-a-sum-of-digits/ex1.in @@ -0,0 +1,8 @@ +7 +12 +1 +2 +3 +1434 +2024 +200000 diff --git a/comp/vlad-and-a-sum-of-digits/ex2.in b/comp/vlad-and-a-sum-of-digits/ex2.in @@ -0,0 +1,1001 @@ +1000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 +200000 diff --git a/comp/vlad-and-a-sum-of-digits/main.ml b/comp/vlad-and-a-sum-of-digits/main.ml @@ -0,0 +1,63 @@ +(* +- given n: + - create arr [1,2,...,n] + - compute the sum across all digits in the elements + - 11 -> 1 + 1 -> 2 + +- hmm, could I just... precompute before even fucking asking? + - nope, 64kb max size + +- after we read in all of our problems, we generate a table for each value from 0 -> upper bound +- we then do lookups per subsequent query + +- alt. idea: + - have a lookup table for each of our queries and be intelligent about which results to cache + - nah, these can be up to 1000 while the total size is up to 10k, only 10x higher, probably fine +*) + +let read_int () = + Scanf.scanf("%d\n") (fun x -> x) +in + +(* returns largest *) + +let readInputs arr = + let rec acc idx = + if idx >= (Array.length arr) + then -1 + else let cn = read_int() in + let () = arr.(idx) <- cn in + let pr = acc (idx + 1) in + if cn > pr then cn else pr + in acc 0 +in + +let rec sumDigits idx = + let base = (idx mod 10) in + if idx >= 10 then + base + sumDigits (idx / 10) + else + base +in + +let preComputeTo arr = + let rec acc running idx = + if idx = Array.length arr + then () + else (let updated = (running + (sumDigits idx)) in arr.(idx) <- updated; acc updated (idx+1)) + in acc 0 0 +in + +let printAnswer cases preComp = + let rec acc idx = + if idx >= Array.length cases then () else (print_int preComp.(cases.(idx)); print_newline (); acc (idx+1)) + in acc 0 +in + + +let testCases = read_int () in + let cases = Array.make (testCases) 0 in + let maxVal = readInputs cases in + let preComp = Array.make (maxVal+1) 0 in + let () = preComputeTo preComp in + printAnswer cases preComp