Zwykły N-cyfrowy zamek szyfrowy składa się z N obracających się tarcz. Każda płyta ma kolejno wpisane cyfry 0–9, a aby ją otworzyć, należy ustawić odpowiednie hasło. Oczywiście, jeśli nie znasz hasła, musisz spróbować najwyżej 10 ^N razy przed jego odblokowaniem. To nie jest interesujące.

Rozważmy więc wariant zamka szyfrowego, nazwijmy go zamkiem ujawniającym odległość.

Przy każdej nieudanej próbie otwarcia zamka ujawniającego odległość reaguje na minimalną liczbę ruchów do odblokowania.

Jeden ruch jest definiowany jako obrót o jedną pozycję, na przykład wymaga 1 ruchu od 890do 899i 9 ruchów od 137do952 .

Wyzwanie

Biorąc pod uwagę zamek ujawniający odległość z nieznanym hasłem, spróbuj otworzyć zamek przy minimalnej liczbie prób (nie ruchów), jednocześnie zapobiegając zbyt długiemu programowi.

Zasady i wyniki

• Powinieneś napisać pełny program, który wprowadza dane ze stdin i wypisuje na stdout. Program powinien wykonać wejście / wyjście w następujący sposób:

Start
    Input an integer N (number of digits) from stdin
    Do
        Output a line containing decimal string of length N (your attempt) to stdout
        Input an integer K (response of the lock) from stdin
    While K not equal 0
End

• Twój program powinien obsłużyć do N = 200 i powinien działać mniej niż 5 sekund na dowolnym wejściu.

• Zera wiodące w danych wyjściowych nie powinny być pomijane.

• Jest 5 danych testowych dla każdej długości, więc całkowita liczba danych testowych wynosi 1000. Dane testowe są generowane losowo.

• Ostateczny wynik to (całkowita liczba domysłów we wszystkich danych testowych) * ln (długość kodu w bajtach + 50). Najniższy wynik wygrywa. (ln jest logiem naturalnym)

• Zdobędę dla ciebie program. Jeśli chcesz wiedzieć, jak zdobędę punkty w twoim programie lub chcesz go zdobyć samodzielnie, spójrz na poprzednie zmiany w tym poście .

• To wyzwanie zakończy się o godzinie 2017.12.12 14:00 UTC. Wyślę wtedy moje rozwiązanie.

Przykład biegania

Linie zaczynające się od >reprezentują dane wejściowe, a inne reprezentują dane wyjściowe programu.

Możesz mieć hasło w pamięci i wchodzić w interakcje z programem, aby je przetestować.

> 3   # 3-digit lock. The hidden password is 746
000   # 1st guess (by program)
> 11  # response to the 1st guess
555   # 2nd guess
> 4   # ...
755
> 2
735
> 2
744
> 2
746   # finally the correct answer! The program attempts 6 times.
> 0   # this is not necessary

Przykładowy program

EDYCJA: Być może powyższy format wejścia / wyjścia nie był jasny. Oto przykładowy program w Pythonie.

Python, 369 bajtów, łączna liczba prób = 1005973, wynik = 6073935

import sys

N = int(input()) # get the lock size

ans = ''
for i in range(N): # for each digit
    lst = []
    for j in range(10): # try all numbers
        print('0' * i + str(j) + '0' * (N - i - 1)) # make a guess
        result = int(input()) # receive the response
        lst.append(result)
    ans += str(lst.index(min(lst)))
print(ans) # output the final answer

Dzięki Jonaszowi za uproszczenie wyzwania.

C, 388 374 368 bajtów, łączna liczba prób = 162751, wynik = 982280

char s[999];i;G;H;t;n;h;e;R(x){scanf("%d",x);}W(i,x,a){printf((i-n?0:4)+"%0*d%0*d\n",i,x,n-i,0);R(a);}S(k,i){if(!(t=e=k>4?s[i]=48:k<1?s[i]=53:!G?H=k,G=i:0)){for(;t++<n;)putchar(48|t==i|t==G);puts("");R(&t);t==h?W(G,e=1,&t):0;s[G]=t>h?53+H:53-H,s[i]=t>h^e?53+k:53-k;G=0;}}main(){R(&n);for(W(n,0,&h);i++<n;S(t-h+5>>1,i))W(i,5,&t);s[G]=53+H,puts(s+1),s[G]=53-H,puts(s+1);}

C # (.NET Core) , 617 bajtów, łączna liczba prób = 182255, wynik = 1185166

