Вы управляете роботом, который двигается по клетчатому полю. Ваша задача написать алгоритм, с помощью которого робот гарантированно посетить все клетки поля, до которых возможно добраться. Каждая клетка может быть либо свободной, либо занятой стеной. Робот может передвигаться только из свободной клетки в свободную. Размер и форма поля заранее неизвестны. Роботу можно отдать одну из четырёх команд передвижения: вперёд, назад, влево, вправо. По результату выполнения компанды можно понять, сделал ли робот движение, или на пути оказалась стена.
А теперь, знатоки, внимание, вопрос: у этой задачи существует детерминированное решение? То есть такое, которое гарантированно решит задачу в поставленных условиях за конечное время? Например, можно случано бродить по полю бесконечное время, и тогда задача будет решена, потому что для любой достижимой клетки вероятность перехода в неё будет ненулевой. Или же можно случайно бродить по полю, ограничив число итераций. Тогда программа завершится в конечное время, но результат будет вероятностным (посетили ~ X% поля).
Вопрос был задан на собеседовании в одной из компаний FANG, и я был очень удивлён, потому что компания каждый год кричит: "Мы больше не задаём задачи про люки и т.д., учите алгоритмы, и будет вам счатье!". Я ничего не имею против нестандартных задач, просто не люблю, когда нарушаются правила игры. Если же у этой задачи есть детерминированное решение, значит у меня где-то пробел в знаниях.
Мой подход
Во время собеседования я остановился на том, что нужно собрать достаточный набор признаков, чтобы можно было отличать различные состояния, когда мы попадаем в одну и ту же клетку. Например, смещение клетки относительно старта + направление движения. Тогда придумав какое-нибудь нехитрое правило передвижения (например, правило "правой руки"), можно бродить до тех пор, пока мы не попадём в состояние, в которое уже попадали.
Альтернативным подходом было бы запустить несколько роботов, каждый из которых будет действовать отлично от других. Тогда условиев завершения будет встреча роботов в одной и той же клетке. Но тут снова всё упирается в правило обхода, а доказать корректность для каких-то тривиальных правил я не смог за отведённое время.
К сожалению, изрядную часть времени собеседования я потратил на размышление о том, стоил ли искать точный алгоритм или может лучше придумать хорошую эвристику?
Вообщем, такие задачи и так никто не любит кроме олимпиадников, а когда ещё непонятно, в какую область стоит углубляться, то совсем грустно становится. Если вы собеседуете, то не надо так.
M>Вы управляете роботом, который двигается по клетчатому полю. Ваша задача написать алгоритм, с помощью которого робот гарантированно посетить все клетки поля, до которых возможно добраться. Каждая клетка может быть либо свободной, либо занятой стеной. Робот может передвигаться только из свободной клетки в свободную. Размер и форма поля заранее неизвестны. Роботу можно отдать одну из четырёх команд передвижения: вперёд, назад, влево, вправо. По результату выполнения компанды можно понять, сделал ли робот движение, или на пути оказалась стена.
Если я ничего не упустил из условия, то задача решается элементарно (заливка/поиск в ширину/заполнение карты):
1. Допустим, на шаге i у нас есть множество известных клеток на карте (на 0м шаге известна клетка, где мы стоим)
2. Ищем все достижимые (при движении по известной части карты) неизвестные клетки (т.е. граничащие с известными "не стенами"), если таких нет, то завершаем работу
3. Идём в любую из них по известной части карты (можно в ближайшую)
4. При достижении определяем, стена ли там, достраиваем известную часть карты
5. Повторяем с шага 1
Здравствуйте, mbait, Вы писали:
M>Вы управляете роботом, который двигается по клетчатому полю. Ваша задача написать алгоритм, с помощью которого робот гарантированно посетить все клетки поля, до которых возможно добраться. Каждая клетка может быть либо свободной, либо занятой стеной. Робот может передвигаться только из свободной клетки в свободную. Размер и форма поля заранее неизвестны. Роботу можно отдать одну из четырёх команд передвижения: вперёд, назад, влево, вправо. По результату выполнения компанды можно понять, сделал ли робот движение, или на пути оказалась стена.
Совсем брутфорс решение:
— Предполагаем, что размер доски 3х3 и робот в ее центре
— Перебираем все ячейки в пределах предполагаемого размера, и пытаемся посетить каждую ячейку (с помощью того же А*). Считаем, сколько удалось посетить.
— После того, как все ячейки посещены, увеличиваем предполагаемый размер доски (3х3 — 5х5 — 7х7 — ...) и повторяем
— Если по сравнению с предыдущей итерацией количество посещенных ячеек не увеличилось, значит мы достигли пределов доски
Здравствуйте, mbait, Вы писали:
M>Вообщем, такие задачи и так никто не любит кроме олимпиадников, а когда ещё непонятно, в какую область стоит углубляться, то совсем грустно становится. Если вы собеседуете, то не надо так.
Это просто собеседование по определению того, есть ли у человека хотя бы минимальное профильное ИТ образование. Не диплом, а образование. Конкретно эта задача сводится к базовым графовым алгоритмам, а именно поиск в глубину или ширину, в данном случае пофиг вроде.
И да, в ИТ бывает случаи, когда реально требуются базовые институтские знания хотя бы на уровне первого курса. Конкретно эта задача простейшая — ее задача не завалить, ибо в стрессовой ситуации кандидат может лажануться, а просто детектор учился кандидат в институте или нет. Если учился — даже на остаточных знаниях лет через 30 это вообще не задача. Не всегда все сводится к фреймворкам, в институтах про всякие деревья и графы совсем не зря рассказывают. И в реальности задачи, если понадобится, совсем не такие простые, которые были в институте.
Здравствуйте, mbait, Вы писали:
M>Вообщем, такие задачи и так никто не любит кроме олимпиадников, а когда ещё непонятно, в какую область стоит углубляться, то совсем грустно становится. Если вы собеседуете, то не надо так.
если количество клеток лимитировано — то банальный брутфорс в глубину ... часто бывает на собеседованиях
Здравствуйте, mbait, Вы писали: M>Вы управляете роботом, который двигается по клетчатому полю. Ваша задача написать алгоритм, с помощью которого робот гарантированно посетить все клетки поля, до которых возможно добраться. Каждая клетка может быть либо свободной, либо занятой стеной. Робот может передвигаться только из свободной клетки в свободную. Размер и форма поля заранее неизвестны. Роботу можно отдать одну из четырёх команд передвижения: вперёд, назад, влево, вправо. По результату выполнения компанды можно понять, сделал ли робот движение, или на пути оказалась стена. M>А теперь, знатоки, внимание, вопрос: у этой задачи существует детерминированное решение? То есть такое, которое гарантированно решит задачу в поставленных условиях за конечное время? Например, можно случано бродить по полю бесконечное время, и тогда задача будет решена, потому что для любой достижимой клетки вероятность перехода в неё будет ненулевой. Или же можно случайно бродить по полю, ограничив число итераций. Тогда программа завершится в конечное время, но результат будет вероятностным (посетили ~ X% поля). M>Вопрос был задан на собеседовании в одной из компаний FANG, и я был очень удивлён, потому что компания каждый год кричит: "Мы больше не задаём задачи про люки и т.д., учите алгоритмы, и будет вам счатье!". Я ничего не имею против нестандартных задач, просто не люблю, когда нарушаются правила игры. Если же у этой задачи есть детерминированное решение, значит у меня где-то пробел в знаниях. M>
Мой подход
M>Во время собеседования я остановился на том, что нужно собрать достаточный набор признаков, чтобы можно было отличать различные состояния, когда мы попадаем в одну и ту же клетку. Например, смещение клетки относительно старта + направление движения. Тогда придумав какое-нибудь нехитрое правило передвижения (например, правило "правой руки"), можно бродить до тех пор, пока мы не попадём в состояние, в которое уже попадали.
M>Альтернативным подходом было бы запустить несколько роботов, каждый из которых будет действовать отлично от других. Тогда условиев завершения будет встреча роботов в одной и той же клетке. Но тут снова всё упирается в правило обхода, а доказать корректность для каких-то тривиальных правил я не смог за отведённое время.
M>К сожалению, изрядную часть времени собеседования я потратил на размышление о том, стоил ли искать точный алгоритм или может лучше придумать хорошую эвристику?
M>Вообщем, такие задачи и так никто не любит кроме олимпиадников, а когда ещё непонятно, в какую область стоит углубляться, то совсем грустно становится. Если вы собеседуете, то не надо так.
Задача снимается, потому что я перечитал и понял, что в такой постановке это обычный поиск в ширину. Возможно, там было что-то ещё. Эх, надо было сразу написать, а так уже больше года прошло...
Здравствуйте, mbait, Вы писали:
M>Вообщем, такие задачи и так никто не любит кроме олимпиадников, а когда ещё непонятно, в какую область стоит углубляться, то совсем грустно становится. Если вы собеседуете, то не надо так.
Сморти заливка
Пример реализации — команда "заливка" в любом графическом редакторе.
M>Вы управляете роботом, который двигается по клетчатому полю. Ваша задача написать алгоритм, с помощью которого робот гарантированно посетить все клетки поля, до которых возможно добраться. Каждая клетка может быть либо свободной, либо занятой стеной. Робот может передвигаться только из свободной клетки в свободную. Размер и форма поля заранее неизвестны. Роботу можно отдать одну из четырёх команд передвижения: вперёд, назад, влево, вправо. По результату выполнения компанды можно понять, сделал ли робот движение, или на пути оказалась стена.
Я бы сначала задумался, что в на первой клетке у тебя есть 4 шага и если ты ушел на втором, то у клетки останется еще два не проверенных пути. Во второй клетке, я имею три пути и путь назад, где есть ещё два не проверенных, сделав предположим во 2-ой клетке шаг на второй попытке, я буду знать, что во второй клетке, остался один путь не проверенный и один путь назад к первой клетке. Напишу так шагов 10 на бумажке. Посмотрю на что это "похождение" будет похоже, что бы робот не гулял зря по клеткам у которых нет выхода. Подумал как бы можно учесть количество непроверенных шагов у предыдущих клеток. Придумал бы структуру(или структуры) для хранения информации о клетке. Взял бы либо список, либо очередь, либо стэк для хранения структур. Возможно даже два таких класса. Написал бы вышеописанный алгоритм "похождение". Потом запустил бы обход этой доски. А сколько времени отводилось на решение этой задачи? 45 мин.?
Здравствуйте, mbait, Вы писали:
M>А теперь, знатоки, внимание, вопрос: у этой задачи существует детерминированное решение?
У этой задачи существует детерминированное решение даже при отсутствии обратной связи.
Даже если все, что мы можем — это только подавать команды, но никогда не знаем, удалось ли роботу их выполнить.
Мы можем сформировать последовательность команд, которая будет гарантировать обход всех достижимых клеток лабиринта независимо от лабиринта.
Если нам известен размер лабиринта и известно начальное положение робота:
1. Берем множество всех возможных лабиринтов (оно конечно) и нумеруем их.
2. В каждый лабиринт помещаем по роботу. Настраиваем их всех на прием нашего передатчика, чтобы каждая поданная команда выполнялась всеми роботами одновременно.
3. Даем последовательность команд, котрая заставит первого робота обойти свой лабиринт (остальные роботы параллельно выполняют те же команды).
4. Даем последовательность команд, которая заставит второго робота обойти свой лабиринт из точки, в которой он оказался после выполнения пункта 3.
5. Даем последовательность команд, которая заставит третьего робота обойти свой лабиринт из точки, в которой он оказался после выполнения пунктов 3 и 4.
6. Даем последовательность команд, которая заставит четвертого робота обойти свой лабиринт из точки, в которой он оказался после выполнения пунктов 3, 4 и 5.
...
И так, пока не заставим последнего робота обойти последний лабиринт.
Получается, что каждый робот выполнил одну и ту же (очень длинную) последовательность команд, и каждый робот при этом обошел свой лабиринт.
Таким образом, эта очень длинная последовательность команд и есть детерминированное решение, подходящее для любого лабиринта.
Решение можно расширить для случая, если мы не знаем начальное положение робота, и даже для случая, если мы не знаем размер лабиринта
(в последнем случае последовательность команд получится бесконечной, на каждый конкретный лабиринт она будет обходить за конечное время)
решение вполне себе обычный dfs, только надо еще хранить направление, как робот попал в заданную клетку, чтобы делать шаг назад, для того чтобы запоминать уже посещенные клетки надо ввести систему координат. Вот вроде бы и всё
Здравствуйте, mbait, Вы писали:
M>Вопрос был задан на собеседовании в одной из компаний FANG, и я был очень удивлён, потому что компания каждый год кричит: "Мы больше не задаём задачи про люки и т.д., учите алгоритмы, и будет вам счатье!"
"A" такое спрашивает, но они, вроде, не орали что на гномов забили (то был "G") Кстати ко такой "N"? Microsoft?
Здравствуйте, De-Bill, Вы писали:
DB>Если я ничего не упустил из условия, то задача решается элементарно (заливка/поиск в ширину/заполнение карты): DB>1. Допустим, на шаге i у нас есть множество известных клеток на карте (на 0м шаге известна клетка, где мы стоим)
Не совсем понятно, как робот определяет известна ему клетка или нет? Думаю на циклических полях алгоритм нерабочий.
Здравствуйте, iriska2, Вы писали:
I>для того чтобы запоминать уже посещенные клетки надо ввести систему координат.
А какую систему координат нужно ввести для заранее неизвестного поля?
Кстати ко такой "N"? Microsoft? 
