Una cerradura de combinación ordinaria de N dígitos consta de N discos giratorios. Cada disco tiene dígitos 0-9 inscritos en orden, y debe convertirlos a la contraseña correcta para abrirlo. Obviamente, si no conoce la contraseña, deberá intentarlo como máximo 10 ^N veces antes de desbloquearla. Eso no es interesante.

Así que consideremos una variante del bloqueo de combinación, llámelo bloqueo que revela la distancia.

En cada intento fallido de abrir una cerradura que revela la distancia, responderá la cantidad mínima de movimientos para desbloquear.

Un movimiento se define como una rotación de una posición, por ejemplo, necesita 1 movimiento de 890a 899y 9 movimientos de 137a 952.

El reto

Dado un bloqueo que revela la distancia con su contraseña desconocida, intente abrir el bloqueo con un número mínimo de intentos (no movimientos), mientras evita que el programa se alargue demasiado.

Reglas y calificaciones

• Debe escribir un programa completo que ingrese desde stdin y salga a stdout. El programa debe hacer entrada / salida de la siguiente manera:

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

• Su programa debe manejar hasta N = 200, y debe ejecutar menos de 5 segundos en cualquier entrada.

• Los ceros a la izquierda en la salida no deben omitirse.

• Hay 5 datos de prueba para cada longitud, por lo que el número total de datos de prueba es 1000. Los datos de prueba se generan aleatoriamente.

• La puntuación final será (número total de conjeturas en todos los datos de prueba) * ln (longitud del código en bytes + 50). La puntuación más baja gana. (ln es registro natural)

• Marcaré el programa por ti. Si desea saber cómo calificaré su programa, o si desea calificarlo usted mismo, eche un vistazo a las ediciones anteriores en esta publicación .

• Este desafío finalizará el 07/12/2017 a las 14:00 UTC. Publicaré mi solución entonces.

Ejecutando ejemplo

Las líneas que comienzan con >representan la entrada y otras representan la salida del programa.

Puede tener una contraseña en mente e interactuar con su programa para probarla.

> 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 muestra

EDITAR: Tal vez el formato de entrada / salida anterior no estaba claro. Aquí hay un programa de muestra en Python.

Python, 369 bytes, número total de intentos = 1005973, puntaje = 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

Gracias a Jonás por simplificar el desafío.

C, 388 374 368 bytes, los intentos totales = 162 751, puntuación = 982 280

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, intentos totales = 182255, puntaje = 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;}}}

Esperemos que C # en este formato funcione para usted. Tiene la forma de un programa completo, por lo que debería haber una forma de compilar en un ejecutable. Avíseme si hay algo que pueda hacer para que sea más fácil. Los bytes son parte de la puntuación a pesar de que se eliminó la etiqueta Code Golf, por lo que mi envío oficial elimina todos los espacios en blanco innecesarios y los nombres útiles. Mi explicación a continuación utilizará fragmentos del código no protegido:

Explicación

Este programa usa solo un 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;
        }

Esto escribe la conjetura en stdout, luego lee la distancia desde stdin. También finaliza inmediatamente el programa si una suposición es la combinación exacta. Yo lo llamo mucho. A continuación, la configuración inicial:

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

Esto obtiene la duración de la combinación, luego comienza a adivinar con todos los ceros. Luego, itera a través de cada dígito en un forbucle.

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

Para cada dígito, adivina 5, luego decide el siguiente paso en función de cómo cambió la distancia desde la suposición anterior (donde ese dígito era 0).

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

Si la distancia aumentó en 5, entonces 0 fue correcto para esa distancia. Ajuste ese dígito de nuevo a 0. Alterar la distancia registrada manualmente evita una suposición adicional.

case -5:
    break;

Si la distancia disminuyó en 5, entonces 5 es el dígito correcto y pasamos al siguiente dígito inmediatamente.

Después de eso las cosas son complicadas. Usar 5y 0para mis conjeturas iniciales significa que las posibilidades de diferencia restantes son 3, 1, -1, -3con 2 posibilidades para cada una, que necesitan una conjetura adicional para distinguir. Cada uno de estos casos toma una forma similar

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

Algunos de los números cambian, pero esencialmente intentamos una de las dos posibilidades y verificamos si el cambio fue el correcto para ese dígito. Si no fue así, entonces el otro dígito es correcto, así que configuramos ese dígito y luego ajustamos la diferencia manualmente.

Este método significa que debemos requerir, como máximo, 1 conjetura para los 0 iniciales, 2 conjeturas por dígito, y luego 1 conjetura final para asegurar que el último dígito no caiga.

Sin embargo, puede tener errores, funciona hasta donde he comprobado manualmente, pero eso no es garantía. Error encontrado y aplastado gracias a Colera Su

Python 2 y 3: 175 bytes, intentos totales = 1005972, puntaje = 5448445

Este programa requiere ceil (log (n)) * 10 intentos por combinación o cada dígito toma 10 intentos (por lo tanto, 333toma 30 intentos).

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)

Muchas gracias a Colera Su por ayudarme con la funcionalidad de entrada / salida.

Versión de Desafío de Python ( Modificado por OP ).

Escribí una versión del código de bloqueo dentro de Python. Puede seguir adelante y usarlo si está tratando de resolver esto en Python (como yo). Lo siguiente funciona en Python 2 y 3. Tenía mucho más sentido implementar el bloqueo como una clase con la que se puede probar y decidí crear una función de generador para adivinar las 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 (puntaje = 1175356) 258 bytes, intentos totales = 202999, puntaje = 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)

Pruébalo en línea!

Versión stdin-stdout, según lo solicitado por el OP, sin repeticiones. Gracias a Colera Su por arreglar un error inicial. Esta es una versión marginalmente más corta que la de los comentarios.

A continuación, la presentación de TIO para ejecutar un lote de pruebas dentro de 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}

Pruébalo en línea!

Consideremos un vector de ceros como la suposición inicial. Llamemos a V la distancia entre la suposición actual y la solución. Para cada posición solo necesita verificar los cambios en V cuando reemplaza 0 con 5 y con 4. De hecho, las diferencias entre cambiar 0 con 5 se enumeran en mi vector s1. Las diferencias entre cambiar 0 con 4 se enumeran en mi vector s2. Como puede ver, estos dos vectores mapean de manera única los dígitos de la solución.

El número total de pruebas es, por lo tanto, 3 * L 2 * L + 1, donde L es la longitud del código: una comprobación inicial contra todos los ceros, luego dos comprobaciones para cada dígito, una contra 5 y otra contra 4.

La mejora de un factor 3 a un factor 2 se inspiró en la presentación de Kamil Drakari.

El resto del envío de TIO es repetitivo para R. El envío de TIO muestra el tiempo de ejecución y el número total de operaciones para 1000 ejecuciones con L = 1 ... 200, 5 repeticiones para cada valor de L.