Для всех, кто пишет что в алгоритме ошибка, так как мы смотрим только на предыдущий слой и теряем информацию о предыдущих слоях: На самом деле ошибки нет, вероятно комментаторы путают с алгоритмом DFS или вариантом BFS на очереди (где нужно запоминать все посещенные вершины). Почему этот алгоритм корректен? Если предположить что на текущем шаге мы попытаемся пойти из ячейки X в ячейку Y, в которой уже были, но которая лежит не в предыдущем слое, то значит она лежит в предпредыдущем или более ранних слоях. Но тогда мы бы перешли по этому ребру Y - X в тот момент, когда рассматривали эту клетку Y и в этом случае X лежало бы не в текущем слое, а в следующем за слоем, в котором лежит Y. Но в предположении X лежит именно в текущем, а Y лежит не в предыдущем. Значит предположение неверно, а значит достаточно рассматривать для клеток, которые мы хотим посетить, лежат ли они в предыдущем слое. И этого будет достаточно.
Более простое объяснение: предыдущий слой это как бы затычка для пути назад. А поскольку это поиск в ширину, то мы эти затычки ставим для всех возможных путей назад, то есть как не старайся не получится "обойти" предыдущий слой со стороны. Аналогия такая: два длинных коридора с дверьми, которые иногда пересекаются. Ты и твой друг идете одновременно от начала корридоров, и закрываете за собой каждую дверь. Так вот ты не сможешь в месте пересечения коридора пойти назад, т.к. твой друг уже закрыл за собой предыдущуб дверь. При этом не важно сколько до этого дверей было закрыто, главное что он последнюю закрыл в том месте, где вы встретились, поэтому ты не сможешь через его коридор пойти назад, и ты будешь вынужден пойти дальше вперед
Спасибо за объяснение. А для тех кто считает, что лучше один раз увидеть. Посмотрите на доску на которой Саша показал уже 3-й слой (4:08). Где-нибудь можно попасть с клетки 3-го слоя на клетку слоя 0 или 1.
Если брать очень большое поле, то для общего случая нахождения кратчайшего пути стоит добавит разбивку на сектора. В случае с конем можно сделать еще проще, первые ходы должны делаться с учетом кратчайшей дистанции, и только начиная с дистанции в 4 клетки выполнять обозначенный автором кульбит
Вот я тоже думаю, обход поля n*n это O(n^2), но кажется можно за линейную сложность. Типа мы можем просчитать окрестность исходной точки, потом из каждой точки окрестности сделать простой алгоритм, который примерно 1. Находит два необходимых вида шагов O(1) 2. Считает необходимое колво шагов O(1) k 3. Находит точное количества шагов для шага типа1 и типа2 (линейный поиск O(n), т.к суммарно шагов тип1+тип2 = k точно меньше 2n), и если ответ нашелся, значит это будет тип1+тип2+шаг окрестности. Если не нашелся, значит забиваем на эту точку окрестности 4. Повторяем для каждой точки окрестности и ищем минимальное среди ответов O(c), с количество точек в окрестности Итого у на фиксированная окрестность а количество шагов растет линейно, значит сложность лин поиска тоже растет линейно. Также заметим, что порядок шагов тип1 и тип2 не важен, так что тут все ок.
Здесь можно (даже бы я сказал нужно) использовать алгоритм А*, а за эвристическию функцию можно взять манхеттенское расстояние от коня до конечной клетки
Кстати, не уверен, что А* сработает в данном случае, так как алгоритм выберет самую ближайшую клетку к конечной клетке, но так как конь ходит буквой Г он же может крутиться несколько раз вокруг конечной клетки что бы в неё попасть. А соседняя клетка (которая будет иметь большее манхэтоновское расстояние) попадёт в конечную клетку раньше, хоть эвристика в ней изначально была больше. Я не ради прикопаться, мне тоже сразу в голову пришёл этот алгоритм, просто интересно так это или нет.
@@ЕгорПичугин-у5мконь бы не крутился вокруг цели. Он бы просто игнорировал уже пройденные ( найденые ходы ). Если с первой попытки он был не нашел путь, то начал бы обходить ближайшие. Но даже так это было бы куда эффективнее по памяти, чем делать поиск в ширину, так как мы не хранили бы явно плохие ходы
Привет! Заметил пару неточностей. 1. Ты говоришь, что не посещаешь уже посещенные клетки. Но это утверждение верно только для предыдущего слоя - в коде ты никак не помечаешь те клетки, что были посещены ещё раньше. 2. Формально это можно назвать обходом графа в ширину, но мне кажется, это решение методом динамического программирования. А если попытаться оптимизироавть решение и не проверять заведомо более длинные пути (а ограничиться только квадратом (0, 0) (n, n)), то это уже точно не будет обходом графа в ширину(так как мы не посещаем все вершины). 3. Решение данной конкретной задачи обходом графа в ширину довольно неэффективно - сложность получается ~(2n)^2*Log(n), тогда как методом динамического программирования мы можем обойтись n^2, перебрав каждую вершину урезанного квадрата лишь единожды. n это большая по модулю координата целевой точки. Upd: попытавшись набросать решение методом динамического программирования, понял, что у меня не получается) Конь ходит слишком сложно, чтобы за один проход можно было заполнить массив, не возвращаясь к уже посещённым клеткам. А вот в обходе графа ограничить поле всё равно было бы нелишним.
> если попытаться оптимизироавть решение и не проверять заведомо более длинные пути (а ограничиться только квадратом (0, 0) (n, n)), то это... ....не будет работать. Например конь (0,0) выход (1,1) А вообще, мне кажется тут есть математическое решение.
1) В этом и суть решения - можно проверять только предыдущий слой, нельзя попытаться пойти из слоя №3 НЕ в предыдущий слой №2 или следующий слой №4 (иначе бы слои формировались по-другому), поэтому не имеет смысла проверять все посещенные вершины, а только посещенные на последнем слое. Как раз таки поэтому это алгоритм обхода в глубину на двух списках (более классическое решение - одна очередь). 2) Метод BFS (Breadth-first search) как ни странно использует идею динамического программирования. Одно использует, а не заменяет другое. Вы ведь не скажете "Ну я бы не стал доезжать на работу на Мерседесе, я бы предпочел просто доехать на машине." Поиск в ширину реализуется на динамическом программировании. Посещать не все вершины - не значит не обходить граф, но оптимизации действительно здесь приемлемы (можете еще почитать про итеративный поиск в глубину iterative deepening depth-first search). 3) Тут используем хеш таблицу, а не дерево поиска, поэтому время работы алгоритма O(n^2). Но вы все еще правы, что BFS реализуется через идею динамического программирования, просто обход ячеек при рекурентном пересчете соответствует обходу графа.
Тут экспоненциальный рост клеток с каждым слоем и симметрия 4-го порядка, стоила взять координаты цели по модулю и начать с двух ходов 1, 2 и 2, 1 на первом слое. Так-же можно игнорировать все клетки с отрицательными координатами, это сэкономит память.
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)
Вообще в классическом БФС используется очередь (Queue), а не некие уровни. 1. Запихиваешь в очередь первую клетку. 2. Извлекаешь. 3. Находишь всех соседей, в нашем случае восемь возможных ходов коня. 4. Фильтруешь уже посещённые. 5. Запихиваешь в очередь. 6. Гото 2 до победы. Если смотреть только на previous_layer, то потеряется информация о посещённых клетках на предыдущих ходах.
@@rasimbot ну bfs как будто именно для поиска путей используется, а не расстояний, хотя его и можно упростить до поиска минимального расстояния. + как и сказано в видосе, bfs запускается на графе, хоть шахматная доска и представима в виде графа, сам граф в этом решении не строится и вряд ли можно говорить о bfs, хотя и оч похоже. Например, если эту задачку чуть изменить и просить искать не кратчайшее расстояние, а кратчайший путь (именно вывести все посещенные клетки по порядку), то решение из видоса как будто не позволит этого сделать, с bfs получилось бы (ну мне так кажется). Я не с целью надушнить, если что, если это решение без построение графа можно под вышеописанную задачу изменить, буду рад услышать)
Сначала конь на клетке 1:1 (зачем-то), потом уже на логичной 0:0. Ну и можно оптимизировать конкретный кейс с учетом осей симметрии доски и обработать только 1/8 всех клеток.
Обычная задача на волновой алгоритм. По предоставленному решению. Нет контроля выхода за границу доски. Также проверяем попадание в клетку на предыдущем уровне, но не на уровнях ранее, для данного контроля можно использовать обычный двумерный массив описывающий доску и хранящий уровни посещения в каждой клетке
Можно ещё параллельно вычислять дорогу от коня к точке и от точки к коню ровно до тех пор покуда не найдётся первое пересечение. Действий суммарно будет больше, но зато массив будет меньше...хотел сказать я, но потом обнаружил одно геометрическое свойство: сумма длин окружностей, пересекающихся в одной точке равна длине окружности с радиусом, равным расстоянию между центрами этих окружностей)))
Спасибо за bfs! Но в аналитическом решении сложность О(1). N = (lnl + lml)/3 ± 4. Начальные координаты коня (0,0), конечные (n, m). Если рассмотреть как ходить в конце (варианты), то формула будет без погрешностей.
Решение автора работает похоже на работу ИИ, он также связывает всё послойно, и между всеми элементами одного слоя и другого присутствует связь, таким образом происходит имитация синапсов, что помогает ему осмыслить любые возможные варианты.
функция 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])))]
@@widny31 ну да, я и написал, что хардкод в данном случае читабельнее. просто показал, как в Питоне выражается "по одной оси на два, по другой -- на один во всех возможный направлениях" посредством функций из itertools
Во-первых нормализовать данные. Стартовая клетка пусть будет (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) и нулевым выделением памяти на каждой итерации. Описывать сложнее, чем написать код.
Я тоже так решил. Я бы взял разность между координатами по модулю и вычитал (2, 1), (1, 2), пока это возможно, а затем конь либо достигнет цели, либо доберется до любой клетки рядом за 2 хода.
у меня в школе была задача посчитать за какое минимальное число шагов конь пройдет по каждой клетке поля по 1 разу. И всё это на паскале с отрисовкой доски и прочего)
Анимация супер! С помощью чего она сделана? Объяснение тоже класс, после него стала меньше бояться задач на шахматной доске. Немного сложно было воспринимать объяснение кода под музыку. Отдельное спасибо за питон!
Сразу в голову пришла идея через обход в ширину как только сказал про хеш-таблицу ( чтобы в ней хранить позиции, в которых мы были ). На код варсе это 3-4 тир задач.
Вычисляем первый круг, а дальше копипастим весь массив с наложением в нужную сторону. Если требуется заполнение всей доски или идет непопадание, возможен банальный брутфорс, либо от последней позиции, либо вообще всех возможных комбинаций массива.
Если наше поле заранее известного размера, то надо использовать обычный массив, а не хеш таблицы. И второе, поиск в ширину выглядит красиво, когда наша цель находиться в нескольких шагах, а когда до неё шагов 30, то мы умрём прежде чем поиск в ширину найдёт путь.
я бы решал через алгебру, но нужно обработать крайние случаи и написать костыли. А так если люди не против и нужно что-то сделать за короткое время то и так можно.
я бы решал это волновым алгоритмом (алгоритм Ли) без той части где путь восстанавливается. моё решение может быть чуть хуже по памяти, потому что нужно было бы создать двумерный массив с запасом по три клетки от каждой координаты старта и финиша. за то весьма наглядно бы получилось)) номер фронта волны который запишется в ячейку с координатами финиша и будет ответом
Видосы у тебя всегда классыные, и объясняешь хорошо, побольше бы. По самому алгоритму. Слишком ресурсоемко обходить все клетки, особенно для большого поля, например, если выход стоит в 50,50 зачем нам идти в минус? а там будет обход и просчет лишних тысяч вариантов, а если доска 100тыс на 100тыс ? Как-то слишком в лоб, можно оптимизировать, тем более, что мы знаем, что конь всегда сдвигается на 2 и 1 клетку, можно заранее проложить маршрут в направлении выхода, а потом при приближении уже перебирать варианты. Конечно, код будет сложнее, но все зависит от задачи, надо экономить ресурсы или нет.
Считаем разницу по оси 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, то со слоями может быть проблема, а так нет.
конь на нулевых кордах, мы просто берем число координат, до которых нам нужно дойти и переводим их в положит число, например дали -2 -7, то это считаем как 2 и 7, если -2 7, то 2 7 и тд. берем эти х и у, отнимаем максимальное количество 3 1, 1 3, 6 0 и 0 6 (последняя пара дает sum+=2, первая sum++) до того момента, пока х
Не,вообще транзитивное замыкание с минимальным весом штука крутая и очень мощная,но тут явно можно докрутить из-за специфики задачи. Скажем,вот у нас две точки,которые надо соединить и они образуют как бы прямоугольник и вот выясняется,что если его немного расширить,то любой минимальный путь можно перестроить без потерь так,чтобы он в прямоугольник попал. Для удобства перекрутим так всё,чтобы вход был слева снизу и выход справа сверху. Понятно,что на ответ это не повлияет,а вот на ход решения повлияет сжатием бреда. Докажем это замысловатое (или не особо) утверждение: Пускай есть какой-то путь и он неуменьшаем.Тогда все точки,которые выходят за верхнее ограничение мы отразим зеркально вниз,если есть такие две точки,что она на одном уровне.Понятно,что такое преобразование не изменит длинну пути,но применив так много раз потом мы запихаем весь путь в рамки наши.Проблема в том,что они могут быть на разных уровнях,так как по осям у нас переход на 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'|}. Если что,это расстояние от начала и конца до противоположных стенок.Если не хватит,то увеличивать СО ВСЕХ СТОРОН! Теперь с чистой совестью можно урезать поле,зная,что все пути будут (хоть и перекрученные) найдены и замыкание именно для последней вершины будет таким же. Тут,конечно,важно,что для других вершин это будет не так (хотя,нам какая разница). Заметим,что такая оптимизация хоть и сложна в понимании,проста в реализации и при том очень эффективна.
Анимация огонь )) Но задается вопрос, т.к. мы знаем паттерн движения коня, то почему не исключить несонаправленные вектора для, новых точек и вектора старта и финиша ?
аааа зачем уровни массив постоянного размера очередь размером в поле и ячейка ввиде структуры (visited, from, steps) и просто перебираешь каждую ячейку из очереди при переборе добавляются новые как только достал из очереди новую ячейку то проделываешь с ней все действия проверяя в начале на visited и в конце проверяешь, если это target, тогда пишешь ответ, но продолжаешь досчитывать, чтобы в последствии можно было использовать данный массив для нахождения количества шагов до любой ячейки от того же самого положения коня за O(1), просто ткнув в этот массив пальцем, а там уже будет ответ в поле steps у ячейки а если случится такое что у тебя в очереди закончились ячейки то говоришь что пути нет в итоге работает даже для не ровного поля и с островами а очередь размером в поле потому что возможно построить поле где в стеке будет лежать больше половины ячеек
Спасибо! 1. хотелось бы в коде видеть номера строк, чтобы ссылаться на них в комментах 2. не увидел ограничения доски, возможно мне стоит самому реализовать, но кажется, находясь в x=2 y=1 мы выскочим за пределы доски. 3. не увидел где инициализируются x, y, возможно это особенность, или просто опустили из примера. 4. что если выход будет в [-1, -1] ?
2. Ограничение не нужно в контексте задачи. Ограничения доски представлены максимальным и минимальным значением типа int в python 3. (x, y) - это итератор в цикле for, который там же инициализируется "for (x, y) in layer" перебирает все пары (кортежи) (x, y), которые находятся в layer 4. Даже чисто математически не имеет значения, если выход находится на отрицательных координатах
@@widny31 2-3 понял, питон не знаю просто. 4 суть не в отрицательных координатах, а в том, что ограничения доски я не видел, поэтому решил, что конь просто уйдёт за пределы и никогда не вернётся в -1,-1.
Это же по сути полный перебор, а значит алгоритм не эффективный. Можно изучить свойства движения коня и вывести некую формулу. Типа идем на прямую к целевой клетке, пока она не попадет в заранее просчитанный квадрат 5*5. Возможно, можно просто формулу вывести четкую
А теперь попробуйте решить ту же задачу, но слегка сложней: Есть вместо одного k коней на поле. Нужно для каждой клетки поля понять за какое минимальное количество ходов один из этих коней доберется до нее
Какие 7.5к € джуниору в Германии?; 90к в год даже техлиды не все получают. В 4к брутто - поверю, если данные есть: законченый универ, например, с дуальным обучением.
Хм. Зачем там хеш-таблица, если проще и быстрее использовать, например, очередь? Я в обходе в ширину обычно просто добавляю в конец очереди новые вершины-кандидаты на обход. Вершины (в данной задаче клетки), которые уже обошли, хранить в отдельной структуре (в данной задаче я бы использовал двумерный массив, но можно и хеш-таблицу).
Хорошее решение. Мысленно представил как решать это на C++, но на Питоне, конечно, компактнее получается решение. Единственный неявный для меня момент алгоритма - это то, что запоминается только предыдущий и текущий слои. Видимо, подразумевается, что с более старыми слоями пересечения быть не может. Приму на веру, видимо, есть строгое доказательство данного факта.
Если граф двунаправленный, то предыдущий слой это заслонка для всех возможных путей обхода. Можешь представить длинный коридор с дверьми, где ты захлопываешь за собой дверь, но предпредыдущая всегда открывается после этого. Но до нее ты не дойдешь, т.к. уже захлопнул дверь, которая ведет к ней.
@@Abingususчто такое «двунаправленный граф»? Я знаю только неориентированные и ориентированные графы. Я не понял, как ваш комментарий относится к тому, что я написал выше. В теории конь не обязан не возвращаться к клеткам из более старых слоев.
решение не лучшее, но сойдет. особенно для джуна.😁 ну шахматная доска это матрица. это раз. врытое уже зависит что именно надо! просчитать ходы - это граф. узнать где какая фигура - это матрица. третье, структуры данных все же стоит подтянуть.😁
через 3 недели у меня тоже собеседование в амазон. в алгоритмах я слаб и учу их практически с нуля. прежде чем посмотреть видео, поставил его на паузу и попробовал решить задачку сам. получилось решить ее за 5 минут. попадется ли мне подобная задача на собеседовании, это уже как повезет.
Вижу недостаток в этом алгоритме. Тут все таки есть повторные посещенния уже пройденых клеток, так как сохраняются лишь два послдних уровня дерева (слоя). Нам не нужно повторно добавлять клетки, в которых мы уже были, потому как для них уже уже известно минимальное число шагов, а так же они породят огромные поддеревья. Что бы избежать этой проблемы, можно добавить либо множество всех посещенных вершин, либо битсет
Неужели там не появляется паттерн, чтобы можно было написать формулы, в которые можно подставить исходную и целевую координаты и сразу получить ответ, по крайне мере для ситуаций, когда исходная и целевые поля не у края доски?
Стоит ли идти учиться на программиста если уже одну профессию закончил но она мне не нравится? Мне уже 23 года - стоит ли рисковать и переучиваться на программиста?
Очень лëгкая задача. Концепт решения верный, а прога не работает. Нет проверки на выход за границы доски, предыдущий слой не нужен, нужно шаги до всех ячеек хранить и лучше это делать в матрице. Ячейка может оказаться недостижимой и при такой реализации прога зациклится.
Слишком ресурсоемкие затраты, не легче для начала отрезать длину перемещения коня +3 за шаг от позиции к близлежайшей точке где будет прямолинейное перемещение к цели, а там уже рассчитать в конце более краткий путь, ибо затраты на расчёт к каждой точке если это доска на 100млн, то расчёт всех слоев будет очень проблемным.
Обычный, но самый не эфективный алгоритм. Кто может сказать О если точни начало и конец находятся далеко друг от друга. Полиномия по любому. А решение проще. двигаемся на прямую в сторону исходной точки максимально быстро, останавливаясь на расстоянии одного прыжка от нее. там мы либо совпадем, либо придется прыгнуть в сторону 1 или 2 раза. Как быстрее прыгать вычисляем по формуле что больше |х1 - х2| или |y1 - y2|. Дальше смотрим, что делится на 2? Соответственно прыжки можно просто посчитать. Немного на пивасике, могу не очень ясно объяснять.
По этому алгоритму с расстояния 3,4 надо прыгать в 2,2. Но это неправильно, потому что из 2,2 придётся 4 хода добираться. Надо прыгать в 1,3, откуда 2 хода. Мне кажется, что надо захардкодить таблицу решений x,y от 0 до 4, а в неё по вашему алгоритму добираться.
Что мне нужно делать, что бы понимать о чем ты вообще говоришь)) Я вообще не улавливаю, что нужно изучать в самом начале ? Я хочу знать, но полагаю нужно дойти до этого, а что бы дойти, нужно с чего то начать, скажи с чего начать, если я даже не понимаю о чем ты говоришь :DDD
Так, если координаты конечной точки известны, то может можно искать только в направлении заданой четверти, чтобы не перебирать 3/4 заведомо не нужных направлений?
Почему из первой точки 8 ходов, если всего 2, а остальные являются их отражением? Сильно подозреваю, что достаточно просто создать матрицу n*n, для одного квадранта, а потом вычислить координаты точки в этих матрицах.
Единственное в чем не вижу смысла - проверка на наличие элемента в сете, т к сет нем может содержать повторяющихся элементов. Он автоматически их убирает
Угу, вот смотрю на эти красивые превью вида "7500 евро в месяц", и понимаю, что ничего не изменилось в США/ЕС. Как не платили, так и не платят. =) PS: для тех, кто не понял, о чём речь -- у них принято зп мерить без налогов и социалки, можете смело вычитать до половины; потом вычитаете стоимость жизни и удивляетесь, как мало остаётся; притом 7-9к это при релокации, а если вы удалёнщик -- рейты сразу падают до 4-5к, и это норма. Но что забавно, чисто по финансам 5к на удалёнке выгоднее, чем 9к с релоком.
Создал Telegram канал, в котором рассказываю о жизни в Лондоне, работе в Google и подготовке к собеседованиям. Подписывайтесь: t.me/saschalukin
С анимацией отлично получилось.
Очень интересно смотреть твои разборы задач + тембр и подача приятные.
Если позволяет время - пиши побольше видео.
Никогда даже не хотел понимать задачи с шахматной доской , после просмотра понял алгоритм 💪🏾
Увидимся через полтора года!
Почему полтора года?
@@rockkley9159 потому что видео на этом канале выходят по особому алгоритму
Ну как успехи?
полтора года прошли уже, чо как?
@@opalevгде они прошли
Саша анимация вообще супер!!! Видео было настолько интересным что ни секунды не промотал. Спасибо за такое понятное и четкое объяснение
Для всех, кто пишет что в алгоритме ошибка, так как мы смотрим только на предыдущий слой и теряем информацию о предыдущих слоях:
На самом деле ошибки нет, вероятно комментаторы путают с алгоритмом DFS или вариантом BFS на очереди (где нужно запоминать все посещенные вершины).
Почему этот алгоритм корректен? Если предположить что на текущем шаге мы попытаемся пойти из ячейки X в ячейку Y, в которой уже были, но которая лежит не в предыдущем слое, то значит она лежит в предпредыдущем или более ранних слоях. Но тогда мы бы перешли по этому ребру Y - X в тот момент, когда рассматривали эту клетку Y и в этом случае X лежало бы не в текущем слое, а в следующем за слоем, в котором лежит Y. Но в предположении X лежит именно в текущем, а Y лежит не в предыдущем. Значит предположение неверно, а значит достаточно рассматривать для клеток, которые мы хотим посетить, лежат ли они в предыдущем слое. И этого будет достаточно.
Более простое объяснение: предыдущий слой это как бы затычка для пути назад. А поскольку это поиск в ширину, то мы эти затычки ставим для всех возможных путей назад, то есть как не старайся не получится "обойти" предыдущий слой со стороны.
Аналогия такая: два длинных коридора с дверьми, которые иногда пересекаются. Ты и твой друг идете одновременно от начала корридоров, и закрываете за собой каждую дверь. Так вот ты не сможешь в месте пересечения коридора пойти назад, т.к. твой друг уже закрыл за собой предыдущуб дверь. При этом не важно сколько до этого дверей было закрыто, главное что он последнюю закрыл в том месте, где вы встретились, поэтому ты не сможешь через его коридор пойти назад, и ты будешь вынужден пойти дальше вперед
@@Abingususчет объяснение намного запутаннее, чем первый коммент)
Спасибо за объяснение. А для тех кто считает, что лучше один раз увидеть. Посмотрите на доску на которой Саша показал уже 3-й слой (4:08). Где-нибудь можно попасть с клетки 3-го слоя на клетку слоя 0 или 1.
Если брать очень большое поле, то для общего случая нахождения кратчайшего пути стоит добавит разбивку на сектора.
В случае с конем можно сделать еще проще, первые ходы должны делаться с учетом кратчайшей дистанции, и только начиная с дистанции в 4 клетки выполнять обозначенный автором кульбит
Вот я тоже думаю, обход поля n*n это O(n^2), но кажется можно за линейную сложность. Типа мы можем просчитать окрестность исходной точки, потом из каждой точки окрестности сделать простой алгоритм, который примерно
1. Находит два необходимых вида шагов O(1)
2. Считает необходимое колво шагов O(1) k
3. Находит точное количества шагов для шага типа1 и типа2 (линейный поиск O(n), т.к суммарно шагов тип1+тип2 = k точно меньше 2n), и если ответ нашелся, значит это будет тип1+тип2+шаг окрестности. Если не нашелся, значит забиваем на эту точку окрестности
4. Повторяем для каждой точки окрестности и ищем минимальное среди ответов O(c), с количество точек в окрестности
Итого у на фиксированная окрестность а количество шагов растет линейно, значит сложность лин поиска тоже растет линейно.
Также заметим, что порядок шагов тип1 и тип2 не важен, так что тут все ок.
Да, с динамическим программированием получится эффективнее.
Мощно ты запарился за анимации!) Но получилось явно очень наглядно и понятно!
Здесь можно (даже бы я сказал нужно) использовать алгоритм А*, а за эвристическию функцию можно взять манхеттенское расстояние от коня до конечной клетки
Не знал что у єтого есть название, но решал бы тоже "через растояние" и ходы, которые его сокращают
Кстати, не уверен, что А* сработает в данном случае, так как алгоритм выберет самую ближайшую клетку к конечной клетке, но так как конь ходит буквой Г он же может крутиться несколько раз вокруг конечной клетки что бы в неё попасть. А соседняя клетка (которая будет иметь большее манхэтоновское расстояние) попадёт в конечную клетку раньше, хоть эвристика в ней изначально была больше. Я не ради прикопаться, мне тоже сразу в голову пришёл этот алгоритм, просто интересно так это или нет.
@@ЕгорПичугин-у5мконь бы не крутился вокруг цели. Он бы просто игнорировал уже пройденные ( найденые ходы ). Если с первой попытки он был не нашел путь, то начал бы обходить ближайшие. Но даже так это было бы куда эффективнее по памяти, чем делать поиск в ширину, так как мы не хранили бы явно плохие ходы
Долго тебя не было, рад новому видео!
Выпускай чаще пожалуйста, ты лучший мой мотиватор )))
Привет! Заметил пару неточностей.
1. Ты говоришь, что не посещаешь уже посещенные клетки. Но это утверждение верно только для предыдущего слоя - в коде ты никак не помечаешь те клетки, что были посещены ещё раньше.
2. Формально это можно назвать обходом графа в ширину, но мне кажется, это решение методом динамического программирования. А если попытаться оптимизироавть решение и не проверять заведомо более длинные пути (а ограничиться только квадратом (0, 0) (n, n)), то это уже точно не будет обходом графа в ширину(так как мы не посещаем все вершины).
3. Решение данной конкретной задачи обходом графа в ширину довольно неэффективно - сложность получается ~(2n)^2*Log(n), тогда как методом динамического программирования мы можем обойтись n^2, перебрав каждую вершину урезанного квадрата лишь единожды. n это большая по модулю координата целевой точки.
Upd: попытавшись набросать решение методом динамического программирования, понял, что у меня не получается) Конь ходит слишком сложно, чтобы за один проход можно было заполнить массив, не возвращаясь к уже посещённым клеткам. А вот в обходе графа ограничить поле всё равно было бы нелишним.
так может обозначишь их?
Если входной массив можно редактировать, то одной из оптимизаций будет простая "покраска" значения
> если попытаться оптимизироавть решение и не проверять заведомо более длинные пути (а ограничиться только квадратом (0, 0) (n, n)), то это...
....не будет работать. Например конь (0,0) выход (1,1)
А вообще, мне кажется тут есть математическое решение.
1) В этом и суть решения - можно проверять только предыдущий слой, нельзя попытаться пойти из слоя №3 НЕ в предыдущий слой №2 или следующий слой №4 (иначе бы слои формировались по-другому), поэтому не имеет смысла проверять все посещенные вершины, а только посещенные на последнем слое. Как раз таки поэтому это алгоритм обхода в глубину на двух списках (более классическое решение - одна очередь).
2) Метод BFS (Breadth-first search) как ни странно использует идею динамического программирования. Одно использует, а не заменяет другое. Вы ведь не скажете "Ну я бы не стал доезжать на работу на Мерседесе, я бы предпочел просто доехать на машине." Поиск в ширину реализуется на динамическом программировании. Посещать не все вершины - не значит не обходить граф, но оптимизации действительно здесь приемлемы (можете еще почитать про итеративный поиск в глубину iterative deepening depth-first search).
3) Тут используем хеш таблицу, а не дерево поиска, поэтому время работы алгоритма O(n^2). Но вы все еще правы, что BFS реализуется через идею динамического программирования, просто обход ячеек при рекурентном пересчете соответствует обходу графа.
@@Arkham_nine хорошо, считаем до [n + 2, n + 2] :)
Спасибо! Отличное видео, интересная задача! Ждем новых роликов.
Тут экспоненциальный рост клеток с каждым слоем и симметрия 4-го порядка, стоила взять координаты цели по модулю и начать с двух ходов 1, 2 и 2, 1 на первом слое. Так-же можно игнорировать все клетки с отрицательными координатами, это сэкономит память.
Спасибо за задачу! Очень подробно объяснил)
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)
онглечанен, ставит скобку после текста 😂
Вау, очень крутое и понятное объяснение. Анимация - огонь
Вообще в классическом БФС используется очередь (Queue), а не некие уровни.
1. Запихиваешь в очередь первую клетку.
2. Извлекаешь.
3. Находишь всех соседей, в нашем случае восемь возможных ходов коня.
4. Фильтруешь уже посещённые.
5. Запихиваешь в очередь.
6. Гото 2 до победы.
Если смотреть только на previous_layer, то потеряется информация о посещённых клетках на предыдущих ходах.
Уровень в данном случае это синоним глубины. Какие к этому могут быть претензии?
@@rasimbot ну bfs как будто именно для поиска путей используется, а не расстояний, хотя его и можно упростить до поиска минимального расстояния. + как и сказано в видосе, bfs запускается на графе, хоть шахматная доска и представима в виде графа, сам граф в этом решении не строится и вряд ли можно говорить о bfs, хотя и оч похоже. Например, если эту задачку чуть изменить и просить искать не кратчайшее расстояние, а кратчайший путь (именно вывести все посещенные клетки по порядку), то решение из видоса как будто не позволит этого сделать, с bfs получилось бы (ну мне так кажется). Я не с целью надушнить, если что, если это решение без построение графа можно под вышеописанную задачу изменить, буду рад услышать)
@@КамильБадрутдинов-р8щ учи теорию графов лучше)
@@vanel9933 так а что учить то подскажи)
Сначала конь на клетке 1:1 (зачем-то), потом уже на логичной 0:0. Ну и можно оптимизировать конкретный кейс с учетом осей симметрии доски и обработать только 1/8 всех клеток.
Обычная задача на волновой алгоритм. По предоставленному решению. Нет контроля выхода за границу доски. Также проверяем попадание в клетку на предыдущем уровне, но не на уровнях ранее, для данного контроля можно использовать обычный двумерный массив описывающий доску и хранящий уровни посещения в каждой клетке
Блин, смотрю каждое твое видео. Спасибо за контент. Тоже мечтаю попасть в google
мечтать мало, нужно работать над собой, чтоб туда попасть
эта задача очень лёгкая
Анимация наглядная, круто!
Можно ещё параллельно вычислять дорогу от коня к точке и от точки к коню ровно до тех пор покуда не найдётся первое пересечение. Действий суммарно будет больше, но зато массив будет меньше...хотел сказать я, но потом обнаружил одно геометрическое свойство: сумма длин окружностей, пересекающихся в одной точке равна длине окружности с радиусом, равным расстоянию между центрами этих окружностей)))
Спасибо за bfs!
Но в аналитическом решении сложность О(1).
N = (lnl + lml)/3 ± 4. Начальные координаты коня (0,0), конечные (n, m). Если рассмотреть как ходить в конце (варианты), то формула будет без погрешностей.
Решение автора работает похоже на работу ИИ, он также связывает всё послойно, и между всеми элементами одного слоя и другого присутствует связь, таким образом происходит имитация синапсов, что помогает ему осмыслить любые возможные варианты.
функция 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])))]
по-моему, вот ЭТО более нечитабельно. Функция moves выглядит куда проще и нагляднее
@@widny31 ну да, я и написал, что хардкод в данном случае читабельнее. просто показал, как в Питоне выражается "по одной оси на два, по другой -- на один во всех возможный направлениях" посредством функций из itertools
Во-первых нормализовать данные. Стартовая клетка пусть будет (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) и нулевым выделением памяти на каждой итерации. Описывать сложнее, чем написать код.
Я тоже так решил. Я бы взял разность между координатами по модулю и вычитал (2, 1), (1, 2), пока это возможно, а затем конь либо достигнет цели, либо доберется до любой клетки рядом за 2 хода.
Блин! точно! это же графы! спасибо большое!
у меня в школе была задача посчитать за какое минимальное число шагов конь пройдет по каждой клетке поля по 1 разу. И всё это на паскале с отрисовкой доски и прочего)
Анимация супер! С помощью чего она сделана? Объяснение тоже класс, после него стала меньше бояться задач на шахматной доске. Немного сложно было воспринимать объяснение кода под музыку. Отдельное спасибо за питон!
У меня 4 года опыта в программировании, 3 года коммерции, чувствую себя таким джуном) Старший разработчик - джун.
Сразу в голову пришла идея через обход в ширину как только сказал про хеш-таблицу ( чтобы в ней хранить позиции, в которых мы были ). На код варсе это 3-4 тир задач.
в случае коня есть много места для эвристической оптимизации BFS, чтобы не идти в заведомо ложном направлении
Вычисляем первый круг, а дальше копипастим весь массив с наложением в нужную сторону.
Если требуется заполнение всей доски или идет непопадание, возможен банальный брутфорс,
либо от последней позиции, либо вообще всех возможных комбинаций массива.
Спасибо, очень крутая анимация, такую в Keynote просто сделаешь, так?
Если наше поле заранее известного размера, то надо использовать обычный массив, а не хеш таблицы. И второе, поиск в ширину выглядит красиво, когда наша цель находиться в нескольких шагах, а когда до неё шагов 30, то мы умрём прежде чем поиск в ширину найдёт путь.
задача - проверить понимание поиска в ширину.. дальше на интервью можно было бы спросить "а давай оптимизируем?"
Делай, пожалуйста, больше видео по алгоритмам
я бы решал через алгебру, но нужно обработать крайние случаи и написать костыли. А так если люди не против и нужно что-то сделать за короткое время то и так можно.
Спасибо за видео. На курсах по изучению Пайтон решал эту же задачу:)) интересно посмотреть твое решение. Лайк
я бы решал это волновым алгоритмом (алгоритм Ли) без той части где путь восстанавливается. моё решение может быть чуть хуже по памяти, потому что нужно было бы создать двумерный массив с запасом по три клетки от каждой координаты старта и финиша. за то весьма наглядно бы получилось)) номер фронта волны который запишется в ячейку с координатами финиша и будет ответом
Для ускорения можно было бы запустить два поиска в ширину одновременно, тогда бы мы могли сократить лишние переборы путей в других направлениях.
Знаю 2 решения:
1. За O(1) можно пересчитать по формуле, опирающиюся на полуинвариант сумм
2. BFS или Дейкстра, оба за O(n) в данном случае
А можно ссылку на объяснение первого решения? Или просто объяснить поподробнее)
очень интересная задача. хорошо рассказано. выпускай ролики чаще
Можно слоями, а можно просто назначить вес каждой клетке.
С анимацией хорошо получилось, пожалуйста, делай больше видео
Хорошая задачка, но мне больше интересно как анимация делалась :)
1. Полный перебор не нужен - можно оптимизировать:
1.1. если исходная клетка X
спс. намешалo бы добавить анализ сложности (временной и по памяти)
Видосы у тебя всегда классыные, и объясняешь хорошо, побольше бы. По самому алгоритму. Слишком ресурсоемко обходить все клетки, особенно для большого поля, например, если выход стоит в 50,50 зачем нам идти в минус? а там будет обход и просчет лишних тысяч вариантов, а если доска 100тыс на 100тыс ? Как-то слишком в лоб, можно оптимизировать, тем более, что мы знаем, что конь всегда сдвигается на 2 и 1 клетку, можно заранее проложить маршрут в направлении выхода, а потом при приближении уже перебирать варианты. Конечно, код будет сложнее, но все зависит от задачи, надо экономить ресурсы или нет.
Считаем разницу по оси 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, то со слоями может быть проблема, а так нет.
конь на нулевых кордах, мы просто берем число координат, до которых нам нужно дойти и переводим их в положит число, например дали -2 -7, то это считаем как 2 и 7, если -2 7, то 2 7 и тд. берем эти х и у, отнимаем максимальное количество 3 1, 1 3, 6 0 и 0 6 (последняя пара дает sum+=2, первая sum++) до того момента, пока х
Ничего не понятно из твоего объяснения
un canal ruso que encontré para aprender estructura de datos muy buen canal
Задача класс! Больше подобного контента!
Не,вообще транзитивное замыкание с минимальным весом штука крутая и очень мощная,но тут явно можно докрутить из-за специфики задачи.
Скажем,вот у нас две точки,которые надо соединить и они образуют как бы прямоугольник и вот выясняется,что если его немного расширить,то любой минимальный путь можно перестроить без потерь так,чтобы он в прямоугольник попал.
Для удобства перекрутим так всё,чтобы вход был слева снизу и выход справа сверху.
Понятно,что на ответ это не повлияет,а вот на ход решения повлияет сжатием бреда.
Докажем это замысловатое (или не особо) утверждение:
Пускай есть какой-то путь и он неуменьшаем.Тогда все точки,которые выходят за верхнее ограничение мы отразим зеркально вниз,если есть такие две точки,что она на одном уровне.Понятно,что такое преобразование не изменит длинну пути,но применив так много раз потом мы запихаем весь путь в рамки наши.Проблема в том,что они могут быть на разных уровнях,так как по осям у нас переход на 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'|}.
Если что,это расстояние от начала и конца до противоположных стенок.Если не хватит,то увеличивать СО ВСЕХ СТОРОН!
Теперь с чистой совестью можно урезать поле,зная,что все пути будут (хоть и перекрученные) найдены и замыкание именно для последней вершины будет таким же.
Тут,конечно,важно,что для других вершин это будет не так (хотя,нам какая разница).
Заметим,что такая оптимизация хоть и сложна в понимании,проста в реализации и при том очень эффективна.
Анимация огонь ))
Но задается вопрос, т.к. мы знаем паттерн движения коня, то почему не исключить несонаправленные вектора для, новых точек и вектора старта и финиша ?
Легенда вернулась, увидимся через год?)
Задача решается поиском в ширину. Решал аналогичную задачу в универе на экзамене по АСД (Алгоритмы и структуры данных) на третьем курсе
аааа зачем уровни
массив постоянного размера
очередь размером в поле
и ячейка ввиде структуры (visited, from, steps)
и просто перебираешь каждую ячейку из очереди
при переборе добавляются новые
как только достал из очереди новую ячейку то проделываешь с ней все действия проверяя в начале на visited и в конце проверяешь, если это target, тогда пишешь ответ, но продолжаешь досчитывать, чтобы в последствии можно было использовать данный массив для нахождения количества шагов до любой ячейки от того же самого положения коня за O(1), просто ткнув в этот массив пальцем, а там уже будет ответ в поле steps у ячейки
а если случится такое что у тебя в очереди закончились ячейки то говоришь что пути нет
в итоге работает даже для не ровного поля и с островами
а очередь размером в поле потому что возможно построить поле где в стеке будет лежать больше половины ячеек
Спасибо!
1. хотелось бы в коде видеть номера строк, чтобы ссылаться на них в комментах
2. не увидел ограничения доски, возможно мне стоит самому реализовать, но кажется, находясь в x=2 y=1 мы выскочим за пределы доски.
3. не увидел где инициализируются x, y, возможно это особенность, или просто опустили из примера.
4. что если выход будет в [-1, -1] ?
про доску в начале объяснялось, про то, что она бесконечная не сказано, но обрати внимание на координаты. Если [1,1] Это стартовая позиция
@@kotiko_oksвидимо нужно самому реализовать с тестами)
2. Ограничение не нужно в контексте задачи. Ограничения доски представлены максимальным и минимальным значением типа int в python
3. (x, y) - это итератор в цикле for, который там же инициализируется
"for (x, y) in layer" перебирает все пары (кортежи) (x, y), которые находятся в layer
4. Даже чисто математически не имеет значения, если выход находится на отрицательных координатах
@@widny31 2-3 понял, питон не знаю просто. 4 суть не в отрицательных координатах, а в том, что ограничения доски я не видел, поэтому решил, что конь просто уйдёт за пределы и никогда не вернётся в -1,-1.
Это же по сути полный перебор, а значит алгоритм не эффективный.
Можно изучить свойства движения коня и вывести некую формулу. Типа идем на прямую к целевой клетке, пока она не попадет в заранее просчитанный квадрат 5*5. Возможно, можно просто формулу вывести четкую
когда лет 20-25 назад делал игру Lines на дельфи аналогично просчитывал путь для шарика из исходной точки в точку в которую кликнул игрок
Альманах...круто, мне нравится
Спасибо, хорошая задача и разбор
А теперь попробуйте решить ту же задачу, но слегка сложней:
Есть вместо одного k коней на поле. Нужно для каждой клетки поля понять за какое минимальное количество ходов один из этих коней доберется до нее
Какие 7.5к € джуниору в Германии?; 90к в год даже техлиды не все получают. В 4к брутто - поверю, если данные есть: законченый универ, например, с дуальным обучением.
Хм. Зачем там хеш-таблица, если проще и быстрее использовать, например, очередь? Я в обходе в ширину обычно просто добавляю в конец очереди новые вершины-кандидаты на обход. Вершины (в данной задаче клетки), которые уже обошли, хранить в отдельной структуре (в данной задаче я бы использовал двумерный массив, но можно и хеш-таблицу).
Добрый день, Александр, отличное видео! Вы устраивались на Junior Software Engineer, я правильно понимаю?
спасибо
Хорошее решение. Мысленно представил как решать это на C++, но на Питоне, конечно, компактнее получается решение. Единственный неявный для меня момент алгоритма - это то, что запоминается только предыдущий и текущий слои. Видимо, подразумевается, что с более старыми слоями пересечения быть не может. Приму на веру, видимо, есть строгое доказательство данного факта.
Если граф двунаправленный, то предыдущий слой это заслонка для всех возможных путей обхода. Можешь представить длинный коридор с дверьми, где ты захлопываешь за собой дверь, но предпредыдущая всегда открывается после этого. Но до нее ты не дойдешь, т.к. уже захлопнул дверь, которая ведет к ней.
@@Abingususчто такое «двунаправленный граф»? Я знаю только неориентированные и ориентированные графы. Я не понял, как ваш комментарий относится к тому, что я написал выше. В теории конь не обязан не возвращаться к клеткам из более старых слоев.
круто, спасибо за видосы!
решение не лучшее, но сойдет. особенно для джуна.😁
ну шахматная доска это матрица. это раз.
врытое уже зависит что именно надо! просчитать ходы - это граф. узнать где какая фигура - это матрица.
третье, структуры данных все же стоит подтянуть.😁
через 3 недели у меня тоже собеседование в амазон. в алгоритмах я слаб и учу их практически с нуля.
прежде чем посмотреть видео, поставил его на паузу и попробовал решить задачку сам. получилось решить ее за 5 минут. попадется ли мне подобная задача на собеседовании, это уже как повезет.
Вижу недостаток в этом алгоритме. Тут все таки есть повторные посещенния уже пройденых клеток, так как сохраняются лишь два послдних уровня дерева (слоя). Нам не нужно повторно добавлять клетки, в которых мы уже были, потому как для них уже уже известно минимальное число шагов, а так же они породят огромные поддеревья. Что бы избежать этой проблемы, можно добавить либо множество всех посещенных вершин, либо битсет
Лучший мотиватор!
спасибо за видео
Спасибо за задачу
Неужели там не появляется паттерн, чтобы можно было написать формулы, в которые можно подставить исходную и целевую координаты и сразу получить ответ, по крайне мере для ситуаций, когда исходная и целевые поля не у края доски?
Можно за линейную, написал коммень, но кажется можно за консьантную сложность
Стоит ли идти учиться на программиста если уже одну профессию закончил но она мне не нравится? Мне уже 23 года - стоит ли рисковать и переучиваться на программиста?
главное чтоб нравилась профессия
Я бы решал через вектор до выхода - т.е. какой из возможных ходов сокращаяет дистанцию до выхода
Спасибо
Очень лëгкая задача. Концепт решения верный, а прога не работает. Нет проверки на выход за границы доски, предыдущий слой не нужен, нужно шаги до всех ячеек хранить и лучше это делать в матрице. Ячейка может оказаться недостижимой и при такой реализации прога зациклится.
Слишком ресурсоемкие затраты, не легче для начала отрезать длину перемещения коня +3 за шаг от позиции к близлежайшей точке где будет прямолинейное перемещение к цели, а там уже рассчитать в конце более краткий путь, ибо затраты на расчёт к каждой точке если это доска на 100млн, то расчёт всех слоев будет очень проблемным.
осталось только посмотреть что такое A* и ускорить нахождение решения в среднем в 4 раза
агонь!
Обычный, но самый не эфективный алгоритм. Кто может сказать О если точни начало и конец находятся далеко друг от друга. Полиномия по любому. А решение проще. двигаемся на прямую в сторону исходной точки максимально быстро, останавливаясь на расстоянии одного прыжка от нее. там мы либо совпадем, либо придется прыгнуть в сторону 1 или 2 раза. Как быстрее прыгать вычисляем по формуле что больше |х1 - х2| или |y1 - y2|. Дальше смотрим, что делится на 2? Соответственно прыжки можно просто посчитать. Немного на пивасике, могу не очень ясно объяснять.
я тебя ясно понял потому что сам на пивасике
По этому алгоритму с расстояния 3,4 надо прыгать в 2,2. Но это неправильно, потому что из 2,2 придётся 4 хода добираться. Надо прыгать в 1,3, откуда 2 хода.
Мне кажется, что надо захардкодить таблицу решений x,y от 0 до 4, а в неё по вашему алгоритму добираться.
есть подозрение, что задача решается проще, но мне лень сейчас думать :)
Спасибо!
Что мне нужно делать, что бы понимать о чем ты вообще говоришь)) Я вообще не улавливаю, что нужно изучать в самом начале ? Я хочу знать, но полагаю нужно дойти до этого, а что бы дойти, нужно с чего то начать, скажи с чего начать, если я даже не понимаю о чем ты говоришь :DDD
Это вроде простой перебор всех возможных вариантов
Так, если координаты конечной точки известны, то может можно искать только в направлении заданой четверти, чтобы не перебирать 3/4 заведомо не нужных направлений?
Почему из первой точки 8 ходов, если всего 2, а остальные являются их отражением? Сильно подозреваю, что достаточно просто создать матрицу n*n, для одного квадранта, а потом вычислить координаты точки в этих матрицах.
Здравствуйте, Александр, а Лукин Владимир Николаевич не ваш родственник (в маи преподаёт) ?
Единственное в чем не вижу смысла - проверка на наличие элемента в сете, т к сет нем может содержать повторяющихся элементов. Он автоматически их убирает
Возможно, я где-то ошибаюсь. В любом случае спасибо за ролик, анимации идеально подходят для понимания.
Я опирался на то, что код написан на Python, но, видимо, это не так. В любом случае, можешь скинуть свой код в текстовом виде?
Можно добавить эвристическую функцию и получить AStar (будет быстрее)
Я так понимаю, доска задачи бесконечная? Функция moves не смотрит на границы доски.
Да ну нах..лучше в таксисты пойду.
Угу, вот смотрю на эти красивые превью вида "7500 евро в месяц", и понимаю, что ничего не изменилось в США/ЕС. Как не платили, так и не платят. =)
PS: для тех, кто не понял, о чём речь -- у них принято зп мерить без налогов и социалки, можете смело вычитать до половины; потом вычитаете стоимость жизни и удивляетесь, как мало остаётся; притом 7-9к это при релокации, а если вы удалёнщик -- рейты сразу падают до 4-5к, и это норма. Но что забавно, чисто по финансам 5к на удалёнке выгоднее, чем 9к с релоком.
Четко
Решение на JS, такое-же как в видео
function findMinSteps(END_POINT = [ 1, 1 ], START_POINT = [ 5, 5 ]) {
let step = 0;
let combinations = 0;
let currentLayer = new Set([ START_POINT.toString() ]);
let prevLayer = new Set();
while (!isFindDistance(currentLayer)) {
let nextLayer = new Set();
currentLayer.forEach((point) => {
const _point = point.split(",");
moves(+_point[0], +_point[1]).forEach((newPoint) => {
if (!prevLayer.has(newPoint)) {
nextLayer.add(newPoint);
}
});
});
[ prevLayer, currentLayer ] = [ currentLayer, nextLayer ];
step++;
}
function isFindDistance(layer) {
combinations += layer.size;
return layer.has(`${ END_POINT[0] },${ END_POINT[1] }`);
}
function moves(x, y) {
const points = new Set();
points.add([ x + 1, y + 2 ].toString());
points.add([ x - 1, y + 2 ].toString());
points.add([ x + 2, y + 1 ].toString());
points.add([ x + 2, y - 1 ].toString());
points.add([ x + 1, y - 2 ].toString());
points.add([ x - 1, y - 2 ].toString());
points.add([ x - 2, y + 1 ].toString());
points.add([ x - 2, y - 1 ].toString());
return points;
}
return { step, combinations };
}
const now = performance.now()
console.log(findMinSteps([ 227, 369 ]));
console.log((performance.now() - now) / 1000)
Can we see the same BFS done recursively ? Would it be an easier way to implement if you have just 15 minutes?
Мне в голову dict пришёл. Можно ли это реализовать, если layer_number - ключ, а сет таплов(или списков) с доступными координатами - значение?