Otrzymujesz maszynę z dwoma 16-bitowymi rejestrami xi y. Rejestry są inicjowane x=1i y=0. Jedyną operacją, jaką może wykonać maszyna, jest dodanie modułu 65536. To znaczy:

• x+=y- xzastępuje się przez (x + y) mod 65536; ypozostaje niezmieniony
• y+=x - podobnie dla y
• x+=x- xzastępuje się przez 2x mod 65536; legalne tylko, jeśli xjest parzyste
• y+=y - podobnie dla y

Celem jest uzyskanie z góry określonej liczby w jednym z rejestrów (albo xalbo y).

Napisz program lub podprogram, który odbiera liczbę (in stdin, argvparametr funkcji, top stosu lub inne konwencjonalne miejsce) i wysyła program, aby uzyskać ten numer. Dane wyjściowe powinny przejść do stdout, lub (jeśli twój język nie ma stdout), na inne konwencjonalne urządzenie wyjściowe.

Program wyjściowy może wynosić do 100% plus 2 kroki daleko od optymalnego. Oznacza to, że jeśli najkrótszy program do uzyskania numeru docelowego ma nkroki, twoje rozwiązanie nie może być dłuższe niż 2n+2. To ograniczenie ma na celu uniknięcie „zbyt łatwych” rozwiązań (np. Liczenie 1, 2, 3, ...), ale nie wymaga pełnej optymalizacji; Oczekuję, że najkrótszy program jest najłatwiejszy do znalezienia, ale nie jestem pewien ...

Na przykład: Input = 25. Output:

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

Kolejny przykład: dla dowolnej liczby Fibonacciego, wyjście ma ten naprzemienny wzór. Dla Input = 21 wyjście to

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

Najkrótszy kod (mierzony w bajtach) wygrywa.

(ta łamigłówka została zainspirowana kodem 16-bitowego procesora, który musiałem ostatnio wygenerować)

PS Zastanawiam się - dla jakiej liczby optymalny program jest najdłuższy?

CJam, 31

Podobnie jak odpowiedź @Tobia , mój algorytm jest również bezwstydnie skradziony inspirowany odpowiedzią @CChak . Ale posługując się czarną magią, jaką jest CJam, udało mi się wprowadzić jeszcze mniejszą implementację algorytmu.

Wypróbuj tutaj.

Gra w golfa:

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

Nie golfowany:

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.";

Proszę mnie poprawić, jeśli się mylę, ale uważałem, że operacja modulo 65536 stosowana w odpowiedziach z podobnym algorytmem jest niepotrzebna. Zinterpretowałem to pytanie w taki sposób, że możemy założyć, że wejście będzie prawidłową 16-bitową liczbą całkowitą bez znaku, a także wszelkie wartości pośrednie lub wyniki tego algorytmu.

Perl 107 97

Pierwszy post, więc proszę bardzo.

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

Który pasuje do wszystkich kryteriów dodawania rejestru, ale nie przeprowadziłem wyczerpującego sprawdzenia, aby sprawdzić, czy moja odpowiedź zawsze mieści się w granicach 2n + 2 od optymalnej liczby kroków. Jest jednak w granicach limitu dla każdej liczby Fibonacciego.

Oto bardziej szczegółowy podział

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.

Jak wspomniałem, to moja pierwsza gra w golfa, więc jestem pewien, że można to poprawić. Nie jestem też pewien, czy początkowe wywołanie podprogramu musi zostać policzone w wywołaniu rekurencyjnym, czy nie, co może zwiększyć liczbę znaków.

Co ciekawe, możemy zmniejszyć kod o 11 bajtów * i poprawić naszą „wydajność” pod względem liczby operacji rejestru, zmniejszając wymóg, że tylko parzyste wartości mogą być „podwojone”. Dołączyłem to dla zabawy:

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

Rozpocznij uzupełnienie:

Naprawdę podobał mi się ten problem i od kilku tygodni bawię się nim z przerwami. Myślałem, że opublikuję swoje wyniki.

