Find the password

Question

An ordinary N-digit combination lock consists of N rotating discs. Each disc has digits 0-9 inscribed in order, and you need to turn them to the correct password to open it. Obviously, if you don't know the password, you will need to try at most 10^N times before unlocking it. That's not interesting.

So let's consider a variant of combination lock, name it distance-revealing lock.

In every unsuccessful attempt to open an distance-revealing lock, it will respond the minimum number of movements to unlock.

One movement is defined as a rotation by one position, for example it needs 1 movement from 890 to 899, and 9 movements from 137 to 952.

The Challenge

Given a distance-revealing lock with its password unknown, try to open the lock with a minimal number of attempts (not movements), while keeping the program from getting too long.

Rules & Scorings

• You should write a full program which inputs from stdin and outputs to stdout. The program should do input/output as following:

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

• Your program should handle up to N = 200, and should run less than 5 seconds on any input.

• Leading zeros in output shouldn't be omitted.

• The are 5 testdata for every length, so the total number of testdata is 1000. The testdata are randomly generated.

• The final score will be (total number of guesses in all testdata) * ln(code length in bytes + 50). Lowest score wins. (ln is natural log)

• I will score the program for you. If you want to know how I will score your program, or you want to score it by yourselves, take a look at previous edits on this post.

• This challenge will end at 2017/12/07 14:00 UTC. I will post my solution then.

Running Example

Lines starting with > represent input, and others represent program output.

You can have a password in your mind and interact with your program to test it.

> 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

Sample Program

EDIT: Maybe the input/output format above was not clear. Here's a sample program in Python.

Python, 369 bytes, total number of attempts = 1005973, score = 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

Thanks to Jonah for simplifying the challenge.

Answer 1

C, 388 374 368 bytes, total attempts = 162751, score = 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);}

Answer 2

C# (.NET Core), 617 bytes, total attempts = 182255, score = 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;}}}

Hopefully C# in this format works for you. It is in the form of a complete program, so there should be a way to compile to an executable. Let me know if there's anything I can do to make it easier. Bytes are part of the scoring even though the Code Golf tag is removed so my official submission removes all the unneeded whitespace and useful names. My explanation below will use fragments of the ungolfed code:

Explanation

This program uses only a single helper method:

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

This writes the guess to stdout, then reads the distance from stdin. It also immediately ends the program if a guess is the exact combination. I call it a lot. Next the initial setup:

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

This gets the length of the combination, then starts guessing with all 0s. Afterwards, it iterates through each digit in a for loop.

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

For each digit, it guesses 5, then decides on the next step based on how the distance changed since the previous guess (where that digit was 0).

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

If the distance increased by 5, then 0 was correct for that distance. Adjust that digit back to 0. Altering the recorded distance manually prevents an extra guess.

case -5:
    break;

If the distance decreased by 5, then 5 is the correct digit and we move to the next digit immediately.

After that things are tricky. Using 5 and 0 for my initial guesses means that the remaining difference possibilities are 3, 1, -1, -3 with 2 possibilities for each, which need 1 additional guess to distinguish. Each of these cases takes a similar form

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

Some of the numbers change, but essentially we try one of the two possibilities, and check whether the change was the correct one for that digit. If it wasn't, then the other digit is correct so we set that digit then adjust the difference manually.

This method means we should require, at most, 1 guess for the initial 0s, 2 guesses per digit, and then 1 final guess to ensure the last digit doesn't fall through.

It might be buggy though, it works as far as I've checked manually but that's no guarantee. Bug found and squashed thanks to Colera Su

Answer 3

Python 2 and 3: 175 bytes, total attempts = 1005972, score = 5448445

This program takes ceil(log(n))*10 attempts per combination or every single digit takes 10 attempts (so, 333 takes 30 attempts).

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)

Huge thanks to Colera Su for helping me with the input/output functionality.

Python Version of Challenge (Modified by OP).

I wrote a version of the lock code inside of Python. You can go ahead and use if you're trying to solve this in Python (like me). The following works in Python 2 and 3. It made a lot more sense just to implement lock as a class you can test against and I decided to create a generator function for guessing the inputs.

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

Answer 4

R, 277 bytes (score=1175356) 258 bytes, total attempts = 202999, score = 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)

Try it online!

Stdin-stdout version, as requested by the OP, no boilerplates. Thanks to Colera Su for fixing an initial bug. This is a marginally shorter version than the one in the comments.

---

Here below the TIO submission to run a batch of tests within 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}

Try it online!

Let's consider a vector of zeros as the initial guess. Let's call V the distance between the current guess and the solution. For each position you only need to check the changes in V when you replace 0 with 5 and with 4. In fact, the differences between changing 0 with 5 are listed in my vector s1. The differences between changing 0 with 4 are listed in my vector s2. As you see these two vectors uniquely map the digits of the solution.

The total number of tests is thus 3*L 2*L + 1, where L is the length of the code: an initial check against all zeros, then two checks for each digit, one against 5 and one against 4.

The improvement from a factor 3 to a factor 2 was inspired by Kamil Drakari's submission.

The rest of the TIO submission is boilerplate for R. The TIO submission showcases the running time and the total number of operations for 1000 runs with L=1...200, 5 replicates for each value of L.