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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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)

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

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

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

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

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

Спасибо!

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

Спасибо

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

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

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

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

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

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

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

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

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

Во-первых нормализовать данные. Стартовая клетка пусть будет (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) и нулевым выделением памяти на каждой итерации. Описывать сложнее, чем написать код.

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

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

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

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

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

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

Четко

функция 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])))]

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

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

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, я правильно понимаю?

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

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

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

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

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

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

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

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

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

Считаем разницу по оси 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, то со слоями может быть проблема, а так нет.

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

Не,вообще транзитивное замыкание с минимальным весом штука крутая и очень мощная,но тут явно можно докрутить из-за специфики задачи. Скажем,вот у нас две точки,которые надо соединить и они образуют как бы прямоугольник и вот выясняется,что если его немного расширить,то любой минимальный путь можно перестроить без потерь так,чтобы он в прямоугольник попал. Для удобства перекрутим так всё,чтобы вход был слева снизу и выход справа сверху. Понятно,что на ответ это не повлияет,а вот на ход решения повлияет сжатием бреда. Докажем это замысловатое (или не особо) утверждение: Пускай есть какой-то путь и он неуменьшаем.Тогда все точки,которые выходят за верхнее ограничение мы отразим зеркально вниз,если есть такие две точки,что она на одном уровне.Понятно,что такое преобразование не изменит длинну пути,но применив так много раз потом мы запихаем весь путь в рамки наши.Проблема в том,что они могут быть на разных уровнях,так как по осям у нас переход на 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'|}. Если что,это расстояние от начала и конца до противоположных стенок.Если не хватит,то увеличивать СО ВСЕХ СТОРОН! Теперь с чистой совестью можно урезать поле,зная,что все пути будут (хоть и перекрученные) найдены и замыкание именно для последней вершины будет таким же. Тут,конечно,важно,что для других вершин это будет не так (хотя,нам какая разница). Заметим,что такая оптимизация хоть и сложна в понимании,проста в реализации и при том очень эффективна.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Обычный, но самый не эфективный алгоритм. Кто может сказать О если точни начало и конец находятся далеко друг от друга. Полиномия по любому. А решение проще. двигаемся на прямую в сторону исходной точки максимально быстро, останавливаясь на расстоянии одного прыжка от нее. там мы либо совпадем, либо придется прыгнуть в сторону 1 или 2 раза. Как быстрее прыгать вычисляем по формуле что больше |х1 - х2| или |y1 - y2|. Дальше смотрим, что делится на 2? Соответственно прыжки можно просто посчитать. Немного на пивасике, могу не очень ясно объяснять.

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

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

Моя проблема с этой задачей заключается в том что я знаю алгоритм DFS но не знаю как работают шахматы😅

осталось только посмотреть что такое A* и ускорить нахождение решения в среднем в 4 раза

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

А дальше должен быть тест, когда доска не 100х100, а 10 000 000 на 10 000 000 и нужно пройти из конца в конец.

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

В теории топологии пространства вообще можно ни куда не двигать фигуру....просто наложить на нужную клетку другую с конем

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

Единственное в чем не вижу смысла - проверка на наличие элемента в сете, т к сет нем может содержать повторяющихся элементов. Он автоматически их убирает

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

Почему променял джаву на питон?(

жаль код не на яве показал, подписывался из-за этого языка на канал(

Думал пойму, но не понял.

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

я бы ее не решил )

Я бы никак не решал её, просто заплакал бы. Реально, не получается понять как придумать алгоритм