17
\$\begingroup\$

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

\$\endgroup\$
  • 1
    \$\begingroup\$ Is R2-D2 or C-3PO possible names? \$\endgroup\$ – Simon Forsberg May 4 '16 at 17:19
  • \$\begingroup\$ @SimonForsberg no :) \$\endgroup\$ – CodeYogi May 4 '16 at 17:25
  • 5
    \$\begingroup\$ When a robot is reset, should it return its name to the name pool? \$\endgroup\$ – brian_o May 4 '16 at 21:28
  • \$\begingroup\$ @SimonForsberg, May the 4th be with you. \$\endgroup\$ – Hank D May 4 '16 at 22:06
  • 1
    \$\begingroup\$ The challenge makes no sense. If we already prevent collisions by tracking which names have been used, then there is no need for randomness — a simple counter with a duplicates filter will do. \$\endgroup\$ – 200_success May 5 '16 at 0:29
13
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Why ThreadLocalRandom? also should I check that the length of set reaches 676000? \$\endgroup\$ – CodeYogi May 4 '16 at 17:24
  • 1
    \$\begingroup\$ @CodeYogi The advantage of ThreadLocalRandom is that it instantly solves the problem of not creating new random instances: there is a single one per thread that you access with current(). (see also here). And it has very convenient methods to generate numbers within bounds, unlike Random. Performance-wise for single-threaded applications, it will be the same. \$\endgroup\$ – Tunaki May 4 '16 at 17:50
  • \$\begingroup\$ @CodeYogi For the second part, yes you'll need to check that the maximum size has been reached if you don't want to end in an infinite loop. \$\endgroup\$ – Tunaki May 4 '16 at 19:30
  • 2
    \$\begingroup\$ @Ext3h Random.nextInt(...) is specified like this All bound possible int values are produced with (approximately) equal probability so it really covers the whole range. However, I do agree with the big performance problem when we hit the few last names. \$\endgroup\$ – Tunaki May 4 '16 at 23:07
  • 1
    \$\begingroup\$ @CodeYogi It limits scope to only the for loop) which is a best practice. Declare inside the for loop whenever you can. \$\endgroup\$ – Insane May 5 '16 at 14:51
4
\$\begingroup\$

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);
}
\$\endgroup\$
  • \$\begingroup\$ You sure about matches? The JavaDoc of Matcher.matches (which this method eventually calls) says "Attempts to match the entire region against the pattern." (emphasis mine). It only returns true if the whole input matches the pattern. \$\endgroup\$ – Boris the Spider May 5 '16 at 7:40
  • \$\begingroup\$ Thanks Boris, I thought I tested that yesterday before I posted the answer but I clearly missed it, you're right it does match against the whole string. \$\endgroup\$ – nickb May 5 '16 at 12:27
2
\$\begingroup\$

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:

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.

\$\endgroup\$
  • \$\begingroup\$ Yes, that's an important point about the tests (worth mentioning though is that I think those tests are provided by the site giving the problem so they're not really OP's code). \$\endgroup\$ – Tunaki May 4 '16 at 22:14
  • \$\begingroup\$ @Tunaki Oh! Haha, I didn't realize that. But as you said, I think it's important that OP (as a consumer) is aware of the deficiency, so I'll leave my answer posted. \$\endgroup\$ – brian_o May 4 '16 at 22:22
  • \$\begingroup\$ I'm not sure I agree with this reasoning; If the tests the same seed every time, then it's very possible that you will get false positives (the seed could generate the same name twice, for example) and false negatives (I can't think of any for this example)... the non-determinism in a way is just being factored out of the particular test and into the test definition as changing how many calls to the random generator or their order will also alter the results of the test. I'd prefer that tests log the seed they're operating on so that the case can be reproduced instead of locking the seed. \$\endgroup\$ – meiamsome May 5 '16 at 13:32
  • \$\begingroup\$ @meiamsome I understand what you're saying, but we may have to agree to disagree. If you logged a failing value then adjust your code to compensate, how do you run the same test again? How are you confident that your modifications don't protect against regression in previous cases that worked with the old unmodified code? \$\endgroup\$ – brian_o May 5 '16 at 14:10
  • \$\begingroup\$ Running a bunch of times with new random values each time is a nice way to explore the solution space, but it serves a very different purpose than what most people want their unit tests to do. \$\endgroup\$ – brian_o May 5 '16 at 14:12
2
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ "Negligible" is in the eye of the beholder, but I take your point that storing and shuffling every value is certainly within the realm of possibility. I especially like the suggestion that storage can be compacted using a less-naive approach than simply chucking each name in a (comparatively huge) string. Neat! \$\endgroup\$ – brian_o May 5 '16 at 14:28
  • \$\begingroup\$ I agree that it is possible to store every possibility in this case (I also mentioned it in my answer). On another hand, if tomorrow the robots are named with a few more letters, building the table won't be negligible anymore :). \$\endgroup\$ – Tunaki May 5 '16 at 14:33
  • 1
    \$\begingroup\$ @Tunaki There is already room for two additional letters in the 32-bit integer, even more in 64-bit integers, but the table gets too big in these cases. Even with just one extra letter you are at 68MB and with two additional ones at 1.7 GB. 64 Bit integers have room for 8 letters more resulting in a table nearly one exabyte large, which does not fit in RAM. Yet. Also: the exact meaning of "negligible" is in the eye of the beholder ;-) \$\endgroup\$ – deamentiaemundi May 5 '16 at 16:54
  • \$\begingroup\$ The spec says The names must be random: they should not follow a predictable sequence. \$\endgroup\$ – abuzittin gillifirca May 9 '16 at 8:45
  • \$\begingroup\$ @abuzittingillifirca it is still an unsolved question if there exists perfect randomness but I'm pretty sure that the current cryptographic generators are sufficient for this task. \$\endgroup\$ – deamentiaemundi May 9 '16 at 13:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.