using System;namespace p{class C{static void Main(){var l=Console.ReadLine();int L=int.Parse(l);var g=new int[L];var p=n(g);for(int i=0;i<L;i++){g[i]=5;var d=n(g);var f=d-p;var s=f;switch(s){case 5:g[i]=0;d-=5;break;case-5:break;case 3:g[i]=1;d=n(g);f=d-p;if(f>0){g[i]=9;d-=2;}break;case 1:g[i]=2;d=n(g);f=d-p;if(f>0){g[i]=8;d-=4;}break;case-1:g[i]=3;d=n(g);f=d-p;if(f>0){g[i]=7;d-=4;}break;case-3:g[i]=4;d=n(g);f=d-p;if(f>-3){g[i]=6;d-=2;}break;}p=d;}n(g);}static int n(int[] g){foreach(var i in g){Console.Write(i);}Console.WriteLine();var s=Console.ReadLine();var d=int.Parse(s);if(d<1) Environment.Exit(0);return d;}}}

Mam nadzieję, że C # w tym formacie działa dla Ciebie. Ma postać kompletnego programu, więc powinien istnieć sposób na kompilację do pliku wykonywalnego. Daj mi znać, jeśli mogę coś zrobić, aby to ułatwić. Bajty są częścią punktacji, mimo że tag Code Golf został usunięty, więc moje oficjalne zgłoszenie usuwa wszystkie niepotrzebne białe znaki i przydatne nazwy. Moje wyjaśnienie poniżej użyje fragmentów niepoznanego kodu:

Wyjaśnienie

Ten program używa tylko jednej metody pomocniczej:

static int newGuess(IEnumerable<int> guess)
        {
            foreach (var item in guess)
            {
                Console.Write(item);
            }
            Console.WriteLine();
            var distanceString = Console.ReadLine();
            var distance = int.Parse(distanceString);
            if (distance < 1) System.Environment.Exit(0);
            return distance;
        }

Spowoduje to zapisanie domysły na stdout, a następnie odczyta odległość od stdin. Również natychmiast kończy program, jeśli zgadnięcie jest dokładną kombinacją. Często to nazywam. Następnie wstępna konfiguracja:

var lengthString = Console.ReadLine();
int length = int.Parse(l);
var guess = new int[length];
var prevDistance = newGuess(guess);

Pobiera długość kombinacji, a następnie rozpoczyna zgadywanie ze wszystkimi zerami. Następnie iteruje każdą cyfrę w forpętli.

guess[i] = 5;
var distance = newGuess(guess);
var difference = distance - prevDistance;
var switchVar = difference;
switch (switchVar)

Dla każdej cyfry zgaduje 5, a następnie decyduje o kolejnym kroku na podstawie zmiany odległości od poprzedniej domysły (gdzie ta cyfra wynosiła 0).

case 5:
    guess[i] = 0;
    distance -= 5;
    break;

Jeśli odległość wzrosła o 5, wówczas 0 było prawidłowe dla tej odległości. Dostosuj tę cyfrę z powrotem do 0. Ręczna zmiana zarejestrowanej odległości zapobiega dodatkowemu zgadywaniu.

case -5:
    break;

Jeśli odległość zmniejszyła się o 5, wówczas 5 jest poprawną cyfrą i natychmiast przechodzimy do następnej cyfry.

Po tym wszystko jest trudne. Użycie 5i 0dla moich początkowych domysłów oznacza, że ​​pozostałe możliwości różnic są 3, 1, -1, -3z 2 możliwościami dla każdej, które wymagają 1 dodatkowego odgadnięcia, aby rozróżnić. Każdy z tych przypadków ma podobną formę

case 3:
    guess[i] = 1;
    distance = newGuess(guess);
    difference = distance - prevDistance;
    if (difference > 0)
    {
        guess[i] = 9;
        distance -= 2;
    }

Niektóre liczby się zmieniają, ale zasadniczo wypróbowujemy jedną z dwóch możliwości i sprawdzamy, czy zmiana była poprawna dla tej cyfry. Jeśli tak nie było, to druga cyfra jest poprawna, więc ustawiamy tę cyfrę, a następnie dostosowujemy różnicę ręcznie.

Ta metoda oznacza, że ​​powinniśmy wymagać maksymalnie 1 zgadywania dla początkowych zer, 2 zgadnięć na cyfrę, a następnie 1 zgadywania końcowego, aby upewnić się, że ostatnia cyfra nie spadnie.

Może to być wadliwe, działa, o ile sprawdziłem ręcznie, ale to nie jest gwarancja. Błąd znaleziony i zgnieciony dzięki Colera Su

Python 2 i 3: 175 bajtów, łączna liczba prób = 1005972, wynik = 5448445

Ten program wymaga pułapu (log (n)) * 10 prób na kombinację lub każda cyfra wymaga 10 prób (czyli 33330 prób).

