Averigüe a quién le toca comprar los cruasanes, teniendo en cuenta las posibles ausencias

Un equipo ha decidido que cada mañana alguien debería traer cruasanes para todos. No debería ser la misma persona cada vez, por lo que debería haber un sistema para determinar a quién le toca el turno. El propósito de esta pregunta es determinar un algoritmo para decidir a quién le tocará traer croissants mañana.

Restricciones, supuestos y objetivos:

• El turno de traer croissants se determinará la tarde anterior.
• En cualquier día, algunas personas están ausentes. El algoritmo debe elegir a alguien que estará presente ese día. Suponga que todas las ausencias se conocen con un día de anticipación, de modo que el comprador del cruasán se puede determinar la tarde anterior.
• En general, la mayoría de las personas están presentes la mayoría de los días.
• En aras de la equidad, todos deberían comprar cruasanes tantas veces como los demás. (Básicamente, suponga que cada miembro del equipo tiene la misma cantidad de dinero para gastar en croissants).
• Sería bueno tener algún elemento de aleatoriedad, o al menos percibir aleatoriedad, para aliviar el aburrimiento de una lista. Esto no es una restricción difícil: es más un juicio estético. Sin embargo, no se debe elegir a la misma persona dos veces seguidas.
• La persona que trae los cruasanes debe saberlo de antemano. Entonces, si la persona P debe traer cruasanes el día D, entonces este hecho debe determinarse en algún día anterior donde la persona P esté presente. Por ejemplo, si el portador de croissant siempre se determina el día anterior, entonces debe ser una de las personas que están presentes el día anterior.
• El número de miembros del equipo es lo suficientemente pequeño como para que los recursos informáticos y de almacenamiento sean efectivamente ilimitados. Por ejemplo, el algoritmo puede basarse en una historia completa de quién trajo croissants en el pasado. Hasta unos pocos minutos de cálculo en una PC rápida todos los días estaría bien.

Este es un modelo de un problema del mundo real, por lo que puede desafiar o refinar los supuestos si cree que modelan mejor el escenario.

_{Origen 1: Descubre quién comprará los cruasanes de Florian Margaine.
Origen 2: descubre quién va a comprar los cruasanes de Gilles.
Esta pregunta es la misma versión que la de Gilles y se ha vuelto a publicar en Programadores como un experimento para ver cómo las diferentes comunidades abordan un desafío de programación.}

Usaría un algoritmo de puntuación. Cada persona comienza con una puntuación de cero. Cada vez que traigan croissants, incremente su puntaje en 1. El puntaje de todos los miembros del equipo que no trajeron croissants se reduce en 1 / N. Por lo tanto, un puntaje de 0 significa que un miembro del equipo no ha comprado en exceso o en exceso.

Sin aleatoriedad, elija a la persona con el puntaje más bajo de la lista de los que estarán presentes.

Para agregar aleatoriedad, ordene la lista por puntaje y elija al azar de la lista de todos los miembros del equipo con puntaje negativo. Al restringir a puntajes negativos, se asegura de que nadie tenga demasiada "suerte" durante muchas semanas.

La ventaja de este algoritmo es que no depende de mantener registros históricos y permite fácilmente agregar nuevos miembros del equipo en cualquier momento.

Se podría adaptar para permitir que las ausencias sean relativamente comunes al disminuir las puntuaciones de solo los presentes para disfrutar de los cruasanes.

Lo que haría, si tuviera que elegir esto, es conseguir un sombrero y poner los nombres de todos en el sombrero una vez en pequeños pedazos de papel. Luego, cada día, sacaba al azar el nombre de alguien del sombrero, y esa es la persona que trae los cruasanes al día siguiente. Ese papel luego se pega en un tablero, bajo "TRAIENDO MAÑANA A LOS CROISSANTS". El papel que está actualmente en el tablero se tira a la basura.

También tendría una caja. Comienza vacío. Cada día, antes de dibujar los nombres, volcaría el contenido de la caja en el sombrero, luego revisaría los papeles del sombrero y eliminaría a todos los que estarán ausentes mañana. Sus nombres van en la caja.

Si es hora de dibujar un nombre y el sombrero está vacío, rompería un poco más de papel y agregaría el nombre de todos una vez, luego movería los nombres de todos los que estarán ausentes mañana a la caja.

Debido a estos dos últimos pasos, es posible que el mismo nombre esté en el sombrero varias veces a la vez. Si el nombre que dibujo es el mismo que aparece en la pizarra, movería ese papel a la caja y luego volvería a dibujar.

No debería ser demasiado difícil traducir este sistema a un algoritmo en el idioma que elija.

Algoritmo, pequeño algoritmo. Usa un 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)
)

Quien compra

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

Después de que compran:

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

Y luego establecer:

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

... porque soy de la vieja escuela.

No debería ser demasiado difícil agregar un poco de aleatoriedad ajustando la primera consulta, tal vez agregando un random () en lugar de ordenar por fecha de última compra.

