Découvrez à qui revient l'achat des croissants, en tenant compte des éventuelles absences

Une équipe a décidé que chaque matin, quelqu'un devrait apporter des croissants pour tout le monde. Ce ne devrait pas être la même personne à chaque fois, donc il devrait y avoir un système pour déterminer de quel tour il s'agit. Le but de cette question est de déterminer un algorithme pour décider à quel tour ce sera demain d'apporter des croissants.

Contraintes, hypothèses et objectifs:

• Dont le tour est d'apporter des croissants sera déterminé l'après-midi précédent.
• Chaque jour, certaines personnes sont absentes. L'algorithme doit choisir quelqu'un qui sera présent ce jour-là. Supposons que toutes les absences soient connues un jour à l'avance, afin que l'acheteur du croissant puisse être déterminé l'après-midi précédent.
• Dans l'ensemble, la plupart des gens sont présents la plupart du temps.
• Dans un souci d'équité, chacun devrait acheter des croissants autant de fois que les autres. (Fondamentalement, supposez que chaque membre de l'équipe ait le même montant d'argent à dépenser pour des croissants.)
• Ce serait bien d'avoir un élément de caractère aléatoire, ou du moins de caractère aléatoire perçu, afin d'alléger l'ennui d'une liste. Ce n'est pas une contrainte dure: c'est plus un jugement esthétique. Cependant, la même personne ne doit pas être choisie deux fois de suite.
• La personne qui apporte les croissants doit le savoir à l'avance. Donc, si la personne P doit apporter des croissants le jour J, alors ce fait devrait être déterminé un jour précédent où la personne P est présente. Par exemple, si le porteur de croissants est toujours déterminé la veille, il doit s'agir de l'une des personnes présentes la veille.
• Le nombre de membres de l'équipe est suffisamment petit pour que les ressources de stockage et de calcul soient effectivement illimitées. Par exemple, l'algorithme peut s'appuyer sur une histoire complète de qui a apporté des croissants par le passé. Jusqu'à quelques minutes de calcul sur un PC rapide chaque jour serait OK.

Il s'agit d'un modèle d'un problème réel, vous êtes donc libre de contester ou d'affiner les hypothèses si vous pensez qu'elles modélisent mieux le scénario.

_{Origine 1: Découvrez qui va acheter les croissants de Florian Margaine.
Origine 2: Découvrez qui va acheter les croissants de Gilles.
Cette question est la même version que celle de Gilles et a été republiée sur Programmers comme une expérience pour voir comment les différentes communautés relèvent un défi de programmation.}

J'utiliserais un algorithme de notation. Chaque personne commence par un score de zéro. Chaque fois qu'ils apportent des croissants, augmentez leur score de 1. Le score de tous les membres de l'équipe qui n'ont pas apporté de croissants est diminué de 1 / N. Ainsi, un score de 0 signifie qu'un membre de l'équipe n'a ni sur ni sous-acheté.

Sans hasard, choisissez la personne avec le score le plus bas dans la liste de ceux qui seront présents.

Pour ajouter un caractère aléatoire, triez la liste par score et choisissez au hasard dans la liste de tous les membres de l'équipe avec un score négatif. En vous limitant aux scores négatifs, vous vous assurez que personne ne sera trop «chanceux» pendant plusieurs semaines.

L'avantage de cet algorithme est qu'il ne dépend pas de la tenue de registres historiques et qu'il permet facilement l'ajout de nouveaux membres de l'équipe à tout moment.

Il pourrait être adapté pour permettre aux absences d'être relativement courantes en décrémentant les scores des seuls présents pour profiter des croissants.

Ce que je ferais, si je devais choisir cela, c'est de prendre un chapeau et de mettre les noms de chacun dans le chapeau une fois sur de petits morceaux de papier. Ensuite, chaque jour, je tirais au hasard le nom de quelqu'un sur le chapeau, et c'est la personne qui apporte les croissants le lendemain. Ce papier est ensuite collé sur un tableau, sous "BRINGING CROISSANTS TOMORROW". Le papier qui est actuellement au tableau est jeté.

J'aurais aussi une boîte. Ça commence vide. Chaque jour, avant de dessiner les noms, je jetais le contenu de la boîte dans le chapeau, puis parcourais les papiers dans le chapeau et retirais tous ceux qui devaient s'absenter demain. Leurs noms vont dans la boîte.

S'il est temps de dessiner un nom et que le chapeau est vide, je déchirerais un peu plus de papier et ajouterais le nom de tout le monde une fois, puis déplacerais les noms de tous ceux qui vont s'absenter demain dans la boîte.

En raison de ces deux dernières étapes, il est possible que le même nom soit dans le chapeau plusieurs fois à la fois. Si le nom que je dessine est le même que celui qui est sur le tableau, je déplacerais ce papier dans la boîte, puis je dessinerais à nouveau.

Il ne devrait pas être trop difficile de traduire ce système en un algorithme dans la langue de votre choix.

Algorithme, smalgorithme. Utilisez une base de données.

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)
)

Qui achète?

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

Après avoir acheté:

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

Et puis définissez:

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

... parce que je suis de la vieille école.

Il ne devrait pas être trop difficile d'ajouter un peu de caractère aléatoire en modifiant la première requête - peut-être en ajoutant random () au lieu de trier par date de last_purchase.

