Scopri a chi tocca acquistare i croissant, tenendo conto delle possibili assenze

13

Una squadra ha deciso che ogni mattina qualcuno dovrebbe portare croissant per tutti. Non dovrebbe essere la stessa persona ogni volta, quindi dovrebbe esserci un sistema per determinare di chi è il turno successivo. Lo scopo di questa domanda è quello di determinare un algoritmo per decidere il turno di portare i croissant domani.

Vincoli, ipotesi e obiettivi:

  • Il cui turno è quello di portare i croissant saranno determinati il pomeriggio precedente.
  • In un dato giorno, alcune persone sono assenti. L'algoritmo deve scegliere qualcuno che sarà presente in quel giorno. Supponiamo che tutte le assenze siano note con un giorno di anticipo, quindi il compratore di croissant può essere determinato nel pomeriggio precedente.
  • In generale, la maggior parte delle persone è presente quasi tutti i giorni.
  • Nell'interesse dell'equità, tutti dovrebbero comprare croissant tante volte quanto gli altri. (Fondamentalmente, supponiamo che ogni membro del team abbia la stessa quantità di denaro da spendere nei croissant.)
  • Sarebbe bello avere qualche elemento di casualità, o almeno percepita casualità, al fine di alleviare la noia di un roster. Questo non è un limite difficile: è più di un giudizio estetico. Tuttavia, la stessa persona non dovrebbe essere scelta due volte di seguito.
  • La persona che porta i croissant dovrebbe sapere in anticipo. Quindi, se la persona P deve portare i croissant il giorno D, allora questo fatto dovrebbe essere determinato in un giorno precedente in cui la persona P è presente. Ad esempio, se il cornetto del cornetto è sempre determinato il giorno prima, allora dovrebbe essere una delle persone presenti il giorno prima.
  • Il numero di membri del team è abbastanza ridotto da consentire l'archiviazione illimitata delle risorse di archiviazione e elaborazione. Ad esempio, l'algoritmo può basarsi su una storia completa di chi ha portato cornetti quando in passato. Fino a pochi minuti di calcolo su un PC veloce ogni giorno andrebbe bene.

Questo è un modello di un problema del mondo reale, quindi sei libero di sfidare o affinare le ipotesi se pensi che modellano meglio lo scenario.

Origine 1: Scopri chi comprerà i croissant di Florian Margaine.
Origine 2: Scopri chi sta per acquistare il croissant di Gilles.
Questa domanda è la stessa versione di Gilles, ed è stata postata su Programmers come esperimento per vedere come le diverse comunità affrontano una sfida di programmazione.

    
posta GlenH7 25.07.2013 - 20:42
fonte

6 risposte

26

Userei un algoritmo di punteggio. Ogni persona inizia con un punteggio pari a zero. Ogni volta che portano croissant, incrementa il loro punteggio di 1. Il punteggio di tutti i membri del team che non hanno portato croissant è decrementato di 1 / N. Pertanto, un punteggio pari a 0 significa che un membro del team non ha più o meno comprato.

Senza casualità, scegli la persona con il punteggio più basso tra quelli che saranno presenti.

Per aggiungere casualità, ordina l'elenco in base al punteggio e scegli a caso dall'elenco di tutti i membri del team con un punteggio negativo. Limitando i punteggi negativi, si garantisce che nessuno sarà troppo "fortunato" per molte settimane.

Il vantaggio di questo algoritmo è che non fa affidamento sul mantenimento dei record storici e consente facilmente l'aggiunta di nuovi membri del team in qualsiasi momento.

Potrebbe essere adattato per consentire alle assenze di essere relativamente comuni diminuendo il punteggio di solo i presenti per godersi i croissant.

    
risposta data 25.07.2013 - 22:05
fonte
7

Quello che farei, se dovessi sceglierlo, è prendere un cappello e mettere i nomi di tutti nel cappello una volta su piccoli pezzi di carta. Poi, ogni giorno, estraggo a caso il nome di qualcuno dal cappello, e quella è la persona che porta i croissant il giorno dopo. Quel foglio viene poi incollato su un tabellone, sotto "PORTARE I CROISSANTI DOMANI". La carta attualmente sul tavolo viene gettata via.

Avrei anche una scatola. Inizia vuoto. Ogni giorno, prima di disegnare i nomi, butto il contenuto della scatola nel cappello, poi sfoglio i fogli nel cappello e rimuovo tutti quelli che domani saranno assenti. I loro nomi vanno nella scatola.

Se è il momento di disegnare un nome e il cappello è vuoto, vorrei strappare un po 'di carta e aggiungere il nome di tutti una volta, quindi spostare i nomi di tutti quelli che saranno assenti domani alla scatola.

A causa di questi ultimi due passaggi, è possibile che lo stesso nome sia nel cappello più volte contemporaneamente. Se il nome che mi capita di disegnare è lo stesso del nome che c'è sulla lavagna, sposterei quella carta nella scatola, e poi disegnerei di nuovo.

Non dovrebbe essere troppo difficile tradurre questo sistema in un algoritmo nella tua lingua preferita.

    
risposta data 25.07.2013 - 20:56
fonte
6

Algoritmo, smalgoritmo. Utilizza 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)
)

Chi compra?

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

Dopo l'acquisto:

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

E poi imposta:

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

... perché sono vecchia scuola.

Non dovrebbe essere troppo difficile aggiungere un po 'di casualità modificando la prima query - magari aggiungendo un random () invece di ordinare per data last_purchase.

    
risposta data 25.07.2013 - 21:12
fonte
4

