main.ml (3399B)
1 (* pre: 2 - dictionary contains uppercase ascii 3 inv: 4 - upper and lowercase results always match for word 5 *) 6 7 let dictContainsStr word dictionary = 8 match Hashtbl.find_opt dictionary (String.uppercase_ascii word) with 9 | Some _ -> true 10 | None -> false 11 in 12 13 (* post: 14 - new dictionary elements contain only uppercase ascii 15 *) 16 17 let readFile dict filename = 18 let ch = open_in filename in 19 (try 20 21 let rec acc () = 22 let line = input_line ch in Hashtbl.replace dict (String.uppercase_ascii line) (); acc () 23 in acc () 24 25 with End_of_file -> ()); 26 close_in ch 27 in 28 29 (* 30 scrabble: 31 - take in a string and return all possible valid words using these letters 32 - how many letters do we have? 33 - 26 ^ 7 34 - 8_031_810_176 selections 35 - dp approach with prefix matching 36 - count the characters in our string 37 - compare the counts of characters in other strings, noting we have a match if the counts correspond 38 - this scales with the size of the dictionary because we read each dictionary element 39 40 - create a 26-dimensional vector that encodes the word frequencies per word 41 - [a_count, b_count, c_count, ..., z_count] -- per word in our dictionary 42 - note: comparing two of these vectors is constant time because size is bounded (to 26) 43 - alt: 44 - we could make each of these encodings the key in hashtable, then perform a lookup? 45 - we still have to find each of the matching strings and return them 46 - dict [encoding] = [s_1,s_2,...] 47 - the issue with this is we are only checking on thes basis of full text match 48 - so we still want to generate and lookup all subsets of our characters 49 - there are thusly 2**7 to check = 128 selections 50 *) 51 52 53 let testMembership word dict = 54 if dictContainsStr word dict then print_endline "Found" else print_endline "Not found" 55 in 56 57 let countsOf word = 58 let counts = Array.make 26 0 in 59 String.iter (fun c -> 60 let i = Char.code (c) - Char.code 'A' in 61 if i >= 0 && i < 26 then counts.(i) <- counts.(i) + 1) word; 62 counts 63 in 64 65 66 let genLookup lookup dict = 67 Hashtbl.iter (fun word _ -> 68 let encoding = countsOf word in 69 match Hashtbl.find_opt lookup encoding with 70 | Some words -> Hashtbl.replace lookup encoding (word :: words) 71 | None -> Hashtbl.replace lookup encoding [word]) dict 72 in 73 74 let rec printList ls = 75 match ls with 76 | [] -> () 77 | h :: t -> print_endline h; printList t 78 in 79 80 81 let subCounts cts = 82 let rec go i = 83 if i = 26 then [[]] 84 else 85 let rest = go (i + 1) in 86 List.concat_map 87 (fun k -> List.map (fun r -> k :: r) rest) 88 (List.init (cts.(i) + 1) Fun.id) 89 in 90 List.map Array.of_list (go 0) 91 in 92 93 let printMatches characters lookup = 94 let subs = subCounts (countsOf characters) in 95 let matches = List.filter_map (fun sub -> Hashtbl.find_opt lookup sub) subs in 96 match matches with 97 | [] -> print_endline "No matching words found" 98 | _ -> List.iter printList matches 99 in 100 101 let dict = Hashtbl.create 10 102 in let () = readFile dict "dictionary.txt" 103 in testMembership "aardvark" dict; testMembership "rasoiena" dict; 104 let lookup = Hashtbl.create 178691 in 105 genLookup lookup dict; 106 let characters = "TAOMFEA" in printMatches characters lookup;