Введение
Предположим на мгновение, что гадюки и скалы находятся всего в двух шагах от трех.
o
---
Hsss! |
';;' ___ /_\ ___ _
|
Вы, к сожалению, пленник садистского мучителя. Вы должны сделать шаг влево или вправо каждый ход. Если вы этого не сделаете, они застрелят вас мгновенно. Вам разрешено планировать свои шаги заранее, но как только вы сделаете свой первый шаг, вы не сможете изменить свой план. (И бездельничать; тебя пристрелят.)
Внезапно, яркая идея приходит на ум ...
Ах! Я могу просто чередовать шаг вправо и влево! Шаг вправо, шаг влево, шаг вправо, шаг влево и так далее ...
Ах, ах, ах, не так быстро. Как я уже сказал, мучитель садистский. Они выбирают, делать ли вам каждый шаг, или каждый второй шаг, или каждый третий шаг, и так далее. Так что, если вы наивно выберете последовательность, RLRLRL...
то они могут заставить вас сделать каждый второй шаг, который начинается с LL
. Ой! Вы были укушены гадюками! Тьма налетает на тебя, а все остальное исчезает ...
На самом деле нет, ты еще не умер. Вы все еще должны придумать свой план. Подумав об этом несколько минут, вы понимаете, что обречены. Нет способа спланировать серию шагов, которые гарантируют вам выживание. Лучшее, что вы можете придумать, это RLLRLRRLLRR
. 1 Одиннадцать безопасных шагов и не более. Если это двенадцатый шаг R
, то Мучитель заставит вас сделать каждый шаг, а затем последние три шага отправят вас с обрыва. Если это двенадцатый шаг L
, то Мучитель заставит вас сделать каждый третий шаг ( LRLL
), что приведет вас прямо к выводку гадюк и их смертоносным укусам.
Вы выбираете R
в качестве двенадцатого шага, надеясь задержать вашу смерть как можно дольше. С ревом в ушах, вы удивляетесь себе ...
Что если бы у меня было три шага?
Осторожно, спойлеры!
Ты бы все равно умер. Как выясняется, независимо от того, сколько у вас шагов, будет определенная точка, где независимо от того, какой выбор вы сделаете, есть последовательность шагов, которую ваш мучитель может выбрать, чтобы убедиться, что вы встретите свою смертельную судьбу. 2 Однако, когда гадюки и обрыв находятся в трех шагах, вы можете сделать всего 1160 безопасных шагов, а когда они находятся в четырех шагах, есть как минимум 13 000 безопасных шагов! 3
Соревнование
Учитывая одно целое число n < 13000
, выведите последовательность n
безопасных шагов, предполагая, что обрыв и гадюки находятся в четырех шагах.
правила
- Может быть либо полной программой, либо функцией.
- Ввод может быть взят через STDIN или эквивалентный, или как аргумент функции.
- Вывод должен иметь два различных символов (которые могут быть
+/-
,R/L
,1/0
и т.д.). - Любые пробелы в выводе не имеют значения.
- Жесткое кодирование решения не допускается. Это бы упростило эту задачу.
- Ваша программа должна (в теории) закончиться в приличном количестве времени. Как и в,
n=13000
может занять как месяц, но это не должно занять тысячу и более лет. То есть без грубой силы. (Ну, по крайней мере, попытайтесь избежать этого.) - Бонус жизни: обеспечьте серию
2000
безопасных шагов. Если вы сделаете это, Мучитель будет настолько впечатлен вашим упорством, настойчивостью и предусмотрительностью, что они позволят вам жить. Это один раз. (Рассматривайте эту последовательность как двоичное число и предоставляйте десятичный эквивалент для проверки. Это предназначено для поощрения ответов, которые заканчиваются быстро, поскольку ответы могут занимать очень много времени.) - Оценка: байты , если вы не имеете права на бонус - умножьте на 0,75 .
1 Существует хорошее объяснение этой проблемы и «решения» одной из звезд Numberphile, Джеймса Грайма, на своем канале YouTube здесь: https://www.youtube.com/watch?v=pFHsrCNtJu4 .
2 Эта гипотеза 80-летней давности, известная как проблема несоответствия Эрдоса, была доказана совсем недавно Теренсом Тао. Вот очень хорошая статья в журнале Quanta об этом: https://www.quantamagazine.org/20151001-tao-erdos-discrepancy-problem/ .
3 Источник: SAT-атака на гипотезу несоответствия Эрдоса. Автор Борис Конев и Алексей Лисица. Получено здесь: http://arxiv.org/pdf/1402.2184v2.pdf .
источник
n=13000
, получат ли первые 2000 инструкций бонус? Кажется бессмысленным, так вы, вероятно, имели в виду что-то еще?n=13000
в течение года, может быть, десяти. Ты собираешься ждать месяцn=2000
? Наверное, нет. И если вы это сделаете , то вы все равно заслуживаете бонуса.Ответы:
Ява, 915 * 0,75 = 686,25
Ввод принимается в качестве аргумента командной строки.
Это пробует почти все возможности (единственное ограничение - первые 8 шагов должны идти только в пределах -1..1), шаг за шагом, используя магическую эвристику вуду, чтобы выбрать, какой способ попробовать первым.
Он решает 2000 и даже 4000 за 1 секунду на моем (довольно быстром) компьютере. Нужно больше оперативной памяти для больших чисел; самый большой ввод, который я решил в пределах 8 ГБ - 5023, и это заняло около 30 секунд
Десятичное представление решения на 2000 шагов, необходимое для бонуса:
Добавьте
Yb
к нему в CJam, чтобы преобразовать обратно в двоичный файл.Об эвристике: во-первых, есть шаблон, который я использую: каждые 9 шагов пытаются повторить первые 9, за исключением того, что каждый (9 * x) -й шаг пытается повторить x-й шаг. Это основано на решении, которое я скачал и использовал (жестко запрограммировал) в своем ответе на python.
Я отслеживаю количество раз, которое я отклонялся от образца, а также количество раз, когда я достигал "края" (1 шаг от смерти). Эвристическая функция - это, в основном, взвешенная комбинация этих двух чисел и количества предпринятых шагов.
Эвристика может быть дополнительно улучшена для улучшения скорости, и есть несколько способов добавить в нее случайный фактор.
На самом деле, я только что прочитал о мультипликативных функциях в связи с этой проблемой, и похоже, что это может обеспечить значительное улучшение (TODO: реализовать это позже).
Развернулся и прокомментировал:
источник
Python 2, 236 байт
Это довольно быстро, для метода грубой силы, он занимает всего несколько секунд для n = 223, но намного дольше для n> = 224.
Объяснение: Отслеживайте список пар строк-списков (s, u), где список u таков, что u [i] является текущей позицией после выполнения каждого i-го шага в строке. Для каждой строки в списке попробуйте добавить «L» или «R», а затем измените значения в списке, которые пересекаются. (т.е. если полученная строка имеет длину 10, добавьте или вычтите 1 из позиций 1,2,5 и 10, в соответствии с направлениями, которые вы переместили). Если вы превысите 3 или -3, выбросьте новую пару, в противном случае оставьте ее в списке. Самые длинные строки сохраняются в конце. Получив строку длины n, верните ее.
источник
//
было доступно в Python 2.Python 2, 729 байт
Я думаю, что это также относится и к бонусу, если идея состоит в том, чтобы «вознаграждать ответы, которые заканчиваются быстро».
Тем не менее, это жестко запрограммированный ответ, который не соответствует духу задачи (хотя он явно не запрещен, когда я его написал).
источник