Обычный N-значный кодовый замок состоит из N вращающихся дисков. Каждый диск имеет цифры 0-9, вписанные по порядку, и вам нужно повернуть их на правильный пароль, чтобы открыть его. Очевидно, что если вы не знаете пароль, вам нужно будет попробовать не более 10 ^N раз, прежде чем его разблокировать. Это не интересно

Итак, давайте рассмотрим вариант кодового замка, назовите его блокирующим расстояние.

При каждой неудачной попытке открыть замок, открывающий расстояние, он ответит минимальное количество движений, чтобы разблокировать.

Одно движение определяется как вращение на одну позицию, например, требуется 1 движение от 890до 899и 9 движений от 137до 952.

Соревнование

Учитывая блокирующую дистанцию ​​блокировку с неизвестным паролем, попробуйте открыть блокировку с минимальным количеством попыток (не перемещений), не допуская слишком долгого выполнения программы.

Правила и оценки

• Вы должны написать полную программу, которая вводит из stdin и выводит в stdout. Программа должна выполнять ввод / вывод следующим образом:

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

• Ваша программа должна обрабатывать до N = 200 и работать на любом входе менее 5 секунд.

• Начальные нули в выходных данных не должны быть опущены.

• Для каждой длины 5 тестовых данных, поэтому общее количество тестовых данных равно 1000. Тестовые данные генерируются случайным образом.

• Окончательный результат будет (общее количество предположений во всех тестовых данных) * ln (длина кода в байтах + 50). Самый низкий балл побеждает. (натуральный бревно)

• Я оценю программу для вас. Если вы хотите знать, как я буду оценивать вашу программу, или вы хотите оценить ее самостоятельно, посмотрите предыдущие изменения в этом посте .

• Это испытание закончится в 2017/12/07 14:00 UTC. Я опубликую свое решение тогда.

Пример выполнения

Строки, начинающиеся с >представления ввода, а другие представляют вывод программы.

Вы можете иметь пароль в уме и взаимодействовать с вашей программой, чтобы проверить его.

> 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

Пример программы

РЕДАКТИРОВАТЬ: Может быть, формат ввода / вывода выше не было ясно. Вот пример программы на Python.

Python, 369 байт, общее количество попыток = 1005973, оценка = 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

Спасибо Ионе за упрощение задачи.

C 388 374 368 байт, общее количество попыток = 162751, оценка = 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 байт, всего попыток = 182255, оценка = 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;}}}

Надеюсь, C # в этом формате работает для вас. Это в форме законченной программы, поэтому должен быть способ компиляции в исполняемый файл. Дайте мне знать, если я могу что-нибудь сделать, чтобы было легче. Байты являются частью оценки, даже если тег Code Golf удален, поэтому мое официальное представление удаляет все ненужные пробелы и полезные имена. Мое объяснение ниже будет использовать фрагменты кода без ключа:

объяснение

Эта программа использует только один вспомогательный метод:

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

Это записывает предположение в стандартный вывод, а затем считывает расстояние от стандартного ввода. Это также немедленно завершает программу, если предположение является точной комбинацией. Я это часто называю. Далее начальная настройка:

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

Получается длина комбинации, затем начинается угадывание со всеми 0. После этого он перебирает каждую цифру в forцикле.

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

Для каждой цифры он угадывает 5, а затем принимает решение о следующем шаге, основываясь на том, как изменилось расстояние со времени предыдущего предположения (где эта цифра была 0).

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

Если расстояние увеличилось на 5, то 0 было правильным для этого расстояния. Установите эту цифру обратно на 0. Изменение записанного расстояния вручную предотвращает дополнительные предположения.

case -5:
    break;

Если расстояние уменьшилось на 5, то 5 - правильная цифра, и мы сразу же переходим к следующей цифре.

После этого все сложно. Использование 5и 0для моих начальных догадок означает, что оставшиеся возможности различий имеют 3, 1, -1, -32 варианта для каждого, для различения которого требуется 1 дополнительное предположение. Каждый из этих случаев принимает аналогичную форму

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

Некоторые числа меняются, но по сути мы пробуем одну из двух возможностей и проверяем, было ли изменение правильным для этой цифры. Если это не так, тогда другая цифра верна, поэтому мы устанавливаем эту цифру, а затем корректируем разницу вручную.

Этот метод означает, что нам нужно, самое большее, 1 предположение для начальных 0, 2 догадки на цифру, а затем 1 последнее предположение, чтобы последняя цифра не провалилась.

Это может быть ошибкой, это работает, насколько я проверял вручную, но это не гарантия. Ошибка обнаружена и устранена благодаря Colera Su

Python 2 и 3: 175 байт, общее количество попыток = 1005972, оценка = 5448445

Эта программа принимает ceil (log (n)) * 10 попыток на комбинацию или каждая цифра занимает 10 попыток (то есть, 33330 попыток).

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)

Огромное спасибо Colera Su за помощь в работе с функциями ввода / вывода.

Python-версия Challenge ( изменена OP ).

Я написал версию кода блокировки внутри Python. Вы можете пойти дальше и использовать, если вы пытаетесь решить эту проблему в Python (как я). Следующее работает в Python 2 и 3. Было гораздо больше смысла просто реализовать блокировку как класс, с которым вы можете протестировать, и я решил создать функцию генератора для угадывания входных данных.

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 байтов (оценка = 1175356) 258 байтов, всего попыток = 202999, оценка = 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)

Попробуйте онлайн!

Версия стандартного ввода-вывода, запрошенная OP, без шаблонов. Спасибо Колере Су за исправление первоначальной ошибки. Это немного более короткая версия, чем в комментариях.

Здесь ниже представление TIO для запуска серии тестов в TIO

R 189 байт

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}

Попробуйте онлайн!

Давайте рассмотрим вектор нулей как начальную догадку. Назовем V расстоянием между текущим предположением и решением. Для каждой позиции вам нужно только проверять изменения в V, когда вы заменяете 0 на 5 и на 4. На самом деле, различия между изменением 0 на 5 перечислены в моем векторе s1. Различия между изменением 0 на 4 перечислены в моем векторе s2. Как вы видите, эти два вектора однозначно отображают цифры решения.

Таким образом, общее количество тестов составляет 3 * L 2 * L + 1, где L - длина кода: начальная проверка на все нули, затем две проверки на каждую цифру, одна на 5 и одна на 4.

Улучшение с фактора 3 до фактора 2 было вдохновлено представлением Камиля Дракари.

Остальная часть представления TIO является образцом для R. Представление TIO показывает время выполнения и общее количество операций на 1000 циклов с L = 1 ... 200, 5 повторов для каждого значения L.