Задача из Моего Собеседования в Amazon - Поиск в Ширину 

Создал Telegram канал, в котором рассказываю о жизни в Лондоне, работе в Google и подготовке к собеседованиям. Подписывайтесь: t.me/saschalukin

С анимацией отлично получилось. Очень интересно смотреть твои разборы задач + тембр и подача приятные. Если позволяет время - пиши побольше видео.

Увидимся через полтора года!

Никогда даже не хотел понимать задачи с шахматной доской , после просмотра понял алгоритм 💪🏾

Долго тебя не было, рад новому видео!

Саша анимация вообще супер!!! Видео было настолько интересным что ни секунды не промотал. Спасибо за такое понятное и четкое объяснение

Мощно ты запарился за анимации!) Но получилось явно очень наглядно и понятно!

Выпускай чаще пожалуйста, ты лучший мой мотиватор )))

Спасибо! Отличное видео, интересная задача! Ждем новых роликов.

Спасибо за задачу! Очень подробно объяснил)

Спасибо за видео. На курсах по изучению Пайтон решал эту же задачу:)) интересно посмотреть твое решение. Лайк

Анимация наглядная, круто!

Вау, очень крутое и понятное объяснение. Анимация - огонь

очень интересная задача. хорошо рассказано. выпускай ролики чаще

круто, спасибо за видосы!

Спасибо, хорошая задача и разбор

Задача класс! Больше подобного контента!

Спасибо за задачу

С анимацией хорошо получилось, пожалуйста, делай больше видео

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

Для всех, кто пишет что в алгоритме ошибка, так как мы смотрим только на предыдущий слой и теряем информацию о предыдущих слоях: На самом деле ошибки нет, вероятно комментаторы путают с алгоритмом DFS или вариантом BFS на очереди (где нужно запоминать все посещенные вершины). Почему этот алгоритм корректен? Если предположить что на текущем шаге мы попытаемся пойти из ячейки X в ячейку Y, в которой уже были, но которая лежит не в предыдущем слое, то значит она лежит в предпредыдущем или более ранних слоях. Но тогда мы бы перешли по этому ребру Y - X в тот момент, когда рассматривали эту клетку Y и в этом случае X лежало бы не в текущем слое, а в следующем за слоем, в котором лежит Y. Но в предположении X лежит именно в текущем, а Y лежит не в предыдущем. Значит предположение неверно, а значит достаточно рассматривать для клеток, которые мы хотим посетить, лежат ли они в предыдущем слое. И этого будет достаточно.

Congrats Alex! Good explanation. Here is a point you can deal better with: You were java dev, and you use java terminology in your verbal explanations, but code is written in python. So little fellas can easily miss those word about hashed collection. Hope you'll continue doing videos like this)

Блин, смотрю каждое твое видео. Спасибо за контент. Тоже мечтаю попасть в google

Блин! точно! это же графы! спасибо большое!

Лучший мотиватор!

Здесь можно (даже бы я сказал нужно) использовать алгоритм А*, а за эвристическию функцию можно взять манхеттенское расстояние от коня до конечной клетки

спасибо за видео

Спасибо!

Спасибо за bfs! Но в аналитическом решении сложность О(1). N = (lnl + lml)/3 ± 4. Начальные координаты коня (0,0), конечные (n, m). Если рассмотреть как ходить в конце (варианты), то формула будет без погрешностей.

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

Альманах...круто, мне нравится

