Optimizing Bingo Caller Method

Question

I am dong a competitive programming problem I have passed all the tests. but my program times out. I need help optimizing my code so it can run faster.

---

Task:

• Finish method: BingoCaller.GetNumber()
  

• Return all numbers in the range of 1 until 75 once and in random order

• If there are no numbers left, return an empty string

• The numbers are returned one by one in Bingo style:

  "I27", "N40", "B5", "B12", "I28", "O69", "B1", ...

• These are the ranges that you must follow:

  • A number within range 1 to 15 starts with a 'B'

  • A number within range 16 to 30 starts with an 'I'

  • A number within range 31 to 45 starts with an 'N'

  • A number within range 46 to 60 starts with a 'G'

  • A number within range 61 to 75 starts with an 'O'

• Use System.Random to generate your random numbers. Pass via the constructor for testing purposes.

---

My code below

       using System;
       using System.Collections.Generic;

       public class BingoCaller
        {

            private Random random;


            static List<int> List = new List<int>();


            public BingoCaller(Random random)
            {
                this.random = random;

            }

            public string GetNumber()
            {

            Start:

             var item = random.Next(75);


                if (List.Contains(item))
                {
                  goto Start;
                }
                else
                {
                    List.Add(item);

                    if (item >= 61)
                    {
                        return "O" + item;
                    }
                    else if (item >= 46)
                    {
                        return "G" + item;
                    }
                    else if (item >= 31)
                    {
                        return "N" + item;
                    }
                    else if (item >= 16)
                    {
                        return "I" + item;
                    }
                    else
                    {
                        return "B" + item;
                    }

                }


            }
        }

Answer 1

The trick is to use a HashSet<int> for tracking drawn numbers that has a lookup of O(n) and to stop drawing new numbers if all 75 numbers has already been drawn because calls to the Next(..) method are expensive and the execution time unnecessarily increases.

The HashSet's Add method returns true if a value could be added so we can use it with a while loop until we find the next not yet drawn number.

private HashSet<int> _drawn = new HashSet<int>();

private int? NextNumber()
{
    var i = default(int?);
    while (_drawn.Count < 75 && !_drawn.Add((int)(i = random.Next(1, 76))));
    return i;
}

public string GetNumber()
{
    var i = NextNumber();
    if (i.HasValue)
    {
        if (i <= 15) return $"B{i}";
        if (i <= 30) return $"I{i}";
        if (i <= 45) return $"N{i}";
        if (i <= 60) return $"G{i}";
        if (i <= 75) return $"O{i}";
    }
    return string.Empty;
}

This solution passes all 19 tests and executes in about 620ms.

Remember to add using System.Collections.Generic; so that the HashSet<int> work.

---

Unfortuantelly the C# 7 version does not work on Codewars but it looks nice too

public string GetNumber()
{
    switch (NextNumber())
    {            
        case int i when i <= 15: return $"B{i}";
        case int i when i <= 30: return $"I{i}";
        case int i when i <= 45: return $"N{i}";
        case int i when i <= 60: return $"G{i}";
        case int i when i <= 75: return $"O{i}";
        default: return string.Empty;
    }
}

and with one local function we could encapsulate the while condition:

private int? NextNumber()
{
    var i = default(int?);
    bool CanDrawNext() 
    {
        return 
            _drawn.Count < 75 && 
            _drawn.Add((int)(i = random.Next(1, 76))) == false;
    }        
    while (CanDrawNext());
    return i;
}

Answer 2

It is considered bad practice to use goto-statements in modern programming because it quickly gets hard to follow the structure, so avoid that. Instead you could use a while-loop in a kind of this manner:

while (list.Count < 75)
{
  var number = random.Next(75);
  if (list.Contains(number))
    continue;
    ...
}

---

var item = random.Next(75);

