12
\$\begingroup\$

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 10N times before unlocking it. That's not interesting.

combination lock

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.

\$\endgroup\$
3
\$\begingroup\$

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);}
\$\endgroup\$
  • \$\begingroup\$ Welcome to PPCG! You got a nice score of 162751*ln(388+50)=989887. \$\endgroup\$ – Colera Su Nov 28 '17 at 6:48
3
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ I tested it and it didn't work when answer is 37. The output is: 00, 50, 30, 75, 75 (yes, two 75s). \$\endgroup\$ – Colera Su Nov 21 '17 at 23:07
  • \$\begingroup\$ Replacing < with > in every if in switch seems to fix the bug. If that's what you want, your score is 182255*ln(617+50)=1185166. \$\endgroup\$ – Colera Su Nov 21 '17 at 23:30
  • \$\begingroup\$ @ColeraSu Indeed! I must have made a mistake with the find/replace when shortening the code. I've made the fix in the golfed code (the verbose version had the correct comparisons). \$\endgroup\$ – Kamil Drakari Nov 22 '17 at 5:05
2
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ First, sorry about that I wrote the LockIO class wrong. I've sent a edit request. Second, I think you've misread the scoring criterion. The score is calculated by the testdata generated by the generator, not example (I executed your program, and the total number is 1005972). The natural log is also missing. Third, I've specified that you need to provide a full program, so you should include the LockIO part in your byte count as well. Additionally, you need to output the final result, and that is also counted in the score. \$\endgroup\$ – Colera Su Nov 20 '17 at 10:33
  • \$\begingroup\$ @ColeraSu How is "the class LockIO" related here? Also what is the second block of Python code used for? \$\endgroup\$ – user202729 Nov 20 '17 at 10:35
  • \$\begingroup\$ @user202729 Lock and masterLock is just for convenience of testing. LockIO is what you actually need to submit, since it uses the required I/O format. \$\endgroup\$ – Colera Su Nov 20 '17 at 10:57
  • \$\begingroup\$ @nfnneil I've added a sample program in the main post. I also sent an edit request for your reference. \$\endgroup\$ – Colera Su Nov 20 '17 at 11:49
  • \$\begingroup\$ @ColeraSu As I was falling asleep I realized what you meant and thanks man. It was a good challenge. \$\endgroup\$ – Neil Nov 20 '17 at 19:55
2
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ I get Error in scan(n = 1) : scan() expected 'a real', got 'S=rep(0,L)' when executing. \$\endgroup\$ – Colera Su Nov 22 '17 at 9:09
  • 1
    \$\begingroup\$ It seems that scan(file=file("stdin"),n=1) works. This program (same as yours, just corrected I/O) get a score of 202999*ln(277+50)=1175356. \$\endgroup\$ – Colera Su Nov 22 '17 at 9:35
  • \$\begingroup\$ @ColeraSu , I may have missed something, but I thought that 202999*ln(258+50) != 202999*ln(277+50) \$\endgroup\$ – NofP Nov 26 '17 at 21:57
  • \$\begingroup\$ Seems that @user202729 made a typo. Fixed. \$\endgroup\$ – Colera Su Nov 27 '17 at 1:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.