Вступление
"Muhuhuhahahah!" Безумный ученый смеется. "Ты пойман в ловушку в моей собственной маленькой игре!"
Перед вами смертельная яма змей, а позади вас бездонная пропасть. Выхода нет, ты застрял!
«В двух шагах от вас - яма со змеями, а в двух шагах от вас - пропасть. Но! Прежде чем двигаться, вы ДОЛЖНЫ записать последовательность шагов вперед и назад и отдать их мне. Но! Потому что я Я чувствую себя немного злым сегодня, я могу заставить вас сделать вместо каждого шага каждый nшаг, nкоторый меньше длины вашей последовательности!
Выбирай мудро, сейчас.
Какое максимальное количество шагов вы можете сделать перед своей неминуемой смертью?
задача
Введенное выше вступление является искажением гипотезы расхождения Эрда , которая недавно была подтверждена (если вы хотите больше узнать об этом, перейдите к этому видео , написанному Джеймсом Граймом - я «украл» у него извращенный вопрос).
Ответ на введение - 11шаги, но я не буду слишком углубляться в доказательство. Ответ, если расстояние между вами и двумя «опасностями» составляло 3шаги, это 1160шаги, хотя это еще не подтверждено должным образом.
Ваша задача состоит в том, чтобы создать программу, которая генерирует самую длинную последовательность шагов, которую вы можете достичь, для большего x, где xуказано количество шагов между вами и двумя «опасностями». Ваша программа должна принимать xи выводить правильную последовательность для этого x.
Для целей этой задачи +представляет собой шаг вперед и -представляет собой шаг назад.
Итак, выход для входа 2:
+--+-++--++
Что работает, независимо от того, nчто выберет безумный ученый. Для нашего вызова x = 5.
ПРИМЕЧАНИЕ. Эта задача не является дублированием этой задачи или этой задачи , так как моя задача сосредоточена на выводе, а не на самом коде - другими словами, это не задача игры в гольф. Кроме того, эти проблемы основаны на том x = 3, что уже имеет установленную верхнюю границу.
Правила:
- Вся ваша программа должна соответствовать вашему ответу. Однако, если он не подходит, предоставьте дополнительный репозиторий Github или что-то подобное.
- Вы можете обновить как свой ответ, так и свою программу, если вы можете получить более высокий балл за счет оптимизации своего кода - но при этом вы должны обновить все в списке ниже.
- В своем ответе вы должны иметь:
- Ваша программа целиком или ссылка на репозиторий GH, содержащий ваш код
- Количество сгенерированных шагов - это будет ваш окончательный счет .
- Вы также должны предоставить онлайн-версию последовательности в Pastebin или что-то подобное. Это так, чтобы мы могли проверить ваш ответ.
- Время последнего обновления вашего финального счета, поэтому мне не нужно проверять вашу историю
- Вы не можете жестко кодировать последовательности заранее.
- Ваша программа должна работать для всех
x(гдеxуказано количество шагов между вами и ямой и пропастью), но вам нужно только указать счетx = 5.
Ответ с наибольшим счетом выигрывает!
источник
nшаг, гдеnлюбое число меньше размера вашей последовательности.x=5потребовало бы серьезного прорыва, который заслуживал бы публикации. Учтите, что максимум 1160 дляx=3был доказан и опубликован в 2014 году, а дальнейшие значения неизвестны. ,Ответы:
Руст, счет = 4997216, время = 2017-07-12 00:18 UTC
Это улучшает лучший результат, который я смог найти в литературе, который был 1148805 (Ронан Ле Бра, Карла П. Гомес, Барт Сельман, О проблеме расхождения Эрда , 2014), в 4,3 раза.
Выходная последовательность длиной 4997216
Исходный код на GitHub
Бег
Программа принимает максимальное расхождение в качестве аргумента (это x - 1 на языке вызова, чтобы соответствовать более распространенному математическому соглашению). Он создает инкрементные выходные данные в слегка сжатом формате, который выглядит следующим образом для x = 3:
где
addозначает добавление последовательности знаков в конец текущей последовательности,deleteсредство удаление некоторого количества знаков с конца текущей последовательности иlengthопределение длины текущей последовательности. Эта схема позволяет избежать получения многих гигабайт промежуточных результатов при обнаружении более длинных и длинных последовательностей. На данный момент вы можете получить лучший результат с помощью следующей программы на Python:Как это устроено
Здесь около тысячи строк кода, поэтому это будет лишь приблизительный обзор.
Мы ограничиваем поиск полностью мультипликативными последовательностями (последовательности с f ( a · b ) = f ( a ) · f ( b )), потому что это означает, что нам нужно лишь ограничиться частичными суммами для n = 1 и частичными суммы для n ≥ 2 будут автоматически удовлетворять той же границе.
Для любой подстроки f ( i + 1),…, f ( j ) частично назначенной последовательности знаков (таким образом, каждый элемент равен «+», «-» или неизвестен), определите опасность + ( i , j ), чтобы она была в два раза больше число '+ минус длина j - i (для удобства мы допускаем, чтобы i было меньше - x + 2, и предполагаем, что f (- x + 3) = ⋯ = f (0) =' + 'для это цель). Определите опасность - ( i , j ) аналогично. Тогда оценка частичных сумм для n = 1 эквивалентно условию, что всякий раз, когда i ≡j ≡ x (mod 2), опасность + ( i , j ) ≤ x - 2 и опасность - ( i , j ) ≤ x - 2.
Мы строим инкрементную структуру данных, которая поддерживает запросы постоянного времени для подстроки с наибольшей опасностью, с логарифмическими обновлениями времени. Это работает, связывая четыре значения:
с каждой строкой длины 2, каждой второй строкой длины 4, каждой четвертой строкой длины 8 и так далее. Значения, связанные с более длинной строкой, могут быть вычислены в постоянное время из значений, связанных с двумя ее половинами.
Эта структура, дополненная некоторой вспомогательной информацией, позволяет очень быстро выполнять распространение ограничений и обнаружение конфликтов на частичных последовательностях. Мы используем это, чтобы сделать CDCL подобного поиска с распространением единиц измерения, уровнями принятия решений и не хронологическим отслеживанием (пока без обучения по пунктам) для полных последовательностей большей и большей длины.
На каждом шаге поиска мы делаем предположение для самого раннего неназначенного знака. Эвристика, используемая, чтобы сделать это предположение, очень важна для избежания большого количества возвратов; мы используем f (3 · k ) = - f ( k ), f (3 · k + 1) = '+', f (3 · k + 2) = '-'.
Результаты
Поиск несоответствия 0, 1 и 2 немедленно находит оптимальные полностью мультипликативные последовательности длины 0, 9 и 246.
Поиск несоответствия 3 застревает в течение нескольких секунд на 41319, что довольно далеко от известной оптимальной полностью мультипликативной последовательности длиной 127645, найденной Le Bras et al., 2014 (и очень немного более длинного немультипликативного расширения длины 130000, обнаруженного вскоре после этого. ), но намного лучше, чем самая известная последовательность до длины 17000 .
Поиск по несоответствию 4 улучшает самую длинную последовательность более или менее непрерывно в течение примерно пяти минут, пока она не застрянет на 4997216. Лучшая ранее известная последовательность длиной 1148805 = 9 · 127645 была расширена из последовательности несоответствия 3 путем замены каждого знака s на + - - + - ++ - s . Насколько я могу судить, такие длинные последовательности слишком сложны для непосредственного улучшения SAT-анализатора (но, может быть, вы, дорогой читатель, можете доказать, что я ошибался!).
Я ожидаю, что мне нужно будет добавить какое-то изучение статей в мою программу, чтобы преодолеть эти барьеры.
Последовательность как растровое изображение 2187 × 2285
(Нажмите для просмотра в полном разрешении.)
источник
Haskell , счет = 9020, время = 2017-06-09 00:52 UTC
Попробуйте онлайн!
Эта оценка (9 n - 1 - 1) /11 / 8 для всех n . Вот первые несколько результатов:
источник