This statement sets item to a number in the interval of \$[0, 75[\$, but you were supposed to handle the interval \$[1, 75]\$

---

instead of if (item >= 61) it is more readable to write if (item > 60)

---

It seems that GetNumber() is missing a stop-condition. It will run forever between goto Start and Start: when the list is full. (That may be your "time out"-problem).

---

Instead of the long list of if-statements, you could use the simple relation between the prefix's position in the word "BINGO" and the random number to extract it as:

string bingo = "BINGO"; // Make it a class field.
int index = ...
char prefix = bingo[index]

(it has something to do with 15).

---

The pattern of filling a list with found numbers tends to be slower and slower in response time as the size of the list grows because the next random number is more and more likely to be in the list. Potentially a valid number may never be found...

A better approach could be to create the list of the 75 numbers in the constructor in advance and then remove them one by one from the list when found by random.Next():

...
var number = list[random.Next(0, list.Count)];
list.Remove(number);
...

This will decrease in response time and you avoid the looping.

---

A solution could be:

  public class BingoCaller
  {
    private Random random;
    List<int> list;
    string bingo = "BINGO";

    public BingoCaller(Random random)
    {
      this.random = random;
      list = Enumerable.Range(1, 75).ToList();
    }

    public string GetNumber()
    {
      if (list.Count == 0)
        return "";

      var number = list[random.Next(0, list.Count)];
      list.Remove(number);
      char prefix = bingo[(number - 1) / 15];
      return $"{prefix}{number}";
    }
  }

Answer 3

Searching List and retry until you get an unused number is not efficient
HashSet would be better but still not good as you still retry

Item needs to have a +1 when you return it

I would just shuffle once up front - exactly 74 calls to Random.Next
This is Fisher Yates shuffle - it is proven to be a correct shuffle

public class Bingo
{
    static List<string> bingoBalls = new List<string>(75);
    IEnumerator bingoBallsEnumerator;
    public Bingo (Random Rand)
    {
        CreateBingoBalls();
        ShuffleBingoBalls(bingoBalls, Rand);
        bingoBallsEnumerator = bingoBalls.GetEnumerator();
        //foreach (string s in bingoBalls)
        //    Debug.WriteLine(s);
        //Debug.WriteLine("");
    }
    private void CreateBingoBalls()
    {
        char[] BINGO = "BINGO".ToCharArray();
        for (int i = 1; i <= 75; i++)
        {
            string next = BINGO[(i-1) / 15] + i.ToString();
            //Debug.WriteLine(next);
            bingoBalls.Add(next);
        }
    }
    private void ShuffleBingoBalls(List<string> BingoBalls, Random Rand)
    {
        for(int i = BingoBalls.Count-1; i > 0 ; i--)
        {
            int j = rand.Next(i + 1);
            if(j != i)
            {
                string temp = BingoBalls[i];
                BingoBalls[i] = BingoBalls[j];
                BingoBalls[j] = temp;
            } 
        }       
    }
    public string GetNextBingoBall()
    {
        if (bingoBallsEnumerator.MoveNext())
        {
            return bingoBallsEnumerator.Current.ToString();
        }
        else
        {
            return string.Empty;
        }
    }
}

Surprised me but this is faster

public class Bingo2
{
    private List<int> bingoBalls = Enumerable.Range(1, 75).ToList();
    private Random rand;
    public Bingo2(Random Rand)
    {
        rand = Rand;
    }
    private int ballIndex;
    private int ballCount;
    private char[] BINGO = "BINGO".ToCharArray();
    public string GetNextBingoBall()
    {
        ballCount = bingoBalls.Count;
        if (ballCount == 0)
            return string.Empty;
        if (ballCount == 1)
        {
            ballIndex = bingoBalls[0];
            bingoBalls.Clear();
            return BINGO[(ballIndex - 1) / 15] + ballIndex.ToString();
        }
        ballIndex = bingoBalls[random.Next(ballCount)];
        bingoBalls.Remove(ballIndex);
        return BINGO[(ballIndex - 1) / 15] + ballIndex.ToString();
    }
}

Answer 4

All the answers focus on using Random in the GetNumber() method, which isn't necessary.

We can speed this up by eliminating the random from that method entire.

What's the one, absolute truth about our desired task? The order will never change. We can build the order of our numbers in the constructor, and create an index field instead of all the code being in the GetNumber() method.

We can also make this run in \$O(n)\$ time (right now you have no big-O run-time, your method could be running infinitely).

Code:

class BingoCaller
{
    private int[] _numbers;
    private int _index;
    private const string _letterMap = "BINGO";

    public BingoCaller(Random rand)
    {
        _numbers = Enumerable.Range(1, 75).OrderBy(x => rand.Next()).ToArray();
    }

    public string GetNumber()
    {
        if (_numbers.Length > _index)
        {
            var num = _numbers[_index++];
            return _letterMap[(num - 1) / 15].ToString() + num;
        }
        return string.Empty;
    }
}

My test:

void Main()
{
    var lastNumber = string.Empty;
    var bingoCaller = new BingoCaller(new Random(0));
    var numbers = new List<string>();

    while ((lastNumber = bingoCaller.GetNumber()) != string.Empty)
    {
        Console.WriteLine($"Number: {lastNumber}");
        numbers.Add(lastNumber);
    }

    Console.WriteLine($"Unique numbers: {numbers.GroupBy(x => x).Count()}");
}

Output:

Number: I16
Number: N37
Number: I24
Number: I30
Number: O65
Number: N43
Number: G49
Number: O67
Number: N31
Number: G55
Number: B5
Number: O62
Number: O70
Number: G50
Number: N44
Number: B10
Number: B11
Number: N33
Number: I20
Number: G47
Number: N39
Number: N38
Number: G51
Number: B8
Number: N32
Number: G48
Number: B12
Number: B14
Number: O72
Number: G54
Number: N41
Number: I26
Number: I29
Number: B4
Number: B6
Number: G53
Number: O61
Number: B13
Number: N35
Number: O68
Number: O73
Number: I19
Number: G60
Number: I28
Number: I25
Number: N42
Number: G52
Number: O74
Number: B1
Number: G58
Number: N36
Number: B3
Number: G46
Number: O75
Number: I21
Number: B2
Number: G57
Number: O69
Number: O66
Number: I22
Number: G59
Number: I17
Number: G56
Number: O63
Number: O64
Number: B7
Number: N45
Number: I27
Number: N40
Number: B9
Number: B15
Number: N34
Number: I23
Number: I18
Number: O71
Unique numbers: 75

The 'Unique numbers' line prints 75, which means we had no duplicates.

Now I won't guarantee that this passes their tests. They might be passing a specific Random and expecting a specific order, but this will return a consistent order each and every time.