Вам предоставляется машина с двумя 16-битными регистрами, xи y. Регистры инициализированы x=1и y=0. Единственная операция, которую может выполнить машина, это сложение по модулю 65536. То есть:

• x+=y- xзаменен на (x + y) mod 65536; yбез изменений
• y+=x - аналогично для y
• x+=x- xзаменен на 2x mod 65536; законно только если xчет
• y+=y - аналогично для y

Цель состоит в том, чтобы получить заранее определенное число в одном из регистров (либо, xлибо y).

Напишите программу или подпрограмму, которая получает число (in stdin, argvпараметр функции, вершина стека или любое другое обычное место) и выводит программу для получения этого числа. Вывод должен идти stdoutили (если у вашего языка нет stdout) на любое другое обычное устройство вывода.

Программа вывода может составлять до 100% плюс 2 шага, далеких от оптимальных. То есть, если в самой короткой программе для получения целевого числа есть nшаги, ваше решение не может быть длиннее, чем 2n+2. Это ограничение состоит в том, чтобы избегать «слишком простых» решений (например, считая 1, 2, 3, ...), но не требует полной оптимизации; Я ожидаю, что самую короткую программу легче всего найти, но не уверен ...

Например: Вход = 25. Выход:

y+=x
x+=y
x+=y
x+=x
x+=x
x+=x
y+=x

Другой пример: для любого числа Фибоначчи выходные данные имеют этот чередующийся шаблон. Для ввода = 21 выход

y+=x
x+=y
y+=x
x+=y
y+=x
x+=y
y+=x

Самый короткий код (измеряется в байтах) выигрывает.

(эта головоломка была вдохновлена ​​неким кодом для 16-битного процессора, который мне пришлось генерировать недавно)

PS Интересно - для какого числа оптимальная программа самая длинная?

CJam, 31

Как и ответ @Tobia , мой алгоритм также бесстыдно украден, вдохновленный ответом @CChak . Но, используя черную магию CJam, мне удалось сделать еще меньшую реализацию алгоритма.

Попробуй это здесь.

Golfed:

qi{_4%!:X)/X!-'xX+"
y+="@}h;]W%`

Ungolfed:

qi          "Read input and convert to integer.";
{           "Do...";
  _4%!:X    "Assign (value mod 4 == 0) to X.";
  )/X!-     "If X, divide value by 2. If not X, decrement value.";
  'xX+      "If X, put 'y' on the stack. If not X, put 'x' on the stack.";
  "
y+="        "Put '\ny+=' on the stack.";
  @         "Rotate top 3 elements of stack left so the value is on top.";
}h          "... while value is not zero.";
;           "Discard zero value on stack.";
]W%         "Collect stack into array and reverse.";

Пожалуйста, исправьте меня, если я ошибаюсь, но я полагал, что операция по модулю 65536, используемая в ответах с похожим алгоритмом, не нужна. Я интерпретировал вопрос так, что мы можем предположить, что входными данными будет действительное 16-разрядное целое число без знака, и любые промежуточные значения или результаты этого алгоритма также будут.

Perl 107 97

Первый пост, так что здесь идет.

sub h{($i)=@_;return if(($i%=65536)==0);($i%4==0)?do{h($i/2);say"y+=y";}:do{h($i-1);say"y+=x";}}

Что соответствует всем критериям добавления в регистр, но я не провел исчерпывающую проверку, чтобы убедиться, что мой ответ всегда был в пределах 2n + 2 от оптимального количества шагов. Впрочем, оно хорошо вписывается в предел для каждого числа Фибоначчи.

Вот более подробная разбивка

sub h{                           # Declare the subroutine, it should be called referencing an integer value
   ($i)=@_;                      # Assign the i variable to the integer used in the call
   return if(($i%=65536)==0);    # Check for base condition of called by 0, and enforce modulo from the start.
   ($i%4==0) ?                   # If the value passed is even, and will result in an even number if we halve it
   do{h($i/2);say"y+=y";}        # Then do so and recurse 
   :do{h($i-1);say"y+=x";}       # Otherwise "subtract one" and recurse
}                                # Note that the print statements get called in reverse order as we exit.

