Здравствуйте, mbait, Вы писали:

Задача на рекурсию с бэктракингом. в ссылке ниже решение без препятствий (без бэктракинга):
https://stackoverflow.com/a/45199670

Здравствуйте, serrrgi0, Вы писали:

S>Не совсем понятно, как робот определяет известна ему клетка или нет?
Запрета же на сохранение информации о пройденном пути нет, и результат выполнения каждой команды известен.

Здравствуйте, 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>но в задаче ни о чем таком не сказано.
Уверен вы правы, но у ТС написано "Размер и форма поля заранее неизвестны."

Здравствуйте, 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);
}

Здравствуйте, elmal, Вы писали:

E>Это просто собеседование по определению того, есть ли у человека хотя бы минимальное профильное ИТ образование. Не диплом, а образование. Конкретно эта задача сводится к базовым графовым алгоритмам, а именно поиск в глубину или ширину, в данном случае пофиг вроде.

E>И да, в ИТ бывает случаи, когда реально требуются базовые институтские знания хотя бы на уровне первого курса. Конкретно эта задача простейшая — ее задача не завалить, ибо в стрессовой ситуации кандидат может лажануться, а просто детектор учился кандидат в институте или нет. Если учился — даже на остаточных знаниях лет через 30 это вообще не задача. Не всегда все сводится к фреймворкам, в институтах про всякие деревья и графы совсем не зря рассказывают. И в реальности задачи, если понадобится, совсем не такие простые, которые были в институте.

Можешь накидать решение и сказать сколько времени на это ушло?
Я знаю коллег, которые могут быстро решить очень многие задачи. Т.е. накидать решение за час для задачи, которую сложно и за 5 часов решить. Причём нормальное решение, и вообще они хорошие программисты. Только вот в проектной разработке каких-то выдающихся результатов от них я не видел. Результат не плохой, они явно тянут, но не более.

Здравствуйте, alzt, Вы писали:

A>Можешь накидать решение и сказать сколько времени на это ушло?
Накидать могу. Ибо это алгоритм заливки в видоизмененном виде. Сам алгоритм заливки простейший — просто рекурсивный поиск в глубину по возможным вариантам. Псевдокод самой заливки, в лоб и простейшим способом:

fill(nextPos) {
    if(isWall(nextPos)) {
        return;
    }   
    fill(up(nextPos));
    fill(down(nextPos));
    fill(left(nextPos));
    fill(right(nextPos));
}

Остается только определить что будет содержаться в структуре nextPos, там будет скорее всего позиция робота и ориентация. Плюс определить функции up, down, left, right. Ну и где то вывод результатов сделать.

Потратил 5 минут за завтраком, в основном на набор текста. Устно на собеседовании сказал бы решение за минуту, если б заставили на бумажке — написал бы тоже, что и сейчас. Потребовали бы полного решения на бумажке — послал бы лесом. Мог ошибиться. В реальном проекте подобное решение бы делать не стал, а свел бы к функциям dfs, который принимает node, с список вариантом с возможными исходами, в данном случае вверх вниз влево вправо. Он возвращает ленивый итератор уже посещенных, и далее в процедуре вывода я бы уже думал как повернуть робота чтобы добиться чтоб робот проходил по заданному пути. (на набор этого еще 5 минут потратил)

Здравствуйте, serrrgi0, Вы писали:

P>>но в задаче ни о чем таком не сказано.
S>Уверен вы правы, но у ТС написано "Размер и форма поля заранее неизвестны."

Так это не замкнутость, а именно размер (10 клеток, или 100, 1000, 1000000000) и форма (квадрат, круг и прочие произвольные формы).

Здравствуйте, elmal, Вы писали:

M>>Вообщем, такие задачи и так никто не любит кроме олимпиадников, а когда ещё непонятно, в какую область стоит углубляться, то совсем грустно становится. Если вы собеседуете, то не надо так.

E>Это просто собеседование по определению того, есть ли у человека хотя бы минимальное профильное ИТ образование. Не диплом, а образование. Конкретно эта задача сводится к базовым графовым алгоритмам, а именно поиск в глубину или ширину, в данном случае пофиг вроде.

E>И да, в ИТ бывает случаи, когда реально требуются базовые институтские знания хотя бы на уровне первого курса. Конкретно эта задача простейшая — ее задача не завалить, ибо в стрессовой ситуации кандидат может лажануться, а просто детектор учился кандидат в институте или нет. Если учился — даже на остаточных знаниях лет через 30 это вообще не задача. Не всегда все сводится к фреймворкам, в институтах про всякие деревья и графы совсем не зря рассказывают. И в реальности задачи, если понадобится, совсем не такие простые, которые были в институте.