Привет! Заметил пару неточностей. 1. Ты говоришь, что не посещаешь уже посещенные клетки. Но это утверждение верно только для предыдущего слоя - в коде ты никак не помечаешь те клетки, что были посещены ещё раньше. 2. Формально это можно назвать обходом графа в ширину, но мне кажется, это решение методом динамического программирования. А если попытаться оптимизироавть решение и не проверять заведомо более длинные пути (а ограничиться только квадратом (0, 0) (n, n)), то это уже точно не будет обходом графа в ширину(так как мы не посещаем все вершины). 3. Решение данной конкретной задачи обходом графа в ширину довольно неэффективно - сложность получается ~(2n)^2*Log(n), тогда как методом динамического программирования мы можем обойтись n^2, перебрав каждую вершину урезанного квадрата лишь единожды. n это большая по модулю координата целевой точки. Upd: попытавшись набросать решение методом динамического программирования, понял, что у меня не получается) Конь ходит слишком сложно, чтобы за один проход можно было заполнить массив, не возвращаясь к уже посещённым клеткам. А вот в обходе графа ограничить поле всё равно было бы нелишним.

Спасибо

Хорошая задачка, но мне больше интересно как анимация делалась :)

Делай, пожалуйста, больше видео по алгоритмам

Тут экспоненциальный рост клеток с каждым слоем и симметрия 4-го порядка, стоила взять координаты цели по модулю и начать с двух ходов 1, 2 и 2, 1 на первом слое. Так-же можно игнорировать все клетки с отрицательными координатами, это сэкономит память.

Анимация огонь )) Но задается вопрос, т.к. мы знаем паттерн движения коня, то почему не исключить несонаправленные вектора для, новых точек и вектора старта и финиша ?

Can we see the same BFS done recursively ? Would it be an easier way to implement if you have just 15 minutes?

Добрый день, Александр, отличное видео! Вы устраивались на Junior Software Engineer, я правильно понимаю?

у меня в школе была задача посчитать за какое минимальное число шагов конь пройдет по каждой клетке поля по 1 разу. И всё это на паскале с отрисовкой доски и прочего)

Видосы у тебя всегда классыные, и объясняешь хорошо, побольше бы. По самому алгоритму. Слишком ресурсоемко обходить все клетки, особенно для большого поля, например, если выход стоит в 50,50 зачем нам идти в минус? а там будет обход и просчет лишних тысяч вариантов, а если доска 100тыс на 100тыс ? Как-то слишком в лоб, можно оптимизировать, тем более, что мы знаем, что конь всегда сдвигается на 2 и 1 клетку, можно заранее проложить маршрут в направлении выхода, а потом при приближении уже перебирать варианты. Конечно, код будет сложнее, но все зависит от задачи, надо экономить ресурсы или нет.

Сначала конь на клетке 1:1 (зачем-то), потом уже на логичной 0:0. Ну и можно оптимизировать конкретный кейс с учетом осей симметрии доски и обработать только 1/8 всех клеток.

Четко

Сразу в голову пришла идея через обход в ширину как только сказал про хеш-таблицу ( чтобы в ней хранить позиции, в которых мы были ). На код варсе это 3-4 тир задач.

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

Хм. Зачем там хеш-таблица, если проще и быстрее использовать, например, очередь? Я в обходе в ширину обычно просто добавляю в конец очереди новые вершины-кандидаты на обход. Вершины (в данной задаче клетки), которые уже обошли, хранить в отдельной структуре (в данной задаче я бы использовал двумерный массив, но можно и хеш-таблицу).

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

Так, если координаты конечной точки известны, то может можно искать только в направлении заданой четверти, чтобы не перебирать 3/4 заведомо не нужных направлений?

Вообще в классическом БФС используется очередь (Queue), а не некие уровни. 1. Запихиваешь в очередь первую клетку. 2. Извлекаешь. 3. Находишь всех соседей, в нашем случае восемь возможных ходов коня. 4. Фильтруешь уже посещённые. 5. Запихиваешь в очередь. 6. Гото 2 до победы. Если смотреть только на previous_layer, то потеряется информация о посещённых клетках на предыдущих ходах.

