Skip to content

Instantly share code, notes, and snippets.

@ivg
Created December 6, 2016 00:14
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save ivg/a5385ffc042a5edf7b05d1ccbe093272 to your computer and use it in GitHub Desktop.
find all possible dictionary words that can be built from a given set of 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