Да я уже нашел ошибку в статье, так что этот вопрос уже закрыт.
Благодарю вас за проделанную работу. Однако, ни на одну фактическую ошибку вы так и не указали, зато сообщили всем вокруг, что не смогли ничего понять.
Убедительно прошу прекратить вас спамить и замусоривать комментарии.
Имея на руках две реализации можем посмотреть как они себя поведут в бенчмарке (Length - кратное увеличение размера строки, чтобы смотреть как ведет себя реализация на больших данных)
Из статьи не совсем ясно, что такое "большие данные". Нет ни слова о том, как вы их на самом деле генерируете, а это может существенно влиять на бенчмарки.
Если я верно понял, вы просто много раз повторяете исходную строку? В таком случае, это не совсем честный бенчмарк, т.к. максимум достигается почти сразу (на первом же вхождении исходной строки в длинную). Интереснее было бы посмотреть на тест, в котором максимум постоянно растет.
О багах знаю, нашел сильно после выхода статьи, исправлять не стал так как из головы уже всё выветрилось, а заново изучать код, быстро вникать в тему - я не способен. Поэтому просто не стал трогать.
Получается, если я захочу воспроизвести ваши результаты на своем компьютере и измерить время работы у себя, у меня не получится это сделать? В чем смысл тогда вообще код приводить, если вы знаете, что он работать не будет?
Сниппет — это блок с краткой информацией о странице сайта, содержащий ссылку на документ, который отображается в результатах поиска.
Сниппет - это просто англицизм от англ. snippet - фрагмент, отрывок. Тем более, смысл был из контекста понятен.
Браво! А теперь замените черепаху на синюю клетку и получится дословно алгоритм из статьи.
Создать список синих клеток (все свободные клетки лабиринта)
Цикл - пока список синих клеток не пуст
Рассчитать путь для синей клетки до выхода
Записать в результирующий список команд
Передвинуть все синие клетки из списка по маршруту из п.3 производя слияние элементов списка при совпадении клеток или удаляя из списка тех, что вышли из лабиринта
мне не требуется Дейкстра чтобы найти выход, информация о том как именно выйти строится во время обхода.
Да нет никакой разницы как вы его найдете, хоть dfs запустите. Речь же не о том. Задача стояла "придумайте алгоритм, который выпишет конечную последовательность". Это теоретическая задача, а не контест. Здесь никаких ограничений по времени и памяти нет у вас нет.
Для меня тут очевидно, что "проделав данный маршрут" черепаха могла вернуться в исходную точку, а значит состояние не изменилось, а значит она не перешла в другую клетку, а значит количество вариантов нового расположения осталось неизменным.
Это неверно. Из того, что черепаха могла вернуться в ту же точку не следует, что число вариантов не изменилось. У меня в статье на рис. 3 как раз изображены такие случаи, однако все равно появилась новая белая клетка.
Объясните другими словами, так как исходя из первого абзаца мы не можем исключить вероятность того, что множества вернулись в исходное состояние, а значит ничего никуда не перешло.
Множество не могли вернуться в исходное состояние, т.к. минимум одна синяя клетка перешла в зеленую (а зеленая умеет переходить только сама в себя, если хотите).
А здесь я уже запутался. В первом абзаце вы пишете о теоретической возможности не попасть на выход, а в этом абзаце вы уже подразумеваете что строите гарантирующий выход маршрут.
Не всякая синяя клетка попадет в зеленую. Но одна (та самая, выбранная нами) - обязательно попадает.
И что конкретно значат синие и белые клетки? Как именно вы их определяете?
Синяя клетка - это клетка, где может находиться черепаха. Например, вначале все кроме клетки "выход" - синие.
Белая клетка - это клетка, где гарантированно нет черепахи.
Зеленая клетка - клетка "выход".
По какому принципу вы их уменьшаете на 1 и какой критерий их выбора?
Выполняя итерацию за итерацией, число синих клеток уменьшается хотя бы на 1 естественным образом. Наша задача - отслеживать их. Для этого просто вручную посмотрим куда переходит каждая из них. Минимум одна синяя точно перейдет в зеленую (т.к. она была выбрана и для нее специально был построен туда маршрут), остальные - отследим и перейдем к следующей итерации =)
Это утверждение ложно, не на каждой итерации черепашка будет попадать на клетку "выход". Чем меньше у вас будет черепашек, тем больше будут интервалы между выходами.
Итерация = следование по маршруту до выхода. После каждой итерации число синих клеток уменьшится хотя бы на 1.
Не понятен смысл этого утверждения, для нас абсолютно не важно что где-то освободится клетка, мы же не в неё идём.
Если число белых клеток увеличилось, значит число синих уменьшилось, т.к. в сумме их всегда n*m-1. Когда синие клетки закончатся, черепашка гарантированно выйдет.
Тут вас спасло "хотя бы", так как в теории вы можете взять одну единственную черепаху и пока ведёте её к выходу у вас просто весь лабиринт опустеет
Все рассуждения, очевидно, про верхнюю оценку числа ходов. Это называется аккуратно формулировать свои мысли :)
Маршруты вида Ч -> Ч плохи тем, что одна черепаха может убегать от другой. Объяснить как строить такие склейки сложнее, чем просто вести черепашек в выходу :)
Простой пример. Я произвольно (я имею право) выбираю клетку под клеткой выход (на картинке). Теперь по предложенному способу наша послебовательность up. :)
Тогда прямо под клеткой выход появится пустая клетка (где точно не может быть черепахи). Более того, весь нижний ряд можно считать теперь пустыми клетками, если хотите. Число пустых клеток увеличилось. Теперь проделаем так с оставшимися непустыми клетками, при этом будем следить куда клетки переходят. Важно, что число пустых клеток будет строго монотонно расти от итерации к итерации.
то что одна клетка освободится это очевидно, но это же не решение
Минимум одна клетка освободится, и мы легко сможем все свободные (белые) клетки найти, выполнив набор команд для каждой занятой (синей) клетки. Каждый раз число свободных (белых) клеток увеличивается хотя бы на 1, за счет того, что мы будем выбирать новую синюю клетку и запускать программу на выход из нее.
Благодарю вас за проделанную работу. Однако, ни на одну фактическую ошибку вы так и не указали, зато сообщили всем вокруг, что не смогли ничего понять.
Убедительно прошу прекратить вас спамить и замусоривать комментарии.
Спасибо!
Из статьи не совсем ясно, что такое "большие данные". Нет ни слова о том, как вы их на самом деле генерируете, а это может существенно влиять на бенчмарки.
Если я верно понял, вы просто много раз повторяете исходную строку? В таком случае, это не совсем честный бенчмарк, т.к. максимум достигается почти сразу (на первом же вхождении исходной строки в длинную). Интереснее было бы посмотреть на тест, в котором максимум постоянно растет.
del
Получается, если я захочу воспроизвести ваши результаты на своем компьютере и измерить время работы у себя, у меня не получится это сделать? В чем смысл тогда вообще код приводить, если вы знаете, что он работать не будет?
Сниппет - это просто англицизм от англ. snippet - фрагмент, отрывок. Тем более, смысл был из контекста понятен.
У вас во втором сниппете кода баг. Сможете найти?
Вполне корректный алгоритм.
А код на питоне вас устроит? :)
Браво! А теперь замените черепаху на синюю клетку и получится дословно алгоритм из статьи.
Создать список синих клеток (все свободные клетки лабиринта)
Цикл - пока список синих клеток не пуст
Рассчитать путь для синей клетки до выхода
Записать в результирующий список команд
Передвинуть все синие клетки из списка по маршруту из п.3 производя слияние элементов списка при совпадении клеток или удаляя из списка тех, что вышли из лабиринта
Вернуться в п.2
Так если задача не причем, почему пишите об этом здесь?
Оптимизация чего? Я как автор статьи не совсем понимаю, о чем вы :)
Да нет никакой разницы как вы его найдете, хоть dfs запустите. Речь же не о том. Задача стояла "придумайте алгоритм, который выпишет конечную последовательность". Это теоретическая задача, а не контест. Здесь никаких ограничений по времени и памяти нет у вас нет.
Затем, что вы не знаете, где черепаха. Все синие клетки для вас норм.
Кто кого троллит)
Одна итерация - это не одна команда, а последовательность команд, переводящая одну из синих клеток в зеленую.
То, что выбрав любую точку можно дойти до выхода доказывать как раз не нужно, т.к. это следует из словосочетания "связный лабиринт" :)
Этого может не произойти, если черепаха сидит не в выбранной вами клетке. Она может сидеть в любой синей, мы же не знаем в какой из них :)
Одна клетка обязательно перейдет в зеленую. Остальные - как повезет. Если ваша черепаха в той выбранной синей, то она точно выйдет.
Это неверно. Из того, что черепаха могла вернуться в ту же точку не следует, что число вариантов не изменилось. У меня в статье на рис. 3 как раз изображены такие случаи, однако все равно появилась новая белая клетка.
Множество не могли вернуться в исходное состояние, т.к. минимум одна синяя клетка перешла в зеленую (а зеленая умеет переходить только сама в себя, если хотите).
Не всякая синяя клетка попадет в зеленую. Но одна (та самая, выбранная нами) - обязательно попадает.
Синяя клетка - это клетка, где может находиться черепаха. Например, вначале все кроме клетки "выход" - синие.
Белая клетка - это клетка, где гарантированно нет черепахи.
Зеленая клетка - клетка "выход".
Выполняя итерацию за итерацией, число синих клеток уменьшается хотя бы на 1 естественным образом. Наша задача - отслеживать их. Для этого просто вручную посмотрим куда переходит каждая из них. Минимум одна синяя точно перейдет в зеленую (т.к. она была выбрана и для нее специально был построен туда маршрут), остальные - отследим и перейдем к следующей итерации =)
Отличное наблюдение, все верно! :)
Итерация = следование по маршруту до выхода. После каждой итерации число синих клеток уменьшится хотя бы на 1.
Если число белых клеток увеличилось, значит число синих уменьшилось, т.к. в сумме их всегда n*m-1. Когда синие клетки закончатся, черепашка гарантированно выйдет.
Все рассуждения, очевидно, про верхнюю оценку числа ходов. Это называется аккуратно формулировать свои мысли :)
Это как?
Маршруты вида Ч -> Ч плохи тем, что одна черепаха может убегать от другой. Объяснить как строить такие склейки сложнее, чем просто вести черепашек в выходу :)
Тогда прямо под клеткой выход появится пустая клетка (где точно не может быть черепахи). Более того, весь нижний ряд можно считать теперь пустыми клетками, если хотите. Число пустых клеток увеличилось. Теперь проделаем так с оставшимися непустыми клетками, при этом будем следить куда клетки переходят. Важно, что число пустых клеток будет строго монотонно расти от итерации к итерации.
Минимум одна клетка освободится, и мы легко сможем все свободные (белые) клетки найти, выполнив набор команд для каждой занятой (синей) клетки. Каждый раз число свободных (белых) клеток увеличивается хотя бы на 1, за счет того, что мы будем выбирать новую синюю клетку и запускать программу на выход из нее.