Во-первых нормализовать данные. Стартовая клетка пусть будет (0,0), а координаты цели во-первых возьмем по модулю, что не изменит количество шагов, а перенесет цель в верхний правый квадрант заеркально осей, и затем если Х > Y поменяем их местами, чтобы поместить цель выше диагонали (0,0) - (N,N). Для квадрата 5х5 проще всего создать хэш-таблицу, выйдет всего 14 элементов. Если цель дальше 5 клеток то "прыгаем" к ней двигая доску, или вычитая (2,1) из координат цели, добавляя к счетчику 1. Если на очередной итерации цель ушла левее оси Y (отрицательный X), либо "упала" под диагональ (Y < X), то вычитаем не (2,1), а либо (2, -1), либо (1, 2) соответственно. Физический смысл легко увидеть если нарисовать каждую из ситуаций. Как только на очередной итерации мы попали в квадрат 5х5 к цели, снова нормализуем координаты и берем значение из таблицы, добавляем к счетчику итераций и получаем итоговое. Некрасивая таблица из 14 значений с лихвой компенсируется сложностью О(n) и нулевым выделением памяти на каждой итерации. Описывать сложнее, чем написать код.

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

через 3 недели у меня тоже собеседование в амазон. в алгоритмах я слаб и учу их практически с нуля. прежде чем посмотреть видео, поставил его на паузу и попробовал решить задачку сам. получилось решить ее за 5 минут. попадется ли мне подобная задача на собеседовании, это уже как повезет.

un canal ruso que encontré para aprender estructura de datos muy buen canal

Можно слоями, а можно просто назначить вес каждой клетке.

Вычисляем первый круг, а дальше копипастим весь массив с наложением в нужную сторону. Если требуется заполнение всей доски или идет непопадание, возможен банальный брутфорс, либо от последней позиции, либо вообще всех возможных комбинаций массива.

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

Мне в голову dict пришёл. Можно ли это реализовать, если layer_number - ключ, а сет таплов(или списков) с доступными координатами - значение?

Хорошее решение. Мысленно представил как решать это на C++, но на Питоне, конечно, компактнее получается решение. Единственный неявный для меня момент алгоритма - это то, что запоминается только предыдущий и текущий слои. Видимо, подразумевается, что с более старыми слоями пересечения быть не может. Приму на веру, видимо, есть строгое доказательство данного факта.

Ееее Саша видос запилил ща смотреть буду

Стоит ли идти учиться на программиста если уже одну профессию закончил но она мне не нравится? Мне уже 23 года - стоит ли рисковать и переучиваться на программиста?

конь на нулевых кордах, мы просто берем число координат, до которых нам нужно дойти и переводим их в положит число, например дали -2 -7, то это считаем как 2 и 7, если -2 7, то 2 7 и тд. берем эти х и у, отнимаем максимальное количество 3 1, 1 3, 6 0 и 0 6 (последняя пара дает sum+=2, первая sum++) до того момента, пока х

Здравствуйте, Александр, а Лукин Владимир Николаевич не ваш родственник (в маи преподаёт) ?

А входит ли в условие задачи память? Ведь алгоритм не слабо так сжирает память

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

функция moves более надежно но абсолютно нечитабельно записывается в данном виде: from itertools import permutations, product return [tuple(em * es for em, es in zip(m,s)) for m, s in product(permutations([1, 2]), product(*permutations([1, -1])))]

Легенда вернулась, увидимся через год?)

Какие 7.5к € джуниору в Германии?; 90к в год даже техлиды не все получают. В 4к брутто - поверю, если данные есть: законченый универ, например, с дуальным обучением.

