Черепаха в лабиринте: Медлительное путешествие к свободе

Да я уже нашел ошибку в статье, так что этот вопрос уже закрыт.

Благодарю вас за проделанную работу. Однако, ни на одну фактическую ошибку вы так и не указали, зато сообщили всем вокруг, что не смогли ничего понять.

Убедительно прошу прекратить вас спамить и замусоривать комментарии.

Спасибо!

В поисках алгоритмического дзена

Имея на руках две реализации можем посмотреть как они себя поведут в бенчмарке (Length - кратное увеличение размера строки, чтобы смотреть как ведет себя реализация на больших данных)

Из статьи не совсем ясно, что такое "большие данные". Нет ни слова о том, как вы их на самом деле генерируете, а это может существенно влиять на бенчмарки.

Если я верно понял, вы просто много раз повторяете исходную строку? В таком случае, это не совсем честный бенчмарк, т.к. максимум достигается почти сразу (на первом же вхождении исходной строки в длинную). Интереснее было бы посмотреть на тест, в котором максимум постоянно растет.

В поисках алгоритмического дзена

del

В поисках алгоритмического дзена

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

Получается, если я захочу воспроизвести ваши результаты на своем компьютере и измерить время работы у себя, у меня не получится это сделать? В чем смысл тогда вообще код приводить, если вы знаете, что он работать не будет?

Сниппет — это блок с краткой информацией о странице сайта, содержащий ссылку на документ, который отображается в результатах поиска.

Сниппет - это просто англицизм от англ. snippet - фрагмент, отрывок. Тем более, смысл был из контекста понятен.

В поисках алгоритмического дзена

У вас во втором сниппете кода баг. Сможете найти?

// SkipWord
int maxlen = 1;
int maxindex = -1;
int temp_maxlen = 0;
int temp_maxindex = 0;
int i = 0;
while (i < str.Length)
{
    if ((str[i] >= 'a' && str[i] <= 'z') || (str[i] >= 'A' && str[i] <= 'Z'))
    {
        temp_maxlen = 0;
        temp_maxindex = i;
        do
        {
            temp_maxlen++;
            i++;
        }
        while (((str[i] >= 'a' && str[i] <= 'z') || (str[i] >= 'A' && str[i] <= 'Z')) && i < str.Length);
        if (temp_maxlen > maxlen)
        {
            maxlen = temp_maxlen;
            maxindex = temp_maxindex;
        }
    }
    i++;
}
Console.WriteLine("Длина = {0}, слово = {1}", maxlen, str.Substring(maxindex, maxlen));

Черепаха в лабиринте: Медлительное путешествие к свободе

о том и речь, нет алгоритма и нет реализации, есть идея

Вполне корректный алгоритм.

небрежно оформленная, вы даже псевдокод написали умолчав о половине действий

А код на питоне вас устроит? :)

Черепаха в лабиринте: Медлительное путешествие к свободе

Браво! А теперь замените черепаху на синюю клетку и получится дословно алгоритм из статьи.

1. Создать список синих клеток (все свободные клетки лабиринта)

2. Цикл - пока список синих клеток не пуст

3. Рассчитать путь для синей клетки до выхода

4. Записать в результирующий список команд

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

6. Вернуться в п.2

Черепаха в лабиринте: Медлительное путешествие к свободе

а причем здесь задача? я пишу о реализации своего алгоритма на ЯП, вы за контекстом треда следите.

Так если задача не причем, почему пишите об этом здесь?

Черепаха в лабиринте: Медлительное путешествие к свободе

Где некая оптимизация, отчего-то же автор даже статью написал

Оптимизация чего? Я как автор статьи не совсем понимаю, о чем вы :)

Черепаха в лабиринте: Медлительное путешествие к свободе

мне не требуется Дейкстра чтобы найти выход, информация о том как именно выйти строится во время обхода.

Да нет никакой разницы как вы его найдете, хоть dfs запустите. Речь же не о том. Задача стояла "придумайте алгоритм, который выпишет конечную последовательность". Это теоретическая задача, а не контест. Здесь никаких ограничений по времени и памяти нет у вас нет.

Черепаха в лабиринте: Медлительное путешествие к свободе

Зачем мне выбирать клетку без черепахи?

Затем, что вы не знаете, где черепаха. Все синие клетки для вас норм.

Мне кажется вы уже просто меня троллите.

Кто кого троллит)