Как я уже говорил, это моя первая попытка игры в гольф, поэтому я уверен, что это можно улучшить. Кроме того, я не уверен, должен ли начальный вызов подпрограммы учитываться в рекурсивном вызове или нет, что может привести нас к росту на несколько символов.

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

sub h{($i)=@_;return if(($i%=65536)==0);($i%2==0)?do{h($i/2);say"y+=y";}:do{h($i-1);say"y+=x";}}

Начать приложение:

Мне очень понравилась эта проблема, и я возился с ней в течение последних нескольких недель. Думаю, я опубликую свои результаты.

Некоторые цифры:

Используя алгоритм BFS, чтобы найти оптимальное решение, в первых 2 ^ 16 числах есть только 18 чисел, которые требуют 23 шага. Это: 58558, 59894, 60110, 61182, 61278, 62295, 62430, 62910, 63422, 63462, 63979, 64230, 64314, 4486, 64510, 64698, 64854, 65295.

Используя рекурсивный алгоритм, описанный выше, «самое трудное» число - 65535 при 45 операциях. (65534 занимает 44, и есть 14 чисел, которые делают 43 шага) 65535 также является наибольшим отклонением от оптимального, 45 против 22. Разница в 23 шага составляет 2n + 1. (Только 2 числа достигают 2n: 65534, 32767, 32751.) За исключением тривиальных (с нулевым шагом) случаев, в определенном диапазоне рекурсивный метод в среднем приблизительно в 1,4 раза превышает оптимальное решение.

Итог: для чисел 1-2 ^ 16 рекурсивный алгоритм никогда не пересекает определенный порог 2n + 2, поэтому ответ верен. Однако я подозреваю, что он станет слишком далеко от оптимального решения для больших регистров / большего количества битов.

Код, который я использовал для создания BFS, был небрежным, занимал много памяти, не комментировался и совершенно сознательно не включался. Так что ... тебе не нужно доверять моим результатам, но я довольно уверен в них.

Python 3, 202 байта

def S(n):
 q=[(1,0,"")];k=65536
 while q:
  x,y,z=q.pop(0)
  if n in{x,y}:print(z);return
  q+=[((x+y)%k,y,z+"x+=y\n"),(x,(x+y)%k,z+"y+=x\n")]+[(2*x%k,y,z+"x+=x\n")]*(~x&1)+[(x,2*y%k,z+"y+=y\n")]*(~y&1)

(Спасибо @rationalis за несколько байтов)

Вот очень простое решение. Хотел бы я лучше сыграть в гольф на последней линии, но у меня сейчас нет идей. Позвони с S(25).

Программа просто делает простую BFS без кеширования, поэтому работает очень медленно. Вот S(97)пример вывода:

y+=x
x+=y
x+=x
x+=x
x+=x
x+=x
y+=x
y+=x
x+=y

Dyalog APL, 49 символов / байт *

{0=N←⍵|⍨2*16:⍬⋄0=4|N:⎕←'y+=y'⊣∇N÷2⋄⎕←'y+=x'⊣∇N-1}

Алгоритм бесстыдно вдохновлен ответом @CChak .

Пример:

    {0=N←⍵|⍨2*16:⍬⋄0=4|N:⎕←'y+=y'⊣∇N÷2⋄⎕←'y+=x'⊣∇N-1} 25
y+=x
y+=x
y+=y
y+=x
y+=x
y+=y
y+=y
y+=x

Ungolfed:

