ocaml-programming

Simple OCaml programs
git clone git://git.laack.co/ocaml-programming.git
Log | Files | Refs | README

commit 9bbd171c112fce73e5150b4d98c7dbe122b9cee0
parent 2d4aae6cc66401191987352ceb9a6fef3a855f0e
Author: Andrew Laack <andrew@laack.co>
Date:   Wed, 11 Nov 2026 14:47:43 -0600

Word dictionary lookup

Diffstat:
Aotr/dict-contains/dictionary.txt | 63+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Aotr/dict-contains/main.ml | 106+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
2 files changed, 169 insertions(+), 0 deletions(-)

diff --git a/otr/dict-contains/dictionary.txt b/otr/dict-contains/dictionary.txt @@ -0,0 +1,63 @@ +AA +AAH +AAHED +AAHING +AAHS +AAL +AALII +AALIIS +AALS +AARDVARK +AARDVARKS +AARDWOLF +AARDWOLVES +AARGH +AARRGH +AARRGHH +AAS +AASVOGEL +AASVOGELS +AB +ABA +ABACA +ABACAS +ABACI +ABACK +ABACTERIAL +ABACUS +ABACUSES +ABAFT +ABAKA +ABAKAS +ABALONE +ABALONES +ABAMP +ABAMPERE +ABAMPERES +ABAMPS +ABANDON +ABANDONED +ABANDONER +ABANDONERS +ABANDONING +ABANDONMENT +ABANDONMENTS +ABANDONS +ABAPICAL +ABAS +ABASE +ABASED +ABASEDLY +ABASEMENT +ABASEMENTS +ABASER +ABASERS +ABASES +ABASH +ABASHED +ABASHEDLY +ABASHES +ABASHING +ABASHMENT +ABASHMENTS +ABASIA diff --git a/otr/dict-contains/main.ml b/otr/dict-contains/main.ml @@ -0,0 +1,106 @@ +(* pre: + - dictionary contains uppercase ascii +inv: + - upper and lowercase results always match for word +*) + +let dictContainsStr word dictionary = + match Hashtbl.find_opt dictionary (String.uppercase_ascii word) with + | Some _ -> true + | None -> false +in + +(* post: + - new dictionary elements contain only uppercase ascii +*) + +let readFile dict filename = + let ch = open_in filename in + (try + + let rec acc () = + let line = input_line ch in Hashtbl.replace dict (String.uppercase_ascii line) (); acc () + in acc () + + with End_of_file -> ()); + close_in ch +in + +(* +scrabble: +- take in a string and return all possible valid words using these letters +- how many letters do we have? + - 26 ^ 7 + - 8_031_810_176 selections + - dp approach with prefix matching + - count the characters in our string + - compare the counts of characters in other strings, noting we have a match if the counts correspond + - this scales with the size of the dictionary because we read each dictionary element + +- create a 26-dimensional vector that encodes the word frequencies per word + - [a_count, b_count, c_count, ..., z_count] -- per word in our dictionary + - note: comparing two of these vectors is constant time because size is bounded (to 26) + - alt: + - we could make each of these encodings the key in hashtable, then perform a lookup? + - we still have to find each of the matching strings and return them + - dict [encoding] = [s_1,s_2,...] + - the issue with this is we are only checking on thes basis of full text match + - so we still want to generate and lookup all subsets of our characters + - there are thusly 2**7 to check = 128 selections +*) + + +let testMembership word dict = + if dictContainsStr word dict then print_endline "Found" else print_endline "Not found" +in + +let countsOf word = + let counts = Array.make 26 0 in + String.iter (fun c -> + let i = Char.code (c) - Char.code 'A' in + if i >= 0 && i < 26 then counts.(i) <- counts.(i) + 1) word; + counts +in + + +let genLookup lookup dict = + Hashtbl.iter (fun word _ -> + let encoding = countsOf word in + match Hashtbl.find_opt lookup encoding with + | Some words -> Hashtbl.replace lookup encoding (word :: words) + | None -> Hashtbl.replace lookup encoding [word]) dict +in + +let rec printList ls = + match ls with + | [] -> () + | h :: t -> print_endline h; printList t +in + + +let subCounts cts = + let rec go i = + if i = 26 then [[]] + else + let rest = go (i + 1) in + List.concat_map + (fun k -> List.map (fun r -> k :: r) rest) + (List.init (cts.(i) + 1) Fun.id) + in + List.map Array.of_list (go 0) +in + +let printMatches characters lookup = + let subs = subCounts (countsOf characters) in + let matches = List.filter_map (fun sub -> Hashtbl.find_opt lookup sub) subs in + match matches with + | [] -> print_endline "No matching words found" + | _ -> List.iter printList matches +in + +let dict = Hashtbl.create 10 + in let () = readFile dict "dictionary.txt" + in testMembership "aardvark" dict; testMembership "rasoiena" dict; + let lookup = Hashtbl.create 178691 in + genLookup lookup dict; + let characters = "TAOMFEA" in printMatches characters lookup;