Kunci kombinasi N-digit biasa terdiri dari N disc yang berputar. Setiap disk memiliki angka 0-9 yang ditulis secara berurutan, dan Anda perlu mengubahnya ke kata sandi yang benar untuk membukanya. Tentunya, jika Anda tidak tahu kata sandinya, Anda harus mencoba paling banyak 10 ^N kali sebelum membukanya. Itu tidak menarik.

Jadi mari kita pertimbangkan varian kunci kombinasi, beri nama kunci pengungkap jarak.

Dalam setiap upaya yang gagal untuk membuka kunci pengungkapan jarak, itu akan merespon jumlah minimum gerakan untuk membuka kunci.

Satu gerakan didefinisikan sebagai rotasi oleh satu posisi, misalnya diperlukan 1 gerakan dari 890ke 899, dan 9 gerakan dari 137ke 952.

Tantangan

Mengingat kunci pengungkap jarak dengan kata sandi tidak dikenal, coba buka kunci dengan jumlah upaya minimal (bukan gerakan), sambil menjaga program agar tidak terlalu lama.

Aturan & Penilaian

• Anda harus menulis program lengkap yang input dari stdin dan output ke stdout. Program harus melakukan input / output sebagai berikut:

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

• Program Anda harus menangani hingga N = 200, dan harus berjalan kurang dari 5 detik pada input apa pun.

• Nol terdepan dalam output tidak boleh diabaikan.

• Ini adalah 5 testdata untuk setiap panjang, sehingga jumlah total testdata adalah 1000. Testdata dihasilkan secara acak.

• Skor akhir akan menjadi (jumlah total tebakan di semua testdata) * ln (panjang kode dalam byte + 50). Skor terendah menang. (Dalam log alami)

• Saya akan mencetak skor program untuk Anda. Jika Anda ingin tahu bagaimana saya akan menilai program Anda, atau Anda ingin membuat skor sendiri, lihat suntingan sebelumnya pada posting ini .

• Tantangan ini akan berakhir pada 2017/12/07 14:00 UTC. Saya akan memposting solusi saya kemudian.

Contoh Menjalankan

Baris dimulai dengan >mewakili input, dan lainnya mewakili output program.

Anda dapat memiliki kata sandi di pikiran Anda dan berinteraksi dengan program Anda untuk mengujinya.

> 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

Program Sampel

EDIT: Mungkin format input / output di atas tidak jelas. Berikut ini contoh program dengan Python.

Python, 369 byte, jumlah upaya = 1005973, skor = 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

Terima kasih kepada Jonah karena menyederhanakan tantangan.

C, 388 374 368 byte, total upaya = 162751, skor = 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 byte, upaya total = 182255, skor = 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;}}}

Semoga C # dalam format ini berfungsi untuk Anda. Itu dalam bentuk program yang lengkap, jadi harus ada cara untuk dikompilasi ke executable. Beri tahu saya jika ada yang bisa saya lakukan untuk membuatnya lebih mudah. Bytes adalah bagian dari penilaian meskipun tag Golf Code dihapus sehingga kiriman resmi saya menghapus semua spasi kosong yang tidak dibutuhkan dan nama-nama berguna. Penjelasan saya di bawah ini akan menggunakan bagian-bagian dari kode yang tidak dikenali:

Penjelasan

Program ini hanya menggunakan metode pembantu tunggal:

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;
        }

Ini menulis tebakan ke stdout, kemudian membaca jarak dari stdin. Ini juga segera mengakhiri program jika tebakan adalah kombinasi yang tepat. Saya sering menyebutnya. Selanjutnya pengaturan awal:

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

Ini mendapatkan panjang kombinasi, lalu mulai menebak dengan semua 0s. Setelah itu, iterates melalui setiap digit dalam satu forlingkaran.

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

Untuk setiap digit, tebakan 5, lalu putuskan pada langkah berikutnya berdasarkan bagaimana jarak berubah sejak tebakan sebelumnya (di mana angka itu 0).

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

