Find out whose turn it is to buy the croissants, accounting for possible absences

Question

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

Answer 1

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.

Answer 2

What I would do, if I had to pick this, is get a hat, and put everyone's names in the hat once on little pieces of paper. Then each day, I'd draw someone's name from the hat at random, and that's the person who brings the croissants the next day. That paper then gets tacked up on a board, under "BRINGING CROISSANTS TOMORROW". The paper that's currently on the board gets thrown away.

I'd also have a box. It starts out empty. Each day, before drawing the names, I'd dump the contents of the box into the hat, then go through the papers in the hat and remove everyone who's going to be absent tomorrow. Their names go in the box.

If it's time to draw a name and the hat is empty, I'd tear up some more paper and add everyone's name once, then move the names of everyone who's going to be absent tomorrow to the box.

Because of these last two steps, it's possible for the same name to be in the hat multiple times at once. If the name I happen to draw is the same as the name that's on the board, I'd move that paper to the box, and then draw again.

It shouldn't be too difficult to translate this system to an algorithm in your language of choice.

Answer 3

Algorithm, smalgorithm. Use a DB.

create table team_members 
(
    id integer auto_increment,
    name varchar(255),
    purchase_count integer,
    last_purchase_date datetime,
    present integer,
    prefers_donuts integer default 0,
    primary key( id)
)

Who buys?

select id from team_members where (present = 1) and (prefers_donuts = 0) order by purchase_count, last_purchase_date limit 1;

After they buy:

update team_members set purchase_count = purchase_count + 1, last_purchase_date = now() where id = ?

And then set:

insert into team_members (name, prefers_donuts) values ('GrandmasterB', 1);

...because I'm old school.

It shouldn't be too difficult to add a little randomness by tweaking the first query - maybe by adding a random() instead of sorting by last_purchase date.

Answer 4

I've actually had to solve this problem somewhat in the real world:

remember how many times people have gotten donuts
every day:
  var candidates = everyone
  toss out people who aren't here tomorrow
  toss out people who aren't here today 
  toss out the person who got them today (unless they're the only one left)
  toss out everyone where "times they got donuts"/"times everyone has got donuts"
    is more than 1/number of people (unless that would eliminate everyone)

  pick someone at random from the candidates

What happens is people who have bought donuts "too much" (due to bad luck, going to work when others are on vacation, etc) are excluded from the pool until enough acquisitions go by to put them back under the "right" percent of purchases.

This would need to be expanded to better handle hiring new people though...

Anyways, this design worked really well for changing variables (who is in, who is out) and when the schedule needs to be (practically) infinite. As an added bonus, it's easy to make deterministic by seeding your RNG.

Answer 5

Not as good as some of the other answers already presented, but another way of looking at the problem:

1. Make a list of all participating employees
2. Duplicate the list a lot of times (say, 1,000)
3. Shuffle the list

Each afternoon, select the next available croissant-bringer. Each morning, the croissant-bringer crosses his/her name off the top of the list.

Daily processing is pen & paper simple.

New Hires & Terminations Alumni would probably best be handled by making a new list. If CPU cycles ever get expensive again (or you have 100M employees & only a 1st gen Arduino) then it'd be easy to salt the original list with an appropriate number of place holders.

---

More info (per request).

Using this approach with an arbitrarily long list, you get the benefit of transparency.

Not only do you know who will bring croissants tomorrow, you know who is scheduled to bring them in the day after, and so on. Of course the further out in time you look the less accurate you'll be due to absences, etc.

Sneaky devs who figure out how to weight their slips of paper in a hat won't have as much opportunity to avoid their croissant-bringing duties.

Whining non-devs who claim the processed is rigged can easily review the data, come up with the wrong conclusion, and whine anyway.

Answer 6

Non Random

Maintain a ordered list. If a person is absent on the day they are supposed to buy, swap them with the next available person. Eventually the person will be present and thus buy croissants. So, the contents of the list remain the same, but persons may be moved or up down depending on absenses.

New people get inserted to the list after the current position. People who quit or terminated get removed from the list. The current position increments by 1 every day, when it reaches the end, it will go back to the start.

This assumes there are enough people in the list to account for the average absense time to promote fairness.

Random

We can't just select random people each day as there will be short term bias, for example flip a coin 10 times and you could come up heads 8 and tails 2, so heads would be screwed for the short term. So, we need to create buckets of people to keep it fair.

The bucket is determined by the number of times people have bought crossiants in the past. So, in this case, we would store a dictionary of people and crossiant buys. On day 1 everyone is in bucket zero. As people buy croissiants, they will be assigned to the next bucket up, i.e 1, 2, etc. The random part is picking from the pool of available people in the bucket. The first available bucket is the one with the fewest buys. If there are 10 people in the bucket, then pick a random number from 1 to 10 and that who buys croissants. New people are assigned the lowest current bucket so they don't end up buying extra rounds of crossiants (although they will be in the buy pool right away). If no one is available in the lowest bucket (they are all absent), then you go to the next highest bucket. For example, let's say there is a list of 10 people. On day 8, 8 people are in bucket 1 and 2 are in bucket 0. The two people in bucket 0 are absent. In this case, bucket 1 will be used and one person will end up in bucket 2. But, people will always be within a few crossiant buys (buckets) within each other, because the person now in bucket 2 will most likely not be in the buy pool for a while.

Tweaks could be added to make sure the same person does not buy two days in a row and there are some edge cases to handle, but this would add an element of randomness as well as keeping it fair. Also, one might want to keep actual croissant buys versus current bucket separated. As people leave, there are removed from the bucket either by marking them permanately absent or deleting them altogether.