Quiz Maker Algorithm
Tags: javascript, algorithms
Published: 2022-09-25 09:19:01

## 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](https://www.random.org/sequences/). It was able to generate random sequences from 1 to N.  
![random sequence of 1 to 15](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/olz2uqoa6k4w66211z0d.png)

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](https://www.random.org/sequences/) 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.


![advanced mode](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/uedxfzouk6asm03wc0yf.png)

![persistent random sequence](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/xmvzgemfv7dgtrvox4gw.png)

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

![pricing](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/tudd936lfvhspwwwezw4.png)


## 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](https://bost.ocks.org/mike/shuffle/) 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](https://bost.ocks.org/mike/shuffle/).

### 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.

```javascript
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_id`s. 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
```javascript
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:
```javascript
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 `userId`s 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:
```javascript
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
```javascript
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](https://twitter.com/HarishTeens)