{
    N←(2*16)|⍵                 # assign the argument modulo 65536 to N
    0=N: ⍬                     # if N = 0, return an empty value (that's a Zilde, not a 0)
    0=4|N: ⎕←'y+=y' ⊣ ∇N÷2     # if N mod 4 = 0, recurse with N÷2 and *then* print 'y+=y'
    ⎕←'y+=x' ⊣ ∇N-1            # otherwise, recurse with N-1 and *then* print 'y+=x'
}

_{* Dyalog APL поддерживает устаревшую кодировку, в которой символы APL отображаются в верхние 128-байтовые значения. Поэтому программу APL, которая использует только символы ASCII и символы APL, можно считать байтами == символов.}

Питон, 183

def S(n):
 b,c,e=16,'x+=x\n','x+=y\n';s=d='y+=x\n';a=i=0
 if n<2:return
 while~n&1:n>>=1;a+=1
 while n:n>>=1;s+=[e,c][i]+d*(n&1);i=1;b-=1
 while a:s+=[c,c*b+e*2][i];i=0;a-=1
 print(s)

Я не могу гарантировать, что это останется в пределах 2х оптимальной программы для четных чисел, но она эффективна. Для всех допустимых входных данных 0 <= n < 65536это по сути мгновенно и генерирует программу максимум из 33 инструкций. Для произвольного размера регистра n(после фиксации этой константы) на это потребуется O(n)не более 2n+1инструкций.

Некоторая бинарная логика

Любое нечетное число nможет быть достигнуто в течение 31 шагов: делать y+=x, получать x,y = 1,1, а затем продолжает удваивая xс x+=x(для первого удвоения сделать x+=y, так как xнечетно , чтобы начать с). xтаким образом достигнет каждой степени 2 (это просто сдвиг влево), поэтому вы можете установить любой бит yравным 1, добавив соответствующую степень 2. Поскольку мы используем 16-битные регистры и каждый бит, кроме для первого требуется одно удвоение для достижения и одно y+=xдля установки, мы получаем максимум 31 опс.

Любое четное число n- это просто некоторая степень 2, назовите его a, умножьте на нечетное число, назовите его m; то есть n = 2^a * mили эквивалентно n = m << a. Используйте описанный выше процесс, чтобы получить m, затем сбросьте xего, сдвинув влево до тех пор, пока не станет 0. Сделайте a, x+=yчтобы установить x = m, а затем продолжайте удваивать x, используя в первый раз x+=yи затем используя x+=x.

Что бы там ни было a, требуется 16-aсдвиг, xчтобы получить y=mи дополнительные aсдвиги, чтобы сбросить x=0. Другие aсдвиги xпроизойдут после x=m. Таким образом, общее количество 16+aсмен используется. Есть до 16-aбитов, которые нужно установить, чтобы получить m, и каждый из них будет по одному y+=x. Наконец, нам нужен дополнительный шаг, x=0чтобы установить его в m x+=y. Таким образом, для получения любого четного числа требуется не более 33 шагов.

Конечно, вы можете обобщить это на регистр любого размера, и в этом случае он всегда принимает самое большее 2n-1и 2n+1ops для нечетных и четных nбитов соответственно.

Оптимальность

Этот алгоритм производит программу, близкие к оптимальному (т.е. в пределах , 2n+2если nминимальное количество шагов) для нечетных чисел. Для заданного нечетного числа n, если mth-й бит является первым 1, то любая программа предпринимает как минимум mшаги, чтобы добраться до x=nили y=n, поскольку операция, которая увеличивает значения регистров быстрее всего,x+=x или y+=y(т.е. удваивается), и mдля получения 1- mй бит из 1. Поскольку этот алгоритм выполняет не более 2mодного шага (не более двух на удвоение, одно для сдвига и одно y+=x), любое нечетное число представляется почти оптимальным.

Четные числа не так хороши, так как он всегда использует 16 операций для сброса, xпрежде чем что-либо еще, а 8, например, может быть достигнуто за 5 шагов.

