Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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.

share|improve this question

We're looking for long answers that provide some explanation and context. Don't just give a one-line answer; explain why your answer is right, ideally with citations. Answers that don't include explanations may be removed.

2  
Added post notice, I'll protect if need be but I'd like to keep it as open as I can I for as long as I can. Regarding this question being in any way difficient, it is an experiment. It will stay open. For Science! –  World Engineer Jul 25 '13 at 19:15
4  
More suited for Code Golf? –  jmo21 Jul 25 '13 at 20:50
3  
Who cares? No self-respecting team would have croissants. Now, doughnuts, on the other hand, that's an interesting question. –  Ross Patterson Jul 25 '13 at 21:52
3  
This sounds like a perfect use case for DA Form 6 (heck, it's worked for the Army since 1974!). See AR 220-45 for usage. It should be relatively simple to translate that into an algorithm. –  Adam Balsam Jul 26 '13 at 0:27
2  
(to expand on @AdamBalsam the form armypubs.army.mil/eforms/pdf/A6.PDF and usage apd.army.mil/pdffiles/r220_45.pdf ... and please don't suggest this to my former employer, they have enough policies and procedures as it is) –  MichaelT Jul 26 '13 at 2:36

10 Answers 10

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.

share|improve this answer
2  
I think your last paragraph is essential, otherwise someone who goes on holiday for a month (honeymoon maybe) would come back to a massive negative score and much buying. –  James Jul 25 '13 at 20:47
8  
Could also tweak: -1 if you eat a pastry someone else brought. (N-1) if you buy pastries. That way if someone gets lucky and only buys for 4, then the next day the person gets unlucky and buys for 7, those two buys aren't treated equally. -1 because a pastry you buy for yourself is neutral. –  James Jul 25 '13 at 21:15
    
@James, no fear; the OP is in the U.S., and no one in the U.S. gets anywhere near that much vacation. :( –  Kyralessa Jul 26 '13 at 11:21
    
@James Yeah, that's a good improvement. –  Steven Burnap Jul 26 '13 at 17:48

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.

share|improve this answer
    
Sorting through the hat for everyone who's going to be out seems like a real pain. –  Bobson Jul 25 '13 at 19:16
    
@Bobson: The question specifically says that the size of the team is relatively small. If I was dealing with a large data set, I'd do something more sophisticated. –  Mason Wheeler Jul 25 '13 at 19:18

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.

share|improve this answer
    
+1. For new hires, do you initialize purchase_count to the average of everyone else? –  Dan Pichelman Jul 25 '13 at 20:20
6  
Hmm, very good question. That would probably work. Or you can just make the new guy bring the croissants every morning until he catches up. He is the new guy after all. –  GrandmasterB Jul 25 '13 at 23:05

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.

share|improve this answer

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.

share|improve this answer
1  
Terminations? Ghenghis Khan approves of this post. –  Deer Hunter Jul 25 '13 at 23:47
1  
@DeerHunter I've always disliked the way HR talks about "terminating people". It brings to mind firing squads. Maybe I should have said "New Hires & Alumni..." instead. –  Dan Pichelman Jul 26 '13 at 2:29

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.

share|improve this answer
1  
Added Random implementation. –  Jon Raynor Jul 26 '13 at 17:33

Mason Wheeler's hat approach works but assumes croissant consumption is uniform. For a physical hat it's probably the right approach.

For an electronic hat, though, you can be more fair.

Every day everyone who is there puts their name in the hat.

When pick time comes around a name is pulled and checked for validity--the person must be there both today (to be notified) and tomorrow (to bring them.) If it's a valid pick you remove as many copies of his name as people who will be there tomorrow, if it's invalid it goes back and you draw again.

Note that you must handle the case where there are a negative number of copies of a name in the hat.

share|improve this answer
    
and how would you end up with a negative number of copies of a name in the hat? –  GlenH7 Jul 25 '13 at 20:37
    
@GlenH7: It's inevitable. Look at day #1--there's exactly one copy of each name in the hat but the guy who ends up buying tomorrow gets several copies of his name removed. –  Loren Pechtel Jul 25 '13 at 21:50
1  
I'm sorry, but that explanation makes no sense to me. Your answer is reasonably solid excepting your last statement. –  GlenH7 Jul 25 '13 at 23:23
1  
To be more clear - why would you remove entries from the hat based upon the number of croissants brought in? And why would you allow (or prevent?) "negative entries" within the electronic hat? You may have a valid approach with tying croissant consumption with who is placed in the hat, but your answer doesn't clearly draw that out. –  GlenH7 Jul 26 '13 at 14:42
    
One name goes into the hat for every employee every day. One name comes out of the hat for every person for whom croissants are bought. –  Loren Pechtel Jul 26 '13 at 19:26

My algorithm is:

  • Make a list of people who are here today and tomorrow (and didn't buy croissants today if possible)
  • Choose one at random

Over a couple of weeks, the croissant buying should be more than sufficiently distributed. The gains of a more complicated algorithm seem smaller than the benefits of a simple algorithm everyone can understand.

If buying croissants three days in a row is a financial burden for anybody, then the idea is horribly offensive whether you have three-day runs or not, and you should have an optional kitty.

share|improve this answer

Things needed: A chotchky or some other unique object for each person (Pieces of paper with unique symbols/numbers on each one would work too). Table or container to keep unique objects.

The rule: no one that doesn't have an object will be picked to go get croissants.

  1. At the start give every body an object from the unique collection.

  2. Some one volunteers to start.

  3. The first/next person buys the croissants.

    The one who just bought the pastries -

  4. puts there unique object in the place where those are kept.

  5. picks the next person(The potential next person gets to refuse if she will be absent the next day).

  6. Continue through steps 3-5 until no one has a unique object.

  7. Every one gets their objects back again.

  8. Restart to step 1.

The above solution assumes that every one is willing to participate, and no one wants to write a computer program for it. This solution also relies on the honour system.

No one will go more than any one else because of the main rule. Step 5 provides some randomness.

No absent person will miss there pastry purchase responsibility because they wont be present to give up their unique object.

If there is cheating any one can create a list of people who've taking a turn.

Edit:

The following is a modification for steps 1, 4, and 5. The way to do this with a pc is to have a graphical interface with randomly placed red colored shapes with team names placed on the screen. The current croissant buyer would select the next person with a touch/click on the shape to change it's color to green so the next person would know they're up.The colors are incidental. They can be any color as long as each color would be consistent for each step.

When a team member got back from a croissant run they would click/touch their shape to make it fade away so it's not touchable/click-able any more.

When the last graphic is clicked/touched to make it fade away all the team's shapes appear again on the display.

All the above steps apply except instead of objects there are shapes on a screen with names. To make it work there is the added complexity of have the shapes change state.

This method could also be adapted to phones where every one's phone shares the graphic and any team members actions on it would update all the other phones.

share|improve this answer
1  
Your analog approach may work, but this question is specifically looking for an algorithmic approach that could be automated and programmed. –  GlenH7 Jul 26 '13 at 14:43
    
This could be used as a program. I'll update the answer soon. –  Quentin Engles Jul 26 '13 at 18:51
    
GlenH7 The question also specifies to challenge the assumptions. The assumption that a team is always made of people who can write programs is under question. Sure they could outsource the croissant engine, but how much are they willing to pay for orderly pastry purchasing software. I updated the question any way. –  Quentin Engles Jul 26 '13 at 19:16

It's not much of an "algorithm", but in my company, people bring in cakes on their birthdays.

That way:

  • Everyone always knows when they need to do it
  • It's more personal
  • If they're away, or know they clash with someone else, they'll know in advance and can sort it out ad hoc.
share|improve this answer
1  
This doesn't answer the posted question, unless you have enough people to bring in a cake every day. (I'm not the down voter) –  Dan Pichelman Jul 29 '13 at 13:17
1  
Please don't create additional answers in order to clarify a previous answer. Consider editing this answer into your other answer and removing this answer. Or consider removing this answer altogether as the question clearly asks for an algorithmic approach to solving the problem. The implied preference is for a solution that can be automated since the site is about programming. –  GlenH7 Jul 29 '13 at 13:20
    
@Dan, but the problem said realistic answers are ok -- cake N times a year is normally a lot nicer than cake every day! –  Jack V. Jul 29 '13 at 14:46
    
@Glen "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." –  Jack V. Jul 29 '13 at 14:46

protected by World Engineer Jul 26 '13 at 19:40

Thank you for your interest in this question. Because it has attracted low-quality answers, posting an answer now requires 10 reputation on this site.

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.