17 июл. 2009 г.

Задачка: Роботы-парашютисты

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

Каждый робот после посадки оставляет в месте приземления парашют.
Далее роботы начинают действовать в соответствии с заложенной в них программой. За один шаг программы робот может проверить, есть ли в его ячейке какой-нибудь парашют (но не может проверить, есть ли в ячейке другой робот!), и может при желании сдвинуться влево или вправо на одну ячейку. Программы всех роботов выполняются с одинаковой скоростью.
Количество роботов неизвестно. Но это количество — конечное число.

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

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

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

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

Vladimir Dolzhenko комментирует...

@Nodir:
роботы не мешают друг другу, т.е. их может быть в одной ячейке сколько угодно. Парашют так же не создаёт преград - парашют является меткой. Требуется получить программу для роботов, которая заставит их собраться всем когда-нибудь в одном месте.

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

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

Andrey ``Bass'' Shcheglov комментирует...

1. Знают ли роботы о своём количестве "в рантайме"?
2. Можно ли разных роботов запрограммировать по-разному?
3. Можно ли, программируя роботов, научить их отличать одно направление ленты от другого (т. е., для определённости, чтобы они одно направление одинаково считали направлением "вперёд", а другое -- "назад")?

Andrey ``Bass'' Shcheglov комментирует...

4. Может ли в одной ячейче находиться более одного парашюта? Т. е. возможна ли Бозе-конденсация парашютов в одном квантовом состоянии?

5. Может ли робот при своём перемещении из ячейки с парашютами захватить все парашюты с собой (т. е. снять булевский флаг "в ячейке есть парашюты"?

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

Некоторый уточнения данные по GTalk:

me: привет! :)

Vladimir: салют

me: я там еще комментарий написал, как то условия все равно не очевидны хотел попробовать решить задачку в рамках изучения OCaml, Сорри, что пристаю с уточнениями

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

me: ааа, то есть робот может двинуться либо вправо либо влево
я то думал, что система двухмерная

Vladimir: На одномерную бесконечную ленту десантируют роботов.

me: лента широкая и поделена на ячеки как шахматная доска

Vladimir: широкая, но 1-мерная

me: точно, надо читать внимательнее

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

me: а парашют от парашюта отличить может?

Vladimir: т.е ?

me: ну то есть: свой, чужой, уже видел

Vladimir: ну если есть память

me: ну чтобы использовать парашюты как метки, что уже был в ячейке

Vladimir: он может считать свою позицию относительно своего места посадки

me: все, точно, все таки видимо я уже окончательно испорчен embedded developing-ом, когда каждый байт считать надо :)

Vladimir: :)))))))))))))))))))))
я же сказу сказал - память есть сколько угодно и под какие угодно структуры
После того, как роботы соберутся вместе, не обязательно, чтобы они оставались в этом положении или остановились. Достаточно лишь, чтобы за конечное число шагов гарантированно наступила ситуация, когда все роботы находятся в одной и той же ячейке ленты.

me: угу, но жучок то в голове уже сидит (Оптимизация использования памяти!!!)

Vladimir: :)) я понимаю

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

Никто не решил эту задачу?

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

Должен остаться только один. Все роботы как роботы, а один терминатор. Он двигается по расширяющейся амплитуде и убивает всех встречных роботов и пожирает их. Предварительно хачит все их коды доступов, пароли и явки, чтобы если чё, можно было сойти за сожранного(вспоминаем тематичные игры/фильмы). Попутно запоминает сколько сожрал, сколько парашютов видел. Вот как то так. Когда сожрёт всех - взламывает систему и вызывает спасательный шатл в котором отправляется на землю за добавкой.