Descubra de quem é a vez de comprar os croissants, respondendo por possíveis ausências

Uma equipe decidiu que todas as manhãs alguém deveria trazer croissants para todos. Não deve ser a mesma pessoa todas as vezes; portanto, deve haver um sistema para determinar de quem é a próxima vez. O objetivo desta pergunta é determinar um algoritmo para decidir de quem será a vez de trazer croissants amanhã.

Restrições, premissas e objetivos:

• De quem é a vez de trazer croissants, será determinado na tarde anterior.
• Em qualquer dia, algumas pessoas estão ausentes. O algoritmo deve escolher alguém que estará presente naquele dia. Suponha que todas as ausências sejam conhecidas com um dia de antecedência, para que o comprador do croissant possa ser determinado na tarde anterior.
• No geral, a maioria das pessoas está presente na maioria dos dias.
• No interesse da justiça, todos devem comprar croissants tantas vezes quanto os outros. (Basicamente, suponha que todo membro da equipe tenha a mesma quantia de dinheiro para gastar em croissants.)
• Seria bom ter algum elemento aleatório, ou pelo menos percebido aleatoriedade, a fim de aliviar o tédio de uma lista. Esta não é uma restrição difícil: é mais um julgamento estético. No entanto, a mesma pessoa não deve ser escolhida duas vezes seguidas.
• A pessoa que traz os croissants deve saber com antecedência. Portanto, se a pessoa P trouxer croissants no dia D, esse fato deve ser determinado em um dia anterior em que a pessoa P está presente. Por exemplo, se o portador de croissant é sempre determinado no dia anterior, deve ser uma das pessoas presentes no dia anterior.
• O número de membros da equipe é pequeno o suficiente para que os recursos de armazenamento e computação sejam efetivamente ilimitados. Por exemplo, o algoritmo pode contar com uma história completa de quem trouxe croissants quando no passado. Até alguns minutos de computação em um PC rápido todos os dias seria bom.

Este é um modelo de um problema do mundo real, portanto, você pode desafiar ou refinar as suposições se achar que elas modelam melhor o cenário.

_{Origem 1: Descubra quem vai comprar os croissants de Florian Margaine.
Origem 2: descubra quem vai comprar os croissants da Gilles.
Esta pergunta é da mesma versão que a de Gilles e foi publicada novamente nos programadores como um experimento para ver como as diferentes comunidades lidam com um desafio de programação.}

Eu usaria um algoritmo de pontuação. Cada pessoa começa com uma pontuação zero. Cada vez que eles trazem croissants, aumente sua pontuação em 1. A pontuação de todos os membros da equipe que não trouxeram croissants é decrementada em 1 / N. Portanto, uma pontuação 0 significa que um membro da equipe não comprou nem comprou nem comprou demais.

Sem aleatoriedade, escolha a pessoa com a pontuação mais baixa da lista daqueles que estarão presentes.

Para adicionar aleatoriedade, classifique a lista por pontuação e escolha aleatoriamente fora da lista de todos os membros da equipe com pontuação negativa. Ao restringir as pontuações negativas, você garante que ninguém terá muita "sorte" por muitas semanas.

A vantagem desse algoritmo é que ele não depende de manter registros históricos e permite facilmente a adição de novos membros da equipe a qualquer momento.

Poderia ser adaptado para permitir que as ausências fossem relativamente comuns, diminuindo a pontuação apenas dos presentes para apreciar os croissants.

O que eu faria, se tivesse que escolher isso, era pegar um chapéu e colocar os nomes de todos no chapéu uma vez em pedacinhos de papel. Então, todos os dias, eu desenhava o nome de alguém do chapéu aleatoriamente, e essa é a pessoa que traz os croissants no dia seguinte. Esse artigo é então afixado em um quadro, sob "LEVANDO AMORTECEDORES AMANHÃ". O papel que está atualmente no quadro é jogado fora.

Eu também teria uma caixa. Começa vazio. Todos os dias, antes de desenhar os nomes, eu despejava o conteúdo da caixa no chapéu, depois vasculhava os papéis do chapéu e removia todos que estavam ausentes amanhã. Os nomes deles estão na caixa.

Se estiver na hora de desenhar um nome e o chapéu estiver vazio, rasgarei um pouco mais de papel e adicionaria o nome de todos uma vez, depois moverei os nomes de todos os que amanhã estarão ausentes na caixa.

Devido a essas duas últimas etapas, é possível que o mesmo nome esteja no chapéu várias vezes ao mesmo tempo. Se o nome que eu desenhei for o mesmo que está no quadro, eu moveria esse papel para a caixa e depois desenharia novamente.

Não deve ser muito difícil traduzir esse sistema para um algoritmo no idioma de sua escolha.

Algoritmo, smalgoritmo. Use um banco de dados.

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

Quem compra?

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

Depois que eles compram:

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

E então defina:

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

... porque eu sou da velha escola.