N=int(input());o=0
def c(a):
 print("0"*(N-len(str(a)))+str(a))
 return int(input())
for j in range(N):m={c(i):i for i in reversed(range(0,10**(j+1),10**j))};o+=m[min(m)]
c(o)

Ogromne podziękowania dla Colera Su za pomoc w zakresie funkcji wejścia / wyjścia.

Wersja Python Challenge ( zmodyfikowana przez OP ).

Napisałem wersję kodu blokady w Pythonie. Możesz przejść dalej i użyć, jeśli próbujesz rozwiązać ten problem w Pythonie (tak jak ja). Poniższe działa w Pythonie 2 i 3. Bardziej sensownym było zaimplementowanie blokady jako klasy, na której można testować, i postanowiłem stworzyć funkcję generatora do odgadywania danych wejściowych.

import sys

class Lock:
    def __init__(self, number):
        self.lock = str(number)
    def l(self): #lengthOfNumber
        return len(self.lock)
    def c(self, guess): #check a guess
        guess = str(guess)
        guess = "0" * (len(self.lock) - len(guess)) + guess
        difference = 0
        for i in range(len(self.lock)):
            d1 = abs(int(self.lock[i]) - int(guess[i]))
            d2 = 10 - d1
            difference += d1 if d1 < d2 else d2
        return difference

def masterLock():
    testdata = ["000","555","755","735","744","746"]
    for answer in testdata:
        yield Lock(answer)

class LockIO:
    def __init__(self):
        self.lock = int(input())
    def l(self):
        return self.lock
    def c(self, guess):
        guess = str(guess)
        guess = "0" * (self.lock - len(guess)) + guess
        print(guess)
        sys.stdout.flush()
        return int(input())

for l in masterLock():
    # Write your code here that tries to guess it
    #   When you're done testing you can unindent your code,
    #   replace "for l in masterLock():" with "l = LockIO()"
    #   and submit the code.
    # 
    # Examples:
    #  l.l()      # returns the length of the lock
    #  l.c("952") # returns the distance to the lock
    #  l.c(952)   #  number also works
    pass

R , 277 bajtów (wynik = 1175356) 258 bajtów, łączna liczba prób = 202999, wynik = 1163205

f=file("stdin","r")
w=function(b=1,A=X){cat(A,"\n",sep="");if(b){b=scan(f,n=1)};b}
M=0:9
s1=c(-5,-3,-1,1,3,5,3,1,-1,-3)
s2=s1+rep(c(1,-1),,,5)
L=w(1,"")
X=S=rep(0,L)
v0=w()
for(i in 1:L){X[i]=5
v1=v0-w()
X[i]=4
v2=v0-w()
S[i]=M[s1==v1&s2==v2]
X=0*S}
b=w(0,S)

Wypróbuj online!

Wersja stdin-stdout, zgodnie z żądaniem OP, bez płyt grzewczych. Dzięki Colera Su za naprawienie początkowego błędu. To jest nieco krótsza wersja niż ta w komentarzach.

Poniżej przedłożenie TIO w celu przeprowadzenia serii testów w TIO

R 189 bajtów

M=0:9
s1=c(-5,-3,-1,1,3,5,3,1,-1,-3)
s2=c(-4,-2,0,2,4,4,2,0,-2,-4)
f=function(L){S=rep(0,L)
v0=v(S)
X=S
for(i in c(1:L)){X[i]=5
v1=v0-v(X)
X[i]=4
v2=v0-v(X)
S[i]=M[s1==v1&s2==v2]
X[i]=0}
S}

Wypróbuj online!

Rozważmy wektor zer jako wstępne zgadywanie. Nazwijmy V odległość między bieżącą zgadywanką a rozwiązaniem. Dla każdej pozycji musisz tylko sprawdzić zmiany w V, gdy zamienisz 0 na 5 i na 4. W rzeczywistości różnice między zmianą 0 na 5 są wymienione w moim wektorze s1. Różnice między zmianą 0 na 4 są wymienione w moim wektorze s2. Jak widać, te dwa wektory jednoznacznie odwzorowują cyfry rozwiązania.

Łączna liczba testów wynosi zatem 3 * L 2 * L + 1, gdzie L jest długością kodu: wstępne sprawdzenie wszystkich zer, następnie dwa sprawdzenia każdej cyfry, jeden przeciwko 5 i jeden przeciwko 4.

Ulepszenie z czynnika 3 do czynnika 2 zostało zainspirowane poddaniem się Kamila Drakariego.

Reszta przedłożenia TIO jest płytą kotłową dla R. Przedłożenie TIO pokazuje czas działania i całkowitą liczbę operacji dla 1000 przebiegów z L = 1 ... 200, 5 powtórzeń dla każdej wartości L.