3
\$\begingroup\$

Robot Name

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.

That was the instructions given to me. The only constraints is the tests. From my previous post I'm trying to improve on my naming conventions, DRY code, access modifiers, and keeping it readable. Any advice would help me a lot since I'm learning C# and teaching myself. Thank you for your help especially to those that follow my progress and help me.

using System;
using System.Collections.Generic;
using System.Linq;

public class Robot
{
    private static Random _random;
    private string _name;
    private static readonly HashSet<string> _nameList = new HashSet<string>();
    public string Name => _name;

    public Robot()
    {
        _random = new Random();
        _name = GenerateRandomName();
    }

    public void Reset()
    {
        _nameList.Remove(_name);
        _name = GenerateRandomName();
    }

    private static string GenerateRandomLetters() => new string(Enumerable.Repeat("ABCDEFGHIJKLMNOPQRSTUVWXYZ", 2)
      .Select(s => s[_random.Next(s.Length)]).ToArray());

    private static string GenerateRandomName()
    {
        string name;

        do
        {
            name = $"{GenerateRandomLetters()}{_random.Next(10)}{_random.Next(10)}{_random.Next(10)}";
        }
        while (_nameList.Contains(name));

        _nameList.Add(name);
        return name;
    }
}
using System.Collections.Generic;
using Xunit;

public class RobotNameTests
{
    private readonly Robot robot = new Robot();

    [Fact]
    public void Robot_has_a_name() => Assert.Matches(@"^[A-Z]{2}\d{3}$", robot.Name);

    [Fact]
    public void Name_is_the_same_each_time() => Assert.Equal(robot.Name, robot.Name);

    [Fact]
    public void Different_robots_have_different_names() => Assert.NotEqual(new Robot().Name, robot.Name);

    [Fact]
    public void Can_reset_the_name()
    {
        var originalName = robot.Name;
        robot.Reset();
        Assert.NotEqual(originalName, robot.Name);
    }

    [Fact]
    public void After_reset_the_name_is_valid()
    {
        robot.Reset();
        Assert.Matches(@"^[A-Z]{2}\d{3}$", robot.Name);
    }

    [Fact]
    public void Robot_names_are_unique()
    {
        var names = new HashSet<string>();
        for (int i = 0; i < 10_000; i++) {
            var robot = new Robot();
            Assert.True(names.Add(robot.Name));
        }
    }
}

The test are immutable. They cannot be altered at all. I did not write these test. I have to work within the test. I would be interested in learning on how to improve on them out of curiosity at best.

\$\endgroup\$
4
  • \$\begingroup\$ Do not call things something like _nameList, call it what would call it in real life: _names (or rather _possibleNames). Case in point: your _nameList isn't even a List, it's a Hashset, and thus the name does not correspond with its actual type. \$\endgroup\$ – BCdotWEB Apr 30 '20 at 7:00
  • \$\begingroup\$ @BCdotWEB what about _robotNames or _robotNamesInUse? \$\endgroup\$ – Milliorn Apr 30 '20 at 20:01
  • \$\begingroup\$ Write a test to generate 676000 robots, it Will take incredibly long. Write a test to create 676001 robots And your program Will get stuck in an Infinite loop. Assuming alphabet with 26 letters... \$\endgroup\$ – slepic May 1 '20 at 5:45
  • \$\begingroup\$ Bonus question, if you choose 10000 items from 676000 possibilities, what Is the probability that two chosen elements are the same? In other words, what Is the reliability of the Robot_names_are_unique test? Well, it Is less than 100% And it would be less than 100% for any number of robots smaller then all of them plus 1. So only reliable test is to check that you can create 676000 robots and creating another one must fail. \$\endgroup\$ – slepic May 1 '20 at 6:16
4
\$\begingroup\$

We can create 676000 robots with unique names, because we have 26 possibilities for each 'letter position' and 10 possibilities for 'number position' in our name. So calculation is 26 * 26 * 10 * 10 * 10 = 676000.

Why am I mentioning that? Because that number is not so big and maybe it's worth to consider pregenerating all possible values, keep them in pool and get/return when necessary. That's another approach. I don't want to say that it's better. It will be more memory consuming solution, but robot 'initialization' will be faster. Also it'll be easier to apply fix for point 6. Anyway, you should always get what suits your requirements.

