# Algorithm for querying linearly through a non-linear list of questions

For a multiplayers trivia game, I need to supply my users with a new quizz in a desired subject (Science, Maths, Litt. and such) at the start of every game.

I've generated about 5K quizzes for each subject and filled my database with them. So my 'Quizzes' database looks like this:

``````|ID   |Subject     |Question
+-----+------------+----------------------------------
|  23 |Science     | What's water?
|  42 |Maths       | What's 2+2?
|  99 |Litt.       | Who wrote "Pride and Prejudice"?
| 123 |Litt.       | Who wrote "On The Road"?
| 146 |Maths       | What's 2*2?
| 599 |Science     | You know what's cool?
|1042 |Maths       | What's the Fibonacci Sequence?
|1056 |Maths       | What's 42?
And so on... (Much more detailed/complex but I'll keep the exemple simple)
``````

As you can see, due to technical constraints (MongoDB), my IDs are not linear but I can use them as an increasing suite.

So far, my algorithm to ensure two users get a new quizz when they play together is the following:

``````// Take the last played quizzes by P1 and P2
var q_one = player_one.getLastPlayedQuizz('Maths');
var q_two = player_two.getLastPlayedQuizz('Maths');

// If both of them never played in the subject, return first quizz in the list
if ((q_one == NULL) && (q_two == NULL))
return QuizzDB.findOne({subject: 'Maths'});

// If one of them never played, play the next quizz for the other player
// This quizz is found by asking for the first quizz in the desired subject where
// the ID is greater than the last played quizz's ID (if the last played quizz ID
// is 42, this will return 146 following the above example database)
if (q_one == NULL)
return QuizzDB.findOne({subject: 'Maths', ID > q_two});
if (q_two == NULL)
return QuizzDB.findOne({subject: 'Maths', ID > q_one});

// And if both of them have a lastPlayedQuizz, we return the next quizz for the
// player whose lastPlayedQuizz got the higher ID
if (q_one > q_two)
return QuizzDB.findOne({subject: 'Maths', ID > q_one});
else
return QuizzDB.findOne({subject: 'Maths', ID > q_two});
``````

Now here comes the real problem:

Once I get to the end of my database (let's say, P1's last played quizz in 'Maths' is 1056, P2's is 146 and P3 is 1042), following my algorithm, P1's ID is the highest so I ask for the next question in 'Maths' where ID is superior to 1056. There is nothing, so I roll back to the beginning of my quizz list (with a random skipper to avoid having the first question always show up). P1 and P2's last played will then be 42 and they will start fresh from the beginning of the list. However, if P1 (42) plays against P3 (1042), the resulting ID will be 1056...which P1 already played two games ago.

Basically, players who just "rolled back" to the beginning of the list will be brought back to the end of the list by players who still haven't rolled back. The rollback WILL happen in the end, but it'll take time and there'll be a "bottleneck" at the beginning and at the end.

Thus my question: What would be the best algorith to avoid this bottleneck and ensure players don't get stuck endlessly on the same quizzes?

Also bear in mind that I've got some technical constraints:

• I can't get a random question in a subject (ie: no "QuizzDB.findOne({subject: 'Maths'}).skip(random());"). It's cool to skip on one to twenty records, but the MongoDB documentation warns against skipping too many documents.
• I would like to avoid building an array of every quizz played by each player and find the next non-played in the database with a \$nin.

-
Have a look at map/reduce, it allows you to execute js code on the server. You could either use random numbers to add a random value to your question, then sort by that value to get a random question. Or you could simply add a sequential ID so you can pick a random number client side. You should consider storing which questions the player answered "last", besides the problem you highlighted you would also have a repeatable sequence which would make the game less fun. You could just keep track of the last X questions instead of resetting after all questions have been used. – Daniel Carlsson Sep 1 '12 at 17:32
mongodb.org/display/DOCS/MapReduce - for the documentation of this functionality – Daniel Carlsson Sep 1 '12 at 17:33

I see a lot of entropy here; i will try to clear the air:

• Programs = Data structures + Algorithms
• You can write the best linear algorithm in the world but if your data structure it's not linear, you can think about that forever without solving the issue
• Since you have to think about the data structures first, at least in this scenario, you are picking the worst possible storing solution, I do not know about this MongoDB but after a brief search turns out that is nothing more than a text file and a text file it's a non linear storage solution, for 5K questions is the horror
• A linear data structure will mantain the time/performance required to access the information linear, that basically means the same, no matter how the data structure grows in time if it's big or small, for this reason you should use something like an SQL based database, there is SQLite that is a public domain project and you also do not have to worry about any license at all, completely free and you can do what you want to do with it.
• If you are using an SQL based approach you will get benefits using a different database table for each topic and you can also simplify or template your code doing this, so you can even abstract the topic itself and you do not have to write code for each possible topic.
• With SQLite you also get a series of basic functions for your query, one that can mimic a random access it's included

I hope that things are more clear now.

-