Узнайте, чья очередь покупать круассаны, с учетом возможного отсутствия

Команда решила, что каждое утро кто-то должен приносить круассаны для всех. Каждый раз это не должен быть один и тот же человек, поэтому должна существовать система, определяющая, чья очередь за ним. Цель этого вопроса состоит в том, чтобы определить алгоритм решения, чья очередь будет приносить круассаны завтра.

Ограничения, предположения и цели:

• Чья очередь приносить круассаны, определится днем ​​ранее.
• В любой день некоторые люди отсутствуют. Алгоритм должен выбрать кого-то, кто будет присутствовать в этот день. Предположим, что все пропуски известны за день, поэтому покупателя круассана можно определить накануне.
• В целом, большинство людей присутствуют в большинстве дней.
• В интересах справедливости каждый должен покупать круассаны столько раз, сколько другие. (По сути, предположим, что у каждого члена команды есть одинаковая сумма денег, которую можно потратить на круассаны.)
• Было бы неплохо иметь некоторый элемент случайности или, по крайней мере, воспринимаемую случайность, чтобы облегчить скуку реестра. Это не жесткое ограничение: это скорее эстетическое суждение. Однако один и тот же человек не должен выбираться дважды подряд.
• Человек, который приносит круассаны, должен знать заранее. Таким образом, если человек P должен принести круассаны в день D, то этот факт следует определить в какой-то предыдущий день, когда присутствует человек P. Например, если средство доставки круассанов всегда определяется накануне, то это должен быть один из людей, присутствующих накануне.
• Количество членов команды достаточно мало, поэтому ресурсы хранения и вычислительные ресурсы практически не ограничены. Например, алгоритм может опираться на полную историю того, кто принес круассаны в прошлом. До нескольких минут вычислений на быстром ПК каждый день будет в порядке.

Это модель реальной проблемы, поэтому вы можете оспорить или уточнить допущения, если считаете, что они лучше моделируют сценарий.

_{Происхождение 1: Узнайте, кто собирается купить круассаны от Флориана Маргэйна.
Происхождение 2: Узнайте, кто собирается покупать круассаны от Жиля.
Этот вопрос является той же версией, что и Жиль, и был повторно опубликован на Программистах в качестве эксперимента, чтобы увидеть, как различные сообщества решают задачи программирования.}

Я бы использовал алгоритм подсчета очков. Каждый человек начинает с нуля. Каждый раз, когда они приносят круассаны, увеличивайте их счет на 1. Оценка всех членов команды, которые не принесли круассаны, уменьшается на 1 / N. Таким образом, оценка 0 означает, что у члена команды нет ни того, ни другого, ни купленного.

Без случайности выберите из списка тех, кто будет присутствовать, человека с наименьшим количеством баллов.

Чтобы добавить случайность, отсортируйте список по баллам и выберите случайным образом из списка всех членов команды с отрицательным баллом. Ограничивая отрицательные оценки, вы гарантируете, что никому не повезет в течение многих недель.

Преимущество этого алгоритма состоит в том, что он не зависит от ведения исторических записей и позволяет легко добавлять новых членов команды в любой момент времени.

Он может быть адаптирован для учета относительно частых пропусков, уменьшая баллы только у тех, кто наслаждается круассанами.

Что бы я сделал, если бы мне пришлось это выбрать, это взять шляпу и положить имена всех в шляпу один раз на маленькие кусочки бумаги. Затем каждый день я наугад вытягивал чье-то имя из шляпы, и именно этот человек приносит круассаны на следующий день. Затем этот документ помещается на доске под заголовком «ПРИНЯТЬ ЗАВТРА КРУАССАНОВ». Бумага, которая в настоящее время находится на доске, выбрасывается.

У меня также была бы коробка. Это начинается пустым. Каждый день перед тем, как нарисовать имена, я складывал содержимое коробки в шляпу, затем просматривал бумаги в шапке и удалял всех, кто будет отсутствовать завтра. Их имена идут в поле.

Если пришло время нарисовать имя, а шляпа пуста, я порвал бы еще бумагу и добавил бы имя каждого, а затем переместил бы имена всех, кто будет отсутствовать завтра, в коробку.

Из-за этих двух последних шагов, одно и то же имя может быть в шапке несколько раз одновременно. Если имя, которое я нарисую, совпадает с именем на доске, я переместил бы эту бумагу в коробку, а затем снова нарисовал.

Не должно быть слишком сложно перевести эту систему на алгоритм на выбранном вами языке.

Алгоритм, маленький алгоритм. Используйте БД.

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

Кто покупает?

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

После того, как они покупают:

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

И затем установить:

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

... потому что я старая школа.

Не должно быть слишком сложно добавить немного случайности, подправив первый запрос - возможно, добавив random () вместо сортировки по дате last_purchase.

