Sprawdź, czyja kolej na zakup rogalików, z uwzględnieniem ewentualnych nieobecności

Zespół zdecydował, że każdego ranka ktoś powinien przynieść rogaliki dla wszystkich. Nie powinna to być ta sama osoba za każdym razem, więc powinien istnieć system określający, która kolej będzie następna. Celem tego pytania jest określenie algorytmu decydującego o tym, czyja kolej przyniesie rogaliki jutro.

Ograniczenia, założenia i cele:

• Który z kolei przyniesie rogaliki, zostanie ustalony poprzedniego popołudnia.
• Każdego dnia niektórzy ludzie są nieobecni. Algorytm musi wybrać kogoś, kto będzie obecny tego dnia. Załóżmy, że wszystkie nieobecności są znane z jednodniowym wyprzedzeniem, więc kupującego rogalika można ustalić poprzedniego popołudnia.
• Ogólnie rzecz biorąc, większość ludzi jest obecna przez większość dni.
• W trosce o sprawiedliwość wszyscy powinni kupować rogaliki tyle razy, ile inni. (Zasadniczo załóżmy, że każdy członek zespołu ma taką samą kwotę do wydania na rogaliki).
• Byłoby miło mieć jakiś element losowości, a przynajmniej postrzegany losowość, aby złagodzić nudę listy. Nie jest to trudne ograniczenie: jest to bardziej osąd estetyczny. Jednak ta sama osoba nie powinna być wybierana dwa razy z rzędu.
• Osoba, która przyniesie rogaliki, powinna wiedzieć wcześniej. Jeśli więc osoba P ma przynieść rogaliki w dniu D, to fakt ten należy ustalić w dniu poprzedzającym, w którym osoba P jest obecna. Na przykład, jeśli przynoszący rogalika jest zawsze określany dzień wcześniej, to powinna to być jedna z osób obecnych dzień wcześniej.
• Liczba członków zespołu jest na tyle mała, że ​​zasoby pamięci i komputera są praktycznie nieograniczone. Na przykład algorytm może polegać na pełnej historii tego, kto przyniósł rogaliki w przeszłości. Nawet kilka minut obliczeń na szybkim komputerze każdego dnia byłoby w porządku.

Jest to model rzeczywistego problemu, więc możesz kwestionować lub udoskonalać założenia, jeśli uważasz, że lepiej modelują scenariusz.

_{Pochodzenie 1: Dowiedz się, kto kupi rogaliki od Floriana Margaine.
Origin 2: Dowiedz się, kto kupi rogaliki od Gillesa.
To pytanie jest tej samej wersji, co Gilles, i zostało ponownie opublikowane w Programistach jako eksperyment, aby zobaczyć, jak różne społeczności podejmują wyzwanie programistyczne.}

Użyłbym algorytmu oceniania. Każda osoba zaczyna od zera. Za każdym razem, gdy przynoszą rogaliki, zwiększają ich wynik o 1. Wynik wszystkich członków zespołu, którzy nie przynieśli rogalików, zmniejsza się o 1 / N. Tak więc wynik 0 oznacza, że ​​członek zespołu nie kupił ani nie kupił zbyt mocno, ani zbyt słabo.

Bez losowości wybierz osobę o najniższym wyniku z listy osób, które będą obecne.

Aby dodać losowość, posortuj listę według wyniku i wybierz losowo z listy wszystkich członków zespołu z wynikiem ujemnym. Ograniczając się do wyników ujemnych, gwarantujesz, że nikt nie będzie zbyt szczęśliwy przez wiele tygodni.

Zaletą tego algorytmu jest to, że nie polega on na prowadzeniu rejestrów historycznych i łatwo pozwala na dodanie nowych członków zespołu w dowolnym momencie.

Można go dostosować, aby nieobecności były stosunkowo częste, zmniejszając wyniki tylko tych obecnych, aby cieszyć się rogalikami.

Gdybym musiał to wybrać, wziąłbym czapkę i umieściłem w niej imiona wszystkich na kawałkach papieru. Potem każdego dnia losowo narysowałem czyjeś imię z kapelusza, a to ta osoba przynosi rogaliki następnego dnia. Ten artykuł jest następnie sczepiany na desce pod „JUTRO PRZYNOSZĄCĄ ​​CROISSANTS”. Papier, który jest obecnie na planszy, zostaje wyrzucony.

Miałbym też pudełko. Zaczyna się pusty. Każdego dnia, przed narysowaniem imion, wrzucałem zawartość pudełka do kapelusza, a następnie przeglądałem papiery w kapeluszu i usuwałem wszystkich, którzy jutro będą nieobecni. Ich nazwiska znajdują się w pudełku.

Jeśli nadszedł czas, aby narysować imię, a czapka jest pusta, oderwałbym trochę papieru i dodałem raz imię każdego, a następnie przeniosłem nazwiska wszystkich, którzy jutro będą nieobecni do pudełka.

Ze względu na te dwa ostatnie kroki możliwe jest, że ta sama nazwa pojawi się w kapeluszu wiele razy na raz. Jeśli imię, które narysowałem, jest takie samo jak imię na planszy, przesunę ten papier do pudełka, a następnie narysuję ponownie.

Przetłumaczenie tego systemu na algorytm w wybranym przez Ciebie języku nie powinno być trudne.

Algorytm, smal Algorytm. Użyj bazy danych.

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

Kto kupuje

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

Po zakupie:

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

A następnie ustaw:

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

... bo jestem starą szkołą.

Dodanie odrobiny losowości nie powinno być zbyt trudne, poprawiając pierwsze zapytanie - być może dodając random () zamiast sortować według daty ostatniego zakupu.