J'ai dû résoudre ce problème quelque peu dans le monde réel:

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

Ce qui se passe, c'est que les gens qui ont acheté des beignets "trop" (en raison de la malchance, d'aller travailler quand d'autres sont en vacances, etc.) sont exclus de la piscine jusqu'à ce qu'il y ait suffisamment d'acquisitions pour les remettre sous le "bon" pourcentage de achats.

Cela devrait être élargi pour mieux gérer l'embauche de nouvelles personnes, bien que ...

Quoi qu'il en soit, cette conception a très bien fonctionné pour changer les variables (qui est dedans, qui est dehors) et quand le calendrier doit être (pratiquement) infini. En prime, il est facile de rendre déterministe en amorçant votre RNG.

Pas aussi bon que certaines des autres réponses déjà présentées, mais une autre façon de voir le problème:

1. Faites une liste de tous les employés participants
2. Dupliquez la liste plusieurs fois (disons, 1 000)
3. Mélangez la liste

Chaque après-midi, sélectionnez le prochain apporteur de croissants disponible. Chaque matin, le porteur de croissants raye son nom du haut de la liste.

Le traitement quotidien est simple avec du papier et du stylo.

Nouvelles embauches et licenciements Les anciens étudiants seraient probablement mieux traités en créant une nouvelle liste. Si les cycles de processeur redeviennent chers (ou si vous avez 100 millions d'employés et seulement un Arduino de 1ère génération), il serait facile de saler la liste d'origine avec un nombre approprié de marques de réservation.

Plus d'infos (par demande).

En utilisant cette approche avec une liste arbitrairement longue, vous bénéficiez de la transparence.

Non seulement vous savez qui apportera des croissants demain, vous savez qui doit les apporter le lendemain, et ainsi de suite. Bien sûr, plus vous regardez loin dans le temps, moins vous serez précis en raison d'absences, etc.

Les développeurs sournois qui savent comment peser leurs bouts de papier dans un chapeau n'auront pas autant d'occasions d'éviter leurs devoirs de croissants.

Pleurer les non-développeurs qui prétendent que le traitement est truqué peut facilement examiner les données, arriver à la mauvaise conclusion et se plaindre de toute façon.

Non aléatoire

Maintenir une liste ordonnée. Si une personne est absente le jour où elle est censée acheter, échangez-la avec la prochaine personne disponible. Finalement, la personne sera présente et achètera donc des croissants. Ainsi, le contenu de la liste reste le même, mais les personnes peuvent être déplacées ou remontées en fonction des absences.

De nouvelles personnes sont insérées dans la liste après la position actuelle. Les personnes qui ont quitté ou résilié sont supprimées de la liste. La position actuelle augmente de 1 chaque jour, lorsqu'elle atteint la fin, elle revient au début.

Cela suppose qu'il y a suffisamment de personnes dans la liste pour tenir compte du temps d'absence moyen pour promouvoir l'équité.

Aléatoire

Nous ne pouvons pas simplement sélectionner des personnes au hasard chaque jour car il y aura un biais à court terme, par exemple lancer une pièce 10 fois et vous pourriez monter les têtes 8 et les queues 2, de sorte que les têtes seraient vissées à court terme. Donc, nous devons créer des groupes de personnes pour que cela soit juste.

Le seau est déterminé par le nombre de fois où les gens ont acheté des croisés dans le passé. Donc, dans ce cas, nous stockerions un dictionnaire de personnes et d'achats croisés. Le premier jour, tout le monde est dans le compartiment zéro. Au fur et à mesure que les gens achètent des croissiants, ils seront assignés au prochain seau, c'est-à-dire 1, 2, etc. La partie aléatoire est choisie dans le pool de personnes disponibles dans le seau. Le premier seau disponible est celui avec le moins d'achats. S'il y a 10 personnes dans le seau, choisissez un nombre aléatoire de 1 à 10 et celui qui achète des croissants. Les nouvelles personnes se voient attribuer le seau actuel le plus bas afin de ne pas finir par acheter des séries supplémentaires de croisés (même si elles seront immédiatement dans le pool d'achat). Si personne n'est disponible dans le compartiment le plus bas (ils sont tous absents), vous passez au compartiment le plus élevé suivant. Par exemple, laissons ' s dire qu'il y a une liste de 10 personnes. Le jour 8, 8 personnes sont dans le seau 1 et 2 sont dans le seau 0. Les deux personnes dans le seau 0 sont absentes. Dans ce cas, le seau 1 sera utilisé et une personne se retrouvera dans le seau 2. Mais, les gens seront toujours à quelques achats croisés (seaux) les uns dans les autres, car la personne qui se trouve maintenant dans le seau 2 ne sera probablement pas dans le pool d'achat pendant un certain temps.

Des ajustements pourraient être ajoutés pour s'assurer que la même personne n'achète pas deux jours de suite et qu'il y a des cas marginaux à gérer, mais cela ajouterait un élément de caractère aléatoire et le maintiendrait juste. En outre, on peut vouloir séparer les achats de croissants réels par rapport au seau actuel. Au fur et à mesure que les gens partent, ils sont retirés du seau soit en les marquant définitivement absents, soit en les supprimant complètement.