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.
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
899, and 9 movements from
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.
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
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.