Не,вообще транзитивное замыкание с минимальным весом штука крутая и очень мощная,но тут явно можно докрутить из-за специфики задачи. Скажем,вот у нас две точки,которые надо соединить и они образуют как бы прямоугольник и вот выясняется,что если его немного расширить,то любой минимальный путь можно перестроить без потерь так,чтобы он в прямоугольник попал. Для удобства перекрутим так всё,чтобы вход был слева снизу и выход справа сверху. Понятно,что на ответ это не повлияет,а вот на ход решения повлияет сжатием бреда. Докажем это замысловатое (или не особо) утверждение: Пускай есть какой-то путь и он неуменьшаем.Тогда все точки,которые выходят за верхнее ограничение мы отразим зеркально вниз,если есть такие две точки,что она на одном уровне.Понятно,что такое преобразование не изменит длинну пути,но применив так много раз потом мы запихаем весь путь в рамки наши.Проблема в том,что они могут быть на разных уровнях,так как по осям у нас переход на 2 или на 1. В этом случае придётся воспользоваться оптимальностью пути. посмотрим на кусок пути,где вот он начал уходить вверх за границу и в какой-то момент вернулся в в прямоугольник,но на уровень ниже (выше нельзя,так как там кончается граница).Тогда давайте заметим такой факт,что нам важно то именно с точки зрения конца пути чтобы всё было хорошо,а на остальное пофигу.Тогда отразим весь этот подпуть относительно горизонтали,проходящей через конец пути.В случае,если начало проблемного подпути было на одной высоте с точкой выхода проблем не будет,но вот если она была ниже на один,придётся ещё подумать. Итак,у нас плохой кусок пути начинается за 1 единицу до конца и заканчивается прямо на конце.Другие случаи мы уже разобрали,этот-последний. Тут прям нетривиально! Рассмотрим последние два действия. У нас проблемы из-за того,что последний ход был на 2 шага по высоте,иначе бы мы нашли что отразить. Так же первый шаг не был по высоте на 1,так как иначе после отражения мы посмотрим на 1 шаг до конца и сможем на изи отразить. Те первый и последний прыжки были на 2 вверх и вниз. Однако раз у нас не совпали высоты,применили прыжок по высоте на 1 нечётное число раз и хотя бы 1 раз. А что,если его убрать и вставить как нам надо? Тогда мы закончим на 2 клетку по иксу куда-то не туда и на 1 клетки по y куда-то не туда. рассмотрим все случаи:(+-2;+1) Тут просто,по иксу понятно что на 2 в нужную сторону догонимся и по игреку как раз одной хватит. Но что,если (+-2;-1),ведь тогда нам надо уже на 3 двигаться.Надо это как-то проработать. Тут просто на самом деле.В каком-то из ходов,где высота по 2 меняем сторону по высоте (как минимум,начало и конец с разными знаками и можно выбрать кандидата (последний после переворота перевернём и кайф)). Так же делаем по иксу хитрость нашу,когда слишком вправо. Влева и вниз - ну просто думаем,что путь шёл с конца на начало и наши рассуждения все. Тут важно,что при любом из описанных действий нехороший кусок теряем как минимум два звена в себе (они становятся хорошими) и конечным количеством таких действий получится всё запихать в коробку. Но какая же коробка? Как минимум,надо по каждой оси чтобы было длинна коробки 4,иначе не проходит наше приведение. Ведь в худшем случае мы сдвигались на 1,при этом замутив крутой перекрут,юзавший ещё 3 ниже. А лучшие вообще ничего не делали плохого:самое жёсткое-это на две спускались,чтобы плохой кусок уменишить. Те min{4;|start'-finish'|} по каждой оси. Ну или,если мы как-то узнали,что в пути нет последнего стрёмного варианта (мало ли),то min{3;|start'-finish'|}. Если что,это расстояние от начала и конца до противоположных стенок.Если не хватит,то увеличивать СО ВСЕХ СТОРОН! Теперь с чистой совестью можно урезать поле,зная,что все пути будут (хоть и перекрученные) найдены и замыкание именно для последней вершины будет таким же. Тут,конечно,важно,что для других вершин это будет не так (хотя,нам какая разница). Заметим,что такая оптимизация хоть и сложна в понимании,проста в реализации и при том очень эффективна.

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

Спасибо! 1. хотелось бы в коде видеть номера строк, чтобы ссылаться на них в комментах 2. не увидел ограничения доски, возможно мне стоит самому реализовать, но кажется, находясь в x=2 y=1 мы выскочим за пределы доски. 3. не увидел где инициализируются x, y, возможно это особенность, или просто опустили из примера. 4. что если выход будет в [-1, -1] ?