End of digression - back to your code!

  1. Why I can't see namespaces both in tests and in class? You copied it that way?
  2. I understand why you set up Random as static, but it's not thread safe the way you implemented it. Reference: [JON SKEET ARTICLE]
  3. Static readonly HashSet is very dangerous, because it's instance is shared between all threads and Hashset.Remove method could cause strange problems/exceptions in multithreaded environment. Of course no one is saying that in requirements, but I think that case should never be ignored. ConcurrentDictionary should be your choice in here, because it ensures thread safety. [MSDN]
  4. Letters in alphabet will never change, so you can keep it as a const field. Thanks to that you'll avoid allocation string for each time somebody tries to generate random letters.
  5. In case for readability I have nothing to add it's pretty clear what's happening here.
  6. Last, but most important, comment from my side. A little challenge for you :) what will happen with your code when you create 676000 robots and try to create one more? Hint: you can use code from Robot_names_are_unique() test method, but increase upper limit of iterations to 676000.

Hope this helps!

\$\endgroup\$
6
  • \$\begingroup\$ 1. That was how it was provided. I didn't think of adding a namespace to it either. I added it to my code. 2. I set it up that way to get it to work as in I had trouble getting it to work on the final test. It would fail without it. I will use @Henrik suggestion to address that. I have yet to get into topics about thread safety so I am unaware of these issues. 3. Is it because its a HashSet, the access modifiers, or both that makes this dangerous? \$\endgroup\$ – Milliorn Apr 30 '20 at 20:13
  • \$\begingroup\$ Oh i wrote about the limit of number of robots into comments on OP question. Now I see you already pointed this out. You were on the very bottom, Gotta bump you up :) \$\endgroup\$ – slepic May 1 '20 at 5:54
  • \$\begingroup\$ if (_robotNamesInUse.Count > _maxRobotNamesInUse) throw new IndexOutOfRangeException("Cannot create more robot names. List is full."); \$\endgroup\$ – Milliorn May 1 '20 at 18:37
  • \$\begingroup\$ Would this and what I posted above work for this case? private const int _maxRobotNamesInUse = 676000; @slepic @Karol \$\endgroup\$ – Milliorn May 1 '20 at 18:37
  • \$\begingroup\$ Basically yes. That rules out the possible Infinite loop. But there Is still the problem that the more robots you create the more likely it Is that you get duplicates during name generation. Lets take the worst case that you Are creating the last possible robot. You have Chance 1:676000 that you randomly choose the last unused name. That's 676000 random names to generate before you find the unused one, on average. Your algorithm Is basically O(r!) where r Is number of existing robots. \$\endgroup\$ – slepic May 1 '20 at 19:19
4
\$\begingroup\$

Again, your code seems well written and easy to follow and understand. Except for the name _nameList (as mentioned in the comment by BCdotWEB) your naming seems ok.

