задача

[juan_gandhi]

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

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

Есть идейки? Мне эту задачку задавали года три назад; я предложил случайные блуждания, но интервьюёры моё решение не поняли. Ну не учили их вероятности. Неважно, однако. Меня больше интересует наличие решения.

Comments

[ded-maxim.livejournal.com]

А сообщения они друг другу посылать могут?

[luzhin.livejournal.com]

Или метки, скажем, на прямой оставлять.
Как мальчик-с-пальчик.

[cmm.livejournal.com]

пущай ходят туда-сюда с увеличивающейся раз от раза амплитудой, и пущай у первого робота амплитуда растёт быстрее чем у второго.

или я чего недопонял?

[nine_k]

+1

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

[spamsink.livejournal.com]

Случайные блуждания не гарантируют обязательности. Эту задачу я видел на форуме головоломок http://wu.webhop.org/ но уже не помню, как она называлась.

[spamsink.livejournal.com]

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

[ex-ex-zhuzh.livejournal.com]

именно-именно. если нет никаких меток, они так и будут всегда на одном и том же расстоянии друг от друга.

[goshen.livejournal.com]

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

[ex-ex-zhuzh.livejournal.com]

по условию они идентичны.

[selfmade.livejournal.com]

Так что, парашут-то остаётся, или они в потьмах бродят?

[ygam.livejournal.com]

Я знаю эту задачу.

[spamsink.livejournal.com]

В каком варианте - с парашютом или с неодновременной высадкой?

[arkanoid.livejournal.com]

Очевидно что задача решается если по условию они высаживаются не строго одновременно.

[itman.livejournal.com]

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

[opegs.livejournal.com]

variant: programmy raznye, parashutov net ==
tochka na ploskosti dolzhna peresech prjamuju x=y,
t.e. hodit' archimedovoj spiralju.

[birdwatcher.livejournal.com]

Надо поставить в них батарейки разной емкости.

[igorsereda.livejournal.com]

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

Если задачка практическая, то она сводится к разделению программ на первую и вторую за счет какого-то инпута/аутпута, типа оставления пахучих меток на прямой.

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

[igorsereda.livejournal.com]

Да, согласен с предыдущим оратором -- если они высаживаются не одновременно, тогда задача решается.

[kot-ivanovich.livejournal.com]

For any given robot it's easy: it has some hardware, which has some UID (say, MAC address of a NIC), which can be used to initialize random numbers generator. Otherwise it's tough...

[malaya-zemlya.livejournal.com]

You need an _infinite_ number of random bits for the solution to work at an arbitrarily large distance between robots. The 64 bits of MAC aren't enough.

[jusio.livejournal.com]

Прикрутить к роботам GPS и узнать их координаты. Либо узнать координаты роботов относительно обьекта, координаты которого известны и плясать от этого. Либо связать их верёвкой (крепкой) и заставить вращаться каждого робота вокруг своей оси. Вариантов куча.

[glocka.livejournal.com]

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

[selfmade.livejournal.com]

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

[109.livejournal.com]

и этот человек пенял на то, как я задачи формулирую.

задай ещё про самолёт на беговой дорожке.

[piggymouse.livejournal.com]

О, расскажи.

интервью

[freedom_of_sea.livejournal.com]

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

Re: интервью

[ivan-gandhi.livejournal.com]

Мне не очевидно было, что она идиотская. Идиотские вопросы бывают, например, такие: "какой ваш главный недостаток". Правда, на этот вопрос есть хороший ответ.

[ex-chrobin.livejournal.com]

высадить их на прямую и выдать эту задачу

[eslitak.livejournal.com]

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

[boriskogan.livejournal.com]

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

[ivan-gandhi.livejournal.com]

Если след оставлять... то да.

[109.livejournal.com]

так что, могут они следы оставлять?

[piggymouse.livejournal.com]

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

[slonopotamus.livejournal.com]

Если с парашютами то знаю и даже решил :)

Робот №88

[lev-shubnikov.livejournal.com]

Простите, читатели, глупость вчера про роботов написал.
Удалю, чтобы не позориться...

А 2 задачки Димы Тихонова оставлю :)
Задача 1: Состав вагонов стоит соединенный в круг на круговом пути. Есть мел, которым можно рисовать на вагонах, но они, возможно, уже изрисованы до нас. Наша задача сосчитать число вагонов.
Задача 2: Линейный список, возможно замкнутый на себя. Как узнать, замкнут он на себя, или имеет конец?

Re: Робот №88

[furia-krucha.livejournal.com]

Задача 2: Линейный список, возможно замкнутый на себя. Как узнать, замкнут он на себя, или имеет конец?
Надо пустить по списку два бегунка, один из которых движется в два раза быстрее второго. Если список замкнут (даже не обязательно в кольцо, можно "с хвостиком") --- бегунки рано или поздно встретятся. Нечто вроде

(defun cyclic-p (list)
    (let ((slow list)
	  (fast (cdr list))
	  (odd nil))
      (while (not (eq fast slow))
        (set 'fast (cdr fast))
        (if odd (set 'slow (cdr slow)))
        (set 'odd (not odd)))
      slow))