De hecho, he tenido que resolver este problema de alguna manera en el mundo real:

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

Lo que sucede es que las personas que han comprado donas "demasiado" (debido a la mala suerte, ir a trabajar cuando otras personas están de vacaciones, etc.) quedan excluidas del grupo hasta que sucedan suficientes adquisiciones para volver a colocarlas en el porcentaje "correcto" de compras

Sin embargo, esto debería ampliarse para manejar mejor la contratación de nuevas personas ...

De todos modos, este diseño funcionó muy bien para cambiar las variables (quién está adentro, quién está afuera) y cuándo el horario debe ser (prácticamente) infinito. Como una ventaja adicional, es fácil ser determinista al sembrar tu RNG.

No es tan bueno como algunas de las otras respuestas ya presentadas, pero es otra forma de ver el problema:

1. Haga una lista de todos los empleados participantes.
2. Duplicar la lista muchas veces (por ejemplo, 1,000)
3. Baraja la lista

Cada tarde, seleccione el próximo proveedor de croissant disponible. Cada mañana, el proveedor de cruasanes cruza su nombre en la parte superior de la lista.

El procesamiento diario es simple con lápiz y papel.

Nuevas contrataciones y terminaciones Alumni probablemente se manejará mejor haciendo una nueva lista. Si los ciclos de la CPU vuelven a ser caros (o tiene 100 millones de empleados y solo un Arduino de primera generación), sería fácil obtener la lista original con un número apropiado de marcadores de posición.

Más información (por solicitud).

Usando este enfoque con una lista arbitrariamente larga, obtienes el beneficio de la transparencia.

No solo sabes quién traerá cruasanes mañana, sino quién está programado para traerlos al día siguiente, y así sucesivamente. Por supuesto, cuanto más tiempo se vea, menos preciso será debido a ausencias, etc.

Los desarrolladores furtivos que descubran cómo pesar sus trozos de papel con un sombrero no tendrán tantas oportunidades de evitar sus deberes de traer croissant.

Los quejosos no desarrolladores que afirman que el proceso está manipulado puede revisar fácilmente los datos, llegar a una conclusión incorrecta y, de todos modos, quejarse.

No aleatorio

Mantener una lista ordenada. Si una persona está ausente el día que debe comprar, cámbiela por la siguiente persona disponible. Finalmente, la persona estará presente y, por lo tanto, comprará cruasanes. Por lo tanto, el contenido de la lista sigue siendo el mismo, pero las personas pueden moverse o subir según las ausencias.

Las personas nuevas se insertan en la lista después de la posición actual. Las personas que renunciaron o terminaron se eliminan de la lista. La posición actual aumenta en 1 cada día, cuando llega al final, volverá al inicio.

Esto supone que hay suficientes personas en la lista para dar cuenta del tiempo de ausencia promedio para promover la equidad.

Aleatorio

No podemos seleccionar personas al azar todos los días, ya que habrá un sesgo a corto plazo, por ejemplo, lanzar una moneda 10 veces y podría aparecer caras 8 y colas 2, por lo que las caras se atornillarían a corto plazo. Por lo tanto, necesitamos crear grupos de personas para que sea justo.

El cubo está determinado por la cantidad de veces que la gente ha comprado cruzadoras en el pasado. Entonces, en este caso, almacenaríamos un diccionario de personas y compras cruzadas. El día 1 todos están en el cubo cero. A medida que las personas compran croissiants, serán asignados al siguiente grupo, es decir, 1, 2, etc. La parte aleatoria se selecciona del grupo de personas disponibles en el grupo. El primer depósito disponible es el que tiene menos compras. Si hay 10 personas en el cubo, elija un número aleatorio del 1 al 10 y el que compre cruasanes. A las personas nuevas se les asigna el segmento actual más bajo para que no terminen comprando rondas adicionales de cruces (aunque estarán en el grupo de compra de inmediato). Si no hay nadie disponible en el segmento más bajo (todos están ausentes), entonces pasa al siguiente segmento más alto. Por ejemplo, deja ' s decir que hay una lista de 10 personas. El día 8, 8 personas están en el cubo 1 y 2 están en el cubo 0. Las dos personas en el cubo 0 están ausentes. En este caso, se usará el cubo 1 y una persona terminará en el cubo 2. Pero las personas siempre estarán dentro de unas pocas compras cruzadas (cubos) entre sí, porque la persona que ahora está en el cubo 2 probablemente no estará en el grupo de compra por un tiempo.

Se podrían agregar ajustes para asegurarse de que la misma persona no compre dos días seguidos y que haya algunos casos límite para manejar, pero esto agregaría un elemento de aleatoriedad y también lo mantendría justo. Además, es posible que desee mantener separadas las compras reales de croissant frente a la cubeta actual. A medida que las personas se van, se eliminan del cubo marcándolos permanentemente ausentes o eliminándolos por completo.