Niedawno na niedawno wydanym Puzzling.SE pojawił się problem z szpiegami rzucającymi kamieniami w rzekę, co w rzeczywistości było dość trudne:
Dwóch szpiegów musi przekazać sobie dwa tajne numery (jeden numer na szpiega), niezauważone przez swoich wrogów. Uzgodnili metodę zrobienia tego z wykorzystaniem tylko 26 nieodróżnialnych kamieni z góry.
Spotykają się nad rzeką, gdzie znajduje się stos 26 kamieni. Zaczynając od pierwszego szpiega, na zmianę wrzucają do rzeki grupę kamieni: pierwszy szpieg rzuca pewną liczbę kamieni, potem drugi, a potem znowu pierwszy ...
Każdy szpieg musi rzucić co najmniej jeden kamień w swojej turze, dopóki wszystkie kamienie nie znikną.
Obserwują wszystkie rzuty i rozchodzą się, gdy nie ma już kamieni. Przez cały czas milczą i żadne informacje nie są wymieniane, z wyjątkiem liczby kamieni rzucanych na każdym kroku.
Jak mogą z powodzeniem wymieniać liczby, jeśli liczby mogą wynosić od 1 do M?
Twoim zadaniem jest zbudować parę programów spy1
i spy2
, że można rozwiązać ten problem na najwyższy możliwy M
.
Każdy z Twoich programów pobierze numer od 1
wybranego M
jako dane wejściowe. Następnie spy1
wyśle liczbę reprezentującą liczbę kamieni, które rzuci do rzeki, do której zostanie wprowadzony, spy2
a także wyśle liczbę, którą należy wprowadzić spy1
, i tak dalej, aż suma wyniesie liczb 26
. Pod koniec rzucania, każdy program wyświetli liczbę, którą według niego miał inny program, która musi pasować do liczby, która faktycznie została wprowadzona do innego programu.
Twój program powinien działać na wszystkich możliwych zamówionych par liczb (i, j)
, gdzie zarówno i
i j
mogą się różnić od 1
celu M
.
Zwycięzcą będzie program, który działa dla największej M
, a pierwsza odpowiedź zostanie rozstrzygnięta. Dodatkowo przyznam nagrodę za reputację +100 za pierwsze rozwiązanie, dla którego udowodniono działanie M >= 2286
, oraz +300 za pierwsze rozwiązanie, dla którego sprawdzono działanie M >= 2535
.
Odpowiedzi:
C #, M = 2535
To implementuje * system, który opisałem matematycznie w wątku, który wywołał ten konkurs. Odbieram premię za 300 powtórzeń. Program wykonuje automatyczne testy, jeśli uruchomisz go bez argumentów wiersza polecenia lub z
--test
argumentem wiersza polecenia; dla szpiega 1, uruchom z--spy1
, i dla szpiega 2 z--spy2
. W każdym przypadku bierze numer, który powinienem przekazać ze standardowego wejścia, a następnie wykonuje rzuty za pomocą standardowego wejścia i standardowego wejścia.* Właściwie znalazłem optymalizację, która robi ogromną różnicę (od kilku minut do wygenerowania drzewa decyzyjnego, do mniej niż sekundy); drzewo, które generuje, jest zasadniczo takie samo, ale wciąż pracuję nad tego dowodem. Jeśli chcesz bezpośredniej implementacji systemu, który opisałem gdzie indziej, zobacz wersję 2 , chociaż możesz chcieć cofnąć dodatkowe rejestrowanie
Main
i lepsze komunikacje między wątkamiTestSpyIO
.Jeśli chcesz, aby przypadek testowy został ukończony w mniej niż minutę, zmień
N
na16
iM
na87
.Instrukcje dla użytkowników systemu Linux
Będziesz potrzebował
mono-csc
skompilować (w systemach opartych na Debianie, jest wmono-devel
pakiecie) imono
uruchomić (mono-runtime
pakiet). Zatem zaklęcia sąitp.
źródło
yum install mono-core
(jako root). 2.dmcs Puzzle625.cs
3.mono Puzzle625.exe --test
Program testujący w języku Python
Myślę, że przydałby się program testowy, który może sprawdzić, czy twoja implementacja działa. Oba poniższe skrypty działają z Python 2 lub Python 3.
Program testujący (
tester.py
):Protokół: Zostaną uruchomione dwa programy szpiegowskie określone w wierszu polecenia. Oczekuje się, że będą oddziaływać wyłącznie poprzez stdin / stdout. Każdy program otrzyma przypisany numer jako pierwszy wiersz wprowadzania. W każdej turze szpieg 1 podaje liczbę kamieni do rzucenia, szpieg 2 odczytuje liczbę ze standardowego rzutu (reprezentującą rzut szpiega 1), a następnie powtarzają się (z odwróconymi pozycjami). Kiedy któryś szpieg ustali, że 26 kamieni zostało rzuconych, zatrzymuje się i wypuszcza przypuszczenie liczby drugiego szpiega.
Przykładowa sesja ze zgodnym szpiegiem 1 (
>
oznacza dane wejściowe do szpiega)Jeśli wybierzesz bardzo dużą literę M, a jej uruchomienie trwa zbyt długo, możesz przełączyć się
test(
natestrand(
ostatnią linię, aby uruchomić losowe testy. W tym drugim przypadku pozostaw program uruchomiony na co najmniej kilka tysięcy prób, aby zwiększyć zaufanie.Przykładowy program (
spy.py
), dla M = 42:Przykładowe użycie:
źródło
Java, M = 2535
OK, oto moja implementacja. Na każdym kroku jeden szpieg wykonuje ruch. Każdy możliwy ruch reprezentuje zakres kodów. Szpieg wybiera ruch pasujący do jego tajnego kodu. Gdy rzucają więcej kamieni, zakres możliwych kodów zmniejsza się, aż w końcu dla obu szpiegów pozostaje tylko jeden kod, zgodnie z wykonanymi ruchami.
Aby odzyskać tajne kody, możesz odtworzyć wszystkie ruchy i obliczyć odpowiednie zakresy kodów. Na koniec dla każdego szpiega pozostaje tylko jeden kod, czyli tajny kod, który chciał przekazać.
Niestety algorytm opiera się na dużej, wstępnie obliczonej tabeli ze setkami tysięcy liczb całkowitych. Metodę tę nie można zastosować mentalnie w przypadku więcej niż 8-10 kamieni.
Pierwszy plik implementuje algorytm szpiega. Część statyczna
codeCount
oblicza wstępnie tabelę, która jest później używana do obliczania każdego ruchu. Druga część implementuje 2 procedury, jedną do wyboru, ile kamieni należy rzucić, drugą do odtworzenia ruchów, aby pomóc w rekonstrukcji tajnych kodów.Drugi plik intensywnie testuje klasę Spy. Metoda
simulate
symuluje proces. Wykorzystuje klasę Szpieg do generowania sekwencji rzutów z tajnych kodów, a następnie rekonstruuje kody z sekwencji.Spy.java
ThrowingStones.java
W celach informacyjnych wstępnie obliczona tablica codeCount zawiera następujące wartości:
Odnosi się to bezpośrednio do zestawów Tk Petera Taylora. Mamy:
źródło
range
pól. Ale bardzo intryguje mnie twoja metoda obliczania tabeli. Czy masz dowód poprawności? Czy jesteś zainteresowany współpracą na papierze, który omawia problem i oblicza jego rozwiązanie?ksh / zsh, M = 126
W tym prostym systemie każdy szpieg rzuca cyframi binarnymi na drugiego szpiega. W każdym rzucie pierwszy kamień jest ignorowany, każdy kolejny kamień ma bit 0, a ostatni kamień to bit 1. Na przykład, aby rzucić 20, szpieg rzuci 4 kamienie (zignoruj, 0, 2, dodaj 4), następnie rzuć 3 kamieniami (zignoruj, 8, dodaj 16), ponieważ 4 + 16 = 20.
Zbiór liczb nie jest ciągły. Wejścia od 0 do 126, ale 127 nie ma. (Jeśli obaj szpiedzy mają 127, potrzebują 28 kamieni, ale mają 26 kamieni). Następnie 128 do 158 jest w środku, 159 jest w środku, 160 do 174 jest w środku, 175 jest w środku, 176 do 182 jest w środku, 183 jest w środku, 184 do 186 jest włączony, 187 jest wyłączony i tak dalej.
Uruchom automatyczną wymianę za pomocą
ksh spy.sh 125 126
lub uruchom pojedynczych szpiegów za pomocąksh spy.sh spy1 125
iksh spy.sh spy2 126
. Tutajksh
może być ksh93, pdksh lub zsh.EDYCJA 14 czerwca 2014: Napraw problem z niektórymi koprocesami w zsh. Będą bezczynne na zawsze i nie wyjdą, dopóki użytkownik ich nie zabije.
źródło