Недавно на недавно выпущенном Puzzling.SE была проблема с шпионами, бросающими камни в реку, что было довольно сложно:
Два шпиона должны передать друг другу два секретных номера (по одному на шпиона), незаметно для их врагов. Они заранее договорились о методе для этого, используя только 26 неразличимых камней.
Они встречаются у реки, где есть груда из 26 камней. Начиная с первого шпиона, они по очереди бросают в реку группу камней: первый шпион бросает некоторое количество камней, затем второй, затем снова первый ...
Каждый шпион должен бросить хотя бы один камень на своем ходу, пока все камни не исчезнут.
Они наблюдают все броски и расходятся, когда камней больше нет. Они все время молчат, и никакой информации не обменивается, кроме количества камней, брошенных за каждый ход.
Как они могут успешно обменять числа, если числа могут быть от 1 до M?
Ваша задача состоит в том, чтобы построить пару программ, spy1
и spy2
, которые могут решить эту проблему максимально возможным M
.
Каждая из ваших программ будет принимать число от 1
выбранного вами в M
качестве входных данных. Затем spy1
будет выведено число, представляющее количество камней, которые он выбрасывает в реку, которое будет входить в spy2
которое также будет выводить число для ввода spy1
, и так далее, пока количество выводимых сумм не сложится 26
. В конце броска каждая программа выведет число, которое, как она считает, имела другая программа, которое должно совпадать с числом, которое фактически было введено другой программе.
Ваша программа должна работать для всех возможных упорядоченных пар чисел, (i, j)
где оба i
и j
могут варьироваться от 1
до M
.
Программа, которая работает для крупнейшего, M
станет победителем, а первый ответ будет опубликован с разрывом связи. Кроме того, я присуждаю +100 репутации за первое решение, на которое доказано, что оно работает M >= 2286
, и +300 за первое решение, на которое доказано, что оно работает M >= 2535
.
Ответы:
C #, M = 2535
Это реализует * систему, которую я математически описал в теме, которая спровоцировала этот конкурс. Я требую 300 повторений бонуса. Программа самопроверяется, если вы запускаете ее без аргументов командной строки или с аргументом
--test
командной строки; для шпиона 1 - с--spy1
, а для шпиона 2 - с--spy2
. В каждом случае он принимает число, которое я должен сообщить от stdin, а затем выполняет броски через stdin и stdout.* На самом деле, я нашел оптимизацию, которая имеет огромное значение (от нескольких минут до генерации дерева решений до менее секунды); дерево, которое оно генерирует, в основном то же самое, но я все еще работаю над доказательством этого. Если вам нужна прямая реализация системы, которую я описал в другом месте, см. Редакцию 2 , хотя вы можете сделать бэкпорт для дополнительной регистрации
Main
и лучшего обмена между потокамиTestSpyIO
.Если вам нужен тестовый пример, который завершается менее чем за минуту, измените
N
на16
иM
на87
.Инструкции для пользователей Linux
Вам нужно
mono-csc
будет скомпилировать (в системах на основе Debian он находится вmono-devel
пакете) иmono
запустить (mono-runtime
пакет). Тогда заклинанияи т.п.
источник
yum install mono-core
(с правами root). 2.dmcs Puzzle625.cs
3.mono Puzzle625.exe --test
Программа Python Tester
Я полагаю, было бы полезно иметь тестовую программу, которая может проверить, работает ли ваша реализация. Оба скрипта ниже работают с Python 2 или Python 3.
Программа тестирования (
tester.py
):Протокол: две шпионские программы, указанные в командной строке, будут выполнены. Ожидается, что они будут взаимодействовать исключительно через stdin / stdout. Каждая программа получит свой присвоенный номер в качестве первой строки ввода. В каждом ходу шпион 1 выводит количество брошенных камней, шпион 2 читает число из стандартного ввода (представляющее бросок шпиона 1), а затем они повторяются (с перевернутыми позициями). Когда один из шпионов определяет, что было брошено 26 камней, он останавливается и выдает свои предположения относительно номера другого шпиона.
Пример сеанса с совместимым шпионом 1 (
>
обозначает вход для шпиона)Если вы выберете очень большое значение M, и его запуск займет слишком много времени, вы можете переключиться
test(
наtestrand(
последнюю строку для запуска случайных тестов. В последнем случае оставьте программу работающей как минимум на несколько тысяч попыток, чтобы укрепить доверие.Пример программы (
spy.py
), для М = 42:Пример использования:
источник
Ява, М = 2535
Хорошо, вот моя реализация. На каждом шаге один шпион делает ход. Каждый возможный ход представляет диапазон кодов. Шпион выбирает ход, соответствующий его секретному коду. По мере того как они бросают больше камней, диапазон возможных кодов уменьшается до тех пор, пока в конце для обоих шпионов не останется возможным только один код в соответствии с ходами, которые они сделали.
Чтобы восстановить секретные коды, вы можете воспроизвести все ходы и вычислить соответствующие диапазоны кодов. В конце для каждого шпиона остается только один код, то есть секретный код, который он хотел передать.
К сожалению, алгоритм основан на большой предварительно вычисленной таблице с сотнями тысяч целых чисел. Метод не может быть применен мысленно с более чем 8-10 камнями возможно.
Первый файл реализует алгоритм шпиона. Статическая часть предварительно вычисляет
codeCount
таблицу, которая позже используется для вычисления каждого движения. Во второй части реализованы 2 процедуры: одна для выбора количества брошенных камней, другая для воспроизведения ходов, чтобы помочь восстановить секретные коды.Второй файл тщательно тестирует класс Spy. Метод
simulate
имитирует процесс. Он использует класс Spy для генерации последовательности бросков из секретных кодов, а затем восстанавливает коды из последовательности.Spy.java
ThrowingStones.java
Для справки, предварительно вычисленный массив codeCount содержит следующие значения:
Это напрямую связано с наборами Питера Тейлора. У нас есть:
источник
range
полям. Но я очень заинтригован вашим методом расчета таблицы. У вас есть доказательства правильности? И вы заинтересованы в совместной работе над документом, в котором обсуждается проблема и рассчитывается ее решение?кш / зш, М = 126
В этой простой системе каждый шпион бросает двоичные цифры другому шпиону. В каждом броске первый камень игнорируется, следующие камни - каждый бит 0, а последний камень - бит 1. Например, чтобы бросить 20, шпион бросил бы 4 камня (игнорировать 0, 2, добавить 4), затем бросьте 3 камня (игнорируйте, 8, добавьте 16), потому что 4 + 16 = 20.
Набор чисел не является смежным. 0 до 126, но 127 нет. (Если у обоих шпионов 127, им нужно 28 камней, но у них есть 26 камней.) Затем 128–158 входят, 159 нет, 160–174 находятся, 175 нет, 176–182 находятся, 183 нет, 184 - 186, 187 - и так далее.
Запустите автоматический обмен
ksh spy.sh 125 126
или запустите отдельных шпионов с помощьюksh spy.sh spy1 125
иksh spy.sh spy2 126
. Здесьksh
может быть ksh93, pdksh или zsh.РЕДАКТИРОВАТЬ 14 июня 2014: исправить проблему с некоторыми процессами в Zsh. Они будут бездействовать вечно и не смогут выйти, пока пользователь их не убьет.
источник