Давно ли вы участвовали в лотерее или розыгрыше? Приходилось ли вам самим их устраивать? Даже если ответы: никогда и нет, уверен, что вы знаете что это такое.
А какие у вас ассоциации от слов «лотерея» и «розыгрыш»? У меня — разноцветные шары с номерами и лотерейная машина, из которой разноцветные шары выпадают по одному и определяют победителя.
Вот и мне некоторое время назад понадобилось “определить” победителей розыгрыша бесплатных места на курс “Разработчик Java” в Otus.ru. Задача звучала просто: есть N email-ов, нужно выбрать среди них случайным образом M email-ов тех, кто будет учиться бесплатно.
Сложность задачи была в том, что это были email-ы всех, кто успешно прошел входное тестирование курса. То есть email-ы программистов. Я представил себе, как я “достаю из кармана” M email-ов и говорю: “Вот эти победили”. И… мне никто не верит. Даже если победители начинают радостно писать в общий чат: “Спасибо, как мы рады!”, мне все равно никто из оставшихся не поверит. Да я бы и сам не поверил, если бы мне просто сказали «победили эти».
Программистам мало сказать кто победил, надо доказать что это действительно случайные победители, и что в общем списке действительно был их email, и что вероятность попасть в победители у всех равна.
Вот в таких условиях нужно было придумать как разыграть места. В этой заметке, я хочу предложить вам мое решение этой задачи. Буду рад комментариям и особенно замечаниями об убедительности моего решения. Вы бы стали обоснованно спорить с результатами, если бы ваш email был в общем списке?
Итак, как провести розыгрыш призов среди программистов:
- Убрать из выбора организатора розыгрыша. Выбирать должен робот.
- Сделать робота открытым, чтобы любой мог посмотреть как он выбирает.
- Сделать случайный выбор псевдослучайным. Так, чтобы любой, кто знает зерно последовательности, его мог повторить.
- И при этом, формировать зерно псевдослучайности на случайности материальной.
- Выложить в общий доступ… email-ы? Чтобы каждый мог найти себя в списке? Нет, этого наши пользователи не оценили бы. Но каким-то образом дать проверить, что ты в списке, нужно.
Первое, что было логично сделать — поручить выбор программе. Написать лотерейную машину, которая бы решала кто победил. Коды моей машины вы можете посмотреть в моем аккаунте на github.
Она состоит из класса для чтения email-ов, класса который производит выбор “шаров” с индексами победителей и класса, который все запускает.
С получением списка email-ов все просто. Их надо прочитать из файла. Сначала я хотел читать email-ы и имена из csv файла, но потом оставил только email-ы, а csv и библиотека, которая его читает, остались.
Результат прочтения email-ов — List я передаю в лотерейную машину. Кроме этого, она на вход получает количество победителей. И еще ей можно задать seed — зерно псевдослучайной последовательности. Его можно задать числом, или строкой. Во втором случае зерном будет hash от строки.
Если у вас есть seed, то лотерейная машина будет выдавать одну и туже “случайную” последовательность победителей при каждом запуске. Случайную, но псевдо. Что, собственно, нам и надо.
Хорошо, список с email-ми у нас есть, лотерейная машина есть, и она использует в работе класс java.util.Random, который дает нам псевдослучайную последовательность на основе seed-а.
Теперь, для успеха нам недостает простой вещи: случайного seed-a — зерна последовательности. Так чтобы он был случайный, но чтобы мы могли его запомнить. Я решил в качестве источника такой материальной случайности использовать содержимое чата. Последние несколько сообщений передать в машину, чтобы она вычислила себе seed.
Все, кто пришли на розыгрыш, могли писать в чат когда угодно и что угодно. Подделать сообщения в чате, так чтобы подгадать с определением hash-а? Я не знаю как это сделать. Кроме того, я попросил желающих что-нибудь в чат написать прямо перед запуском машины.
Как это было, можно посмотреть в записи Дня открытых дверей на youtube.
Мы запустили лотерейную машину и получили победителей. Потом запустили ее еще раз и получили тех же самых.
После чего я предложил изменить текст, и удалил последнее сообщение. Со словами: “а теперь посмотрим как повлиял этот последний комментарий на результат”, я запустил машину и среди результатов был email того кто этот последний комментарий написал. Если бы он его не писал, приз был бы у него. Конечно он это заметил. Конечно мы все это заметили. И победители поблагодарили автора комментария за подарок.
Выкладывать в github email-ы мы конечно не стали. Но в репо вы можете посмотреть файл в котором записаны “обфусцированные” email-ы.
А как бы вы разыграли призы среди программистов? Понятен ли код и принцип работы машины?
Автор: Tully