Интересно, что приведенный выше алгоритм никогда не использует y+=yвообще, так yкак всегда остается нечетным. В этом случае он может найти самую короткую программу для ограниченного набора, состоящего только из 3 операций.

тестирование

# Do an exhaustive breadth-first search to find the shortest program for
# each valid input
def bfs():
    d = {(0,1):0}
    k = 0xFFFF
    s = set(range(k+1))
    current = [(0,1)]
    nexts = []
    def add(pt, dist, n):
        if pt in d: return
        d[pt] = dist
        s.difference_update(pt)
        n.append(pt)
    i = 0
    while len(s) > 0:
        i += 1
        for p in current:
            x,y = p
            add((x,x+y&k), i, nexts)
            add((y,x+y&k), i, nexts)
            if y%2 == 0: add(tuple(sorted((x,y+y&k))), i, nexts)
            if x%2 == 0: add(tuple(sorted((x+x&k,y))), i, nexts)
        current = nexts
        nexts = []
        print(len(d),len(s))

# Mine (@rationalis)
def S(n):
    b,c,e=16,'x+=x\n','x+=y\n';s=d='y+=x\n';a=i=0
    if n<2:return ''
    while~n&1:n>>=1;a+=1
    while n:n>>=1;s+=[e,c][i]+d*(n&1);i=1;b-=1
    while a:s+=[c,c*b+e*2][i];i=0;a-=1
    return s

# @CChak's approach
def U(i):
    if i<1:return ''
    return U(i//2)+'y+=y\n' if i%4==0 else U(i-1)+'y+=x\n'

# Use mine on odd numbers and @CChak's on even numbers
def V(i):
    return S(i) if i % 2 == 1 else U(i)

# Simulate a program in the hypothetical machine language
def T(s):
    x,y = 1,0
    for l in s.split():
        if l == 'x+=x':
            if x % 2 == 1: return 1,0
            x += x
        elif l == 'y+=y':
            if y % 2 == 1: return 1,0
            y += y
        elif l == 'x+=y': x += y
        elif l == 'y+=x': y += x
        x %= 1<<16
        y %= 1<<16
    return x,y

# Test a solution on all values 0 to 65535 inclusive
# Max op limit only for my own solution
def test(f):
    max_ops = 33 if f==S else 1000
    for i in range(1<<16):
        s = f(i); t = T(s)
        if i not in t or len(s)//5 > max_ops:
            print(s,i,t)
            break

# Compare two solutions
def test2(f,g):
    lf = [len(f(i)) for i in range(2,1<<16)]
    lg = [len(g(i)) for i in range(2,1<<16)]
    l = [lf[i]/lg[i] for i in range(len(lf))]
    print(sum(l)/len(l))
    print(sum(lf)/sum(lg))

# Test by default if script is executed
def main():
    test()

if __name__ == '__main__':
    main()

Я написал простой тест, чтобы проверить, что мое решение действительно дает правильные результаты и никогда не проходит 33 шага для всех допустимых входных данных (0 <= n < 65536 ).

Кроме того, я попытался провести эмпирический анализ, чтобы сравнить выходные данные моего решения с оптимальными выходными данными - однако оказывается, что поиск в ширину слишком неэффективен, чтобы получить минимальную длину выходных данных для каждого действительного ввода n. Например, использование BFS для поиска выходных данных n = 65535не завершается в разумные сроки. Тем не менее я ушел bfs()и открыт для предложений.

Тем не менее, я протестировал свое собственное решение с помощью @ CChak (реализовано здесь на Python как U). Я ожидал, что мой будет работать хуже, так как он намного неэффективен для меньших четных чисел, но усреднен по всему диапазону двумя способами, при этом добыча составила в среднем 10,8% до 12,3% короче. Я подумал, что это может быть связано с большей эффективностью моего собственного решения для нечетных чисел, поэтому Vиспользует мое для нечетных чисел и @ CChak для четных чисел, но Vнаходится между ними (примерно на 10% короче, чем на U3% длиннее S).