Não deve ser muito difícil adicionar um pouco de aleatoriedade ajustando a primeira consulta - talvez adicionando um random () em vez de classificar pela data da última compra.

Na verdade, tive que resolver esse problema um pouco no 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

O que acontece é que as pessoas que compraram rosquinhas "demais" (devido à má sorte, indo para o trabalho quando outras estão de férias etc.) são excluídas do pool até que haja aquisições suficientes para colocá-las de volta na porcentagem "certa" de compras.

Isso precisaria ser expandido para melhor lidar com a contratação de novas pessoas ...

De qualquer forma, esse design funcionou muito bem para alterar variáveis ​​(quem está dentro, quem está fora) e quando o cronograma precisa ser (praticamente) infinito. Como um bônus adicional, é fácil tornar determinístico semeando seu RNG.

Não é tão bom quanto algumas das outras respostas já apresentadas, mas outra maneira de encarar o problema:

1. Faça uma lista de todos os funcionários participantes
2. Duplique a lista várias vezes (por exemplo, 1.000)
3. Ordem aleatória da lista

Toda tarde, selecione o próximo portador de croissant disponível. Todas as manhãs, o croissant-bringer cruza seu nome no topo da lista.

O processamento diário é simples em papel e caneta.

Alunos de novas contratações e rescisões provavelmente seriam melhor tratados fazendo uma nova lista. Se os ciclos de CPU voltarem a ser caros novamente (ou se você tiver 100 milhões de funcionários e apenas um Arduino de primeira geração), seria fácil salgar a lista original com um número apropriado de marcadores de posição.

Mais informações (por solicitação).

Usando essa abordagem com uma lista arbitrariamente longa, você obtém o benefício da transparência.

Você não apenas sabe quem trará croissants amanhã, como também deve agendá-los no dia seguinte e assim por diante. É claro que quanto mais tempo você parecer, menos preciso será devido a ausências etc.

Desenvolvedores sorrateiros que descobrirem como pesar suas tiras de papel em um chapéu não terão tanta oportunidade de evitar seus deveres de trazer croissants.

Os não-desenvolvedores que reclamam que o processamento é fraudado pode facilmente revisar os dados, chegar a uma conclusão errada e reclamar de qualquer maneira.

Não aleatório

Mantenha uma lista ordenada. Se uma pessoa estiver ausente no dia em que deveria comprar, troque-a pela próxima pessoa disponível. Eventualmente, a pessoa estará presente e, assim, comprar croissants. Portanto, o conteúdo da lista permanece o mesmo, mas as pessoas podem ser movidas ou para cima, dependendo das ausências.

Novas pessoas são inseridas na lista após a posição atual. As pessoas que saíram ou terminaram são removidas da lista. A posição atual é incrementada em 1 todos os dias. Quando chegar ao fim, ela voltará ao início.

Isso pressupõe que haja número suficiente de pessoas na lista para contabilizar o tempo médio de ausência para promover a justiça.

Aleatória

Não podemos simplesmente selecionar pessoas aleatórias todos os dias, pois haverá viés de curto prazo, por exemplo, jogar uma moeda 10 vezes e você pode subir na cara 8 e na coroa 2, para que as cabeças sejam parafusadas no curto prazo. Então, precisamos criar baldes de pessoas para mantê-lo justo.

O balde é determinado pelo número de vezes que as pessoas compraram crossiants no passado. Portanto, nesse caso, armazenaríamos um dicionário de pessoas e compras cruzadas. No primeiro dia, todos estão no intervalo zero. À medida que as pessoas compram croissiants, elas serão atribuídas ao próximo depósito, ou seja, 1, 2, etc. A parte aleatória é escolhida entre o número de pessoas disponíveis no depósito. O primeiro balde disponível é aquele com menos compras. Se houver 10 pessoas no balde, escolha um número aleatório de 1 a 10 e quem compra croissants. As pessoas novas recebem o menor balde atual, para que não acabem comprando rodadas extras de crossiants (embora estejam no pool de compras imediatamente). Se ninguém estiver disponível no balde mais baixo (todos estão ausentes), você será direcionado para o próximo balde mais alto. Por exemplo, deixe ' s dizem que há uma lista de 10 pessoas. No dia 8, 8 pessoas estão no balde 1 e 2 estão no balde 0. As duas pessoas no balde 0 estão ausentes. Nesse caso, o balde 1 será usado e uma pessoa terminará no balde 2. Mas, as pessoas sempre estarão dentro de algumas compras cruzadas (baldes) umas nas outras, porque a pessoa agora no balde 2 provavelmente não estará no balde. a piscina de compra por um tempo.

Ajustes podem ser adicionados para garantir que a mesma pessoa não compre dois dias seguidos e que haja alguns casos extremos para lidar, mas isso adicionaria um elemento aleatório, além de mantê-lo justo. Além disso, pode-se manter compras reais de croissant versus balde atual separadas. Quando as pessoas saem, elas são removidas do balde, marcando-as permanentemente ausentes ou excluindo-as completamente.