Created
December 6, 2016 00:14
Star
You must be signed in to star a gist
find all possible dictionary words that can be built from a given set of characters
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
(* | |
1. install opam | |
2. install core_kernel library: `opam install core_kernel` | |
3. build with `ocamlbuild -pkg core_kernel scabble.native` | |
4. run as `./scrabble.native /usr/share/dict/american-english` | |
*) | |
open Core_kernel.Std | |
open Format | |
type t = { | |
dict : t Int.Map.t; | |
data : string list; | |
} | |
let spectrum word = | |
let index c = Char.(to_int (uppercase c) - to_int 'A') in | |
let letters = Char.(to_int 'Z' - to_int 'A' + 1) in | |
Array.init letters ~f:(fun i -> | |
String.count word ~f:(fun c -> index c = i)) | |
let empty = {dict = Int.Map.empty; data=[]} | |
let add_word dict word = | |
let count = spectrum word in | |
let rec add {dict; data} i = | |
if i < Array.length count then { | |
data; | |
dict = Map.update dict count.(i) ~f:(function | |
| None -> add empty (i+1) | |
| Some sub -> add sub (i+1)) | |
} else {empty with data = word :: data} in | |
add dict 0 | |
let is_buildable dict word = | |
let count = spectrum word in | |
let rec find {dict} i = | |
i >= Array.length count || | |
Sequence.range 0 count.(i) ~stop:`inclusive |> | |
Sequence.exists ~f:(fun cnt -> match Map.find dict cnt with | |
| None -> false | |
| Some dict -> find dict (i+1)) in | |
find dict 0 | |
let build dict word = | |
let count = spectrum word in | |
let rec find {dict; data} i = | |
if i < Array.length count then | |
Sequence.range 0 count.(i) ~stop:`inclusive |> | |
Sequence.concat_map ~f:(fun cnt -> match Map.find dict cnt with | |
| None -> Sequence.empty | |
| Some dict -> find dict (i+1)) | |
else Sequence.of_list data in | |
find dict 0 | |
module Test = struct | |
let run () = | |
let dict = | |
In_channel.(with_file Sys.argv.(1) | |
~f:(fold_lines ~init:empty ~f:add_word)) in | |
let prompt () = | |
printf "Enter characters and hit enter (or Ctrl-D to stop): %!" in | |
prompt (); | |
In_channel.iter_lines stdin ~f:(fun set -> | |
build dict set |> Sequence.iter ~f:print_endline; | |
prompt ()) | |
end | |
let () = Test.run () |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment