среда, 29 октября 2008 г.

Задача о шляпах от Microsoft

На лестнице стоят 4 человека. Самый верхний стоит на ступеньке, спрятанной за непроницаемой стеной и не видит никого. Все остальные видят только вышестоящих: A видит B и С, B видит C, С видит стену.

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

Дополнительные условия: человечки не могут поворачиваться, не могут переговариваться и перемещаться по лестнице, так же они не могут блефовать и ломать стену.

ЗЫ: Выглядит это примерно так:

28 комментариев:

zwitter комментирует...

ну попробуем.
если задача от микрософта, то подсознательно жду подставы :)

если на B и C шляпы одинакового цвета, то A
иначе он может угадывать с вероятностью 1/2.

какова ценность чувака за стеной ?

caezar комментирует...

Тю. Если на Б и С одинаковые, то А сразу говорит. Если нет, то А молчит и Б понимает что у них с С разные и сразу говорит

Анонимный комментирует...

Плохой перевод. В задаче не сказано что ктото должен чтото вслух сказать. В задаче сказано "поймёт". А это слово означает обычно нечто происходящее молча

sash_ko комментирует...

2Анонимный: это не перевод. но замечание правильное, ничего не сказано, как один из чувачков сообщит о своем озарении

sash_ko комментирует...

2caezar: в точку! если у B и C разные цвета, A молчит, и B видит какой цвет у C, то ему должно стать все понятно. главное, как заметил, Анонимный, что бы чувачки издавали звуки

Анонимный комментирует...

Ещё раз замечу что издавать звуки им запрещено по условиям задачи - так как это попадает под термин "переговариваться"

zwitter комментирует...

+1 анонимусу.
плюс они не могут договариваться заранее о плане угадывания.

Анонимный комментирует...

Вариант - если помещение освещено то по отсвету на стене или светлой шляпе впереди стоящего довольно легко определить тёмная шляпа или светлая - тока что проверил с листом бумаги ; )

Анонимный комментирует...

Также не запрещено закатывать вверх глаза и пытатся рассмотреть поля шляпы : )

Анонимный комментирует...

Короче задачка бы была красивей будь она сформулирована так, чтоб не допускала хаков. Ну например в терминах програмных объектов с чётким интерфейсом через который попадает информация о окружении и через который объект однозначно ограничен в методах комуникации. Как результат испытуемого можно просить - напишите AI алгоритм определения цвета собственной шляпы для каждого объекта.

zwitter комментирует...

анонимус, при чем тут AI?

вам построить алгоритм клональной селекции или нейронную сеть ? не пишите бред...

zwitter комментирует...

зачем вам хаки? условие предельно простое.

sash_ko комментирует...

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

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

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

sash_ko комментирует...

я не знаю точного ответа, но думаю, что решение, предложенное caezar, правильное - все просто и без хаков :)

Анонимный комментирует...

> зачем вам хаки? условие предельно простое.

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

Лично мне бы было на интервью довольно интересен сам факт того что человек будет пробовать искать хаки вне плоскости "математики" но и тем не менее стараясь выполнить условия задачи.

Ключевые слова "будет пробовать".

А не тушеваться из-за того, что его вариант посчитают недостаточно "взрослым" (на самом деле это ж очевидно, что закатив глаза можно элементарно увидеть цвет своей шляпы не снимая её ;)

zwitter комментирует...

2сашко

"Кто из них первый поймет" - "поймет" - не значит "скажет".

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

ну нафига придумывать несуществующую легенду. есть данные, есть условия.

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

zwitter комментирует...

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

sash_ko комментирует...

"Кто из них первый поймет" - "поймет" - не значит "скажет"
но и не значит, что не скажет ;)

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

sash_ko комментирует...

кстати, задачу про гномов на девелоперсах - нифиговые там баталии развернулись :)

Анонимный комментирует...

Я когда в первый раз нанимался мне загадали 3 загадки из разряда почему канализационные люки круглые (в том числе и про люки). На все я практически мгновенно ответил, после чего последовал комент типа: "ну да, задачки известные", хотя я реально их слышал впервый раз - было чертовски обидно (хотя и взяли меня). Собеседуясь через 3 года второй раз, и услышав знакомую мне задачку на указатели (как узнать что в списке нет петель) я (весьма обрадовавшись) на всякий случай минут 10 повыпендривался чёта там рисуя на бумажке и придумывая всякие неправильные решения перед тем как сказать верное.

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

Begemot комментирует...

>>>Ещё раз замечу что издавать звуки им запрещено по условиям задачи - так как это попадает под термин "переговариваться"

Им запрещено "переговариваться",но не запрещено 1 раз сказать их виденье правильного ответа. А фраза
"так же они не могут блефовать" означает что все-таки какой-то версии от них ждут

Fester комментирует...

Ба, Саня, какие люди :)

sash_ko комментирует...

О, Тимоха, ты? :)

Fester комментирует...

А то :)

Анонимный комментирует...

Я так понимаю, что никто из человечков самостоятельно угадать не может: либо A либо B.

Andrey комментирует...

Ну на фига нужен мистер D, который за стеной??

Andrey комментирует...
Этот комментарий был удален автором.
sash_ko комментирует...

2Анонимный: самостоятельно может угадать только А, когда у В и С шляпы одинакового цвета.

2Andrey: с тремя чувачками задача бы сильно упрощалась: было бы 2 шляпы одного цвета и одна другого, в таком случае А всегда бы знал цвет своей шляпы, а В мог знать если у них с А шляпы одинакового цвета. ставить D не за стену не имеет смысла, тогда тоже все было бы ясно сразу. короче, наличие D делает задачу задачей :)