Нет. Например справа от выхода стена, тогда команда "налево" не приведет к тому, что у вас кто-то достигнет финиша.

Одна итерация - это не одна команда, а последовательность команд, переводящая одну из синих клеток в зеленую.

Черепаха в лабиринте: Медлительное путешествие к свободе

То, что выбрав любую точку можно дойти до выхода доказывать как раз не нужно, т.к. это следует из словосочетания "связный лабиринт" :)

Черепаха в лабиринте: Медлительное путешествие к свободе

Мне очевидно что если я веду черепаху на выход, то она выйдет, но зачем тогда вы описываете ситуацию когда этого не происходит?

Этого может не произойти, если черепаха сидит не в выбранной вами клетке. Она может сидеть в любой синей, мы же не знаем в какой из них :)

В моем решении такие ситуации могут быть и я объяснил почему, но у вас синее переходит в зеленое обязательно, зачем тогда этот абзац?

Одна клетка обязательно перейдет в зеленую. Остальные - как повезет. Если ваша черепаха в той выбранной синей, то она точно выйдет.

Черепаха в лабиринте: Медлительное путешествие к свободе

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

Это неверно. Из того, что черепаха могла вернуться в ту же точку не следует, что число вариантов не изменилось. У меня в статье на рис. 3 как раз изображены такие случаи, однако все равно появилась новая белая клетка.

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

Множество не могли вернуться в исходное состояние, т.к. минимум одна синяя клетка перешла в зеленую (а зеленая умеет переходить только сама в себя, если хотите).

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

Не всякая синяя клетка попадет в зеленую. Но одна (та самая, выбранная нами) - обязательно попадает.

И что конкретно значат синие и белые клетки? Как именно вы их определяете?

Синяя клетка - это клетка, где может находиться черепаха. Например, вначале все кроме клетки "выход" - синие.

Белая клетка - это клетка, где гарантированно нет черепахи.

Зеленая клетка - клетка "выход".

По какому принципу вы их уменьшаете на 1 и какой критерий их выбора?

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

Черепаха в лабиринте: Медлительное путешествие к свободе

Отличное наблюдение, все верно! :)

Черепаха в лабиринте: Медлительное путешествие к свободе

Это утверждение ложно, не на каждой итерации черепашка будет попадать на клетку "выход". Чем меньше у вас будет черепашек, тем больше будут интервалы между выходами.

Итерация = следование по маршруту до выхода. После каждой итерации число синих клеток уменьшится хотя бы на 1.

Не понятен смысл этого утверждения, для нас абсолютно не важно что где-то освободится клетка, мы же не в неё идём.

Если число белых клеток увеличилось, значит число синих уменьшилось, т.к. в сумме их всегда n*m-1. Когда синие клетки закончатся, черепашка гарантированно выйдет.

Тут вас спасло "хотя бы", так как в теории вы можете взять одну единственную черепаху и пока ведёте её к выходу у вас просто весь лабиринт опустеет

Все рассуждения, очевидно, про верхнюю оценку числа ходов. Это называется аккуратно формулировать свои мысли :)

Черепаха в лабиринте: Медлительное путешествие к свободе

пусть все черепашки идут к ближайшим известным роутам

Это как?

Черепаха в лабиринте: Медлительное путешествие к свободе

Маршруты вида Ч -> Ч плохи тем, что одна черепаха может убегать от другой. Объяснить как строить такие склейки сложнее, чем просто вести черепашек в выходу :)

Черепаха в лабиринте: Медлительное путешествие к свободе

Простой пример. Я произвольно (я имею право) выбираю клетку под клеткой выход (на картинке). Теперь по предложенному способу наша послебовательность up. :)

Тогда прямо под клеткой выход появится пустая клетка (где точно не может быть черепахи). Более того, весь нижний ряд можно считать теперь пустыми клетками, если хотите. Число пустых клеток увеличилось. Теперь проделаем так с оставшимися непустыми клетками, при этом будем следить куда клетки переходят. Важно, что число пустых клеток будет строго монотонно расти от итерации к итерации.

Черепаха в лабиринте: Медлительное путешествие к свободе

то что одна клетка освободится это очевидно, но это же не решение

Минимум одна клетка освободится, и мы легко сможем все свободные (белые) клетки найти, выполнив набор команд для каждой занятой (синей) клетки. Каждый раз число свободных (белых) клеток увеличивается хотя бы на 1, за счет того, что мы будем выбирать новую синюю клетку и запускать программу на выход из нее.