Пролог
При устройстве на работу меня уже второй раз спрашивают одну и ту же задачу про мышей и отраву. Они как будто из одной методички вопросы берут. Обычно такие логические задачи задают компании, которые высокого мнения о себе. Думаю настало время выдать исчерпывающий ответ на эту тему.
Постановка задачи:
Есть 1000 одинаковых колб с прозрачной жидкостью. В 999 колбах вода, а в одной случайной колбе - отрава. Если мышь попробует отраву, то она погибнет через 1 час (тот час же).
--Как при помощи 10 мышей найти колбу с отравой? Спойлер: Угощать только тех мышей, чей номер равен взведённому биту в двоичном номере колбы. И так для каждой колбы.
--Сколько времена потребуется, чтобы найти отраву? Спойлер: 1 час
--Как при этом погубить как можно меньше мышей? Спойлер: приоритет надо отдавать тем номерам колб, у которых меньшее количество взведенных бит. Меньшая сумма бит.
--А если участие мыши в опыте стоит 100 рублей, а отдельно приобретаемая лицензия на её убийство - тысячу? Как минимизировать расходы на эксперимент?
Пояснения:
1--Любая концентрация отравы приводит к гибели мыши.
2--Метаболизм каждой отдельной мыши не одинаковый и является случайной величиной. После получения отравы одна мышь погибнет через 55 мин, другая через 45 мин, третья через 1 мин. Но через час после получения отравы точно никто не выживет.
I--Иногда задачу перефразируют в контексте "компьютеры и вирусы". Якобы есть 200 программ, одна программа с вирусом и есть 9 DeskTop-ов для проверки. Вирусная программа через неделю после установки сносит OS, стирает весь жесткий диски, выжигает электронную лучевую трубку монитора в 7 местах и прочее. Надо за 1 неделю выявить эту бажную программу.
II--На сайте LeetCode задача и вовсе перефразирована в контексте бедных свинюков (poor-pigs).
458. Poor Pigs
There are buckets buckets of liquid, where exactly one of the buckets is poisonous. To figure out which one is poisonous, you feed some number of (poor) pigs the liquid to see whether they will die or not. Unfortunately, you only have minutesToTest minutes to determine which bucket is poisonous.
You can feed the pigs according to these steps:
Choose some live pigs to feed.
For each pig, choose which buckets to feed it. The pig will consume all the chosen buckets simultaneously and will take no time. Each pig can feed from any number of buckets, and each bucket can be fed from by any number of pigs.
Wait for
minutesToDieminutes. You may not feed any other pigs during this time.After
minutesToDieminutes have passed, any pigs that have been fed the poisonous bucket will die, and all others will survive.Repeat this process until you run out of time.
Given buckets, minutesToDie, and minutesToTest, return the minimum number of pigs needed to figure out which bucket is poisonous within the allotted time.
Определения
Для понимания дальнейшего разговора надо вспомнить вот этот набор определений:
бит - разряд в десятичной представлении числа. Бит может принимать только значение 0 или 1.
триггер - физический прибор для хранения одного бита информации.
регистр - массив триггеров. Физический прибор для хранения целых чисел.
взведённый бит - тот бит, который равен единице. Например в десятичном числе 8=0b1000 взведенный бит - это 3ий. В числе 4=0b100 взведенный бит - это 2. Отсчет от нуля справа налево.
Решение
По сути это задача на знание двоичной системы счисления. Те, кто умеют переводить из dec в bin скорее всего её решит.
Фаза 1: Занумеровать пробирки
Каждой пробирке надо поставить в соответствие десятично число от 1 до 1000. Можно на каждую пробирку наклеить номер.
Фаза 2: Заполнить таблицу двоичного представления чисел номеров колб
Как известно, в мире существует множество систем счисления. Вот самые распространенные: двоичная, восьмеричная, десятичная и шестнадцатеричная. Мы будет работать с десятичной и двоичной.
Номер колбы, dec | Номер колбы, bin | Количество взведенных битов в номере колбы |
0 | 00_0000_0000 | 0 |
1 | 00_0000_0001 | 1 |
2 | 00_0000_0010 | 1 |
3 | 00_0000_0011 | 2 |
.... | .... | |
999 | 11_1110_0111 | 8 |
1000 | 11_1110_1000 | 6 |
вот первые несколько номеров
К слову, число ноль тоже надо использовать для перечисления колб.
Фаза 3: Занумеровать мышей
Каждой мыши надо присвоить порядковый номер. От нуля до 9. Мышь будет выступать в качестве бита (триггера).
Фаза 4: Мышь это бит
Мышей мы занумеровали, чтобы сделать из массива мышей воображаемый регистр.
Фаза 5: угощение мышей
А теперь настало время угощать мышей. Делать это надо аккуратно. Сейчас объясню как. Мы берём пробирку, смотрим на ее номер, переводим номер в двоичное представление, выписываем номера установленных в 1 битов и даем испить из этой пробирки только тем мышам, у которых номер совпадает с номером установленного единичного бита.
Пример:
Вот колба 564. Бинарное представление 564=0b 0010_0011_0100. Установленные биты это:2,4,5,9. Это значит, что из колбы 564 надо дать попробовать по капле мышам 2, 4, 5 и 9 . Остальных пропустить.
Номер мыши --> | 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 | номер пробирки \/ |
двоичное представление номера пробирки | 1 | 0 | 0 | 0 | 1 | 1 | 0 | 1 | 0 | 0 | 564 |
угостить 9 | угостить 5 | угостить 4 | угостить 2 |
И так для всех 1000 колб. Берем колбу и угощаем из нее от нуля до 9 мышей в зависимости от номера колбы. У нас не будет такого, что из одной колбы получат порцию все мыши, так как нет колбы с номером 11_1111_1111=1023.
Получается, что каждая мышь получит коктейль составленный из половины всех пробирок. Нулевая мышь попробует жидкость из всех нечетных пробирок. Вторая мышь попробует из 2; 3; 6; 7; 10; 11 и т д. И так далее. Можно сначала аккуратно составить коктейли, а затем вручить их мышам. Либо все коктейли получатся отравлены, либо частично отравлены, либо все с водой. Тут уж как повезёт.
Все эти коктейли можно приготовить очень быстро, если есть автоматический лабораторный дозатор.
После этого можно засекать 1 час, садиться и просто ждать. Через час должно умереть от 0 до 9 мышей.
Фаза 6: Анализ последствий эксперимента
Мы подбираем погибших мышей, выписываем их номера и составляем двоичное число в котором установлены в один те разряды, которые соответствуют номерам погибших мышей. Переводим это двоичное число в десятичное и , таким образом , мы и получим десятичный номер той пробирки в которой и была отрава. Таким образом, мы за один час найдем номер с отравленной колбой.
Если ни одной мыши не погибло, значит отрава была в нулевой колбе. Её как раз никому не наливали.
Фаза 7: Как при этом погубить как можно меньше мышей?
Более сложная вариация этой классической задачи состоит в том, что накладывает дополнительное ограничение, что надо по возможности умертвить как можно меньше мышей. При этом обычно уменьшают количество исходных пробирок до 100. Решается это достаточно просто. При нумерации пробирок надо отдавать предпочтение тем номерам в которых меньше всего установленных в 1 битов. Вот так. Можно сказать, что появляются новые виртуальные номера (оптимальные номера) для колб.
Как можно заметить, оптимальный номер колбы вовсе не равен её двоичному представлению. Это какая-то другая кодировка. Назовем её кодировка по возрастанию количества установленных в единицу бит. При малом количестве колб, скажем до 200 лучше задействовать именно её.
При умной кодировке для поиска отравы среди 100 колб в жертву придется принести максимум три мыши из 10. А при наивной кодировке погибнет аж 6 мышей! Вот такие пирожки с капустой, понимаете?
А в остальном всё то же самое.
N мышей могут проверить 2^N колб за 1 раунд.
Количество мышей | Количество пробирок |
1 | 1 |
2 | 4 |
4 | 16 |
8 | 256 |
10 | 1024 |
Мы могли бы и в 1023-х пробирках найти отраву за 1 час. Число 1000 было выбрано только лишь, чтобы дезориентировать читателя.
Итоги
Вот такие вот препоны чинят соискателям при трудоустройстве. Лично мне хотелось, чтобы в работе было по более практических задач, а не придуманной работы.
Тем не менее, теперь и Вы умеете решать классическую задачу про мышей и отраву и можете объяснить решение другим.
Как видите двоичная кодировка далеко не всегда самая оптимальная. Вспомните хотя бы коды Грея для кодировки диска абсолютных энкодеров. Есть ещё код Джонсона и прочие двоичные коды.
Если Вам при устройстве на работу задают эту задачу, то сначала сделайте вид, что Вы никогда не слышали про эту задачу, задумайтесь на 20...40 секунд и только потом начните воспроизводить это решение.
Ссылки
№ | Название | URL |
1 | Загадка о тысяче пробирок | |
2 | Аналитика по задаче | https://docs.google.com/spreadsheets/d/1DN4wJo3kCX1mzBhXZqNcawi1d3Xey24ArS25zyAEaD4/edit?gid=0#gid=0 |
3 | Задача о двоичной мыши и тысяче пробирок | https://vk.com/@thecode.media-zadacha-o-dvoichnoi-myshi-i-tysyache-probirok |
4 | Задача о двоичной мыши и тысяче пробирок | |
5 | Задача о двоичной мыши и тысяче пробирок | |
7 | Задача про две ёмкости для жидкости | |
8 | Сканирование шины RS485 (битовая логика в действии) | |
6 | Ликбез по формулам google spreadsheets | https://support.google.com/docs/answer/3098245?sjid=8977904692612096953-EU |
