algorithms

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

commit e4ffd3c573b9d27009003dfb513a5e16200dd43a
parent 76a8db3e66acbba71e67416620e480a257deba25
Author: Andrew Laack <andrew@laack.co>
Date:   Sun, 15 Nov 2026 20:40:03 -0600

two more div 4 problems

Diffstat:
Acomp/a-b-again/ex1.in | 9+++++++++
Acomp/a-b-again/ex2.in | 0
Acomp/a-b-again/main.ml | 10++++++++++
Acomp/a-b-again/thoughts.txt | 0
Acomp/kiakioand-squared-numbers/ex1.in | 9+++++++++
Acomp/kiakioand-squared-numbers/ex2.in | 0
Acomp/kiakioand-squared-numbers/main.ml | 65+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Acomp/kiakioand-squared-numbers/thoughts.txt | 0
8 files changed, 93 insertions(+), 0 deletions(-)

diff --git a/comp/a-b-again/ex1.in b/comp/a-b-again/ex1.in @@ -0,0 +1,9 @@ +8 +77 +21 +40 +34 +19 +84 +10 +99 diff --git a/comp/a-b-again/ex2.in b/comp/a-b-again/ex2.in diff --git a/comp/a-b-again/main.ml b/comp/a-b-again/main.ml @@ -0,0 +1,10 @@ +let readint () = + Scanf.scanf " %d" (fun x -> x) +let testcase () = + let n = readint () in + let rec acc vl = if vl = 0 then 0 else ((vl mod 10) + (acc (vl / 10))) + in (print_int (acc n); print_newline ()) +let () = + let testcases = readint () in + let rec acc idx = if idx = testcases then () else (testcase (); acc (idx+1)) + in acc 0 diff --git a/comp/a-b-again/thoughts.txt b/comp/a-b-again/thoughts.txt diff --git a/comp/kiakioand-squared-numbers/ex1.in b/comp/kiakioand-squared-numbers/ex1.in @@ -0,0 +1,9 @@ +4 +5 +7 4 16 4 2 +4 +1 7 10 100 +3 +4 16 37 +3 +2 20 4 diff --git a/comp/kiakioand-squared-numbers/ex2.in b/comp/kiakioand-squared-numbers/ex2.in diff --git a/comp/kiakioand-squared-numbers/main.ml b/comp/kiakioand-squared-numbers/main.ml @@ -0,0 +1,65 @@ +(* + +- n lighthouses +- each night each has a different number +- if a lighthouse shows x tonight, then tomorrow night it shows the sum of the squares of the decimal digits of x + - 24 + - 2**2 + 4**2 +- 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. +- Kia asks: how many pairs (i,j) with i<j are in tune + +7 4 16 4 2 + +steps: + +0 - 7 4 16 4 2 +1 - 49 16 37 16 4 +2 - 97 37 58 37 16 +3 - 130 58 89 58 37 +4 - 10 + + +1 7 10 100 + +4 16 37 + +2 20 4 + +can I just simulate these + +- : int -> (int -> 'a) -> 'a array = <fun> + +*) + +let readInt () = Scanf.scanf " %d" (fun x -> x) + +let rec nextStep num = + if num = 0 then 0 else ((num mod 10)*(num mod 10)) + (nextStep (num / 10)) + +let rec simulate arr steps = + if steps = 0 then arr else + let nxt = Array.map nextStep arr in simulate nxt (steps-1) + +let score arr = + let tbl = Hashtbl.create 100 in + let rec acc idx running = + if idx = Array.length arr then running + else match (try Some (Hashtbl.find tbl arr.(idx)) with Not_found -> None) with + | Some x -> (Hashtbl.replace tbl arr.(idx) (x+1); acc (idx+1) (running+x)) + | None -> (Hashtbl.add tbl arr.(idx) 1; acc (idx+1) (running)) + in acc 0 0 + + +let testCase () = + let nums = readInt () in + let arr = Array.init nums (fun _ -> readInt ()) + in print_int (score (simulate arr 1000)); print_newline () + +let () = + let testCases = readInt () in + let rec acc idx = + if idx = testCases then () else (testCase (); acc (idx+1)) + in acc 0 + + +(* I have proven collatz conjuecture, just run a bunch of steps *) diff --git a/comp/kiakioand-squared-numbers/thoughts.txt b/comp/kiakioand-squared-numbers/thoughts.txt