# | Название видеоурока | Видео / Тесты | Решило | Рейтинг | Доступ |
---|---|---|---|---|---|
1 |
![]() |
|
|||
В этой серии уроков мы познакомимся с гениальным алгоритмом X Дональда Кнута - Dancing Links. Этот алгоритм можно применять для решения самых разных комбинаторных задач, например, разложение Пентамимо, решение Судоку, размещение ферзей и так далее. Статья Дональда Кнута: https://arxiv.org/pdf/cs/0011047v1.pdf Обзорная статья на Хабре: https://habrahabr.ru/post/194410/ Отчёт отправил: 10558. Иван Воронин Выполнено за 15 мин. [Показать отчёт] Научился: Повторил что такое Dancing Links Сложности: найти время Комментарии: Алгоритм сравнения матриц через линейное представление отличная идея, нашёл в сети картинку, где Судоку решали подобным способом, думаю можно будет записать либо Вип урок либо продолжение уроков для курса Судоку, у нас же есть курс по Сапёру, он вообще состоит из 3 частей. С ферзями тоже этот алгоритм будет работать, я думаю этот алгоритм удобен для проверки корректности созданных карт в Сокобане =) |
|||||
2 | Работа алгоритма |
|
|||
Мы продолжаем знакомство с гениальным алгоритмом X Дональда Кнута - Dancing Links. На этом уроке мы пошагово рассмотрим статью на Хабре. Отчёт отправил: 10558. Иван Воронин Выполнено за 40 мин. [Показать отчёт] Научился: Повторил разбор полётов на Хабре Сложности: найти время Комментарии: На скриншоте видно состояние матрицы каждую итерацию. Использовал тёмный оттенок при сохранении фигуры и светлые оттенки того же цвета для выявления пересечений с ней. Решил так же рассмотреть ситуацию из урока, где первую фигуру выбрали D. Таким образом к тому моменту, когда выбрали вторую фигуру и отсеяли пересечения с ней, осталось всего две фигуры, которые ни с чем не пересекаются, а просто сохраняются и вуаля, решение найдено. з.ы. урок отличный, очень полезно проработать алгоритм для лучшего понимания. з.з.ы. добавил описание цвета в виде легенды внизу скриншота. |
|||||
3 | Двусвязный список с удалением |
|
|||
Мы продолжаем знакомство с гениальным алгоритмом X Дональда Кнута - Dancing Links. На этом уроке мы пошагово рассмотрим статью автора данного алгоритма и рассмотрим пошаговое удаление и возвращение элемента. Отчёт отправил: 10558. Иван Воронин Выполнено за 1 час. 10 мин. [Показать отчёт] Научился: Повторил алгоритм удаление/восстановления элементов из списка. Сложности: найти время Комментарии: Отличный урок, очень хорошо продемонстрирован алгоритм удаления/восстановления элементов списка. Решил реализовать это всё в Excel для большей наглядности. |
|||||
4 | Расширение хоровода |
|
|||
Мы продолжаем знакомство с гениальным алгоритмом X Дональда Кнута - Dancing Links. На этом уроке мы наконец приступим к реализации двусвязного списка на языке C#. Отчёт отправил: 10558. Иван Воронин Выполнено за 50 мин. [Показать отчёт] Научился: Реализации динамичного списка вместо статичного массива. Сложности: найти время Комментарии: Отличный урок, всё гениальное - просто!!! идём дальше. |
|||||
5 | Заголовки столбцов |
|
|||
Мы продолжаем знакомство с гениальным алгоритмом X Дональда Кнута - Dancing Links. На этом уроке мы реализуем перемещение вверх/вниз для реализации четырёх-связного списка, так же создадим класс Header(), чтобы знать в каком столбце мы находимся. Отчёт отправил: 10558. Иван Воронин Выполнено за 45 мин. [Показать отчёт] Научился: Созданию динамического четырёх-связного списка с использованием заголовка как указателя на текущую колонку. Сложности: найти время Комментарии: Урок можно было разбить на две части, создание класса Header() вынести в отдельный и завершить его, чтобы не было неопределённости в конце урока =) В любом случае заготовка отличная, идём дальше. |
|||||
6 | Единичная матрица |
|
|||
Мы продолжаем знакомство с гениальным алгоритмом X Дональда Кнута - Dancing Links. На этом уроке, используя созданный ранее четырёх-связный список, мы добавим необходимые нам элементы для дальнейшем работы с ними. Отчёт отправил: 10558. Иван Воронин Выполнено за 27 мин. [Показать отчёт] Научился: Повторил пройденное Сложности: найти время Комментарии: Заполнили матрицу элементами для примера, проверили работоспособность алгоритма в полевых условиях, осталось добавить функционал перебора возможных вариантов. Чем дальше, тем интереснее. |
|||||
7 | Как ссылки пошли впляс |
|
|||
Мы продолжаем знакомство с гениальным алгоритмом X Дональда Кнута - Dancing Links. На этом уроке мы реализуем заготовку функции Dance() в классе Dance(). Отчёт отправил: 10558. Иван Воронин Выполнено за 17 мин. [Показать отчёт] Научился: Закреплению полученного материала на вебинаре. Сложности: найти время Комментарии: Отличная реализация алгоритма, но нужно идти дальше, чтобы завершить его окончательно и протестировать в полевых условиях. |
|||||
8 | Открытие/закрытие столбцов |
|
|||
Мы продолжаем знакомство с гениальным алгоритмом X Дональда Кнута - Dancing Links. На этом уроке мы доработает функции AddRow() и Dance() в классе Dance(). Так же реализуем функции Cover/Uncover(). Отчёт отправил: 10558. Иван Воронин Выполнено за 33 мин. [Показать отчёт] Научился: Закрепил пройденное на вебинаре. Сложности: найти время Комментарии: Отлично, всё просто супер, ошибка которая возникла с середины урока у меня не проявилась, так как был на вебинаре и успевал за Игромистром, но писал сам, повторяя идеи и сразу написал так как надо. Поэтому искать ошибку не пришлось =) |
|||||
9 | Фигуры из пентамимо |
|
|||
Мы продолжаем знакомство с гениальным алгоритмом X Дональда Кнута - Dancing Links. На этом уроке мы приступаем к решению олимпиадной задачи: Пентамино, заполнив массив всеми вариантами расположения фигур. Отчёт отправил: 10558. Иван Воронин Выполнено за 20 мин. [Показать отчёт] Научился: Повторил пройденное Сложности: найти время Комментарии: Отличная идея хранения вариантов расположения фигур в массиве. Осталось за малым, реализовать алгоритм перебора вариантов расположения фигур. |
|||||
10 | Фигуры в консоли |
|
|||
Мы продолжаем знакомство с гениальным алгоритмом X Дональда Кнута - Dancing Links. На этом уроке мы решили реализовать возможность отображения фигур в консоли, чтобы в дальнейшем видеть что происходит в процессе работы алгоритма. Отчёт отправил: 10558. Иван Воронин Выполнено за 31 мин. [Показать отчёт] Научился: Повторил пройденное Сложности: найти время Комментарии: Вывел все фигур по диагонали. Отличный урок, очень не хватало визуализации происходящего =) |
|||||
11 | Матрица Пентагона |
|
|||
Мы продолжаем знакомство с гениальным алгоритмом X Дональда Кнута - Dancing Links. На этом уроке мы завершим реализацию функции поиска решения Пентамино. Отчёт отправил: 10558. Иван Воронин Выполнено за 32 мин. [Показать отчёт] Научился: Закрепил знания полученный на вебинаре. Сложности: найти время Комментарии: Отличный урок, интересная реализация алгоритма, осталось дождаться окончания его работы =) з.ы. Однозначно требуется оптимизация, чем и займёмся на след. уроке. |
|||||
12 | Пентагон в деталях |
|
|||
Мы продолжаем знакомство с гениальным алгоритмом X Дональда Кнута - Dancing Links. На этом уроке мы воспользуемся функцией Show() в классе Figure() для визуализации генерации всех вариантов расположения фигур Пентамино. Отчёт отправил: 10558. Иван Воронин Выполнено за 27 мин. [Показать отчёт] Научился: Повторил пройденное Сложности: найти время Комментарии: Отличный урок, наглядно показано как формируется матрица всевозможных вариантов расположения фигур на поле. Теперь осталось визуализировать поиск решения, чтобы ожидание завершения алгоритма в не оптимизированном виде было более приятным =) |
|||||
13 | Пентагон ищет решение |
|
|||
Мы продолжаем знакомство с гениальным алгоритмом X Дональда Кнута - Dancing Links. На этом уроке мы визуализируем поиск решения Пентамино с использованием yield. Отчёт отправил: 10558. Иван Воронин Выполнено за 3 час. 41 мин. [Показать отчёт] Научился: Закрепил пройденное Сложности: найти время Комментарии: Добавил поддержку отображения найденных ответов ниже поля перебора относительно друг друга, чтобы не пересекались (проверить можно будет после внедрения оптимизации, так как ждать уж очень долго, хотя и более наглядно). Добавил поддержку полей более 60 клеток (см. скриншот) при этом учитываются дубликаты фигур, цвет фигур, индексация и т.д. все необходимые нюансы. Как видно из скриншота, добавлена поддержка ввода размеров поля через командную строчку, для этого создал батника с необходимыми размерами для тестирования. з.ы. обожаю относительность =) |
|||||
14 | Десятикратная оптимизация |
|
|||
Мы продолжаем знакомство с гениальным алгоритмом X Дональда Кнута - Dancing Links. На этом уроке мы оптимизируем наш алгоритм поиска решения Пентамино. Отчёт отправил: 10558. Иван Воронин Выполнено за 22 мин. [Показать отчёт] Научился: Закрепил пройденное на вебинаре Сложности: найти время Комментарии: Отличное завершение не менее гениального алгоритма, геттеры и сеттеры использовал только в том случае, если нужно запретить использование переменных извне, в нашем случае приватного атрибута не устанавливалось для сеттера, поэтому и смысла в них нет, но то, что они так тормозят это жесть, учту на будущее. Знал, что доп. безопасность кода отнимает ресурсы, но в некоторых ситуациях, если алгоритм вылизан эти можно пренебречь в угоду скорости. Очень хотелось реализовать графическую демонстрацию, но времени как всегда нет, в другой раз обязательно реализую. з.ы. что касается ферзей и судоку, до судоку ещё не добрался. а ферзей ещё год назад реализовал, для ферзей этот алгоритм будет кстати, по поводу судоку как доберусь, так скажу свой вердикт, но в любом случае, в сети уже есть реализации танцующего судоку, так что думаю реализовать реально. |
|||||
Итого: 14 видеоуроков |
4 час. 18 мин. |
17 чел. | |||
Финалисты: Иван Воронин, Андрей, AZANIR, Алексей Малышев, Сергей Соколов, Алексей В., Максим Лапшинов, Spellion, Tekashnik, Yefim, Новопашин Владимир, Bazel, Николай Денисов, Иван, Дмитрий, Max, MaxB . |