In realtà ho dovuto risolvere questo problema in qualche modo nel mondo reale:

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

Quello che succede è che le persone che hanno comprato le ciambelle "troppo" (a causa della sfortuna, andando a lavorare quando gli altri sono in ferie, ecc.) sono escluse dal pool fino a quando passeranno abbastanza acquisizioni per rimetterle sotto "diritto" "percentuale di acquisti.

Questo dovrebbe essere ampliato per gestire meglio l'assunzione di nuove persone anche se ...

Comunque, questo design ha funzionato molto bene per cambiare le variabili (chi è dentro, chi è fuori) e quando il programma deve essere (praticamente) infinito. Come bonus aggiuntivo, è facile determinarlo seminando il tuo RNG.

    
risposta data 25.07.2013 - 22:03
fonte
2

Non buono come alcune delle altre risposte già presentate, ma un altro modo di considerare il problema:

  1. Crea un elenco di tutti i dipendenti partecipanti
  2. Duplica l'elenco un sacco di volte (ad esempio, 1.000)
  3. Mescola l'elenco

Ogni pomeriggio, seleziona il prossimo croissant-bringer disponibile. Ogni mattina, il croissant-portatore incrocia il suo nome in cima alla lista.

L'elaborazione giornaliera è penna & semplice carta.

Nuovi assunti & Terminazioni Alumni probabilmente sarebbe meglio gestirlo creando una nuova lista. Se i cicli della CPU diventano sempre più costosi (o se hai 100 milioni di dipendenti e solo un Arduino di 1 gen), sarebbe facile riempire la lista originale con un numero appropriato di segnaposto.

Ulteriori informazioni (per richiesta).

Utilizzando questo approccio con un elenco arbitrariamente lungo, ottieni il vantaggio della trasparenza.

Non solo sai chi porterà i croissant domani, sai chi è in programma per portarli il giorno dopo, e così via. Ovviamente più lontano nel tempo si guarda, meno accurato sarà dovuto alle assenze, ecc.

Gli sviluppatori furbi che capiscono come appesantire i loro foglietti in un cappello non avranno tante opportunità di evitare i loro compiti di portare i croissant.

I whining non-dev che sostengono che i processati sono truccati possono facilmente rivedere i dati, arrivare a conclusioni sbagliate e uggiolare comunque.

    
risposta data 25.07.2013 - 22:40
fonte
1

Non casuale

Gestisci una lista ordinata. Se una persona è assente il giorno in cui dovrebbero acquistare, scambialo con la persona disponibile successiva. Alla fine la persona sarà presente e quindi comprerà croissant. Quindi, il contenuto della lista rimane lo stesso, ma le persone possono essere spostate o verso il basso a seconda degli assenti.

Le nuove persone vengono inserite nell'elenco dopo la posizione corrente. Le persone che abbandonano o terminano vengono rimosse dall'elenco. La posizione corrente aumenta di 1 ogni giorno, quando raggiunge la fine, tornerà all'inizio.

Questo presuppone che ci siano abbastanza persone nella lista per tenere conto del tempo medio di assenza per promuovere l'equità.

Casuale

Non possiamo semplicemente selezionare persone casuali ogni giorno perché ci saranno pregiudizi a breve termine, ad esempio lanciare una moneta 10 volte e potresti trovare le teste 8 e le code 2, quindi le teste verrebbero avvitate per il breve termine. Quindi, abbiamo bisogno di creare secchi di persone per mantenerlo equo.

Il bucket è determinato dal numero di volte in cui le persone hanno acquistato i crossiants in passato. Quindi, in questo caso, archiviamo un dizionario di persone e acquisti incrociati. Il giorno 1 tutti sono nel secchio zero. Poiché le persone comprano i croissant, saranno assegnati al prossimo bucket up, cioè 1, 2, ecc. La parte a caso sta selezionando dal pool di persone disponibili nel bucket. Il primo secchio disponibile è quello con il minor numero di acquisti. Se ci sono 10 persone nel secchio, scegli un numero casuale compreso tra 1 e 10 e chi acquista i croissant. Alle nuove persone viene assegnato il bucket più basso corrente, in modo che non finiscano per acquistare round extra di crossiants (anche se saranno subito nel pool di buy). Se nessuno è disponibile nel bucket più basso (sono tutti assenti), si passa al bucket successivo più alto. Ad esempio, diciamo che c'è un elenco di 10 persone. Il giorno 8, 8 persone sono nel secchio 1 e 2 nel secchio 0. Le due persone nel secchio 0 sono assenti. In questo caso, verrà utilizzato il bucket 1 e una persona finirà nel bucket 2. Tuttavia, le persone saranno sempre all'interno di alcuni acquisti incrociati (bucket) l'uno all'interno dell'altro, perché molto probabilmente la persona che si trova nel bucket 2 non sarà in il buy pool per un po '.

Potrebbero essere aggiunti dei tweaks per assicurarsi che la stessa persona non acquisti due giorni di fila e che ci siano alcuni casi limite da gestire, ma ciò aggiungerebbe un elemento di casualità oltre a mantenerlo corretto. Inoltre, si potrebbe voler mantenere separati gli effettivi acquisti di croissant rispetto al bucket corrente. Quando le persone se ne vanno, vengono rimosse dal secchio o contrassegnandole definitivamente assenti o cancellandole del tutto.

    
risposta data 25.07.2013 - 23:26
fonte

Leggi altre domande sui tag