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

13

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

Restricciones, suposiciones y objetivos:

  • El turno para traer croissants se determinará la tarde anterior.
  • En un día cualquiera, 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, por lo que el comprador de croissant se puede determinar en 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 imparcialidad, todos deben comprar croissants 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 percepción de 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 croissants debe saber de antemano. Entonces, si la persona P debe traer croissants el día D, este hecho debe determinarse en algún día anterior donde la persona P está presente. Por ejemplo, si el bringer 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 de almacenamiento y computación 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ómputo 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 puedes desafiar o refinar las suposiciones si crees que modelan mejor el escenario.

Origen 1: Averigua quién va a comprar los croissants por Florian Margaine.
Origen 2: Averigüe quién va a comprar el croissants 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 enfrentan un desafío de programación.

    
pregunta GlenH7 25.07.2013 - 20:42

6 respuestas

26

Yo usaría un algoritmo de puntuación. Cada persona comienza con una puntuación de cero. Cada vez que traen croissants, incrementa su puntuación en 1. La puntuación de todos los miembros del equipo que no trajeron croissants se reduce en 1 / N. Por lo tanto, una puntuación de 0 significa que un miembro del equipo no ha comprado más o menos.

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 puntuación y elija al azar de la lista de todos los miembros del equipo con una puntuación negativa. Al restringirte a puntuaciones negativas, te aseguras de que nadie tendrá demasiada "suerte" durante muchas semanas.

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

Podría adaptarse para permitir que las ausencias sean relativamente comunes disminuyendo las puntuaciones de solo los presentes para disfrutar de los croissants.

    
respondido por el Steven Burnap 25.07.2013 - 22:05
7

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 trozos de papel. Luego, cada día, sacaba el nombre de alguien del sombrero al azar, y esa es la persona que trae los croissants al día siguiente. Ese papel luego se clava en un tablero, bajo "TRAER CROISSANTS TOMORROW". El papel que está actualmente en la pizarra se desecha.

También tendría una caja. Empieza vacío. Cada día, antes de dibujar los nombres, vaciaba el contenido de la caja en el sombrero, luego revisaba los papeles del sombrero y eliminaba a todos los que se ausentaran mañana. Sus nombres van en la caja.

Si es el momento de dibujar un nombre y el sombrero está vacío, rasgaré un poco más de papel y agregaré el nombre de todos una vez, luego moveré 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 dibuje es el mismo que el que está en la pizarra, moveré ese papel a la caja y luego dibujaré nuevamente.

No debería ser demasiado difícil traducir este sistema a un algoritmo en el idioma de su elección.

    
respondido por el Mason Wheeler 25.07.2013 - 20:56
6

Algoritmo, smalgorithm. Utilice una base de datos.

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én 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 comprar:

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

Y luego establece:

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 clasificar por fecha de última compra.

    
respondido por el GrandmasterB 25.07.2013 - 21:12
4

En realidad, tuve 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 otros están de vacaciones, etc.) se excluyen del grupo hasta que se realicen suficientes adquisiciones para volver a ponerlas bajo el "derecho "porcentaje de compras.

Esto debería expandirse para manejar mejor la contratación de nuevas personas, sin embargo ...

De todos modos, este diseño funcionó muy bien para cambiar variables (quién está adentro, quién está afuera) y cuando el cronograma debe ser (prácticamente) infinito. Como un bono adicional, es fácil hacer deterministas al sembrar su RNG.

    
respondido por el Telastyn 25.07.2013 - 22:03
2

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. Duplique la lista muchas veces (por ejemplo, 1,000)
  3. Mezclar la lista

Cada tarde, seleccione el siguiente brissant bringer disponible. Cada mañana, el croissant bringer cruza su nombre de la parte superior de la lista.

El procesamiento diario es pluma y amp; papel simple.

Nuevas contrataciones & Terminaciones Los alumnos probablemente se manejen mejor haciendo una nueva lista. Si los ciclos de la CPU vuelven a ser costosos (o si tiene 100 millones de empleados y solo un Arduino de primera generación), sería fácil agregar a la lista original un número adecuado de titulares de lugares.

Más información (por solicitud).

Al utilizar este enfoque con una lista arbitrariamente larga, obtiene el beneficio de la transparencia.

No solo sabe quién traerá croissants mañana, sino también quién tiene previsto traerlos al día siguiente, y así sucesivamente. Por supuesto, cuanto más lejos se vea, menos preciso será debido a las ausencias, etc.

Los devs furtivos que descubren cómo pesar sus trozos de papel en un sombrero no tendrán tantas oportunidades para evitar sus deberes de traer croissant.

Los no devs quejumbrosos que afirman que el procesado está manipulado pueden revisar fácilmente los datos, llegar a una conclusión errónea y lloriquear de todos modos.

    
respondido por el Dan Pichelman 25.07.2013 - 22:40
1

No aleatorio

Mantener una lista ordenada. Si una persona está ausente el día en que se supone que debe comprar, cámbiela por la siguiente persona disponible. Eventualmente la persona estará presente y por lo tanto comprará croissants. Por lo tanto, el contenido de la lista sigue siendo el mismo, pero las personas pueden ser movidas o subidas dependiendo de 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 se incrementa en 1 cada día, cuando llega al final, volverá al inicio.

Esto supone que hay suficientes personas en la lista para explicar el tiempo de ausencia promedio para promover la imparcialidad.

Aleatorio

No podemos simplemente seleccionar personas aleatorias cada día, ya que habrá sesgo a corto plazo, por ejemplo, lanzar una moneda 10 veces y podría aparecer cabezas 8 y colas 2, así que las cabezas se atornillarán a corto plazo. Por lo tanto, necesitamos crear grupos de personas para mantenerlo justo.

La cantidad de veces que la gente ha comprado los cruces en el pasado determina el cubo. 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, se asignarán al siguiente cubo, es decir, 1, 2, etc. La parte aleatoria es seleccionar del grupo de personas disponibles en el cubo. El primer cubo disponible es el que tiene menos compras. Si hay 10 personas en el cubo, elija un número al azar de 1 a 10 y el que compra croissants. A las personas nuevas se les asigna el grupo actual más bajo para que no terminen comprando rondas adicionales de cruces cruzadas (aunque estarán en el grupo de compra de inmediato). Si no hay nadie disponible en el grupo más bajo (todos están ausentes), entonces vaya al siguiente grupo más alto. Por ejemplo, digamos que hay una lista de 10 personas. El día 8, 8 personas están en el cubo 1 y 2 en el cubo 0. Las dos personas en el cubo 0 están ausentes. En este caso, se utilizará el cubo 1 y una persona terminará en el cubo 2. Pero, las personas siempre estarán dentro de unas pocas compras cruzadas (cubos) dentro de la otra, 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 de vanguardia que manejar, pero esto agregaría un elemento de aleatoriedad además de mantenerlo justo. Además, uno podría querer mantener las compras reales de croissant frente al cubo actual separado. A medida que las personas se van, se retiran del cubo ya sea marcándolos como ausentes o eliminándolos por completo.

    
respondido por el Jon Raynor 25.07.2013 - 23:26

Lea otras preguntas en las etiquetas