A team has decided that every morning someone should bring croissants for everybody. It shouldn't be the same person every time, so there should be a system to determine whose turn it is next. The purpose of this question is to determine an algorithm for deciding whose turn it will be to bring croissants tomorrow.
Constraints, assumptions and objectives:
- Whose turn it is to bring croissants will be determined the previous afternoon.
- On any given day, some people are absent. The algorithm must pick someone who will be present on that day. Assume that all absences are known a day in advance, so the croissant buyer can be determined on the previous afternoon.
- Overall, most people are present on most days.
- In the interest of fairness, everyone should buy croissants as many times as the others. (Basically, assume that every team member has the same amount of money to spend on croissants.)
- It would be nice to have some element of randomness, or at least perceived randomness, in order to alleviate the boredom of a roster. This is not a hard constraint: it is more of an aesthetic judgement. However, the same person should not be picked twice in a row.
- The person who brings the croissants should know in advance. So if person P is to bring croissants on day D, then this fact should be determined on some previous day where person P is present. For example, if the croissant bringer is always determined the day before, then it should be one of the persons who are present the day before.
- The number of team members is small enough that storage and computing resources are effectively unlimited. For example the algorithm can rely on a complete history of who brought croissants when in the past. Up to a few minutes of computation on a fast PC every day would be OK.
This is a model of a real world problem, so you are free to challenge or refine the assumptions if you think that they model the scenario better.
Origin 1: Find out who's going to buy the croissants by Florian Margaine.
Origin 2: Find out who's going to buy the croissants by Gilles.
This question is the same version as Gilles', and has been re-posted on Programmers as an experiment to see how the different communities address a programming challenge.
Best Answer
I'd use a scoring algorithm. Each person starts with a score of zero. Each time they bring croissants, increment their score by 1. The score of all team members who did not bring croissants is decremented by 1/N. Thus a score of 0 means that a team member has neither over or under bought.
Without randomness, choose the person with the lowest score out of the list of those who will be present.
To add randomness, sort the list by score and choose at random out of the list of all team members with a negative score. By restricting to negative scores, you ensure that no one will be too "lucky" over many weeks.
The advantage of this algorithm is that it has no reliance on keeping historical records and it easily allows the addition of new team members at any point in time.
It could be adapted to allow for absences being relatively common by decrementing the scores of only those present to enjoy the croissants.