M>Вы управляете роботом, который двигается по клетчатому полю. Ваша задача написать алгоритм, с помощью которого робот гарантированно посетить все клетки поля, до которых возможно добраться. Каждая клетка может быть либо свободной, либо занятой стеной. Робот может передвигаться только из свободной клетки в свободную. Размер и форма поля заранее неизвестны. Роботу можно отдать одну из четырёх команд передвижения: вперёд, назад, влево, вправо. По результату выполнения компанды можно понять, сделал ли робот движение, или на пути оказалась стена.
Если я ничего не упустил из условия, то задача решается элементарно (заливка/поиск в ширину/заполнение карты):
1. Допустим, на шаге i у нас есть множество известных клеток на карте (на 0м шаге известна клетка, где мы стоим)
2. Ищем все достижимые (при движении по известной части карты) неизвестные клетки (т.е. граничащие с известными "не стенами"), если таких нет, то завершаем работу
3. Идём в любую из них по известной части карты (можно в ближайшую)
4. При достижении определяем, стена ли там, достраиваем известную часть карты
5. Повторяем с шага 1
Здравствуйте, mbait, Вы писали:
M>А теперь, знатоки, внимание, вопрос: у этой задачи существует детерминированное решение?
У этой задачи существует детерминированное решение даже при отсутствии обратной связи.
Даже если все, что мы можем — это только подавать команды, но никогда не знаем, удалось ли роботу их выполнить.
Мы можем сформировать последовательность команд, которая будет гарантировать обход всех достижимых клеток лабиринта независимо от лабиринта.
Если нам известен размер лабиринта и известно начальное положение робота:
1. Берем множество всех возможных лабиринтов (оно конечно) и нумеруем их.
2. В каждый лабиринт помещаем по роботу. Настраиваем их всех на прием нашего передатчика, чтобы каждая поданная команда выполнялась всеми роботами одновременно.
3. Даем последовательность команд, котрая заставит первого робота обойти свой лабиринт (остальные роботы параллельно выполняют те же команды).
4. Даем последовательность команд, которая заставит второго робота обойти свой лабиринт из точки, в которой он оказался после выполнения пункта 3.
5. Даем последовательность команд, которая заставит третьего робота обойти свой лабиринт из точки, в которой он оказался после выполнения пунктов 3 и 4.
6. Даем последовательность команд, которая заставит четвертого робота обойти свой лабиринт из точки, в которой он оказался после выполнения пунктов 3, 4 и 5.
...
И так, пока не заставим последнего робота обойти последний лабиринт.
Получается, что каждый робот выполнил одну и ту же (очень длинную) последовательность команд, и каждый робот при этом обошел свой лабиринт.
Таким образом, эта очень длинная последовательность команд и есть детерминированное решение, подходящее для любого лабиринта.
Решение можно расширить для случая, если мы не знаем начальное положение робота, и даже для случая, если мы не знаем размер лабиринта
(в последнем случае последовательность команд получится бесконечной, на каждый конкретный лабиринт она будет обходить за конечное время)
Здравствуйте, mbait, Вы писали:
M>Вы управляете роботом, который двигается по клетчатому полю. Ваша задача написать алгоритм, с помощью которого робот гарантированно посетить все клетки поля, до которых возможно добраться. Каждая клетка может быть либо свободной, либо занятой стеной. Робот может передвигаться только из свободной клетки в свободную. Размер и форма поля заранее неизвестны. Роботу можно отдать одну из четырёх команд передвижения: вперёд, назад, влево, вправо. По результату выполнения компанды можно понять, сделал ли робот движение, или на пути оказалась стена.
Так это же классическая задача обхода графа?
void walk(int x, int y) {
if (wall(x, y)) return;
if (visited(x, y)) return;
markVisited(x, y);
walk(x, y + 1);
walk(x, y - 1);
walk(x - 1, y);
walk(x + 1, y);
}
Здравствуйте, mbait, Вы писали:
M>Вообщем, такие задачи и так никто не любит кроме олимпиадников, а когда ещё непонятно, в какую область стоит углубляться, то совсем грустно становится. Если вы собеседуете, то не надо так.
Это просто собеседование по определению того, есть ли у человека хотя бы минимальное профильное ИТ образование. Не диплом, а образование. Конкретно эта задача сводится к базовым графовым алгоритмам, а именно поиск в глубину или ширину, в данном случае пофиг вроде.
И да, в ИТ бывает случаи, когда реально требуются базовые институтские знания хотя бы на уровне первого курса. Конкретно эта задача простейшая — ее задача не завалить, ибо в стрессовой ситуации кандидат может лажануться, а просто детектор учился кандидат в институте или нет. Если учился — даже на остаточных знаниях лет через 30 это вообще не задача. Не всегда все сводится к фреймворкам, в институтах про всякие деревья и графы совсем не зря рассказывают. И в реальности задачи, если понадобится, совсем не такие простые, которые были в институте.
Здравствуйте, mbait, Вы писали:
M>Вообщем, такие задачи и так никто не любит кроме олимпиадников, а когда ещё непонятно, в какую область стоит углубляться, то совсем грустно становится. Если вы собеседуете, то не надо так.
Сморти заливка
Пример реализации — команда "заливка" в любом графическом редакторе.
Здравствуйте, alzt, Вы писали:
A>Можешь накидать решение и сказать сколько времени на это ушло?
Накидать могу. Ибо это алгоритм заливки в видоизмененном виде. Сам алгоритм заливки простейший — просто рекурсивный поиск в глубину по возможным вариантам. Псевдокод самой заливки, в лоб и простейшим способом:
Остается только определить что будет содержаться в структуре nextPos, там будет скорее всего позиция робота и ориентация. Плюс определить функции up, down, left, right. Ну и где то вывод результатов сделать.
Потратил 5 минут за завтраком, в основном на набор текста. Устно на собеседовании сказал бы решение за минуту, если б заставили на бумажке — написал бы тоже, что и сейчас. Потребовали бы полного решения на бумажке — послал бы лесом. Мог ошибиться. В реальном проекте подобное решение бы делать не стал, а свел бы к функциям dfs, который принимает node, с список вариантом с возможными исходами, в данном случае вверх вниз влево вправо. Он возвращает ленивый итератор уже посещенных, и далее в процедуре вывода я бы уже думал как повернуть робота чтобы добиться чтоб робот проходил по заданному пути. (на набор этого еще 5 минут потратил)
решение вполне себе обычный dfs, только надо еще хранить направление, как робот попал в заданную клетку, чтобы делать шаг назад, для того чтобы запоминать уже посещенные клетки надо ввести систему координат. Вот вроде бы и всё
Здравствуйте, serrrgi0, Вы писали:
S>Не совсем понятно, как робот определяет известна ему клетка или нет?
Запрета же на сохранение информации о пройденном пути нет, и результат выполнения каждой команды известен.
Здравствуйте, antonio_banderas, Вы писали:
_>Только не столько образования, сколько умения думать головой.
Ни то, ни другое. Проверяют надроченность. Для программиста-дженерика это ключевое. В большие конторы через интервью редко берут за специализацию, нужно уметь "в общем и целом", но чтобы от зубов отскакивало.
Здравствуйте, antonio_banderas, Вы писали:
_>Для казалось бы маленького поля 10*10 кол-во лабиринтов = 2^100 = 1.26е30 — уже очень много.
Это только кажется, что очень много! Когда у тебя будет 1.26е30 лабиринтов, тебе будет хотеться 3.33e50 или 4.11e44
Будет казаться, что у тебя их очень мало и что ты заслуживаешь больше.
Даже если у среднего россиянина их будет всего 5.9e11.
Вы управляете роботом, который двигается по клетчатому полю. Ваша задача написать алгоритм, с помощью которого робот гарантированно посетить все клетки поля, до которых возможно добраться. Каждая клетка может быть либо свободной, либо занятой стеной. Робот может передвигаться только из свободной клетки в свободную. Размер и форма поля заранее неизвестны. Роботу можно отдать одну из четырёх команд передвижения: вперёд, назад, влево, вправо. По результату выполнения компанды можно понять, сделал ли робот движение, или на пути оказалась стена.
А теперь, знатоки, внимание, вопрос: у этой задачи существует детерминированное решение? То есть такое, которое гарантированно решит задачу в поставленных условиях за конечное время? Например, можно случано бродить по полю бесконечное время, и тогда задача будет решена, потому что для любой достижимой клетки вероятность перехода в неё будет ненулевой. Или же можно случайно бродить по полю, ограничив число итераций. Тогда программа завершится в конечное время, но результат будет вероятностным (посетили ~ X% поля).
Вопрос был задан на собеседовании в одной из компаний FANG, и я был очень удивлён, потому что компания каждый год кричит: "Мы больше не задаём задачи про люки и т.д., учите алгоритмы, и будет вам счатье!". Я ничего не имею против нестандартных задач, просто не люблю, когда нарушаются правила игры. Если же у этой задачи есть детерминированное решение, значит у меня где-то пробел в знаниях.
Мой подход
Во время собеседования я остановился на том, что нужно собрать достаточный набор признаков, чтобы можно было отличать различные состояния, когда мы попадаем в одну и ту же клетку. Например, смещение клетки относительно старта + направление движения. Тогда придумав какое-нибудь нехитрое правило передвижения (например, правило "правой руки"), можно бродить до тех пор, пока мы не попадём в состояние, в которое уже попадали.
Альтернативным подходом было бы запустить несколько роботов, каждый из которых будет действовать отлично от других. Тогда условиев завершения будет встреча роботов в одной и той же клетке. Но тут снова всё упирается в правило обхода, а доказать корректность для каких-то тривиальных правил я не смог за отведённое время.
К сожалению, изрядную часть времени собеседования я потратил на размышление о том, стоил ли искать точный алгоритм или может лучше придумать хорошую эвристику?
Вообщем, такие задачи и так никто не любит кроме олимпиадников, а когда ещё непонятно, в какую область стоит углубляться, то совсем грустно становится. Если вы собеседуете, то не надо так.
Здравствуйте, mbait, Вы писали:
M>Вы управляете роботом, который двигается по клетчатому полю. Ваша задача написать алгоритм, с помощью которого робот гарантированно посетить все клетки поля, до которых возможно добраться. Каждая клетка может быть либо свободной, либо занятой стеной. Робот может передвигаться только из свободной клетки в свободную. Размер и форма поля заранее неизвестны. Роботу можно отдать одну из четырёх команд передвижения: вперёд, назад, влево, вправо. По результату выполнения компанды можно понять, сделал ли робот движение, или на пути оказалась стена.
Совсем брутфорс решение:
— Предполагаем, что размер доски 3х3 и робот в ее центре
— Перебираем все ячейки в пределах предполагаемого размера, и пытаемся посетить каждую ячейку (с помощью того же А*). Считаем, сколько удалось посетить.
— После того, как все ячейки посещены, увеличиваем предполагаемый размер доски (3х3 — 5х5 — 7х7 — ...) и повторяем
— Если по сравнению с предыдущей итерацией количество посещенных ячеек не увеличилось, значит мы достигли пределов доски
Здравствуйте, mbait, Вы писали:
M>Вообщем, такие задачи и так никто не любит кроме олимпиадников, а когда ещё непонятно, в какую область стоит углубляться, то совсем грустно становится. Если вы собеседуете, то не надо так.
если количество клеток лимитировано — то банальный брутфорс в глубину ... часто бывает на собеседованиях
Здравствуйте, mbait, Вы писали: M>Вы управляете роботом, который двигается по клетчатому полю. Ваша задача написать алгоритм, с помощью которого робот гарантированно посетить все клетки поля, до которых возможно добраться. Каждая клетка может быть либо свободной, либо занятой стеной. Робот может передвигаться только из свободной клетки в свободную. Размер и форма поля заранее неизвестны. Роботу можно отдать одну из четырёх команд передвижения: вперёд, назад, влево, вправо. По результату выполнения компанды можно понять, сделал ли робот движение, или на пути оказалась стена. M>А теперь, знатоки, внимание, вопрос: у этой задачи существует детерминированное решение? То есть такое, которое гарантированно решит задачу в поставленных условиях за конечное время? Например, можно случано бродить по полю бесконечное время, и тогда задача будет решена, потому что для любой достижимой клетки вероятность перехода в неё будет ненулевой. Или же можно случайно бродить по полю, ограничив число итераций. Тогда программа завершится в конечное время, но результат будет вероятностным (посетили ~ X% поля). M>Вопрос был задан на собеседовании в одной из компаний FANG, и я был очень удивлён, потому что компания каждый год кричит: "Мы больше не задаём задачи про люки и т.д., учите алгоритмы, и будет вам счатье!". Я ничего не имею против нестандартных задач, просто не люблю, когда нарушаются правила игры. Если же у этой задачи есть детерминированное решение, значит у меня где-то пробел в знаниях. M>
Мой подход
M>Во время собеседования я остановился на том, что нужно собрать достаточный набор признаков, чтобы можно было отличать различные состояния, когда мы попадаем в одну и ту же клетку. Например, смещение клетки относительно старта + направление движения. Тогда придумав какое-нибудь нехитрое правило передвижения (например, правило "правой руки"), можно бродить до тех пор, пока мы не попадём в состояние, в которое уже попадали.
M>Альтернативным подходом было бы запустить несколько роботов, каждый из которых будет действовать отлично от других. Тогда условиев завершения будет встреча роботов в одной и той же клетке. Но тут снова всё упирается в правило обхода, а доказать корректность для каких-то тривиальных правил я не смог за отведённое время.
M>К сожалению, изрядную часть времени собеседования я потратил на размышление о том, стоил ли искать точный алгоритм или может лучше придумать хорошую эвристику?
M>Вообщем, такие задачи и так никто не любит кроме олимпиадников, а когда ещё непонятно, в какую область стоит углубляться, то совсем грустно становится. Если вы собеседуете, то не надо так.
Задача снимается, потому что я перечитал и понял, что в такой постановке это обычный поиск в ширину. Возможно, там было что-то ещё. Эх, надо было сразу написать, а так уже больше года прошло...
M>Вы управляете роботом, который двигается по клетчатому полю. Ваша задача написать алгоритм, с помощью которого робот гарантированно посетить все клетки поля, до которых возможно добраться. Каждая клетка может быть либо свободной, либо занятой стеной. Робот может передвигаться только из свободной клетки в свободную. Размер и форма поля заранее неизвестны. Роботу можно отдать одну из четырёх команд передвижения: вперёд, назад, влево, вправо. По результату выполнения компанды можно понять, сделал ли робот движение, или на пути оказалась стена.
Я бы сначала задумался, что в на первой клетке у тебя есть 4 шага и если ты ушел на втором, то у клетки останется еще два не проверенных пути. Во второй клетке, я имею три пути и путь назад, где есть ещё два не проверенных, сделав предположим во 2-ой клетке шаг на второй попытке, я буду знать, что во второй клетке, остался один путь не проверенный и один путь назад к первой клетке. Напишу так шагов 10 на бумажке. Посмотрю на что это "похождение" будет похоже, что бы робот не гулял зря по клеткам у которых нет выхода. Подумал как бы можно учесть количество непроверенных шагов у предыдущих клеток. Придумал бы структуру(или структуры) для хранения информации о клетке. Взял бы либо список, либо очередь, либо стэк для хранения структур. Возможно даже два таких класса. Написал бы вышеописанный алгоритм "похождение". Потом запустил бы обход этой доски. А сколько времени отводилось на решение этой задачи? 45 мин.?
Здравствуйте, mbait, Вы писали:
M>Вопрос был задан на собеседовании в одной из компаний FANG, и я был очень удивлён, потому что компания каждый год кричит: "Мы больше не задаём задачи про люки и т.д., учите алгоритмы, и будет вам счатье!"
"A" такое спрашивает, но они, вроде, не орали что на гномов забили (то был "G") Кстати ко такой "N"? Microsoft?
Здравствуйте, De-Bill, Вы писали:
DB>Если я ничего не упустил из условия, то задача решается элементарно (заливка/поиск в ширину/заполнение карты): DB>1. Допустим, на шаге i у нас есть множество известных клеток на карте (на 0м шаге известна клетка, где мы стоим)
Не совсем понятно, как робот определяет известна ему клетка или нет? Думаю на циклических полях алгоритм нерабочий.
Здравствуйте, iriska2, Вы писали:
I>для того чтобы запоминать уже посещенные клетки надо ввести систему координат.
А какую систему координат нужно ввести для заранее неизвестного поля?
Здравствуйте, pagid, Вы писали:
P>Здравствуйте, serrrgi0, Вы писали:
S>>Не совсем понятно, как робот определяет известна ему клетка или нет? P>Запрета же на сохранение информации о пройденном пути нет, и результат выполнения каждой команды известен.
Объясните на примере из двух клеток с 0 и 1 сверху и снизу есть стенки 0 и 1 граничат между собой справа и слева.
Допустим робот изначально смотрит направо. Он идет и оказывается в клетке 1 далее делает еще движение и оказывается в клетке 0 или 2?
Здравствуйте, serrrgi0, Вы писали:
S>Здравствуйте, pagid, Вы писали:
P>>Здравствуйте, serrrgi0, Вы писали:
S>>>Не совсем понятно, как робот определяет известна ему клетка или нет? P>>Запрета же на сохранение информации о пройденном пути нет, и результат выполнения каждой команды известен. S>Объясните на примере из двух клеток с 0 и 1 сверху и снизу есть стенки 0 и 1 граничат между собой справа и слева. S>Допустим робот изначально смотрит направо. Он идет и оказывается в клетке 1 далее делает еще движение и оказывается в клетке 0 или 2?
Команды роботу выбираешь же сам, пойдешь вперед будешь в 2, назад — в 0
Если пространство не плоское а замкнуто в цилиндр тогда да, потряешься при обходе, но в задаче ни о чем таком не сказано.
Здравствуйте, Pyromancer, Вы писали:
P>но в задаче ни о чем таком не сказано.
Уверен вы правы, но у ТС написано "Размер и форма поля заранее неизвестны."
Здравствуйте, elmal, Вы писали:
E>Это просто собеседование по определению того, есть ли у человека хотя бы минимальное профильное ИТ образование. Не диплом, а образование. Конкретно эта задача сводится к базовым графовым алгоритмам, а именно поиск в глубину или ширину, в данном случае пофиг вроде.
E>И да, в ИТ бывает случаи, когда реально требуются базовые институтские знания хотя бы на уровне первого курса. Конкретно эта задача простейшая — ее задача не завалить, ибо в стрессовой ситуации кандидат может лажануться, а просто детектор учился кандидат в институте или нет. Если учился — даже на остаточных знаниях лет через 30 это вообще не задача. Не всегда все сводится к фреймворкам, в институтах про всякие деревья и графы совсем не зря рассказывают. И в реальности задачи, если понадобится, совсем не такие простые, которые были в институте.
Можешь накидать решение и сказать сколько времени на это ушло?
Я знаю коллег, которые могут быстро решить очень многие задачи. Т.е. накидать решение за час для задачи, которую сложно и за 5 часов решить. Причём нормальное решение, и вообще они хорошие программисты. Только вот в проектной разработке каких-то выдающихся результатов от них я не видел. Результат не плохой, они явно тянут, но не более.
Здравствуйте, serrrgi0, Вы писали:
P>>но в задаче ни о чем таком не сказано. S>Уверен вы правы, но у ТС написано "Размер и форма поля заранее неизвестны."
Так это не замкнутость, а именно размер (10 клеток, или 100, 1000, 1000000000) и форма (квадрат, круг и прочие произвольные формы).
Здравствуйте, elmal, Вы писали:
M>>Вообщем, такие задачи и так никто не любит кроме олимпиадников, а когда ещё непонятно, в какую область стоит углубляться, то совсем грустно становится. Если вы собеседуете, то не надо так.
E>Это просто собеседование по определению того, есть ли у человека хотя бы минимальное профильное ИТ образование. Не диплом, а образование. Конкретно эта задача сводится к базовым графовым алгоритмам, а именно поиск в глубину или ширину, в данном случае пофиг вроде.
E>И да, в ИТ бывает случаи, когда реально требуются базовые институтские знания хотя бы на уровне первого курса. Конкретно эта задача простейшая — ее задача не завалить, ибо в стрессовой ситуации кандидат может лажануться, а просто детектор учился кандидат в институте или нет. Если учился — даже на остаточных знаниях лет через 30 это вообще не задача. Не всегда все сводится к фреймворкам, в институтах про всякие деревья и графы совсем не зря рассказывают. И в реальности задачи, если понадобится, совсем не такие простые, которые были в институте.
Почти так.
Только не столько образования, сколько умения думать головой.
Ну или образования. Или эти 2 сущности друг друга замещать могут (кто-то за счет образования вытягивает, а кто-то за счет умения думать).
Судя по тому, что даже эту задачу ТС решить не смог, у него и с тем и с другим не очень. (((
Здравствуйте, Панда, Вы писали:
П>У этой задачи существует детерминированное решение даже при отсутствии обратной связи. П>Даже если все, что мы можем — это только подавать команды, но никогда не знаем, удалось ли роботу их выполнить. П>Мы можем сформировать последовательность команд, которая будет гарантировать обход всех достижимых клеток лабиринта независимо от лабиринта.
П>Если нам известен размер лабиринта и известно начальное положение робота: П>1. Берем множество всех возможных лабиринтов (оно конечно) и нумеруем их.
Множество всех возможных лабиринтов это 2^К, где К это кол-во клеток (каждая клетка может быть либо занята стеной, либо нет).
Это имеет смысл только для очень маленьких полей.
Для казалось бы маленького поля 10*10 кол-во лабиринтов = 2^100 = 1.26е30 — уже очень много.
Для поля чуть побольше 20*20 или 50*50 даже говорить не стоит.
Так что это решение красиво лишь в теории.
Для задачи ТС, где размер поля может быть любым, оно заведомо не подходит. (
Здравствуйте, serrrgi0, Вы писали:
I>>для того чтобы запоминать уже посещенные клетки надо ввести систему координат. S>А какую систему координат нужно ввести для заранее неизвестного поля?
Да любую, координата отрицательной может быть тоже. )
Можно например, чтоб начальная позиция робота была в точке (0,0).
Здравствуйте, elmal, Вы писали:
E>Мог ошибиться.
И, кстати, ошибся — забыл собственно промаркировать, что я посетил, ну и проверить на посещенность . Правильную заливку здесь уже приводили. Но сути не меняет.
Здравствуйте, El Camino Real, Вы писали:
_>>Только не столько образования, сколько умения думать головой. ECR>Ни то, ни другое. Проверяют надроченность. Для программиста-дженерика это ключевое. В большие конторы через интервью редко берут за специализацию, нужно уметь "в общем и целом", но чтобы от зубов отскакивало.
Некоторые отсутсвие образования и отсутствие умения думать головой компенсируют надроченностью. )
Как охотно товарищи рассказывают о себе, кто чем пользуется.
Но без первых двух пунктов на одной надроченности далеко не уедешь, имхо.
Здравствуйте, antonio_banderas, Вы писали:
_>Но без первых двух пунктов на одной надроченности далеко не уедешь, имхо.
Coding interview редко подразумевает позицию в совете директоров, так что далеко ехать от кандидата и не требуется.
Здравствуйте, antonio_banderas, Вы писали:
_> и форма (квадрат, круг и прочие произвольные формы).
Тороид, цилиндр или сфера являются произвольными формами или нет?
Думаю стоило бы ввести ограничение про двумерность пространства.