Um bloqueio comum de combinação de dígitos N consiste em N discos rotativos. Cada disco tem dígitos de 0 a 9 inscritos em ordem e é necessário transformá-los na senha correta para abri-lo. Obviamente, se você não souber a senha, precisará tentar no máximo 10 ^N vezes antes de desbloqueá-la. Isso não é interessante.

Então, vamos considerar uma variante do bloqueio de combinação, nomeá-lo como bloqueio revelador de distância.

Em todas as tentativas frustradas de abrir um bloqueio revelador de distância, ele responderá ao número mínimo de movimentos a serem desbloqueados.

Um movimento é definido como uma rotação por uma posição; por exemplo, ele precisa de 1 movimento de 890para 899e 9 movimentos de 137para 952.

O desafio

Dado um bloqueio revelador de distância com sua senha desconhecida, tente abri-lo com um número mínimo de tentativas (não movimentos), mantendo o programa muito longo.

Regras e Pontuações

• Você deve escrever um programa completo com entradas de stdin e saídas para stdout. O programa deve fazer entrada / saída da seguinte maneira:

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

• Seu programa deve processar até N = 200 e deve executar menos de 5 segundos em qualquer entrada.

• Zeros à esquerda na saída não devem ser omitidos.

• São 5 dados de teste para cada comprimento, portanto, o número total de dados de teste é 1000. Os dados de teste são gerados aleatoriamente.

• A pontuação final será (número total de tentativas em todos os dados do teste) * ln (comprimento do código em bytes + 50). Menor pontuação ganha. (ln é log natural)

• Vou marcar o programa para você. Se você deseja saber como eu classificarei seu programa, ou se você deseja classificá-lo, verifique as edições anteriores deste post .

• Este desafio será encerrado em 07/12/2017 às 14:00 UTC. Vou postar minha solução então.

Exemplo de execução

Linhas começando com >representam entrada e outras representam saída do programa.

Você pode ter uma senha em mente e interagir com seu programa para testá-la.

> 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

Programa de amostra

EDIT: Talvez o formato de entrada / saída acima não esteja claro. Aqui está um exemplo de programa em Python.

Python, 369 bytes, número total de tentativas = 1005973, pontuação = 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

Agradecemos a Jonah por simplificar o desafio.

C, 388 374 368 bytes, total de tentativas = 162751, pontuação = 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 bytes, total de tentativas = 182255, pontuação = 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;}}}

Espero que o C # nesse formato funcione para você. É na forma de um programa completo, portanto, deve haver uma maneira de compilar em um executável. Deixe-me saber se há algo que eu possa fazer para facilitar. Os bytes fazem parte da pontuação, mesmo que a tag Code Golf tenha sido removida. Portanto, meu envio oficial remove todo o espaço em branco desnecessário e nomes úteis. Minha explicação abaixo usará fragmentos do código não destruído:

Explicação

Este programa usa apenas um único método auxiliar:

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

Isso escreve o palpite para stdout e depois lê a distância de stdin. Ele também encerra imediatamente o programa se um palpite é a combinação exata. Eu chamo muito isso. Em seguida, a configuração inicial:

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

Isso obtém o comprimento da combinação e começa a adivinhar com todos os 0s. Depois, itera através de cada dígito em um forloop.

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

Para cada dígito, ele adivinha 5, e decide o próximo passo com base em como a distância mudou desde a estimativa anterior (onde esse dígito era 0).

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

Se a distância aumentasse em 5, 0 estava correto para essa distância. Ajuste esse dígito de volta para 0. Alterar a distância gravada manualmente evita um palpite extra.

case -5:
    break;

Se a distância diminuiu em 5, 5 é o dígito correto e passamos para o próximo dígito imediatamente.

Depois disso, as coisas são complicadas. Usar 5e 0para minhas suposições iniciais significa que as possibilidades de diferença restantes estão 3, 1, -1, -3com 2 possibilidades para cada uma, as quais precisam de um palpite adicional para distinguir. Cada um desses casos assume uma forma semelhante

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

Alguns dos números mudam, mas essencialmente tentamos uma das duas possibilidades e verificamos se a alteração foi a correta para esse dígito. Caso contrário, o outro dígito está correto, portanto, definimos esse dígito e ajustamos a diferença manualmente.

Esse método significa que devemos exigir, no máximo, 1 palpite para os 0s iniciais, 2 palpites por dígito e, em seguida, 1 palpite final para garantir que o último dígito não caia.

Pode ser um bug, porém, funciona até onde eu verifiquei manualmente, mas isso não é garantia. Bug encontrado e esmagado graças a Colera Su

Python 2 e 3: 175 bytes, total de tentativas = 1005972, pontuação = 5448445

Este programa leva o teto (log (n)) * 10 tentativas por combinação ou cada dígito leva 10 tentativas (portanto, 333leva 30 tentativas).

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)

Muito obrigado a Colera Su por me ajudar com a funcionalidade de entrada / saída.

Versão Python do Desafio ( Modificado pelo OP ).

Eu escrevi uma versão do código de bloqueio dentro do Python. Você pode prosseguir e usar se estiver tentando resolver isso em Python (como eu). O seguinte funciona no Python 2 e 3. Fazia muito mais sentido implementar o bloqueio como uma classe com a qual você pode testar e eu decidi criar uma função geradora para adivinhar as entradas.

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 bytes (pontuação = 1175356) 258 bytes, total de tentativas = 202999, pontuação = 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)

Experimente online!

A versão Stdin-stdout, conforme solicitado pelo OP, não possui clichês. Agradecemos a Colera Su por corrigir um erro inicial. Esta é uma versão ligeiramente mais curta que a dos comentários.

Aqui abaixo do envio do TIO para executar um lote de testes no TIO

R , 189 bytes

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}

Experimente online!

Vamos considerar um vetor de zeros como o palpite inicial. Vamos chamar de V a distância entre o palpite atual e a solução. Para cada posição, você só precisa verificar as alterações em V ao substituir 0 por 5 e por 4. De fato, as diferenças entre alterar 0 e 5 estão listadas no meu vetor s1. As diferenças entre alterar 0 e 4 estão listadas no meu vetor s2. Como você vê esses dois vetores, mapeie exclusivamente os dígitos da solução.

O número total de testes é, portanto, 3 * L 2 * L + 1, onde L é o comprimento do código: uma verificação inicial contra todos os zeros, depois duas verificações para cada dígito, uma contra 5 e uma contra 4.

A melhoria de um fator 3 para um fator 2 foi inspirada na submissão de Kamil Drakari.

O restante do envio do TIO é padrão para R. O envio do TIO mostra o tempo de execução e o número total de operações para 1000 execuções com L = 1 ... 200, 5 repetições para cada valor de L.