Jika jarak bertambah 5, maka 0 benar untuk jarak itu. Sesuaikan angka itu kembali ke 0. Mengubah jarak yang direkam secara manual mencegah tebakan tambahan.

case -5:
    break;

Jika jarak menurun 5, maka 5 adalah digit yang benar dan kami segera pindah ke digit berikutnya.

Setelah itu semuanya rumit. Menggunakan 5dan 0untuk tebakan awal saya berarti bahwa kemungkinan perbedaan yang tersisa adalah 3, 1, -1, -3dengan 2 kemungkinan untuk masing-masing, yang membutuhkan 1 tebakan tambahan untuk membedakan. Masing-masing kasus ini mengambil bentuk yang serupa

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

Beberapa angka berubah, tetapi pada dasarnya kami mencoba salah satu dari dua kemungkinan, dan memeriksa apakah perubahan itu yang benar untuk angka itu. Jika tidak, maka digit lainnya sudah benar sehingga kami mengatur digit itu lalu menyesuaikan perbedaannya secara manual.

Metode ini berarti kita harus mensyaratkan, paling banyak, 1 tebakan untuk 0s awal, 2 tebakan per digit, dan kemudian 1 tebakan akhir untuk memastikan digit terakhir tidak jatuh.

Mungkin buggy, itu berfungsi sejauh saya sudah memeriksa secara manual tapi itu bukan jaminan. Bug ditemukan dan tergencet berkat Colera Su

Python 2 dan 3: 175 byte, total upaya = 1005972, skor = 5448445

Program ini membutuhkan ceil (log (n)) * 10 upaya per kombinasi atau setiap digit membutuhkan 10 upaya (jadi, 333dibutuhkan 30 upaya).

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)

Terima kasih banyak kepada Colera Su karena telah membantu saya dengan fungsionalitas input / output.

Versi Python dari Tantangan ( Dimodifikasi oleh OP ).

Saya menulis versi kode kunci di dalam Python. Anda dapat melanjutkan dan menggunakan jika Anda mencoba menyelesaikan ini dengan Python (seperti saya). Berikut ini berfungsi dalam Python 2 dan 3. Itu membuat lebih masuk akal hanya untuk menerapkan kunci sebagai kelas Anda dapat menguji dan saya memutuskan untuk membuat fungsi generator untuk menebak input.

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 byte (skor = 1175356) 258 byte, upaya total = 202999, skor = 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)

Cobalah online!

Versi stdin-stdout, seperti yang diminta oleh OP, tanpa pelat ketel. Terima kasih kepada Colera Su karena telah memperbaiki bug awal. Ini adalah versi yang sedikit lebih pendek daripada yang ada di komentar.

Di sini, di bawah pengajuan TIO untuk menjalankan serangkaian tes dalam TIO

R , 189 byte

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}

Cobalah online!

Mari kita pertimbangkan vektor nol sebagai tebakan awal. Mari kita sebut V jarak antara perkiraan saat ini dan solusinya. Untuk setiap posisi Anda hanya perlu memeriksa perubahan dalam V ketika Anda mengganti 0 dengan 5 dan dengan 4. Bahkan, perbedaan antara mengubah 0 dengan 5 tercantum dalam vektor s1 saya. Perbedaan antara mengubah 0 dengan 4 tercantum dalam vektor s2 saya. Seperti yang Anda lihat, kedua vektor ini secara unik memetakan digit solusi.

Dengan demikian, total jumlah tes adalah 3 * L 2 * L + 1, di mana L adalah panjang kode: pemeriksaan awal terhadap semua nol, lalu dua pemeriksaan untuk setiap digit, satu terhadap 5 dan satu terhadap 4.

Peningkatan dari faktor 3 ke faktor 2 terinspirasi oleh pengajuan Kamil Drakari.

Sisa dari pengajuan TIO adalah boilerplate untuk R. Pengajuan TIO menunjukkan waktu berjalan dan jumlah total operasi untuk 1000 berjalan dengan L = 1 ... 200, 5 ulangan untuk setiap nilai L.