W rzeczywistości musiałem rozwiązać ten problem w prawdziwym świecie:

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

Ludzie, którzy kupili pączki „za dużo” (z powodu pecha, idąc do pracy, gdy inni są na wakacjach itp.) Są wykluczani z puli, dopóki nie przejdzie wystarczająca liczba przejęć, aby przywrócić im „właściwy” procent zakupy.

Trzeba to jednak rozszerzyć, aby lepiej radzić sobie z zatrudnianiem nowych osób ...

W każdym razie ten projekt działał naprawdę dobrze do zmieniania zmiennych (kto jest, kto jest poza) i kiedy harmonogram musi być (praktycznie) nieskończony. Jako dodatkowy bonus, łatwo jest dokonać deterministycznego posiewu RNG.

Nie tak dobre, jak niektóre inne przedstawione już odpowiedzi, ale inny sposób spojrzenia na problem:

1. Zrób listę wszystkich uczestniczących pracowników
2. Powiel listę wiele razy (powiedzmy, 1000)
3. Potasuj listę

Każdego popołudnia wybierz następnego dostępnego rogalika. Każdego ranka przynoszący rogaliki przekreśla swoje imię i nazwisko na szczycie listy.

Codzienne przetwarzanie jest proste jak pióro i papier.

Nowi pracownicy i wypowiedzenia Najlepszym rozwiązaniem dla absolwentów byłoby stworzenie nowej listy. Jeśli cykle procesora znów staną się drogie (lub masz 100 milionów pracowników i tylko Arduino pierwszej generacji), łatwo byłoby posolić oryginalną listę odpowiednią liczbą miejsc zastępczych.

Więcej informacji (na żądanie).

Stosując to podejście z dowolnie długą listą, zyskujesz przejrzystość.

Nie tylko wiesz, kto jutro przyniesie rogaliki, ale wiesz, kto ma je przynieść następnego dnia i tak dalej. Oczywiście im dalej będziesz wyglądać, tym mniej dokładny będziesz z powodu nieobecności itp.

Podstępni deweloperzy, którzy zastanawiają się, jak zważyć kartki papieru w kapeluszu, nie będą mieli okazji uniknąć obowiązków związanych z przynoszeniem rogalików.

Narzekający nie-twórcy, którzy twierdzą, że przetwarzane są sfałszowane, mogą łatwo przejrzeć dane, dojść do niewłaściwych wniosków i skomleć.

Nie losowo

Utrzymaj uporządkowaną listę. Jeśli dana osoba jest nieobecna w dniu, w którym powinna kupić, zamień ją na następną dostępną osobę. W końcu osoba będzie obecna i kupi rogaliki. Tak więc zawartość listy pozostaje taka sama, ale osoby mogą być przenoszone lub podnoszone w dół w zależności od nieobecności.

Nowe osoby zostaną wstawione do listy po bieżącej pozycji. Osoby, które odeszły lub zakończyły pracę, są usuwane z listy. Bieżąca pozycja zwiększa się o 1 każdego dnia, gdy osiągnie koniec, wróci do początku.

Zakłada się, że na liście jest wystarczająca liczba osób, aby uwzględnić średni czas nieobecności w celu promowania uczciwości.

Losowy

Nie możemy po prostu wybierać losowych ludzi każdego dnia, ponieważ będą pojawiać się uprzedzenia krótkoterminowe, na przykład rzuć monetą 10 razy, a możesz wymyślić głowy 8 i ogony 2, więc głowy będą wkręcone na krótki czas. Musimy więc tworzyć wiadra ludzi, aby zachować sprawiedliwość.

Wiadro zależy od tego, ile razy ludzie kupowali crossiantów w przeszłości. Tak więc w tym przypadku przechowowalibyśmy słownik osób i kupno krzyżowe. Pierwszego dnia wszyscy są w koszyku zero. Gdy ludzie kupują rogaliki, zostaną przypisani do następnego segmentu, tj. 1, 2 itd. Losowa część to wybieranie z puli dostępnych osób w segmencie. Pierwszym dostępnym wiadrem jest ten z najmniejszą liczbą zakupów. Jeśli w wiadrze jest 10 osób, wybierz losową liczbę od 1 do 10, która kupuje rogaliki. Nowi ludzie otrzymują najniższy bieżący koszyk, więc nie kończą kupować dodatkowych rund crossiantów (chociaż od razu znajdą się w puli kupna). Jeśli nikt nie jest dostępny w najniższym segmencie (wszystkie są nieobecne), to przejdziesz do następnego najwyższego segmentu. Na przykład niech „ powiedzmy, że jest lista 10 osób. W dniu 8 8 osób jest w koszyku 1, a 2 w koszyku 0. Dwie osoby w koszyku 0 są nieobecne. W tym przypadku zostanie użyte wiadro 1, a jedna osoba skończy w wiadrze 2. Ale ludzie zawsze znajdą się w odległości kilku wzajemnych zakupów (wiader) w sobie, ponieważ osoba znajdująca się teraz w wiadrze 2 najprawdopodobniej nie będzie w kup pulę przez chwilę.

Można wprowadzić poprawki, aby upewnić się, że ta sama osoba nie kupi dwa dni z rzędu i że istnieją pewne przypadki krawędzi do załatwienia, ale dodałoby to element losowości, a także utrzymywało uczciwość. Ponadto, można chcieć zachować rzeczywiste zakupy rogalików w porównaniu z bieżącym koszykiem osobno. Gdy ludzie wychodzą, są usuwani z wiadra, oznaczając je na stałe nieobecne lub usuwając je całkowicie.