Quiz Maker Algorithm

Problem Statement

Given D days and N users.
Build a quiz maker that picks 5 random questions every day from the question set.
Satisfying the below conditions:

1. the likelihood of two users having the same question on the same day is low.
2. the questions are not repeated for any user.

The question set is of length S, which is atleast (D x 5) to gurantee 2nd condition.

Ofcourse we can make (N x D) number of questions to make this simple, but it is practically impossible to find those many questions. And to store all of them is a poor usage of storage.

Solution

The efficient way to do this is to build an algorithm that generates a list of length (D x 5) having numbers ranging from 1 to S. To locate the questions for today(T), we simply have to get the questions from [Tx5, Tx5 + 5].

For example if D = 3; S = 15; the lists of users could be

[10, 2, 1, 12, 9, 14, 11, 6, 7, 4, 5, 0, 3, 8, 13]

[1, 0, 10, 3, 11, 7, 12, 2, 9, 6, 4, 13, 8, 14, 5]

[11, 13, 14, 1, 4, 12, 9, 0, 2, 3, 8, 5, 10, 6, 7]

Exploring available solutions

Generating a random list

Let us begin to explore how we could generate this random list. I did some googling and found this useful website random.org. It was able to generate random sequences from 1 to N.

Problem Solved! Right? Not so soon, haha

If we generate a random sequence for every user, we would have to store it somewhere on a database. Now there are two concerns with this approach:

1. Cost of storing a (D x 5) array for N users. For larger N, this might cost a lot.
2. This is the biggest, if there were to be a leak in the API security and somebody was able to retrieve their list of questions for all days. Then they would know all the questions they are going to receive beforehand.

Hence need to take a different approach.

Deterministic Pseudorandom list

To solve the above 2 problems, I decided not store the array anywhere in Database. Every day when a user requests for their question I shall generate the array in runtime and pick the questions for the day. But for it to work, I would have to generate a deterministic list of numbers for each user. Or else I would be generating random list of numbers every day for the same user. Fortunately random.org had that option as well.

On Advanced Mode, you can seed the randomiser with an input string. So for every unique string, it gives a unique random sequence. It flashed that I could simply pass the user_id and get their respective sequences.

Although their pricing plan was very generous, the fact that it could be done motivated me to build something of my own.

Walkthrough of my solution

Fisher Yates Shuffle algorithm

After digging for a while, I found about Fisher Yates Shuffle algorithm on a stack overflow post. The algorithm is brilliantly crafted. Here is a link that contains beautiful visual explanation of Fisher Yates Shuffle. It is a prerequisite to go through it before you move ahead with this article. I've extended Fisher Yates and customised it according to my needs.

I'll brief what the algorithm is, if in case you haven't checked the website. Fisher Yates Shuffle is an in-place shuffling algorithm that runs in O(n). The idea of it is to pick a random index and swap the element on the random index with the first index. If you repeat this N times decrementing your random range. At the end of it, you would have a shuffled array.

Would highly recommend going through the link.

Extending Fisher Yates to give deterministic sequence

Now that I knew about this. All I needed to do was, generate a list from 1 to S and run Fisher Yates on it. Then I would have my expected list.

function shuffle(array) {
  var currentIndex = array.length, i;

  // While there remain elements to shuffle…
  while (currentIndex != 0) {

    // Pick a remaining element…
    i = Math.floor(Math.random() * currentIndex--);

    // And swap it with the current element.
    [array[currentIndex], array[randomIndex]] = [
    array[randomIndex], array[currentIndex]];
  }

  return array;
}
const arr = Array.from(Array(15).keys())
shuffle(arr)

But if you look closely, this is still shuffling randomly. Now we need to make it pseudorandom using the user_ids. The userId after removing hyphens given by AWS Cognito were of length 32. So I had to figure out a way to use these string bytes for randomizing. Here is my way of doing it:

Step 1
Repeat the string until it is of S length

const multiplier = Math.ceil(array.length / str.length);
for (let i = 0; i < multiplier; ++i)
  clonedStr = clonedStr + newStr;

Step 2
Now we can use this clonedStr byte values to pick random Indices. Here is how the modified while loop would like:

while (currentIndex != 0) {
    rndSeed = rndSeed + clonedStr.charCodeAt(currentIndex);

    // Pick a remaining element.
    randomIndex = rndSeed % array.length;
    currentIndex--;

    // And swap it with the current element.
    [array[currentIndex], array[randomIndex]] = [
    array[randomIndex], array[currentIndex]];
}

I basically pick the ASCII code of the character and mod it with the length of the array to get a pseudo randomIndex. Since the userIds are fixed, this loop always shuffles the array in a deterministic manner.

Step 3
To add additional security, I used a custom Salt value. So even if my algorithm and userId is exposed. Im relying on the secretly stored environment variable for securing the salt. Here is how I implemented salt:

const secretSalt = process.env.SECRET_SALT;
let newStr = "";
for (let i = 0; i < str.length; i = i+1 )
    newStr = newStr + String.fromCharCode((str.charCodeAt(i) + secretSalt) % 256)

I stuff each byte with my salt so the attacker needs to also get my salt to know his sequence. It might not stop them entirely, but definitely will slow them down significantly.

The final version

import moment from 'moment';

const TOTAL_NUMBER_OF_QUESTIONS = 150;
const QUIZ_START_DATE = moment("20220919", "YYYYMMDD");

function shuffle(array: number[], str: string) {
    let currentIndex = array.length, randomIndex: number;
    const multiplier = Math.ceil(array.length / str.length);

    const secretSalt = process.env.SECRET_SALT;
    let newStr = "";
    for (let i = 0; i < str.length; i = i+1 ) newStr = newStr + String.fromCharCode((str.charCodeAt(i) + secretSalt) % 256)
    let clonedStr = "";
    for (let i = 0; i < multiplier; ++i) clonedStr = clonedStr + newStr;

    let rndSeed = 0;

    // While there remain elements to shuffle.
    while (currentIndex != 0) {
        rndSeed = rndSeed + clonedStr.charCodeAt(currentIndex);

        // Pick a remaining element.
        randomIndex = rndSeed % array.length;
        currentIndex--;

        // And swap it with the current element.
        [array[currentIndex], array[randomIndex]] = [
        array[randomIndex], array[currentIndex]];
    }

    return array;
}

function getTodaysQuestions(userId: string) {
    const questionsArray = Array.from(Array(TOTAL_NUMBER_OF_QUESTIONS).keys())
    const seedString = userId.split("-").join("");
    shuffle(questionsArray, seedString);
    const today = moment()
    const diff = today.diff(QUIZ_START_DATE, 'days');

    return questionsArray.slice(diff * 5, (diff + 1) * 5);
}
getTodaysQuestions("noob-master-69")

Conclusion

Thanks for reading. Hope it was useful to you in some way. Please feel free to reach out to me if you want to share improvements or feedbacks. Always happy to know.
Reach out to me via Twitter