2
\$\begingroup\$

Below is a simple typescript class used to generate a room code for an online lobby-based game (for example, https://jackbox.tv/ uses 4 digit codes to join rooms)

The goal of the class is to quickly generate unique 4-letter codes for game lobbies, and release them after the lobby is closed. Typically, less than 100 lobby codes will be used at once so using up all 26^4 codes will likely never happen.

Concerns:

  • Is the method for generating codes efficient? Currently it just picks a random code and keeps incrementing until an unused code is found
  • Is the method for encoding a number to an alphabet efficient? (converting a number to base 26)
const ALPHABET = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";

function randInt(min: number, max: number) {
  return Math.floor(Math.random() * (max - min)) + min;
}

export class RoomCodeManager {
  codeLength: number;
  usedCodes: Set<string>;
  // Generate 4-letter codes by default
  constructor(codeLength = 4) {
    this.codeLength = codeLength;
    this.usedCodes = new Set();
  }
  generateCode() {
    const min = 0;
    const max = Math.pow(ALPHABET.length, this.codeLength);
    let code = randInt(min, max);

    // If every code is already in use, just return a random code
    if (this.usedCodes.size >= max) {
      return this.encodeAlphabet(code);
    }

    // Keep incrementing by 1 until an unused code is found
    while (this.usedCodes.has(this.encodeAlphabet(code))) {
      code = (code + 1) % max;
    }
    this.usedCodes.add(this.encodeAlphabet(code));
    return this.encodeAlphabet(code);
  }
  encodeAlphabet(num: number) {
    let str = "";
    const len = ALPHABET.length;
    while (num > 0) {
      let radix = num % len;
      str = ALPHABET[radix] + str;
      num = Math.floor(num / len);
    }
    return str.padStart(this.codeLength, ALPHABET[0]);
  }
  releaseCode(code: string) {
    this.usedCodes.delete(code);
  }
}
\$\endgroup\$
1
\$\begingroup\$

One important consideration: should those who do not have the code for a room be able to guess it (or guess a random code) and enter a room they were never told the code for? If not, then 4 characters probably isn't quite enough:

  • If guesses and codes were random, the chance of guessing a lobby is on the order of magnitude of 100/450_000. Chances are low, but they're not astronomically low. To make it better, increase the number of characters in a code.
  • But long random character strings are difficult to remember. If you think that might be a problem for the UI, consider using random words instead - for example, have a dictionary of a large number of English words, and then to generate a code, put two or three of them together.

Is the method for generating codes efficient? Currently it just picks a random code and keeps incrementing until an unused code is found

If you really expect there to be less than 100 codes in use at a given time, then the chances of a collision are extremely low, so simply re-picking a random number in such rare cases sounds perfectly fine to me. If the app became more popular and collisions started happening on a regular basis, then it might be time to consider a different approach (such as hashing incremental numbers, or increasing the number of characters, or using a different algorithm entirely).

Is the method for encoding a number to an alphabet efficient? (converting a number to base 26)

When turning a number into a string, I'd prefer to use toString if possible. For example, if you're able to use numbers 0-9 in addition to letters, you could make encodeAlphabet much simpler and use:

  encodeAlphabet(num) {
    return num.toString(36);
  }

(though, for such an approach to be user-friendly, you might also want to remove all characters that might get confused with each other, like O and 0)

Another approach to consider - rather than generating a number and then turning it into a string, how about generating random characters and putting those into a string instead? No need to work with modulo and radix:

generateCode() {
  let code;
  do {
    code = this.getRandomCode();
  } while (this.usedCodes.has(code));
  this.usedCodes.add(code);
  return code;
}
getRandomCode() {
  return Array.from(
    { length: this.codeLength },
    () => String.fromCharCode(Math.floor(Math.random() * 26) + 65)
  ).join('');
}

const ALPHABET = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";

function randInt(min, max) {
  return Math.floor(Math.random() * (max - min)) + min;
}

class RoomCodeManager {
  // Generate 4-letter codes by default
  constructor(codeLength = 4) {
    this.codeLength = codeLength;
    this.usedCodes = new Set();
  }
  generateCode() {
    let code;
    do {
      code = this.getRandomCode();
    } while (this.usedCodes.has(code));
    this.usedCodes.add(code);
    return code;
  }
  getRandomCode() {
    return Array.from(
      { length: this.codeLength },
      () => String.fromCharCode(Math.floor(Math.random() * 26) + 65)
    ).join('');
  }
  releaseCode(code) {
    this.usedCodes.delete(code);
  }
}

const roomCodeManager = new RoomCodeManager();
console.log(roomCodeManager.generateCode());

Regarding

// If every code is already in use, just return a random code
if (this.usedCodes.size >= max) {
  return this.encodeAlphabet(code);
}

Maybe, in such a case, increment this.codeLength instead of returning a duplicate? (Though, this'll probably never happen)

\$\endgroup\$
0
\$\begingroup\$

I believe this is over-engineered in some ways. If all you need is a random 4-character code, the following should suffice:

const generateCode = length => {
  return Array(length).fill('x').join('').replace(/x/g, () => {
    return String.fromCharCode(Math.floor(Math.random() * 26) + 65)
  })
}

console.log(generateCode(4))

JS has a function String.fromCharCode() that turns decimals into the equivalent character. You can look up an ascii table and see that A-Z is 65-90. No need to hardcode a string of letters.

Math.floor(Math.random() * 26) + 65

This piece generates a random digit from 65-90. What it does is take Math.random() (0-1, 1 not included), multiplies it by 26 (gives you 0-26, 26 not included), then offsets by 65 (gives 65-91, 91 not included).

You can keep calling the function until you find a unique random sequence. string.replace() can take a function that allows you to dynamically define a replacement. In our case, a random character form A-Z. The fill-join part is just a way to create a variable-length placeholder string, nothing special there.

\$\endgroup\$
3
  • \$\begingroup\$ You can keep calling the function until you find a unique random sequence The purpose of the class was to encapsulate this process, the set keeps track of codes in use so that collisions don't occur \$\endgroup\$
    – thesilican
    Nov 5 '20 at 15:55
  • \$\begingroup\$ But your process of generating random codes is much more concise and doesn't depend on hard-coded variables which I like, thanks \$\endgroup\$
    – thesilican
    Nov 5 '20 at 15:57
  • \$\begingroup\$ @thesilican Yup, you'd call this inside your class. Your class will track collisions. Just so happened that I copy-pasted the generateCode name to my example snippet and made it confusing. :D \$\endgroup\$
    – Joseph
    Nov 5 '20 at 16:07

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.