I'm attempting the following coding challenge in C#:

Manage robot factory settings.

When a robot comes off the factory floor, it has no name.

The first time you turn on a robot, 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 its name gets wiped. The next time you ask, that robot will respond with a new random name.

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

I've created a Robot class which passes 7 of my 8 unit tests. The one failing is:

[Fact]
public void Robot_names_are_unique()
{
    const int robotsCount = 10_000;
    var robots = new List<Robot>(robotsCount); // Needed to keep a reference to the robots as IDs of recycled robots may be re-issued
    var names = new HashSet<string>(robotsCount);
    for (int i = 0; i < robotsCount; i  ) {
        var robot = new Robot();
        robots.Add(robot);
        Assert.True(names.Add(robot.Name));
        Assert.Matches(@"^[A-Z]{2}\d{3}$", robot.Name);
    }
}

I walked through my code and I believe the issue is because I'm generating random values but I'm not ensuring the values are unique when creating many names. Here's my class:

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

public class Robot
{
    Random random = new Random();
    Dictionary<string, bool> usedNames = new Dictionary<string, bool>();
    public Robot()
    {
        Name = RandomName();
    }

    private string _name;

    public string Name
    {
        get { return _name; }
        set { _name = value; }
    }


    public void Reset()
    {
        Name = RandomName();
    }

    private string RandomName()
    {
        Random rand = new Random();
        int nums = random.Next(000, 1000);
        var val = nums.ToString("000");
        const string chars = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
        string letters = new string(Enumerable.Repeat(chars, 2)
            .Select(s => s[random.Next(s.Length)]).ToArray());
        string name = $"{letters}{val}";
        if (usedNames.ContainsKey(name))
        {
// Implement here or refactor with loop?
        }
        return name;
    }
}

However, after reviewing my code, I feel like there is a better approach. I was thinking the approach would involve iterating through the possible numbers and letters in the name sequentially from start to finish to ensure that each name is unique. Am I on the right track? What could I do better?

CodePudding user response：

We have only

26 * 26 * 1000 == 676000

possible names. Let's generate them all and shuffle. Then we can take next robot name from names one after one:

// Yates algorithm will be faster then ordering by random (here I've used Guid)
static string[] Names = Enumerable
  .Range(0, 26 * 26)
  .SelectMany(letters => Enumerable
     .Range(0, 1000)
     .Select(i => $"{(char)('A'   letters / 26)}{(char)('A'   letters % 26)}{i:000}"))
  .OrderBy(item => Guid.NewGuid())
  .ToArray();

static int currentIndex = -1;

// Interlocked: let's implement thread safe method 
static string NextName() => 
  Names[Interlocked.Increment(ref currentIndex) % Names.Length]; 

Demo:

for (int i = 0; i < 10;   i)
  Console.WriteLine(NextName());    

Outcome: (may vary from workstation to workstation)

JQ393
GQ249
JZ370
OC621
GD309
CP822
DK698
AD610
XY300
WV698

Edit: If we want to reuse names (which are dropped when robot is set to factory default settings) we can use Queue instead of array:

static ConcurrentQueue<string> Names = new ConcurrentQueue<string>(Enumerable
  .Range(0, 26 * 26)
  .SelectMany(letters => Enumerable
     .Range(0, 1000)
     .Select(i => $"{(char)('A'   letters / 26)}{(char)('A'   letters % 26)}{i:000}"))
  .OrderBy(item => Guid.NewGuid()));
  
static string NextName() => Names.TryDequeue(out string result) ? result : "???";

static string ScrapName(string name) => Names.Enqueue(name);

static string ResetName(string oldName) {
  string newName = Names.TryDequeue(out string result) 
    ? result 
    : "???";

  if (!string.IsNullOrEmpty(oldName))
    Names.Enqueue(oldName);

  return newName; 
}

CodePudding user response：

There are a lot of possible names. Unless you plan on having almost half a million robots, a good solution would be to create a custom, reusable generator that keeps track of all generated names.

public class UniqueNameGenerator
{
   private readonly HashSet<string> generatedNames;
   private readonly Random generator;

   public UniqueNameGenerator(Random random = null)
   {
      this.generatedNames = new HashSet<string>();
      this.generator = random ?? new Random();
   }

   public string GenerateName()
   {
      string name;

      do
      {
          name = this.TryGenerateName();
      }
      while(this.generatedNames.Contains(name));

      this.generatedNames.Add(name);
      return name;
   }

   private string TryGenerateName()
   {
      var nameBuilder = new StringBuilder();

      nameBuilder.Append(this.PickRandomLetter('A', 'Z'));
      nameBuilder.Append(this.PickRandomLetter('A', 'Z'));
      nameBuilder.Append(this.PickRandomNumber(0, 1000));

      return nameBuilder.ToString();
   }

   private int PickRandomNumber(int min, int max)
   {
      return this.generator.Next(min, max   1);
   }

   private char PickRandomLetter(char from, char to)
   {
      var letterIndex = this.generator.Next((int)from, (int)to);
      return (char)letterIndex;
   }
}

Keep a static instance of this inside the Robot class, or better, create a RobotFactory that creates robots with a single instance of the UniqueNameGenerator.

CodePudding user response：

use random.choice to select 2 random characters and 3 random numbers

import random

def generate_license():
    letters = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
    numbers = "0123456789"
    license = ""
    for i in range(2):
        license  = random.choice(letters)
    for i in range(3):
        license  = random.choice(numbers)
    return license

for i in range(30):
    print(generate_license())

output:

FD508 FI820 TY975 NR415 GD041 IK313 GR103 WR994 PL631 WT808 UV119 KO727 LK584 GM629 BM545 VX728 UN773 AM000 UW267 KE949 KW182 TL030 YW536 AF038 PQ493 TT153 NP626 JK151 WA536 OU825

CodePudding user response：

One option is to create a class to generate the names. That class should keep track of already created names. This method works better if the number of robots is not huge.

public class NameGenerator
{
    static HashSet<string> created = new HashSet<string>();
    static Random rand = new Random();
    const string chars = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
    
    public static string GetName()
    {
        if (created.Count == 676000) {
            // Throw an exception?
        }

        string name;
        do {
            name = $"{chars[rand.Next(chars.Length)]}{chars[rand.Next(chars.Length)]}{rand.Next(0, 1000):D3}";
        } while (!created.Add(name));
        return name;
    }

    public static void Reset() {
        created = new HashSet<string>();
    }
}

Some quick profiling:

Obviously there is a large increase once you approach the 676,000 limit.