Идея в том, чтобы создать почти повторяющийся узор. То есть создаваемая последовательность изменяется в последний момент, чтобы избежать повторения некоторой подпоследовательности. Следует избегать подпоследовательностей типа AA и ABA (где B не длиннее A).
Примеры:
Я начну с перечисления всех небольших примеров, чтобы сделать мое описание более понятным. Давайте начнем с 0.
Действительно: 0 Неверно: 00 (шаблон AA) Действительно: 01 Неверно: 010 (шаблон ABA) Неверно: 011 (шаблон AA) Действительно: 012 Действительно: 0120 Неверно: 0121 (шаблон ABA) Неверно: 0122 (шаблон AA) Неверно: 01200 (шаблон AA) Неверно: 01201 (шаблон ABA; 01-2-01) Неверно: 01202 (шаблон ABA) Действительно: 01203
Теперь я твердо верю, что a 4
никогда не нужен, хотя у меня нет доказательств, потому что я легко нашел последовательности длиной в сотни символов, которые используют только 0123
. (Вероятно, это тесно связано с тем, что для того, чтобы иметь бесконечные строки без шаблонов АА, нужны всего три символа. На этой странице есть страница Википедии .)
Ввод, вывод
Входные данные представляют собой одно положительное ненулевое целое число n
. Вы можете предположить это n <= 1000
.
Выход - это n
последовательность -характера без подпоследовательностей, которые соответствуют либо запрещенному шаблону (AA или ABA).
Образцы входов и выходов
>>> 1 0 >>> 2 01 >>> 3 012 >>> 4 0120 >>> 5 01203 >>> 50 01203102130123103201302103120132102301203102132012
правила
- Разрешены только символы
0123
. - Не Б не дольше , чем А. Это позволяет избежать ситуации , при которой
012345
должен быть следуют ,6
потому что0123451
есть это:1-2345-1
. Другими словами, последовательность будет тривиальной и неинтересной. n
может быть введен любым желаемым методом, кроме жесткого кодирования.- Вывод может быть либо списком, либо строкой, в зависимости от того, что проще.
- Нет грубой силы ; время работы должно быть порядка минут, максимум час на очень медленной машине
n=1000
. (Это предназначено для дисквалификации решений, которые просто перебирают всюn
длину перестановок{0,1,2,3}
, так что трюк и подобные трюки не допускаются.) - Стандартные лазейки запрещены, как обычно.
- Оценка в байтах. ЭтоКод-гольф, поэтому выигрывает самая короткая запись (вероятно - см. бонус).
- Бонус: выберите самую низкую разрешенную цифру на каждом шаге. Если
1
и3
возможны варианты выбора следующей цифры в последовательности, выберите1
. Вычтите 5 байтов из вашего счета. Тем не менее, обратите внимание на примечание ниже.
Запись!
Возможны тупики. Ваша программа или функция должны избегать этого. Вот пример:
Пень: 0120310213012310320130210312013210230120310213201230210312013023103201230213203102301203210231201302103123013203102130120321023013203123021032012310213012031030132020203013 Пень: 01203102130123103201302103120132102301203102132012302103120130231032012302132031023012032102312013021031230132031021301203210230132031230210320123102130120310301013102323013 Пень: 012031021301231032013021031201321023012031021320123021031201302310320123021320310230120321023120101232312301320310213012032102301320312302103201231021301331030213012031030213 Пень: 01203102130123103201302103120132102301203102132012302103120130231032012302132031023012032102312013021031230132031021301203210230132031230210320110302101203103021012031030210120310302030121030202
Каждая из этих последовательностей не может быть расширена далее (без использования a 4
). Но также обратите внимание, что между первыми двумя и вторыми двумя есть принципиальная разница. Я заменю общую начальную подпоследовательность на, X
чтобы сделать это более понятным.
Пень: X2130120 Пень: X2130123 Пень: Х320 Пень: X321301203102130
Последние две цифры X
- 10
это единственные возможные варианты следующей цифры 2
и 3
. Выбор 2
приводит к ситуации, когда последовательность должна завершаться. Жадный алгоритм не будет работать здесь. (Во всяком случае, не без возврата.)
источник
n
? Если кто-то излагает эвристический полужадный алгоритм, как вы будете проверять, чтобы он не сталкивался с проблемами очень большой длины? Общая проблема интересна, и я не смог найти ничего во избежание шаблона, где мы ограничиваем длину части шаблона. Если кто-то может создать общий рецепт, я ожидаю, что это будет лучшим подходом.n
, но, учитывая, что найденные моей программой пни имеют тенденцию увеличиваться в среднем на 10 цифр каждый раз, я очень уверен, что существует бесконечная последовательность. Я не уверен, как полужадный алгоритм мог быть проверен для произвольно больших последовательностей. Я мог бы ограничить требование доn
= 1000 и просто не беспокоиться о более высокомn
.AA
это действительно тип,ABA
гдеB
пусто. Возможно, это поможет оптимизировать некоторые решения.Ответы:
Retina , 86 байт - 5 = 81
Где
<empty>
представляет собой пустую висячую строку. Вы можете запустить приведенный выше код из одного файла с-s
флагом.Ввод должен быть дан в унарном виде , например
111111
. Я еще не тестировал его на вывод порядка тысячи - два регулярных выражения могут через некоторое время стать немного медленными - но он может легко обработать пару сотен за несколько секунд.объяснение
Это простое решение для возврата.
0
.3
.Этот возврат осуществляется с помощью цикла подстановок регулярных выражений, который прерывается, когда строка остается неизменной в течение одной итерации.
Это добавляет a
_
к входу, который используется для отделения унарного ввода от последовательности, которую мы строим.Это первая замена в цикле (обозначена лидирующей
(
). Регулярное выражение совпадает, если а) в конце строки есть символ слова (т. Е. Цифра) (что означает, что строка действительна - ниже мы увидим, что недопустимые последовательности помечены завершающим символом#
) и б) по крайней мере столько символов в последовательности, сколько на входе (это проверяется с помощью групп балансировки ). Если это так, мы удаляем ввод и добавляем!
. Это!
служит для сбоя всех регулярных выражений в цикле, так что он завершается.Если в конце есть символ слова (то есть последовательность действительна, и цикл не был завершен предыдущим шагом), добавьте a
0
.Если (вместо этого) последовательность была помечена как недействительная и закончилась
3
, мы удаляем это3
(но оставляем последовательность как недействительную, потому что нет никакого возможного продолжения для текущего префикса ..., поэтому следующий символ также должен быть возвращен).Если последовательность помечена как недействительная, и любая цифра, кроме той, которая
3
находится в конце, мы увеличиваем цифру и удаляем маркер.Последняя замена в цикле (как указано
)
). Он проверяет, заканчивается ли строкаABA
(гдеB
она не длиннее,A
а потенциально пуста). Относительные длиныA
иB
снова проверяются с помощью балансировочных групп, а повторениеA
проверяется с помощью простой обратной ссылки.Если это регулярное выражение совпадает, мы помечаем последовательность как недействительную, добавляя
#
.Как только цикл завершается, все, что нам нужно сделать, это удалить
!
и затем оставить желаемый результат.источник
Python 2, 175 - 5 = 170 байт
Это жадный алгоритм с возвратом. Я хотел бы, чтобы это было короче. Я надеюсь, что это правильно (см. Ниже).
Он строит строку по одной цифре за раз. Учитывая строку
d
цифр, которую он уже нашел, он пытается добавить в0
качестве(d+1)
st цифру. Если это не сработает, то попытается a1
, затем a2
, затем a3
. Если ничего из этого не работает, то он возвращается кd
th-й цифре и увеличивает ее (если меньше3
) или удаляет (если равен3
, в этом случае он увеличивает предыдущую и т. Д.).Проверка на достоверность - это строка с
.find
ним. В случае, если кто-то решит прочитать мой код, я должен сказать, что эта программа на самом деле хранит строку в обратном направлении, то есть добавляет цифры впереди . Таким образом, проверка включает в себя поиск мест, где первыеc
цифры снова появляются позже в строке (в любом месте после первыхc
цифр), и если есть какие-либо такие места, является ли промежуточная длина не болееc
.(Конечно, это переворачивает строку перед печатью.)
Это может также легко быть быстрее; Первоначально я имел выход из различных циклов рано для эффективности, но это стоило драгоценных байтов. Это все еще хорошо в диапазоне
n=1000
, хотя.В любом случае, программа, похоже, отдает предпочтение меньшим цифрам, но это не очень сильное предпочтение. Например, запуск его с помощью
n=2000
дал мне строку с523
нулями,502
единицами,497
двойками и478
тройками, заканчивающимися на30210312013021
. Так что, если кто-то еще работает над жадным алгоритмом, возможно, он сможет подтвердить этот результат. Или сn=1000
я получил[263, 251, 248, 238]
за счет цифры.Наконец, я хотел бы упомянуть, что эти подсчеты являются своего рода наводящими на размышления о симметрии, почти (хотя и не совсем), как если бы мы начали с равномерного распределения, а затем преобразовали некоторые из
3
«к0
» и несколько из2
«к1
» s. Но очевидно, что это может быть просто совпадением. Не имею представления!источник
Haskell, 115 (120 байт - 5 бонусов)
Запустить онлайн на Ideone
Пример выполнения:
источник