algorithms

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

commit edb9069f53f2f59bb7fbaad86d0c8dbf6dbf273c
parent 77f117082080792800f0563ebcfb6433f707df09
Author: Andrew Laack <andrew@laack.co>
Date:   Sun, 15 Nov 2026 19:28:00 -0600

Need more arrays with ocaml

Diffstat:
Acomp/need-more-arrays/ex1.in | 13+++++++++++++
Acomp/need-more-arrays/ex2.in | 0
Acomp/need-more-arrays/main.ml | 16++++++++++++++++
Acomp/need-more-arrays/thoughts.txt | 20++++++++++++++++++++
Mmy-problems/interesting-problems.txt | 1+
5 files changed, 50 insertions(+), 0 deletions(-)

diff --git a/comp/need-more-arrays/ex1.in b/comp/need-more-arrays/ex1.in @@ -0,0 +1,13 @@ +6 +6 +1 2 3 4 5 6 +3 +1 2 3 +4 +1 2 2 4 +1 +2 +3 +1 4 8 +2 +1 1 diff --git a/comp/need-more-arrays/ex2.in b/comp/need-more-arrays/ex2.in diff --git a/comp/need-more-arrays/main.ml b/comp/need-more-arrays/main.ml @@ -0,0 +1,16 @@ +let readInt () = + Scanf.scanf " %d" (fun x->x) +let handleTestCase () = + let size = readInt () in + let arr = Array.make size 0 in + let () = + let rec acc idx = + if idx = size then () else (arr.(idx) <- readInt (); acc (idx+1)) + in acc 0 in + print_int (snd ((Array.fold_left (fun (prior,total) current -> (if prior+2 <= current then (current,total+1) else (prior, total))) (-10,0) arr))); + print_newline () +let () = + let testCases = readInt () in + let rec acc idx = + if idx = testCases then () else (acc (idx+1); handleTestCase ()) + in acc 0 diff --git a/comp/need-more-arrays/thoughts.txt b/comp/need-more-arrays/thoughts.txt @@ -0,0 +1,20 @@ +- starting with an array in non-decreasing order + - a_1, a_2, ..., a_n +- you can remove any number of elements from the array, including none, without changing the order of the remaining elements +- after all removals the following will happen: + - a_1 is written to a new array + - if a_1 + 1 < a_2 then a_2 is written to a new array, else a_2 is written to the same array as a_1 + - if a_2 + 1 < a_3 then a_3 is written to a new array, else a_3 is written to the same array as a_2 +- if a = [1,2,4,6], then + - [1] + - since 1+1 !< 2 + - [1, 2] + - since 2+1 < 4 + - [1, 2], [4] + - since 4+1 < 6 + - [1, 2], [4], [6] + +- Your task is to remove elements in such a way that the described algorithm creates as many arrays as possible. If you remove all elements from the array, no new arrays will be created. + +- idea: + - do we just want to remove all elements until the delta between the last existing and the current is at least 2? diff --git a/my-problems/interesting-problems.txt b/my-problems/interesting-problems.txt @@ -17,3 +17,4 @@ strings - given strings a,b,c, find the number of substrings of a,b,c that match d - rabin can get busted +- minimum # of swaps