Niektóre liczby:

Korzystając z algorytmu BFS w celu znalezienia optymalnego rozwiązania, w pierwszych 2 ^ 16 liczbach jest tylko 18 liczb, które wymagają 23 kroków. Są to: 58558, 59894, 60110, 61182, 61278, 62295, 62430, 62910, 63422, 63462, 63979, 64230, 64314, 4486, 64510, 64698, 64854, 65295.

Przy użyciu opisanego powyżej algorytmu rekurencyjnego „Najtrudniejszym” numerem jest 65535 przy 45 operacjach. (65534 zajmuje 44, a jest 14 liczb, które wykonują 43 kroki) 65535 jest również największym odstępstwem od optymalnego, 45 vs 22. Różnica 23 kroków wynosi 2n + 1. (Tylko trzy liczby trafiły w 2n: 65534, 32767, 32751.) Z wyjątkiem przypadków trywialnych (z krokiem zerowym), w zdefiniowanym zakresie, metoda rekurencyjna wynosi średnio około 1,4 razy optymalne rozwiązanie.

Konkluzja: Dla liczb 1-2 ^ 16 algorytm rekurencyjny nigdy nie przekracza zdefiniowanego progu 2n + 2, więc odpowiedź jest poprawna. Podejrzewam jednak, że zacząłby odbiegać zbyt daleko od optymalnego rozwiązania dla większych rejestrów / większej liczby bitów.

Kod, którego użyłem do stworzenia BFS, był niechlujny, wymagał dużej ilości pamięci, nie skomentował i całkiem celowo nie został uwzględniony. Więc ... nie musisz ufać moim wynikom, ale jestem całkiem pewny ich.

Python 3, 202 bajty

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)

(Podziękowania dla @rationalis za kilka bajtów)

Oto niezwykle podstawowe rozwiązanie. Chciałbym móc lepiej grać w ostatnią linię, ale obecnie brakuje mi pomysłów. Zadzwoń zS(25) .

Program wykonuje prosty BFS bez buforowania, więc działa bardzo wolno. Oto S(97)przykładowe dane wyjściowe:

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

Dyalog APL, 49 znaków / bajtów *

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

Algorytm bezwstydnie inspirowany @CChak .

Przykład:

    {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

Nie golfowany:

{
    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'
}

_{* Aplikacja APL Dyalog obsługuje starszy zestaw znaków, w którym symbole APL są odwzorowane na górne 128 bajtów. Dlatego program APL, który używa tylko znaków ASCII i symboli APL, można uznać za bajty == znaków.}

Python, 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)

Nie mogę zagwarantować, że pozostanie w 2x optymalnym programie dla liczb parzystych, ale jest wydajny. Dla wszystkich prawidłowych danych wejściowych jest 0 <= n < 65536to w zasadzie natychmiastowe i generuje program składający się maksymalnie z 33 instrukcji. W przypadku dowolnego rozmiaru rejestru n(po ustaleniu tej stałej) zajęłoby to O(n)najwyżej trochę czasu2n+1 instrukcje.

Trochę logiki binarnej

Dowolną liczbę nieparzystą nmożna osiągnąć w ciągu 31 kroków: wykonaj y+=x, otrzymaj x,y = 1,1, a następnie podwojaj za xpomocą x+=x(dla pierwszego podwojenia x+=y, ponieważ początkowo xjest nieparzysta). xosiągnie w ten sposób każdą potęgę 2 (to tylko przesunięcie w lewo), więc możesz ustawić dowolną wartośćy 1, dodając odpowiednią potęgę 2. Ponieważ używamy rejestrów 16-bitowych i każdy bit oprócz dla pierwszego potrzeba jednego podwojenia, aby osiągnąć, a drugiego y+=xdo ustawienia, otrzymujemy maksymalnie 31 operacji.

