ocaml-programming

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

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;