Я действительно должен был решить эту проблему несколько в реальном мире:

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

Люди, которые купили пончики «слишком много» (из-за неудачи, ходить на работу, когда другие в отпуске и т. Д.), Исключаются из пула, пока не поступит достаточное количество приобретений, чтобы вернуть их под «правильный» процент от покупки.

Это должно быть расширено, чтобы лучше справляться с наймом новых людей, хотя ...

В любом случае, этот дизайн действительно хорошо работал для изменения переменных (кто входит, кто отсутствует) и когда график должен быть (практически) бесконечным. В качестве дополнительного бонуса легко сделать детерминированный, посеяв свой ГСЧ.

Не так хорошо, как некоторые другие ответы, уже представленные, но другой взгляд на проблему:

1. Составьте список всех участвующих сотрудников
2. Дублируйте список много раз (скажем, 1000)
3. Перемешать список

Каждый день выбирайте следующий доступный круассан. Каждое утро создатель круассанов вычеркивает свое имя из верхней части списка.

Ежедневно обрабатывать ручку и бумагу просто.

Новые наймы и увольнения Выпускникам лучше всего заняться составлением нового списка. Если циклы ЦП снова когда-нибудь подорожают (или у вас 100 млн. Сотрудников и только Arduino 1-го поколения), тогда будет легко засолить первоначальный список с соответствующим количеством заполнителей.

Больше информации (по запросу).

Используя этот подход с произвольно длинным списком, вы получаете преимущество прозрачности.

Мало того, что вы знаете, кто принесет завтраки с круассанами, вы знаете, кто должен принести их на следующий день, и так далее. Конечно, чем дальше вы выглядите, тем менее точным вы будете из-за отсутствия и т. Д.

У подлых разработчиков, которые выясняют, как взвесить листки бумаги в шляпе, не будет такой большой возможности избежать своих обязанностей по доставке круассанов.

Ноющие не-разработчики, которые утверждают, что обработанные фальсифицированы, могут легко просмотреть данные, прийти к неправильному выводу и все равно скулить.

Не случайно

Вести упорядоченный список. Если человек отсутствует в день, который он должен купить, обменяйте его следующим доступным человеком. В конце концов человек будет присутствовать и, таким образом, купить круассаны. Таким образом, содержимое списка остается неизменным, но люди могут быть перемещены или вниз в зависимости от отсутствия.

Новые люди вставляются в список после текущей позиции. Люди, которые вышли или прекратили работу, удаляются из списка. Текущая позиция увеличивается на 1 каждый день, когда она достигает конца, она возвращается к началу.

Это предполагает, что в списке достаточно людей, чтобы учесть среднее время отсутствия для продвижения справедливости.

случайный

Мы не можем просто выбирать случайных людей каждый день, так как это приведет к краткосрочному смещению, например, подбросим монету 10 раз, и вы можете поднять головы 8 и хвосты 2, так что головы будут закручены на короткий срок. Итак, нам нужно создавать группы людей, чтобы это было честно.

Ведро определяется тем, сколько раз люди покупали кроссанты в прошлом. Таким образом, в этом случае мы будем хранить словарь людей и покупок с перекрестными ссылками. В первый день все в нулевом ведре. Когда люди покупают круассаны, они будут назначены следующему сегменту, то есть 1, 2 и т. Д. Случайная часть выбирается из пула доступных людей в сегменте. Первое доступное ведро - это то, которое покупает меньше всего. Если в ведре 10 человек, выберите случайное число от 1 до 10 и тот, кто покупает круассаны. Новым людям назначается наименьшее текущее ведро, поэтому они не заканчивают тем, что покупают дополнительные раунды кроссантов (хотя они будут в пуле покупок сразу). Если никого нет в нижнем ведре (они все отсутствуют), то вы переходите к следующему верхнему ведру. Например, пусть скажем, есть список из 10 человек. На 8-й день 8 человек находятся в ведре 1, а 2 - в ведре 0. Два человека в ведре 0 отсутствуют. В этом случае будет использовано ведро 1, и один человек окажется в ведре 2. Но люди всегда будут в пределах нескольких перекрестных покупок (ведер) друг с другом, потому что человек, который сейчас находится в ведре 2, скорее всего, не будет в купить пул на некоторое время.

Можно добавить твики, чтобы убедиться, что один и тот же человек не покупает два дня подряд, и есть некоторые крайние случаи, которые нужно обработать, но это добавит элемент случайности, а также сохранит справедливость. Кроме того, можно хотеть держать фактические покупки круассана против текущего ведра отделенными. Когда люди уходят, их извлекают из ведра, либо помечая их как отсутствующие, либо удаляя их вообще.