Dowolna liczba parzysta nto tylko potęga 2, zadzwoń a, razy liczbę nieparzystą, zadzwoń m; tj. n = 2^a * mlub równoważnie n = m << a. Użyj powyższego procesu, aby uzyskać m, a następnie zresetuj x, przesuwając go w lewo, aż osiągnie wartość 0. Wykonaj a, x+=yaby ustawić x = m, a następnie kontynuuj podwojenie x, przy pierwszym użyciu, x+=ya następnie przy użyciu x+=x.

Cokolwiek ato jest, potrzeba 16-azmian, xaby uzyskać y=mi dodatkowych azmian, aby zresetować x=0. Kolejne azmiany xnastąpią po x=m. 16+aWykorzystano więc całkowitą liczbę zmian. Istnieje kilka 16-abitów, które należy ustawić, aby je zdobyć m, a każdy z nich zajmie jeden y+=x. Wreszcie potrzebujemy dodatkowego kroku, x=0aby ustawić go na m,x+=y . Aby uzyskać dowolną liczbę parzystą, potrzeba maksymalnie 33 kroków.

Możesz oczywiście uogólnić to na dowolny rejestr wielkości, w którym to przypadku zawsze zajmuje najwyżej 2n-1i 2n+1operuje na parzyste i nieparzysten operuje odpowiednio na liczbach .

Optymalność

Ten algorytm tworzy program, który jest prawie optymalny (tzn. 2n+2Jeśli if njest minimalną liczbą kroków) dla liczb nieparzystych. Dla danej liczby nieparzystej n, jeśli ten mbit jest wiodącym 1, to dowolny program podejmuje przynajmniej mkroki, aby dostać się do x=nlub y=n, ponieważ operacja, która najszybciej zwiększa wartości rejestrów, to x+=xlub y+=y(tj. Podwojenie) i potrzeba mpodwojenia, aby dostać się do część mz 1. Ponieważ ten algorytm wykonuje co najwyżej 2mkilka kroków (maksymalnie dwa na podwojenie, jeden dla zmiany i jedeny+=x ), każda liczba nieparzysta jest reprezentowana prawie optymalnie.

Liczby parzyste nie są tak dobre, ponieważ zawsze resetuje 16 operacji x zanim cokolwiek innego, a na przykład 8 można osiągnąć w ciągu 5 kroków.

Co ciekawe, powyższy algorytm nigdy nie używa y+=yw ogóley zawsze jest nieparzysty. W takim przypadku może faktycznie znaleźć najkrótszy program dla ograniczonego zestawu tylko 3 operacji.

Testowanie

# 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()

Napisałem prosty test, aby sprawdzić, czy moje rozwiązanie rzeczywiście daje poprawne wyniki i nigdy nie przekracza 33 kroków, dla wszystkich prawidłowych danych wejściowych ( 0 <= n < 65536).

Ponadto próbowałem przeprowadzić analizę empiryczną, aby porównać wyniki mojego rozwiązania z wynikami optymalnymi - okazuje się jednak, że wyszukiwanie z szerokością pierwszego rzędu jest zbyt mało wydajne, aby uzyskać minimalną długość wyjściową dla każdego ważnego wejścia n. Na przykład użycie BFS do znalezienia wyjścia n = 65535nie kończy się w rozsądnym czasie. Niemniej jednak wyszedłem bfs()i jestem otwarty na sugestie.

Testowałem jednak swoje własne rozwiązanie pod kątem @ CChak (zaimplementowane w Pythonie tutaj jako U). Spodziewałem się, że moja będzie gorzej, ponieważ jest drastycznie nieefektywna dla mniejszych liczb parzystych, ale uśredniona dla całego zakresu na dwa sposoby, kopalnia produkuje średnio o 10,8% do 12,3% mniej. Pomyślałem, że może to wynikało z lepszej wydajności z mojego własnego rozwiązania dla liczb nieparzystych, więc Vużywa moich na liczbach nieparzystych i @ CChak na liczbach parzystych, ale Vjest pomiędzy (około 10% krótszy niż U, 3% dłuższy niż S).