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

hyphenrf's solution

to Robot Name in the OCaml Track

Published at Jul 20 2020 · 0 comments
Instructions
Test suite
Solution

Manage robot factory settings.

When robots come off the factory floor, they have no name.

The first time you boot them up, a random name is generated in the format of two uppercase letters followed by three digits, such as RX837 or BC811.

Every once in a while we need to reset a robot to its factory settings, which means that their name gets wiped. The next time you ask, it will respond with a new random name.

The names must be random: they should not follow a predictable sequence. Random names means a risk of collisions. Your solution must ensure that every existing robot has a unique name.

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

A debugging session with Paul Blackwell at gSchool. http://gschool.it

test.ml

open Base
open OUnit2
open Robot_name

let assert_matches_spec name =
  let is_valid_letter ch = Char.('A' <= ch && ch <= 'Z') in
  let is_valid_digit ch = Char.('0' <= ch && ch <= '9') in
  assert_equal ~printer:Int.to_string 5 (String.length name);
  assert_bool ("First character must be from A to Z") (is_valid_letter @@ name.[0]);
  assert_bool ("Second character must be from A to Z") (is_valid_letter @@ name.[1]);
  assert_bool ("Third character must be from 0 to 9") (is_valid_digit @@ name.[2]);
  assert_bool ("Fourth character must be from 0 to 9") (is_valid_digit @@ name.[3]);
  assert_bool ("Fifth character must be from 0 to 9") (is_valid_digit @@ name.[4]);;

let basic_tests = [
  "a robot has a name of 2 letters followed by 3 numbers" >:: (fun _ctxt ->
      let n = name (new_robot ()) in
      assert_matches_spec n
    );

  "resetting a robot's name gives it a different name" >:: (fun _ctxt ->
      let r = new_robot () in
      let n1 = name r in
      reset r;
      let n2 = name r in
      assert_bool ("'" ^ n1 ^ "' was repeated") String.(n1 <> n2)
    );

  "after reset the robot's name still matches the specification" >:: (fun _ctxt ->
      let r = new_robot () in
      reset r;
      let n = name r in
      assert_matches_spec n
    );
]

(*
Optionally: make this test pass.

There are 26 * 26 * 10 * 10 * 10 = 676,000 possible Robot names.
This test generates all possible Robot names, and checks that there are
no duplicates. It's harder to make pass than the other tests, so it is left
as optional.

To enable it, uncomment the code in the run_test_tt_main
line at the bottom of this module.
*)
let unique_name_tests = [
  "all possible robot names are distinct" >:: (fun _ctxt ->
      let rs = Array.init (26 * 26 * 1000) ~f:(fun _ -> new_robot ()) in
      let empty = Set.empty (module String) in
      let (repeated, _) = Array.fold rs ~init:(empty, empty) ~f:(fun (repeated, seen) r ->
          let n = name r in
          if Set.mem seen n
          then (Set.add repeated n, seen)
          else (repeated, Set.add seen n)
        ) in
      let first_few_repeats = Array.sub (Set.to_array repeated) ~pos:0 ~len:(min 20 (Set.length repeated)) in
      let failure_message = "first few repeats: " ^ (String.concat_array first_few_repeats ~sep:",") in
      assert_bool failure_message (Set.is_empty repeated)
    );
]

let () =
  run_test_tt_main ("robot-name tests" >::: List.concat [basic_tests (* ; unique_name_tests *)])
(**
 *  This runs as expected and passes all (including optional) tests.
 *  Mutable records are great for encoding state without passing params
 *  everywhere.
 *  Hash_set is running 30-50% faster than Set thanks to the fact that it's a
 *  table not a BST internally. I think it depends on whether or not the set is
 *  allowed to grow (collisions)
 *)
open Base
type robot = { mutable id: string }

let known_ids = Hash_set.create ~size:(26*26*1000) ~growth_allowed:true
                (module String) 

let know = Hash_set.mem known_ids
let forget = Hash_set.remove known_ids
let remember = Hash_set.add known_ids


let rec new_robot () =
    let chr = Char.unsafe_of_int in
    let rand_id = String.init 5 ~f:(fun x ->
        if x < 2 then chr @@ Random.int 26 + 0x41
                 else chr @@ Random.int 10 + 0x30)
    in
    if know rand_id then new_robot()
    else (remember rand_id; 
         {id = rand_id})

let name {id} = id

(* we need to call new before removing old to avoid the 
 * tiny chance of duplication *)
let reset old_robot = let new_robot = new_robot () in
    forget old_robot.id;
    old_robot.id <- new_robot.id

Community comments

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

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?