1. Полный перебор не нужен - можно оптимизировать: 1.1. если исходная клетка X

когда лет 20-25 назад делал игру Lines на дельфи аналогично просчитывал путь для шарика из исходной точки в точку в которую кликнул игрок

Поле a1 в шахматах черного цвета)

Можно добавить эвристическую функцию и получить AStar (будет быстрее)

Что мне нужно делать, что бы понимать о чем ты вообще говоришь)) Я вообще не улавливаю, что нужно изучать в самом начале ? Я хочу знать, но полагаю нужно дойти до этого, а что бы дойти, нужно с чего то начать, скажи с чего начать, если я даже не понимаю о чем ты говоришь :DDD

Шахматное поле предполагается бесконечным?

а почему не проверяем x и y плюсовый или минусовый ? если плюсовый то например -x не нужно посмотреть

А теперь попробуйте решить ту же задачу, но слегка сложней: Есть вместо одного k коней на поле. Нужно для каждой клетки поля понять за какое минимальное количество ходов один из этих коней доберется до нее

Знаю 2 решения: 1. За O(1) можно пересчитать по формуле, опирающиюся на полуинвариант сумм 2. BFS или Дейкстра, оба за O(n) в данном случае

Считаем разницу по оси X и Y между текущим положением коня и нужной клеткой, получим Sx и Sy. Если Sx и Sy кратны 3, то количество ходов = (Sx + Sy)/3. В противном случае if Sx>5 then Sx_first = round((Sx-3)/3, 0); Sx_last = Sx - Sx_first*3 else Sx_first = 0; Sx_last = Sx, то же для Sy, Sу_first, Sy_last. Sx_first + Sу_first - количество ходов, что бы оказать в окрестности Sx_last, Sy_last клетки, не более 5 клеток. И вот тут можно применить какой угодно алгоритм. В чём преимущество, если доска 1000^1000 на 1000^1000, то со слоями может быть проблема, а так нет.

у меня была такая задача но шахматная доска 1000 на 1000 и оно работает долго че делать?

Я так понимаю, доска задачи бесконечная? Функция moves не смотрит на границы доски.

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

КрасавчеГ!!!

Да ну нах..лучше в таксисты пойду.

Почему из первой точки 8 ходов, если всего 2, а остальные являются их отражением? Сильно подозреваю, что достаточно просто создать матрицу n*n, для одного квадранта, а потом вычислить координаты точки в этих матрицах.

О(n)^2 очень високая сложность. Можно ли сделать бистрее?

Что-то простенькая довольно задача и данное решение

Это же по сути полный перебор, а значит алгоритм не эффективный. Можно изучить свойства движения коня и вывести некую формулу. Типа идем на прямую к целевой клетке, пока она не попадет в заранее просчитанный квадрат 5*5. Возможно, можно просто формулу вывести четкую

Я бы решал через вектор до выхода - т.е. какой из возможных ходов сокращаяет дистанцию до выхода

Слишком ресурсоемкие затраты, не легче для начала отрезать длину перемещения коня +3 за шаг от позиции к близлежайшей точке где будет прямолинейное перемещение к цели, а там уже рассчитать в конце более краткий путь, ибо затраты на расчёт к каждой точке если это доска на 100млн, то расчёт всех слоев будет очень проблемным.

Но почему (1; 1), а не (0; 0), Карл?

Это вроде простой перебор всех возможных вариантов

А пузырьковый метод не сработал бы?

на с++ к сожалению реализация сложнее устроена)

есть подозрение, что задача решается проще, но мне лень сейчас думать :)

а нет названия у данного алгоритма? я так понял что это не типовой алгоритм

Я бы решал через граф, похожая задача была на лекциях у Тимофея Хирьянова, соответственно граф бы представлял из себя словарь с вершинами и множеством соседних вершин

А это язык программирования пайтон ?

Задача решается поиском в ширину. Решал аналогичную задачу в универе на экзамене по АСД (Алгоритмы и структуры данных) на третьем курсе