Почти так.
Только не столько образования, сколько умения думать головой.
Ну или образования. Или эти 2 сущности друг друга замещать могут (кто-то за счет образования вытягивает, а кто-то за счет умения думать).
Судя по тому, что даже эту задачу ТС решить не смог, у него и с тем и с другим не очень. (((

Здравствуйте, scf, Вы писали:

scf>Так это же классическая задача обхода графа?

scf>

scf>void walk(int x, int y) {
scf>  if (wall(x, y)) return;
scf>  if (visited(x, y)) return;
scf>  markVisited(x, y);
scf>  walk(x, y + 1);
scf>  walk(x, y - 1);
scf>  walk(x - 1, y);
scf>  walk(x + 1, y);
scf>}
scf>

На большой карте у тебя при таком обходе "в лоб" стек закончится. (
А так всё правильно.

P.S. уже после того, как написал это, увидел тег java. В java видимо экономить не принято. )

Ну и еще можно было markWall() добавить, чтоб в 1 и ту же стену с разных сторон не долбиться, но это уже детали...

Здравствуйте, Панда, Вы писали:

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

П>Если нам известен размер лабиринта и известно начальное положение робота:
П>1. Берем множество всех возможных лабиринтов (оно конечно) и нумеруем их.

Множество всех возможных лабиринтов это 2^К, где К это кол-во клеток (каждая клетка может быть либо занята стеной, либо нет).
Это имеет смысл только для очень маленьких полей.
Для казалось бы маленького поля 10*10 кол-во лабиринтов = 2^100 = 1.26е30 — уже очень много.
Для поля чуть побольше 20*20 или 50*50 даже говорить не стоит.
Так что это решение красиво лишь в теории.

Для задачи ТС, где размер поля может быть любым, оно заведомо не подходит. (

Здравствуйте, serrrgi0, Вы писали:

I>>для того чтобы запоминать уже посещенные клетки надо ввести систему координат.
S>А какую систему координат нужно ввести для заранее неизвестного поля?

Да любую, координата отрицательной может быть тоже. )
Можно например, чтоб начальная позиция робота была в точке (0,0).

Здравствуйте, antonio_banderas, Вы писали:

_>Только не столько образования, сколько умения думать головой.
Ни то, ни другое. Проверяют надроченность. Для программиста-дженерика это ключевое. В большие конторы через интервью редко берут за специализацию, нужно уметь "в общем и целом", но чтобы от зубов отскакивало.

Здравствуйте, elmal, Вы писали:

E>Мог ошибиться.
И, кстати, ошибся — забыл собственно промаркировать, что я посетил, ну и проверить на посещенность . Правильную заливку здесь уже приводили. Но сути не меняет.

Здравствуйте, El Camino Real, Вы писали:

_>>Только не столько образования, сколько умения думать головой.
ECR>Ни то, ни другое. Проверяют надроченность. Для программиста-дженерика это ключевое. В большие конторы через интервью редко берут за специализацию, нужно уметь "в общем и целом", но чтобы от зубов отскакивало.

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

Здравствуйте, antonio_banderas, Вы писали:

_>На большой карте у тебя при таком обходе "в лоб" стек закончится. (

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

Здравствуйте, antonio_banderas, Вы писали:

_>Но без первых двух пунктов на одной надроченности далеко не уедешь, имхо.
Coding interview редко подразумевает позицию в совете директоров, так что далеко ехать от кандидата и не требуется.

Здравствуйте, antonio_banderas, Вы писали:

_> и форма (квадрат, круг и прочие произвольные формы).
Тороид, цилиндр или сфера являются произвольными формами или нет?
Думаю стоило бы ввести ограничение про двумерность пространства.

Здравствуйте, antonio_banderas, Вы писали:

_>Для казалось бы маленького поля 10*10 кол-во лабиринтов = 2^100 = 1.26е30 — уже очень много.

Это только кажется, что очень много! Когда у тебя будет 1.26е30 лабиринтов, тебе будет хотеться 3.33e50 или 4.11e44
Будет казаться, что у тебя их очень мало и что ты заслуживаешь больше.
Даже если у среднего россиянина их будет всего 5.9e11.