Generating Robot Name

Question

Problem:

Write a program that manages 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, 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 should not allow the use of the same name twice when avoidable. In some exercism language tracks there are tests to ensure that the same name is never used twice.

Code:

import java.util.Random;
import java.util.Set;
import java.util.HashSet;

public class Robot {
  private static final String ALPHABETS = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
  private static final Set<String> generatedNames = new HashSet<>();
  private String name;

  public String getName() {
    while (name == null) {
      name = generateName();
      if (generatedNames.contains(name)) name = null;
    }
    generatedNames.add(name);
    return name; 
  }

  public void reset() {
    name = null;    
  }

  private String generateName() {
    StringBuilder builder = new StringBuilder();
    int i;
    for (i = 0; i < 2; i++) {
      builder.append(ALPHABETS.charAt(generateRandomInRange(0, 25)));
    }
    for (i = 0; i < 3; i++) {
      builder.append(generateRandomInRange(0, 9));
    }
    return builder.toString();
  }

  private int generateRandomInRange(int min, int max) {
    return new Random().nextInt((max - min) + 1) + min;
  }
}

Test Suite:

import org.junit.Test;

import static org.hamcrest.CoreMatchers.equalTo;
import static org.hamcrest.core.Is.is;
import static org.hamcrest.core.IsNot.not;
import static org.junit.Assert.assertThat;
import static org.junit.Assert.assertEquals;

public class RobotTest {

    private static final String EXPECTED_ROBOT_NAME_PATTERN = "[A-Z]{2}\\d{3}";
    private final Robot robot = new Robot();

    @Test
    public void hasName() {
        assertIsValidName(robot.getName());
    }

    @Test
    public void differentRobotsHaveDifferentNames() {
        assertThat(robot.getName(), not(equalTo(new Robot().getName())));
    }

    @Test
    public void resetName() {
        final String name = robot.getName();
        robot.reset();
        final String name2 = robot.getName();
        assertThat(name, not(equalTo(name2)));
        assertIsValidName(name2);
    }

    private static void assertIsValidName(String name) {
        assertThat(name.matches(EXPECTED_ROBOT_NAME_PATTERN), is(true));
    }
}

Question:

Apart my naming and data structure I am interested in knowing if my solution would scale well or not?

Reference: Exercism

Answer 1

Quality of random numbers

You are generating a random integer in a range with the method

private int generateRandomInRange(int min, int max) {
  return new Random().nextInt((max - min) + 1) + min;
}

This method creates a new Random object each time it is called. This is not a good idea. A random number generator should only be instantiated once and be reused throughout the application.

There is a FindBugs warning for exactly that (emphasis mine):

This code creates a java.util.Random object, uses it to generate one random number, and then discards the Random object. This produces mediocre quality random numbers and is inefficient.

What you want instead is to have a single Random object. You could create it as a constant and then reuse it, like this:

private static final Random RANDOM = new Random();

private int generateRandomInRange(int min, int max) {
    return RANDOM.nextInt((max - min) + 1) + min;
}

But, in this case, since you're using it to return a random integer in a range, it would be even simpler to use the built-in ThreadLocalRandom class:

private int generateRandomInRange(int min, int max) {
    return ThreadLocalRandom.current().nextInt(min, max + 1);
}

This will directly return a random integer in the range [min, max].

Pre-allocating the StringBuilder

Small nit-pick, but you're using

StringBuilder builder = new StringBuilder();

to instantiate the StringBuilder. Since we know that the result will have 5 characters, we might as well initialize it with that:

StringBuilder builder = new StringBuilder(5);

It will create in memory an array of 5 characters instead of 16 (which is the default). As commented by Insane, you could extract that 5 (along with the 2 and 3 in the for loop) into a constant (named, for example, ROBOT_NAME_LENGTH).

Variable scope

In your generateName method, you have:

int i;
for (i = 0; i < 2; i++) {
  builder.append(ALPHABETS.charAt(generateRandomInRange(0, 25)));
}
for (i = 0; i < 3; i++) {
  builder.append(generateRandomInRange(0, 9));
}

which first declares i and uses it afterwards. There is no need to do that and it is a lot clearer to just have

for (int i = 0; i < 2; i++) {
  builder.append(ALPHABETS.charAt(generateRandomInRange(0, 25)));
}
for (int i = 0; i < 3; i++) {
  builder.append(generateRandomInRange(0, 9));
}

About the unicity of the names

Currently, you are storing all the generated names inside a Set. This is great because you can then check in constant-time if a given name was already generated. The small hiccup is that you will keep generating names until you find one that hasn't been generated before.

I don't see an easy way to optimize that or do better. The brute-force solution of generating all possible names up-front is possible in this case (since there are "only" 26 * 26 * 10 * 10 * 10 = 676000 possibilites) but not very pretty, and it wouldn't scale well at all.

Your solution is the best with regard to difficulty to write / understand versus the time it takes to generate the name. I tested with by generating a name for all the 676000 possible robots and it did it in a couple of seconds.

