🎉 Exercism Research is now launched. Help Exercism, help science and have some fun at research.exercism.io 🎉
Avatar of hyphenrf

hyphenrf's solution

to Anagram in the OCaml Track

Published at May 02 2020 · 1 comment
Instructions
Test suite
Solution

Given a word and a list of possible anagrams, select the correct sublist.

Given "listen" and a list of candidates like "enlists" "google" "inlets" "banana" the program should return a list containing "inlets".

Getting Started

  1. Install the Exercism CLI.

  2. Install OCaml.

  3. For library documentation, follow Useful OCaml resources.

Running Tests

A Makefile is provided with a default target to compile your solution and run the tests. At the command line, type:

make

Submitting Incomplete Solutions

It's possible to submit an incomplete solution so you can see how others have completed the exercise.

Feedback, Issues, Pull Requests

The exercism/ocaml repository on GitHub is the home for all of the Ocaml exercises.

If you have feedback about an exercise, or want to help implementing a new one, head over there and create an issue or submit a PR. We welcome new contributors!

Source

Inspired by the Extreme Startup game https://github.com/rchatley/extreme_startup

test.ml

(* anagram - 1.4.1 *)
open Base
open OUnit2
open Anagram

let ae exp got _test_ctxt =
  let printer = String.concat ~sep:";" in
  assert_equal exp got ~printer

let tests = [
  "no matches" >::
  ae [] (anagrams "diaper" ["hello"; "world"; "zombies"; "pants"]);
  "detects two anagrams" >::
  ae ["stream"; "maters"] (anagrams "master" ["stream"; "pigeon"; "maters"]);
  "does not detect anagram subsets" >::
  ae [] (anagrams "good" ["dog"; "goody"]);
  "detects anagram" >::
  ae ["inlets"] (anagrams "listen" ["enlists"; "google"; "inlets"; "banana"]);
  "detects three anagrams" >::
  ae ["gallery"; "regally"; "largely"] (anagrams "allergy" ["gallery"; "ballerina"; "regally"; "clergy"; "largely"; "leading"]);
  "does not detect non-anagrams with identical checksum" >::
  ae [] (anagrams "mass" ["last"]);
  "detects anagrams case-insensitively" >::
  ae ["Carthorse"] (anagrams "Orchestra" ["cashregister"; "Carthorse"; "radishes"]);
  "detects anagrams using case-insensitive subject" >::
  ae ["carthorse"] (anagrams "Orchestra" ["cashregister"; "carthorse"; "radishes"]);
  "detects anagrams using case-insensitive possible matches" >::
  ae ["Carthorse"] (anagrams "orchestra" ["cashregister"; "Carthorse"; "radishes"]);
  "does not detect an anagram if the original word is repeated" >::
  ae [] (anagrams "go" ["go Go GO"]);
  "anagrams must use all letters exactly once" >::
  ae [] (anagrams "tapper" ["patter"]);
  "words are not anagrams of themselves (case-insensitive)" >::
  ae [] (anagrams "BANANA" ["BANANA"; "Banana"; "banana"]);
]

let () =
  run_test_tt_main ("anagrams tests" >::: tests)
let primes = [|2;3;5;7;11;13;17;19;23;29;31;37;41;43
             ;47;53;59;61;67;71;73;79;83;89;97;101|]

let anagrams needle haystack =
    let chksum_and_lower s =
        let sum = ref 1 in
        let lo = ref [] in
        StringLabels.iter s ~f:(fun c -> 
            begin
            sum := !sum * begin 
            Char.lowercase_ascii c |> Char.code 
            |> (-) 0x7A |> Array.get primes end;
            lo := (Char.lowercase_ascii c)::!lo
            end);
        sum, lo
    in
    let (nsum, nlo) = chksum_and_lower needle in
    let len = String.length in
    ListLabels.filter haystack ~f:(fun s ->
        if len s <> len needle then false else
        match chksum_and_lower s with
            | (_, lo ) when lo  = nlo    -> false
            | (sum, _) when sum = nsum   -> true
            | _ -> false )

Community comments

Find this solution interesting? Ask the author a question to learn more.
Avatar of hyphenrf

I think this is slightly more efficient than the previous solution. It exploits the fact that every number is a unique multiplication of primes or a prime itself. A more efficient (and less fiddly) solution I imagine is a letter frequency map. But primes are cool.

What can you learn from this solution?

A huge amount can be learned from reading other people’s code. This is why we wanted to give exercism users the option of making their solutions public.

Here are some questions to help you reflect on this solution and learn the most from it.

  • What compromises have been made?
  • Are there new concepts here that you could read more about to improve your understanding?