algorithms

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

commit 0973b5639e3a817629062f6d57feb90a907ea50d
parent ddeef28235e8f97ea57a88d984ff83a9bb34402a
Author: Andrew Laack <andrew@laack.co>
Date:   Tue, 10 Nov 2026 20:33:00 -0600

Production of snowmen in ocaml (lots of recursive loops)

Diffstat:
Acomp/production-of-snowmen/ex1.in | 17+++++++++++++++++
Acomp/production-of-snowmen/main.ml | 124+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Acomp/production-of-snowmen/slow.ml | 125+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
3 files changed, 266 insertions(+), 0 deletions(-)

diff --git a/comp/production-of-snowmen/ex1.in b/comp/production-of-snowmen/ex1.in @@ -0,0 +1,17 @@ +4 +2 +1 2 +3 4 +5 4 +3 +1 1 1 +2 2 2 +3 3 3 +4 +1 2 1 2 +3 3 2 2 +5 5 5 5 +5 +1 4 2 3 5 +6 4 5 7 6 +7 5 8 10 10 diff --git a/comp/production-of-snowmen/main.ml b/comp/production-of-snowmen/main.ml @@ -0,0 +1,124 @@ +(* +- problem + - producing snowmen + - three snowballs per + - leg ball must be strictly larger than the torso + - torso must be strictly larger than the head + - a,b,c s.t. a < b < c for the balls + - three conveyors with n snowballs each + - first is a_1, a_2, ..., a_n + - second is b_1, b_2, ..., b_n + - third is c_1, c_2, ..., c_n + - cyclic conveyors + - i,j,k where 1 <= i,j,k <= n + - this specifies which balls on each conveyor the production starts from + - assembling goes as follows + - first snowman has head size a_i, torso of b_j, legs of size c_k + - second will have a_{i+1}, b_{j+1}, c_{k+1} + - so on + - last will be: + - a_{i+n-1}, b_{j+n-1}, c_{k+n-1} + - i,j,k must be chosen to make the snowmen stable + - return number of suitable selections for i,j,k + +- thoughts + - brute force approach is to just check each selection of i,j,k + - there are O(n^3) options for this + - at most 5000 elements + - 5000 ** 3 = 125_000_000_000 + - too slow + - 5000 ** 2 = 4_000_000 + - this is probably ~ our target + - what else can we search over? + - selections of base, torso, heads + - there are compression opportunities here (I think) + - basically, we can find the O(n^2) selections of base and torsos + - we then find the O(n^2) selections of torsos and heads + - we then we then match on valid base/torso pairs, joined on torso/head combinations + - concretely, we'd create 2 seperate 5000x5000 grids representing combinations + - this feels off, not sure why + - probably because I haven't entirely solved the problem of constraining the starting points to sane options + - who can we dp on this? + - we're trying to count selections that work + - can we just dp on selections? + - not really because selections aren't preserved across selections + - that's not true, if we just offset each selection they are so kinda? + - this would functionaly change the dimensions of this problem + - instead we care about relative offsets + - that's not obviously better asymptotically + - actually, this drops this down by one factor of n because each selection has n offsets that match the current one + - generally, if we hit a state again, we can return the overall finding of that selection from the prior step because the current is the same + - actually we could constrain our selections with this knowledge and multiply by n at the end + - how would this look? + - we can put the first selection at 0 and vary the other two. this gives us offsets onto them, and we notice that moving the top element is just the same as moving everything by a shift + +- fleshed out + - set i = 0 + - set res = 0 + - for j in range(n): + - for k in range(n): + - if valid i,j,k : res += 1 else continue + - multiply final result by n because i can be 0,1,...,n-1 and still have the same cyclic property + +- can the idea above be memoized? + - sort of. i can be safe relative to j and k but this isn't fool-proof + - we only compare j and k values in unique ways + +*) + +let read_int () = Scanf.scanf " %d" (fun x -> x) in + +let readArr length = + let arr = Array.make length 0 in + + let rec load i = + if i = length then () + else + let () = arr.(i) <- read_int () in + load (i + 1) + in + + let () = load 0 in + arr +in + +let isValid x y j = + let rec loopStep offset = + if offset = Array.length x then true + else if x.(offset) >= y.((offset + j) mod Array.length x) then false + else loopStep (offset + 1) + in + loopStep 0 +in + +let solve a b c = + let n = Array.length a in + let rec loopK k count = + if k = n then count + else + let count = if isValid b c k then count + 1 else count in + loopK (k + 1) count + in + let rec loopJ j count = + if j = n then count + else + let count = if isValid a b j then count + 1 else count in + loopJ (j + 1) count + in + Int64.mul (Int64.mul (Int64.of_int (loopJ 0 0)) (Int64.of_int (loopK 0 0))) (Int64.of_int n) +in + +let rec handleTestCases rem = + if rem > 0 then ( + let ln = read_int () in + let a = readArr ln in + let b = readArr ln in + let c = readArr ln in + print_string (Int64.to_string (solve a b c)); + print_newline (); + handleTestCases (rem - 1)) + else () +in + +let testCases = read_int () in +handleTestCases testCases diff --git a/comp/production-of-snowmen/slow.ml b/comp/production-of-snowmen/slow.ml @@ -0,0 +1,125 @@ +(* +- problem + - producing snowmen + - three snowballs per + - leg ball must be strictly larger than the torso + - torso must be strictly larger than the head + - a,b,c s.t. a < b < c for the balls + - three conveyors with n snowballs each + - first is a_1, a_2, ..., a_n + - second is b_1, b_2, ..., b_n + - third is c_1, c_2, ..., c_n + - cyclic conveyors + - i,j,k where 1 <= i,j,k <= n + - this specifies which balls on each conveyor the production starts from + - assembling goes as follows + - first snowman has head size a_i, torso of b_j, legs of size c_k + - second will have a_{i+1}, b_{j+1}, c_{k+1} + - so on + - last will be: + - a_{i+n-1}, b_{j+n-1}, c_{k+n-1} + - i,j,k must be chosen to make the snowmen stable + - return number of suitable selections for i,j,k + +- thoughts + - brute force approach is to just check each selection of i,j,k + - there are O(n^3) options for this + - at most 5000 elements + - 5000 ** 3 = 125_000_000_000 + - too slow + - 5000 ** 2 = 4_000_000 + - this is probably ~ our target + - what else can we search over? + - selections of base, torso, heads + - there are compression opportunities here (I think) + - basically, we can find the O(n^2) selections of base and torsos + - we then find the O(n^2) selections of torsos and heads + - we then we then match on valid base/torso pairs, joined on torso/head combinations + - concretely, we'd create 2 seperate 5000x5000 grids representing combinations + - this feels off, not sure why + - probably because I haven't entirely solved the problem of constraining the starting points to sane options + - who can we dp on this? + - we're trying to count selections that work + - can we just dp on selections? + - not really because selections aren't preserved across selections + - that's not true, if we just offset each selection they are so kinda? + - this would functionaly change the dimensions of this problem + - instead we care about relative offsets + - that's not obviously better asymptotically + - actually, this drops this down by one factor of n because each selection has n offsets that match the current one + - generally, if we hit a state again, we can return the overall finding of that selection from the prior step because the current is the same + - actually we could constrain our selections with this knowledge and multiply by n at the end + - how would this look? + - we can put the first selection at 0 and vary the other two. this gives us offsets onto them, and we notice that moving the top element is just the same as moving everything by a shift + +- fleshed out + - set i = 0 + - set res = 0 + - for j in range(n): + - for k in range(n): + - if valid i,j,k : res += 1 else continue + - multiply final result by n because i can be 0,1,...,n-1 and still have the same cyclic property + +- can the idea above be memoized? + - sort of. i can be safe relative to j and k but this isn't fool-proof + - we only compare j and k values in unique ways + +*) + +let read_int () = Scanf.scanf " %d" (fun x -> x) in + +let readArr length = + let arr = Array.make length 0 in + + let rec load i = + if i = length then () + else + let () = arr.(i) <- read_int () in + load (i + 1) + in + + let () = load 0 in + arr +in + +let isValid a b c j k = + let rec loopStep offset = + if offset = Array.length a then true + else if + a.(offset) >= b.((offset + j) mod Array.length a) + || b.((offset + j) mod Array.length a) + >= c.((offset + k) mod Array.length a) + then false + else loopStep (offset + 1) + in + loopStep 0 +in + +let solve a b c = + let n = Array.length a in + let rec loopK j k count = + if k = n then count + else + let count = if isValid a b c j k then count + 1 else count in + loopK j (k + 1) count + in + let rec loopJ j count = + if j = n then count else loopJ (j + 1) (loopK j 0 count) + in + loopJ 0 0 * n +in + +let rec handleTestCases rem = + if rem > 0 then ( + let ln = read_int () in + let a = readArr ln in + let b = readArr ln in + let c = readArr ln in + print_int (solve a b c); + print_newline (); + handleTestCases (rem - 1)) + else () +in + +let testCases = read_int () in +handleTestCases testCases