However, it leads to a possible bug.

Possible bug

There are only 676000 possible names. This means that if you want to name the robot 676001, your code will loop forever: it will try again and again to generate a name and will never terminate since they have all been generated.

A possible solution is to test whether all the names have been generated: if it is the case, you can simply clear the generated names set (remove all values). The problem description says:

Your solution should not allow the use of the same name twice when avoidable.

In the case when they have all been generated, it is unavoidable, and one solution could be to decide to start again from 0. Another solution could also be to simply return one by one the already generated names (since we know they are unique) and not generate them again.

Oh, and also, generatedNames should be named GENERATED_NAMES since it is declared as static final.

Answer 2

Tunaki did a great job on your main code, I have one additional comment on how to rewrite your getName() method:

public String getName() {
    if(name == null) {
        do {
            name = generateName();
        } while(generatedNames.contains(name));
        generatedNames.add(name);
    }
    return name; 
}

This makes it a little more clear on your stopping intentions - You're done with the loop as soon as the name you generate isn't in the list of generated names. It's also a perfect use-case for a do...while loop. You must do something at least once!

---

I also have a few suggestions for your test code:

Define and reuse a Pattern object

You're defining a regex with EXPECTED_ROBOT_NAME_PATTERN and even named it Pattern, might as well compile it and save a reference to an actual Pattern object. Otherwise, when you call String#matches, it has to compile it every time:

private static final Pattern EXPECTED_ROBOT_NAME_PATTERN = Pattern.compile("[A-Z]{2}\\d{3}");

You then use it by seeing if it matches:

boolean matches = EXPECTED_ROBOT_NAME_PATTERN.matcher(name).matches();

Unnecessary assertThat

Typically you'll use assertThat in a declarative style to make the code more readable, but your current assertion doesn't read well and isn't very clear on what you're testing for. You can simply use assertTrue, which I think is simpler in this case:

private static void assertIsValidName(String name) {
    boolean matches = EXPECTED_ROBOT_NAME_PATTERN.matcher(name).matches();
    assertTrue("name does not match expected pattern", matches);
}

Answer 3

nickb and Tunaki have provided some helpful advice, especially the part about the random number generator (you should only use one).

I think you've done a really great job with your core Robot class, but I have a serious problem with the design of your tests:

• They are non-deterministic (more info here Non-Determinism)

Your test will run differently with different values every time*. This may sound like a good thing, but tests which don't produce the same results every time they are run are not very useful. You could make the tests deterministic by refactoring and setting the seed for the Robot class's [sole] static Random member in the test fixture. Then you'll be able to the test will run the same way every time, and therefore make any failures reproducible.

--

*Try substituting "[A-W]{2}\\d{3}" for "[A-Z]{2}\\d{3}" and running the test suite several times. Sometimes success, sometimes failure. Without modifications, you won't be able to reproduce failures.

Answer 4

Even generating the last few names (before there are absolutely none left) will lead to a major performance problem. But not just that, worst case, even a faulty random number generator can break this miserably, if it doesn't guarantee that every number in the range is even possible to be generated as part of the current sequence. Which, as far as I'm ware of, isn't necessarily the case.

That means, even if you did reset the name pool after exceeding a certain number of unique names, there is no guarantee that the RNG even allows you to hit the upper border, so you might get caught in an endless retry loop much earlier than expect.

Plus, with over half a million elements top, that HashSet is easily going in the range of a few hundred MB of RAM.

---

With regard to the efficiency, the solution for that one is to use a cryptographic function, asymetric or symetric doesn't matter, which can work with a block size of 19 bit, together with a random key.

Using that to map an steadily incrementing counter onto the combinatoric space of all possible names covers about ~78% of the namespace (524.288 out of 676.000 possible names) and yields pseudo-random names at a constant time.

On 19 bit counter overflow, reset the secret to create a new sequence.

---

Sorry, no code samples this time.

Answer 5

It makes me wonder that nobody proposed a simple table to do it.

With 676,000 entries of 32 bits integers we need slightly less than 4 MB. 32 bits are enough because each entry consists of 5 bits for each letter and 10 bits for the number, makes just 20 bits which fit into a 32 bit integer. A 64 bit integer holds three names and wastes only 4 bits but makes the access of the individual names a wee bit more complicated.

In short:

• Build the table and mix it with the help of some cryptographically secure PRNG. The data type of the table can (and should) be a simple integer array.
• Use a counter to keep the index of the last name used such that the new name is in the array at counter
• If all names are used: reset the counter and mix the table again.

Building the table is simple: just count from zero ("AA000") to 676,000 ("ZZ999"), the runtime should be negligible. Getting the actual name out of the entry needs a bit of bit-juggling but it is not very complicated if you use a simple mapping for the letters.

It should be the fastest way to do it, depending on the speed of the PRNG and I think it is the simplest, too. It is not thread-safe, though, manipulating the counter needs locking.