Below, find my comments inline (// HH: ...) and my refactoring attempt:

// HH: You need a mechanism to remove the name from the name list when the Robot dies (= is garbage collected). Implementing IDisposable could be the way to go.
public class Robot
{
  private static Random _random;
  private string _name; // HH: Use auto property for Name { get; private set; }
  private static readonly HashSet<string> _nameList = new HashSet<string>();
  public string Name => _name; // HH: Use auto property for Name { get; private set; }

  public Robot()
  {
    _random = new Random(); // HH: Instantiate this once when declaring it above. It gives no meaning to recreate a static member for each new instance of the object
    _name = GenerateRandomName();
  }

  public void Reset()
  {
    _nameList.Remove(_name); // HH: this needs to be done after GenerateRandomName() or else you could potentially create and use the same name again.
    _name = GenerateRandomName();
  }

  // HH: See my suggestion for an more readable approach. If you have to break the code into more lines, then IMO block style is more appropriate
  private static string GenerateRandomLetters() => new string(Enumerable.Repeat("ABCDEFGHIJKLMNOPQRSTUVWXYZ", 2)
    .Select(s => s[_random.Next(s.Length)]).ToArray());

  private static string GenerateRandomName()
  {
    string name;

    do
    {
      name = $"{GenerateRandomLetters()}{_random.Next(10)}{_random.Next(10)}{_random.Next(10)}";
    }
    while (_nameList.Contains(name)); // HH: You could just check: _nameList.Add(name) which will return false, if the name is already present in the set

    _nameList.Add(name);
    return name;
  }
}

My version:

  public class Robot : IDisposable
  {
    private static readonly Random _random = new Random();
    const string _nameChars = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
    private static readonly HashSet<string> _namesInUse = new HashSet<string>();
    public string Name { get; private set; }

    public Robot()
    {
      Name = GenerateRandomName();
    }

    public void Reset()
    {
      Name = GenerateRandomName();
      _namesInUse.Remove(Name);
    }

    private static string GenerateRandomLetters()
    {
      return $"{_nameChars[_random.Next(_nameChars.Length)]}{_nameChars[_random.Next(_nameChars.Length)]}";
    }

    private static string GenerateRandomName()
    {
      string name;

      do
      {
        name = $"{GenerateRandomLetters()}{_random.Next(1000):000}";
      } while (!_namesInUse.Add(name));

      return name;
    }

    public void Dispose()
    {
      if (Name != null)
      {
        _namesInUse.Remove(Name);
        Name = null;
      }
    }
  }
\$\endgroup\$
9
  • \$\begingroup\$ Your code indeed fixes points 2 and 4 from my answer, but still thread safety and point 6 seems unresolved. \$\endgroup\$ – Karol Miszczyk Apr 30 '20 at 14:55
  • 1
    \$\begingroup\$ @KarolMiszczyk: I think thread safety is beyond the beginners level. I find your suggestion about generating all the names beforehand as a bad approach. And about name "overflow": If there was a risk of that, the name was probably designed a bit longer than it is. Anyway my answer is an answer to the question not to your answer. :-) \$\endgroup\$ – user73941 Apr 30 '20 at 18:13
  • \$\begingroup\$ @HenrikHansen I changed _nameList to _robotNamesInUse. I've gotten out of the habit of making comments. I need to get in the habit again of doing that in case people are unclear of my intent. Is there a reason why you did Name = GenerateRandomName(); _namesInUse.Remove(Name); and not _robotNamesInUse.Remove(Name); Name = GenerateRandomName(); Basically the order of which one is called is switched. \$\endgroup\$ – Milliorn Apr 30 '20 at 20:18
  • 1
    \$\begingroup\$ @HenrikHansen disregard what I asked about why you swapped those calls. I just realize you notated that when you said _nameList.Remove(_name); // HH: this needs to be done after GenerateRandomName() or else you could potentially create and use the same name again. \$\endgroup\$ – Milliorn Apr 30 '20 at 20:27
  • 1
    \$\begingroup\$ @HenrikHansen it's starting to make sense now. 000-999. \$\endgroup\$ – Milliorn Apr 30 '20 at 23:18
3
\$\begingroup\$

To me, one of the things worth considering is that a Robot object would be more involved than having just a name. To that end it would make sense to have a name generator(RobotNameGenerator) to encapsulate the fields and methods relating to generating the name.

For the actual name generating algorithm, a readonly string for the letters and some LINQ extensions, will reduce it to one line:

String.Join("", Enumerable.Range(0, 2)
                          .Select(x => letters[rnd.Next(26)])
                          .Concat(Enumerable.Range(0, 3)
                                            .Select(x => (char)(rnd.Next(10) + '0'))))

Such a generator when put together could look something like this:

private class RobotNameGenerator
{
    private static readonly string letters = "ABCDEFGHIJKLMNOPQRST";
    private static readonly Random rnd = new Random();
    private static readonly HashSet<string> usedNames = new HashSet<string>();
    public static string GetUniqueName(string nameToReplace = "")
    {
        string name = "";
        do
        {
             name = String.Join("", Enumerable.Range(0, 2)
                                              .Select(x => letters[rnd.Next(26)])
                                              .Concat(Enumerable.Range(0, 3)
                                                                .Select(x => (char)(rnd.Next(10) + '0'))));
        } while (usedNames.Contains(name));
        usedNames.Add(name);
        if (nameToReplace != "")
        {
            CancelUsedName(nameToReplace);
        }
        return name;
    }
    static void CancelUsedName(string name)
    {
        usedNames.Remove(name);
    }
}

After some more thought, I came upon an optimization:

name = String.Join("", Enumerable.Range(0, 5)
       .Select(x => x < 2 ? letters[rnd.Next(letters.Length)] : (char)(rnd.Next(10) + '0')));
\$\endgroup\$
1
  • \$\begingroup\$ That is another interesting perspective using LINQ to set name. \$\endgroup\$ – Milliorn Apr 30 '20 at 23:28

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.