Понял бы я чем Вы хвастаетесь и о чем вся эта ветка дискуссии была. Вот там ниже комментатор написал про петиции, и в целом даже не буду радоваться, что вовремя обозначил "что вопрос никого не волнует", цифры это показывают. С другой стороны моего голоса там не было, так что и утверждаться тут нечем.
У Вас мягко говоря странные представления о психологическом насилии, оно в виде сиюминутного эпизода не особо интересно. Но если это систематика на года, то жизнь может уже обратно не поменяться в принципе.
Разложить в фурье и понизить коэффициенты у известных частот. Впрочем если уже фурье сворачивать в нужный диапазон значений хотя бы тем же xor, то никаких проблем я придумать не могу.
И ещё такая мысль. Если в задачу входит управление роем робопылесосов на одной и той же карте с соперником в равных условиях с сохранением всех остальных условий, то это настоящая котлета :)
до 10 раз разницу, но я искал худшие случаи, а не среднее.
Пропорция увеличивается в зависимости от размера карты, и да именно:
Возвращаясь к вопросу тестируемости... :)
Конечно я "просрал весь бюджет времени" в рамках Вашей идеи задачи для собеседования. 10 минут потратил на то что бы критиковать. 20 минут на описание того, что сделал бы. 30 минут на реализацию этого. 10 минут на придумывание первых тестов в формате input.txt output.txt, карты которые рисовал вручную и так же вручную считал сколько полей останутся неочищенными. Знаете, тоже труд. Никакого генератора у меня не было, потому что алгоритма, который по входу построит мне правильный выход у меня не было. Поэтому рисовал поля от 5х5 до 15х15. И, конечно тут же тесты сфейлились, и пришлось ещё потратить 30 минут на отладку. Правда в этот же момент я заметил, что оптимизация2 это полная ерунда на реальных картах. Следующим шагом я бы с удовольствием нагенерил бы карт побольше (и побольше размером) и стал бы думать не только над корректностью ответа, но и конкретными оптимизациями вызова move(). Не беда, выходные будут - думаю ещё займусь.
Вернувшись к тому, что Вы говорите о вопросе тестируемости, конечно в общих словах я всецело согласен. Удивляет вообще сам факт наличия людей, которым хватает временного бюджета и на MVP решение задачи и на хотя бы ограниченное тестирование. Поэтому прямой вопрос, а они правда были? Вопрос провокационный, но без подвоха.
Согласен, задача вовсе не верихард, а ближе к медиум на литкоде, и требует должной сообразительности, но напрашивается ещё один вопрос, в чем смысл нанимать людей, которые справляются именно с этим, то есть, ну почему Вам нужны именно такие люди.
По моему опыту почти все знакомые сеньоры знатные слоупоки. Такое вот вынужденое искажение происходит.
Да, искажение, Вы абсолютно правы. Мне интересно решать задачки, не потому, что их вообще можно решить, а потому, что их можно решить лучше других. Говорили, что это должно пройти, но нет, время не лечит, и теперь просто это стало хобби. Иногда, конечно искажающим другие процессы, но кто в сущности то без этого :) На CG особого усердия, кстати в топ попасть много не надо, это надо не все подряд хорошо решать, а просто в паре-тройке челленжей абсолютно выиграть.
Да, каюсь, все же не такая уж и сложная задача. Вот уж теперь не знаю, что меня заставило проглядеть идею о том, что код из поста нужно немного исправить, чтобы он заработал. Наверное стойкое ощущение, что в том направлении он все равно был бы безобразно неэффективен (ну это некоторая деформация, да).
Но, оказалось, что это не правда. Я все же написал, как и обозначил идею, решение с битовыми масками для оптимизации обхода. На самом деле тоже не очень много времени заняло, если бы не отладка, то меньше получаса, ну оно работает, хорошо работает, только вот на том небольшом количестве карт для тестирования, которые вручную нарисовал, едва ли более чем в 2 раза более эффективно (в количестве Move()) в среднем, чем предложенный Вами код.
А значит, то решение, направление которого Вы предлагаете вполне решает поставленную задачу. И действительно вполне укладывается и в обозначенное время, и не надо было ничего переусложнять :)
В принципе я и так счел задачу интересной, теперь соглашусь, что пусть и не ультимативно, но в заданном формате собеседований это может быть хорошим выбором.
Да-да, я примеры тоже уже успел посочинять немного, на них все становится сразу более-менее понятно. Мне кажется, именно этого посту и не хватало, чтобы получить более положительную реакцию; привычка читать "по диагонали" уже скорее ближе к норме, чем исключениям, а тут и люди и кони, и странный пылесос, и какие-то движущиеся объекты, и карты со странной геометрией, а нет, все банально об "обойди такую штуку
Но вот для меня как раз "стейкинг" usdt под 17% годовых и был последним звоночком, после которого я вывел с этого кошелька свою горстку тона. Который примерно с этих же пор так и не подрос.
Синусы как раз прекрасно сводятся к простым суммам (ряды Тейлора), но не понятно, как это вообще должно быть связано с отображением результата. В sin(1) ни конечной в десятичной записи рациональной дроби, ни даже периодической вы не увидите, поэтому, по сути вопрос в том, на каком знаке после запятой его округлить. А это примерно "как пользователю нужно". Меня бы 0.01745 бы устроило, кроме тех случаев, когда нужно дальше с этим что-то считать.
Дело в том, что хорошие вычислительные методы, дают предсказуемую погрешность, зачастую значительно меньшую, чем погрешность отдельных операций в составе их алгоритмов. "остаточный член на n-ной итерации", такие вот штуки, и, конечно, кому это надо, они это считают. Смутно конечно помню это с курсов в универе. Но суть представляю: зачем на каждую операцию погрешность считать, тратя на это время, если про многие популярные методы вычислений эти погрешности уже аналитически рассчитаны.
А нафига делать паузы, если скроллящийся текст читаем? На смартфоне, например я скроллю чуть ли не постоянно в принципе, если что-то читаю, причём привык так сразу как только на аппарат с 144Гц перешёл. И примерно с тех же пор вовсе перестал пользоваться eink читалкой, где можно было только pageup/pagedown. Убедиться, что я до конца страницы дочитал, перед перелистыванием, вот ещё. На компе конечно сильно от задач зависит, но код тоже скроллить привык а не закладки на каждый нужный (и ненужный) момент ставить.
Сложно не быть скептиком на эту тему. Полагаю у людей со стократным годовым доходом проблем на этот случай может быть меньше, чем у тех, кто и не пытался раньше ничего "отбеливать", потому как это было не нужно и странно вовсе. У меня вон выписка о покупке долларов в банке за 5 лет перестала быть читаемой в принципе, но даже и она, как я понимаю, не является юридически значимым документом.
И вот не понятно как с такой историей будут работать. Потому что если это засчитывается, то смысл вообще от всех этих проверок кроме нервотрепки? А если не засчитывается, то даже сложно представить какому проценту людей будет не объяснить откуда у них деньги...
Ну так сенсорика человека вещь индивидуальная, да и вообще довольно-таки хрупкая. Кто-то реально не может различить 60 и 120 фпс. Кто-то не может различить даже 24 фпс и 60, а поскольку это "не лечится" с одной стороны, а с другой - ну не то что бы сильно меняет качество жизни, то почему бы не убедить сначала себя, а потом попытаться окружающих, что это мол норма.
Нормальное решение минут пять-десять только голосом объяснять, <...> то, которое справится с всеми возможными замкнутыми комнатами, не попадая в ту же клетку более чем дважды для большинства клеток.
Беру свои слова назад :) На чуть более сложных картах, чем тривиальные (= прямоугольные без препятствий) я так и не пришел к такому решению (которое ограничивает количество повторных посещений клеток, не зависящим от размера карты числом), в фоне думая об этом уже вон сколько.
А чему Вы радуетесь в коде из поста
Скрытый текст
def Clean(robot: Robot, x=0, y=0):
state.add((x,y))
if (x,y-1) not in state and robot.Up():
Clean(robot, x, y-1)
if (x,y+1) not in state and robot.Down():
Clean(robot, x, y+1)
if (x-1,y) not in state and robot.Left():
Clean(robot, x-1, y)
if (x+1,y) not in state and robot.Right():
Clean(robot, x+1, y)
я ума не приложу. Он же даже на тривиальных картах не работает как MVP (не обходит каждую клетку). Упретесь в угол, соседи все были посещены, идти дальше некуда. Единственное, где он работает верно, если на тривиальной карте (ну это не совсем правда, некоторые препятствия он все же обходит) запускать из одного из углов карты :)
Самый простой MVP это как-то так: строим карту препятствий. Идем в ближайшую клетку которую мы еще не сканировали (scanned(x,y)==false), оттуда пробуем Left-назад, Right-назад, Up-назад, Down-назад [сноска1] (если клетки в соответствующем направлении не были посещены И не были проверены на препятствие) и проставляем scanned(x,y)=true, затем идем (можно по кратчайшему пути) в ближайшую клетку, где мы еще не производили сканирование препятствий, и которая не является препятствием сама. Три мапы: visited, blocked и scanned. Visited имеет тот же смысл, что not blocked, это клетки в которых мы были (потому что в них можно побывать). То есть для каждой клетки (x,y) ее !scanned превращается в заполненную информацию blocked/visited ее соседей.
Сноска1: если в Left-назад не удался left, назад идти не надо, а левой клетке проставляем blocked=true. Аналогично для оставшихся трех направлений.
Так мы хотя бы гарантированно обойдем все доступые клетки, только это драматически неэффективно.
На картах с небольшим количеством препятствий можно оптимизировать: Scanned делаем не bool а битовой маской уже проверенных направлений из этой клетки. 0x1 left, 0x2 right, 0x4 up, 0x8 down. Полностью просканированная клетка, соответственно имеет значение 15 (1+2+4+8), и туда мы идем только, если через нее проходит кратчайший маршрут в следующую нужную нам точку. Во всех остальных клетках мы обязаны побывать, и проверить те направления из четырех, которые еще не проверяли (тут напрашивается оптимизация1, о ней ниже). Теперь мы можем идти, по возможности, не меняя предыдущее направление, дальше: допустим мы в клетке (x,y), идем влево, получается: тогда scanned(x,y)+=0x1 (left), visited(x-1,y)=true и из клетки (x-1,y) идем влево тем же способом. Если уперлись в препятствие, возвращаемся к ближайшей клетке, где scanned != 15 и проверяем оставшиеся направления. Оптимизация2 будет заключаться в оптимальном выборе "следующего" направления для проверки для заданной клетки.
Оптимизация1: если мы попали в точку (x,y), то для всех 4 ее соседей можно сразу проставить соответствующие направления scanned. scanned(x,y-1)+=0x8 (для точки (x,y-1) точка (x,y) является нижним соседом, в нее очевидно можно попать, если сама точка (x,y-1) не является препятствием), scanned(x-1,y)+=0x2, и еще 2 кейса.
Оптимизация2: приоритетное направление стоит выбирать как то, в котором можно пройти потенциально бОльшее число клеток. Держим для карты XMin, XMax, YMin, YMax, которые просто значения минимумов и максимумов из координат тех клеток, где мы уже были (visited, напомню, что это тоже самое что known as not blocked). Соответственно, направление это то, где X-XMin, XMax-X и еще два соответствующих варианта - даст максимальное значение.
Здесь нужно еще не запутаться в лапше кода. Потому что blocked это клетки в которые точно нельзя попасть, но при этом из-за оптимизации1 для них вполне могут быть частично проставлены флаги scanned. Ничего страшного, просто имеем в виду. А еще, по большому счету, после введения битовых масок в scanned нам не нужна больше даже мапа visited, она тривиально получается из разворачивания scanned для ее соседей.
Ах да, кратчайший путь ищем обычным BFS, из текущей клетки заполняем динамический массив расстояний до каждой другой точки карты, выбираем там минимум, и сам путь. Никакого смысла что-то усложнять для карт менее, чем из миллиона элементов особо не вижу, но и не в этом сложность. Это минут за 10 пишется, если "рука набита".
Подытожу:
В принципе, это лучшее, что я придумал, не затачивая под конкретные частные случаи возможных карт, и есть интуитивное представление, что под общие случаи ничего сильно лучше не придумать
Это ни разу не 5 минут объяснять.
Это точно не написать за час, если не писал в точности ровно тоже самое раньше
Я не сдержал изначальную "обещания": никакой гарантии о посещении клеток не более чем по два раза здесь нет. Но на около-тривиальных картах (прямоугольные, препятствия все изолированные друг от друга), так и будет конечно. Но так же я могу нарисовать карту, где некоторые клетки будут посещены вплоть до O(общее количество клеток) раз. У робота нет вообще никакой информации о карте изначально, потому так и сложно.
Насколько сложная задача - каждый сам сделает выводы, но лично я, если бы не решал несколько подобную задачу о "слепом пакмэне" отнес бы ее к very hard.
Я и по другую сторону стола сидел, и принял бы в идеале аргумениированный ответ "никак" как финальную точку понимания теории алгоритмической сложности.
Ограничить дерево - это один из способов, да.
Конечно, у нас же дерево в память помещается, а памяти в реальной машине конечное количество, так что на самом деле практически выполнимых алгоритмов с потреблением памяти больше O(1) не существует. Как однократная "шутка" от кандидата это определено плюс. Но второй раз уже не смешно.
Второй вариант: амортизация, если подсчёт перенести в построение или изменение дерева, то получение суммы будет вообще константа.
В дереве, где элементы и их сумма фиксированной длинны, да, конечно, вариант. Было бы в условии задачи это ещё отражено :)
Третий вариант: в дереве нужны ссылки на родителя и соседа, тогда можно сделать обход без дополнительной памяти через конечный автомат.
Ну формально мы добавили ссылки на родителя и соседа в каждый элемент дерева и благополучно сожрали на это O(количество узлов) памяти. Если у нас уже такое дерево было, то круто, а если нет, то условие задачи не выполняется. Это примерно про то, что я в комментарии выше написал, про выбор структуры дерева в памяти.
Ещё можно использовать модификацию дерева, тогда не требуется дополнительная память
Тогда, зачастую, можно и дерево не хранить, а просто только сумму :) напоминает загадку "а и б сидели на трубе".
Но окей, не спорю, есть о чем поговорить, так что вопрос хороший.
Как было у Стругацких: любой может решить решаемую задачу, нам надо решить не решаемую :)
Только вот привычно понимаемым целям найма это несколько противоречит.
Мне важно видеть то, как человек решает задачу которую он НЕ знает, то есть, вынужден думать и искать решение, чем проверять его память.
Скручивать опыт я ещё не пробовал, но вот и о том что в топ-100 codingamer'ов в резюме не добавляю. "только не литкод, пожалуйста, только не литкод" :)
Понял бы я чем Вы хвастаетесь и о чем вся эта ветка дискуссии была. Вот там ниже комментатор написал про петиции, и в целом даже не буду радоваться, что вовремя обозначил "что вопрос никого не волнует", цифры это показывают. С другой стороны моего голоса там не было, так что и утверждаться тут нечем.
У Вас мягко говоря странные представления о психологическом насилии, оно в виде сиюминутного эпизода не особо интересно. Но если это систематика на года, то жизнь может уже обратно не поменяться в принципе.
Осталось понять по отношению к чему покупательная способность за тот же год (на самом деле, немного побольше) упала на те же 20%.
Разложить в фурье и понизить коэффициенты у известных частот. Впрочем если уже фурье сворачивать в нужный диапазон значений хотя бы тем же xor, то никаких проблем я придумать не могу.
И ещё такая мысль. Если в задачу входит управление роем робопылесосов на одной и той же карте с соперником в равных условиях с сохранением всех остальных условий, то это настоящая котлета :)
Пропорция увеличивается в зависимости от размера карты, и да именно:
Конечно я "просрал весь бюджет времени" в рамках Вашей идеи задачи для собеседования. 10 минут потратил на то что бы критиковать. 20 минут на описание того, что сделал бы. 30 минут на реализацию этого. 10 минут на придумывание первых тестов в формате input.txt output.txt, карты которые рисовал вручную и так же вручную считал сколько полей останутся неочищенными. Знаете, тоже труд. Никакого генератора у меня не было, потому что алгоритма, который по входу построит мне правильный выход у меня не было. Поэтому рисовал поля от 5х5 до 15х15. И, конечно тут же тесты сфейлились, и пришлось ещё потратить 30 минут на отладку. Правда в этот же момент я заметил, что оптимизация2 это полная ерунда на реальных картах. Следующим шагом я бы с удовольствием нагенерил бы карт побольше (и побольше размером) и стал бы думать не только над корректностью ответа, но и конкретными оптимизациями вызова move(). Не беда, выходные будут - думаю ещё займусь.
Вернувшись к тому, что Вы говорите о вопросе тестируемости, конечно в общих словах я всецело согласен. Удивляет вообще сам факт наличия людей, которым хватает временного бюджета и на MVP решение задачи и на хотя бы ограниченное тестирование. Поэтому прямой вопрос, а они правда были? Вопрос провокационный, но без подвоха.
Согласен, задача вовсе не верихард, а ближе к медиум на литкоде, и требует должной сообразительности, но напрашивается ещё один вопрос, в чем смысл нанимать людей, которые справляются именно с этим, то есть, ну почему Вам нужны именно такие люди.
По моему опыту почти все знакомые сеньоры знатные слоупоки. Такое вот вынужденое искажение происходит.
Да, искажение, Вы абсолютно правы. Мне интересно решать задачки, не потому, что их вообще можно решить, а потому, что их можно решить лучше других. Говорили, что это должно пройти, но нет, время не лечит, и теперь просто это стало хобби. Иногда, конечно искажающим другие процессы, но кто в сущности то без этого :) На CG особого усердия, кстати в топ попасть много не надо, это надо не все подряд хорошо решать, а просто в паре-тройке челленжей абсолютно выиграть.
Да, каюсь, все же не такая уж и сложная задача. Вот уж теперь не знаю, что меня заставило проглядеть идею о том, что код из поста нужно немного исправить, чтобы он заработал. Наверное стойкое ощущение, что в том направлении он все равно был бы безобразно неэффективен (ну это некоторая деформация, да).
Но, оказалось, что это не правда. Я все же написал, как и обозначил идею, решение с битовыми масками для оптимизации обхода. На самом деле тоже не очень много времени заняло, если бы не отладка, то меньше получаса, ну оно работает, хорошо работает, только вот на том небольшом количестве карт для тестирования, которые вручную нарисовал, едва ли более чем в 2 раза более эффективно (в количестве Move()) в среднем, чем предложенный Вами код.
А значит, то решение, направление которого Вы предлагаете вполне решает поставленную задачу. И действительно вполне укладывается и в обозначенное время, и не надо было ничего переусложнять :)
В принципе я и так счел задачу интересной, теперь соглашусь, что пусть и не ультимативно, но в заданном формате собеседований это может быть хорошим выбором.
Да-да, я примеры тоже уже успел посочинять немного, на них все становится сразу более-менее понятно. Мне кажется, именно этого посту и не хватало, чтобы получить более положительную реакцию; привычка читать "по диагонали" уже скорее ближе к норме, чем исключениям, а тут и люди и кони, и странный пылесос, и какие-то движущиеся объекты, и карты со странной геометрией, а нет, все банально об "обойди такую штуку
Скрытый текст
более-менее эффективно через точно заданный API".
Надеюсь все благополучно решите.
Но вот для меня как раз "стейкинг" usdt под 17% годовых и был последним звоночком, после которого я вывел с этого кошелька свою горстку тона. Который примерно с этих же пор так и не подрос.
Синусы как раз прекрасно сводятся к простым суммам (ряды Тейлора), но не понятно, как это вообще должно быть связано с отображением результата. В sin(1) ни конечной в десятичной записи рациональной дроби, ни даже периодической вы не увидите, поэтому, по сути вопрос в том, на каком знаке после запятой его округлить. А это примерно "как пользователю нужно". Меня бы 0.01745 бы устроило, кроме тех случаев, когда нужно дальше с этим что-то считать.
Дело в том, что хорошие вычислительные методы, дают предсказуемую погрешность, зачастую значительно меньшую, чем погрешность отдельных операций в составе их алгоритмов. "остаточный член на n-ной итерации", такие вот штуки, и, конечно, кому это надо, они это считают. Смутно конечно помню это с курсов в универе. Но суть представляю: зачем на каждую операцию погрешность считать, тратя на это время, если про многие популярные методы вычислений эти погрешности уже аналитически рассчитаны.
А нафига делать паузы, если скроллящийся текст читаем? На смартфоне, например я скроллю чуть ли не постоянно в принципе, если что-то читаю, причём привык так сразу как только на аппарат с 144Гц перешёл. И примерно с тех же пор вовсе перестал пользоваться eink читалкой, где можно было только pageup/pagedown. Убедиться, что я до конца страницы дочитал, перед перелистыванием, вот ещё. На компе конечно сильно от задач зависит, но код тоже скроллить привык а не закладки на каждый нужный (и ненужный) момент ставить.
Сложно не быть скептиком на эту тему. Полагаю у людей со стократным годовым доходом проблем на этот случай может быть меньше, чем у тех, кто и не пытался раньше ничего "отбеливать", потому как это было не нужно и странно вовсе. У меня вон выписка о покупке долларов в банке за 5 лет перестала быть читаемой в принципе, но даже и она, как я понимаю, не является юридически значимым документом.
-- Откуда деньги, которыми погасил кредит?
-- Так вот продал доллары
-- Откуда доллары?
-- Так вот купил 5 лет назад
-- А откуда деньги были на покупку этих долларов?
-- 10 лет под подушкой копил
И вот не понятно как с такой историей будут работать. Потому что если это засчитывается, то смысл вообще от всех этих проверок кроме нервотрепки? А если не засчитывается, то даже сложно представить какому проценту людей будет не объяснить откуда у них деньги...
Ну так сенсорика человека вещь индивидуальная, да и вообще довольно-таки хрупкая. Кто-то реально не может различить 60 и 120 фпс. Кто-то не может различить даже 24 фпс и 60, а поскольку это "не лечится" с одной стороны, а с другой - ну не то что бы сильно меняет качество жизни, то почему бы не убедить сначала себя, а потом попытаться окружающих, что это мол норма.
Беру свои слова назад :) На чуть более сложных картах, чем тривиальные (= прямоугольные без препятствий) я так и не пришел к такому решению (которое ограничивает количество повторных посещений клеток, не зависящим от размера карты числом), в фоне думая об этом уже вон сколько.
А чему Вы радуетесь в коде из поста
Скрытый текст
я ума не приложу. Он же даже на тривиальных картах не работает как MVP (не обходит каждую клетку). Упретесь в угол, соседи все были посещены, идти дальше некуда. Единственное, где он работает верно,
если на тривиальной карте(ну это не совсем правда, некоторые препятствия он все же обходит) запускать из одного из углов карты :)Самый простой MVP это как-то так: строим карту препятствий. Идем в ближайшую клетку которую мы еще не сканировали (scanned(x,y)==false), оттуда пробуем Left-назад, Right-назад, Up-назад, Down-назад [сноска1] (если клетки в соответствующем направлении не были посещены И не были проверены на препятствие) и проставляем scanned(x,y)=true, затем идем (можно по кратчайшему пути) в ближайшую клетку, где мы еще не производили сканирование препятствий, и которая не является препятствием сама. Три мапы: visited, blocked и scanned. Visited имеет тот же смысл, что not blocked, это клетки в которых мы были (потому что в них можно побывать). То есть для каждой клетки (x,y) ее !scanned превращается в заполненную информацию blocked/visited ее соседей.
Сноска1: если в Left-назад не удался left, назад идти не надо, а левой клетке проставляем blocked=true. Аналогично для оставшихся трех направлений.
Так мы хотя бы гарантированно обойдем все доступые клетки, только это драматически неэффективно.
На картах с небольшим количеством препятствий можно оптимизировать: Scanned делаем не bool а битовой маской уже проверенных направлений из этой клетки. 0x1 left, 0x2 right, 0x4 up, 0x8 down. Полностью просканированная клетка, соответственно имеет значение 15 (1+2+4+8), и туда мы идем только, если через нее проходит кратчайший маршрут в следующую нужную нам точку. Во всех остальных клетках мы обязаны побывать, и проверить те направления из четырех, которые еще не проверяли (тут напрашивается оптимизация1, о ней ниже). Теперь мы можем идти, по возможности, не меняя предыдущее направление, дальше: допустим мы в клетке (x,y), идем влево, получается: тогда scanned(x,y)+=0x1 (left), visited(x-1,y)=true и из клетки (x-1,y) идем влево тем же способом. Если уперлись в препятствие, возвращаемся к ближайшей клетке, где scanned != 15 и проверяем оставшиеся направления. Оптимизация2 будет заключаться в оптимальном выборе "следующего" направления для проверки для заданной клетки.
Оптимизация1: если мы попали в точку (x,y), то для всех 4 ее соседей можно сразу проставить соответствующие направления scanned. scanned(x,y-1)+=0x8 (для точки (x,y-1) точка (x,y) является нижним соседом, в нее очевидно можно попать, если сама точка (x,y-1) не является препятствием), scanned(x-1,y)+=0x2, и еще 2 кейса.
Оптимизация2: приоритетное направление стоит выбирать как то, в котором можно пройти потенциально бОльшее число клеток. Держим для карты XMin, XMax, YMin, YMax, которые просто значения минимумов и максимумов из координат тех клеток, где мы уже были (visited, напомню, что это тоже самое что known as not blocked). Соответственно, направление это то, где X-XMin, XMax-X и еще два соответствующих варианта - даст максимальное значение.
Здесь нужно еще не запутаться в лапше кода. Потому что blocked это клетки в которые точно нельзя попасть, но при этом из-за оптимизации1 для них вполне могут быть частично проставлены флаги scanned. Ничего страшного, просто имеем в виду. А еще, по большому счету, после введения битовых масок в scanned нам не нужна больше даже мапа visited, она тривиально получается из разворачивания scanned для ее соседей.
Ах да, кратчайший путь ищем обычным BFS, из текущей клетки заполняем динамический массив расстояний до каждой другой точки карты, выбираем там минимум, и сам путь. Никакого смысла что-то усложнять для карт менее, чем из миллиона элементов особо не вижу, но и не в этом сложность. Это минут за 10 пишется, если "рука набита".
Подытожу:
В принципе, это лучшее, что я придумал, не затачивая под конкретные частные случаи возможных карт, и есть интуитивное представление, что под общие случаи ничего сильно лучше не придумать
Это ни разу не 5 минут объяснять.
Это точно не написать за час, если не писал в точности ровно тоже самое раньше
Я не сдержал изначальную "обещания": никакой гарантии о посещении клеток не более чем по два раза здесь нет. Но на около-тривиальных картах (прямоугольные, препятствия все изолированные друг от друга), так и будет конечно. Но так же я могу нарисовать карту, где некоторые клетки будут посещены вплоть до O(общее количество клеток) раз. У робота нет вообще никакой информации о карте изначально, потому так и сложно.
Насколько сложная задача - каждый сам сделает выводы, но лично я, если бы не решал несколько подобную задачу о "слепом пакмэне" отнес бы ее к very hard.
В принципе, это весело.
Я и по другую сторону стола сидел, и принял бы в идеале аргумениированный ответ "никак" как финальную точку понимания теории алгоритмической сложности.
Конечно, у нас же дерево в память помещается, а памяти в реальной машине конечное количество, так что на самом деле практически выполнимых алгоритмов с потреблением памяти больше O(1) не существует. Как однократная "шутка" от кандидата это определено плюс. Но второй раз уже не смешно.
В дереве, где элементы и их сумма фиксированной длинны, да, конечно, вариант. Было бы в условии задачи это ещё отражено :)
Ну формально мы добавили ссылки на родителя и соседа в каждый элемент дерева и благополучно сожрали на это O(количество узлов) памяти. Если у нас уже такое дерево было, то круто, а если нет, то условие задачи не выполняется. Это примерно про то, что я в комментарии выше написал, про выбор структуры дерева в памяти.
Тогда, зачастую, можно и дерево не хранить, а просто только сумму :) напоминает загадку "а и б сидели на трубе".
Но окей, не спорю, есть о чем поговорить, так что вопрос хороший.
Только вот привычно понимаемым целям найма это несколько противоречит.
Скручивать опыт я ещё не пробовал, но вот и о том что в топ-100 codingamer'ов в резюме не добавляю. "только не литкод, пожалуйста, только не литкод" :)
Впрочем, если структуру представления дерева в памяти выбираю я сам, то конечно есть решение :)
Ну если считать ограниченной высоту дерева, то, думаю и больше трех найдётся. А если нет, увы, это какая-то революция в CS.