Algorithm for querying linearly through a non-linear list of questions
- by JoshLeaves
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.
Thanks for your help
