Anda diberi mesin dengan dua register 16-bit, xdan y. Register diinisialisasi x=1dan y=0. Satu-satunya operasi yang dapat dilakukan mesin adalah penambahan modulo 65536. Yaitu:

• x+=y- xdiganti dengan (x + y) mod 65536; ytidak berubah
• y+=x - sama untuk y
• x+=x- xdiganti dengan 2x mod 65536; sah hanya jika xadil
• y+=y - sama untuk y

Tujuannya adalah untuk mendapatkan nomor yang telah ditentukan di salah satu register (salah satu xatau y).

Tulis sebuah program atau subrutin yang menerima angka (dalam stdin,, argvparameter fungsi, atas tumpukan atau tempat konvensional lainnya), dan output sebuah program untuk mendapatkan nomor ini. Outputnya harus menuju stdout, atau (jika bahasa Anda tidak memiliki stdout) ke perangkat output konvensional lainnya.

Program keluaran bisa hingga 100% plus 2 langkah jauh dari optimal. Artinya, jika program terpendek untuk mendapatkan nomor target memiliki nlangkah-langkah, solusi Anda tidak lebih dari 2n+2. Pembatasan ini untuk menghindari solusi "terlalu mudah" (mis. Menghitung 1, 2, 3, ...) tetapi tidak memerlukan optimisasi penuh; Saya berharap bahwa program terpendek adalah yang termudah untuk ditemukan, tetapi tidak dapat memastikan ...

Misalnya: Input = 25. Output:

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

Contoh lain: Untuk setiap angka fibonacci, output memiliki pola bolak-balik ini. Untuk Input = 21, output adalah

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

Kode terpendek (diukur dalam byte) menang.

(Teka-teki ini terinspirasi oleh beberapa kode untuk prosesor 16-bit yang saya harus hasilkan baru-baru ini)

PS Saya bertanya-tanya - untuk nomor berapa program optimal paling lama?

CJam, 31

Seperti jawaban @Tobia , algoritme saya juga dicuri tanpa malu-malu, terinspirasi oleh jawaban @CChak . Tapi, menggunakan ilmu hitam yaitu CJam, saya berhasil membuat implementasi algoritma yang lebih kecil.

Coba di sini.

Golf:

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

Tidak Disatukan:

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

Tolong perbaiki saya jika saya salah, tetapi saya percaya bahwa operasi modulo 65536 yang digunakan dalam jawaban dengan algoritma yang sama tidak perlu. Saya menafsirkan pertanyaan sehingga kita dapat mengasumsikan bahwa input akan menjadi integer 16-bit unsigned yang valid, dan nilai menengah atau hasil dari algoritma ini juga akan.

Perl 107 97

Posting pertama, jadi begini.

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

Yang cocok dengan semua kriteria tambahan register, tapi saya tidak menjalankan pemeriksaan lengkap untuk melihat apakah jawaban saya selalu dalam 2n + 2 dari jumlah langkah optimal. Namun, ini masih dalam batas untuk setiap angka Fibonacci.

Berikut ini rincian lebih rinci

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.

Seperti yang saya sebutkan, ini adalah upaya pertama saya bermain golf, jadi saya yakin ini bisa diperbaiki. Juga, saya tidak yakin apakah panggilan subroutine awal harus dihitung dalam panggilan rekursif atau tidak, yang dapat mendorong kita beberapa karakter.

Menariknya kita dapat mengurangi kode dengan 11 byte * dan meningkatkan "efisiensi" kami dalam hal jumlah operasi register, dengan melonggarkan persyaratan bahwa hanya nilai genap yang dapat "digandakan". Saya memasukkannya untuk bersenang-senang di sini:

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

Mulai addendum:

Sangat menyukai masalah ini, dan saya telah mengotak-atiknya selama beberapa minggu terakhir. Kupikir aku akan memposting hasil saya.

Beberapa angka:

Menggunakan algoritma BFS untuk menemukan solusi optimal, dalam 2 ^ 16 angka pertama hanya ada 18 angka yang membutuhkan 23 langkah. Mereka adalah: 58558, 59894, 60110, 61182, 61278, 62295, 62430, 62910, 63422, 63462, 63979, 64230, 64314, 4486, 64510, 64698, 64854, 65295.

Menggunakan algoritma rekursif yang dijelaskan di atas, angka "paling sulit" untuk dicapai adalah 65535, pada 45 operasi. (65534 mengambil 44, dan ada 14 angka yang mengambil 43 langkah) 65535 juga merupakan keberangkatan terbesar dari optimal, 45 vs 22. Perbedaan 23 langkah adalah 2n +1. (Hanya tiga angka yang mengenai 2n: 65534, 32767, 32751.) Kecuali kasus sepele (nol-langkah), pada rentang yang ditentukan, metode rekursif rata-rata sekitar 1,4 kali solusi optimal.

Intinya: Untuk angka 1-2 ^ 16, algoritma rekursif tidak pernah melewati ambang batas yang ditentukan 2n + 2, jadi jawabannya valid. Saya menduga bahwa itu akan mulai terlalu jauh dari solusi optimal untuk register yang lebih besar / lebih banyak bit.

Kode yang saya gunakan untuk membuat BFS adalah ceroboh, memori intensif, tidak berkomentar, dan tidak sengaja sengaja dimasukkan. Jadi ... Anda tidak harus mempercayai hasil saya, tapi saya cukup percaya diri dalam hasilnya.

Python 3, 202 byte

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)

(Terima kasih kepada @rasionalis selama beberapa byte)

Inilah solusi yang sangat mendasar. Saya berharap bisa bermain golf dengan baris terakhir dengan lebih baik, tetapi saat ini saya kehabisan ide. Panggil dengan S(25).

Program ini hanya melakukan BFS sederhana tanpa caching, jadi sangat lambat. Berikut ini S(97), untuk beberapa keluaran sampel:

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

Dyalog APL, 49 karakter / byte *

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

Algoritma tanpa malu-malu terinspirasi oleh jawaban @CChak .

Contoh:

    {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

Tidak Disatukan:

{
    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 mendukung legacy charset yang memiliki simbol APL yang dipetakan ke nilai 128 byte atas. Oleh karena itu program APL yang hanya menggunakan karakter ASCII dan simbol APL dapat dianggap sebagai byte == karakter.}

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)

Saya tidak dapat menjamin ini tetap dalam 2x program optimal untuk angka genap, tetapi efisien. Untuk semua input yang valid 0 <= n < 65536, itu pada dasarnya instan, dan menghasilkan program paling banyak 33 instruksi. Untuk ukuran register sewenang-wenang n(setelah menetapkan konstanta itu), akan membutuhkan O(n)waktu paling banyak dengan 2n+1instruksi.

Logika Biner

Angka ganjil ndapat dihubungi dalam 31 langkah: lakukan y+=x, dapatkan x,y = 1,1, dan terus gandakan xdengan x+=x(untuk penggandaan pertama x+=y, karena xganjil untuk memulai). xakan mencapai setiap kekuatan 2 dengan cara ini (itu hanya shift kiri), dan jadi Anda dapat mengatur bit ymenjadi 1 dengan menambahkan kekuatan yang sesuai dari 2. Karena kita menggunakan register 16-bit, dan setiap bit kecuali untuk yang pertama membutuhkan satu penggandaan untuk mencapai dan satu y+=xuntuk ditetapkan, kita mendapatkan maksimal 31 ops.

Setiap bilangan genap nhanya sejumlah 2, sebut saja a, dikalikan dengan angka ganjil, sebut saja m; yaitu n = 2^a * m, atau setara n = m << a,. Gunakan proses di atas untuk mendapatkan m, lalu atur ulang xdengan menggeser ke kiri sampai menjadi 0. Lakukan x+=yuntuk mengatur x = m, dan kemudian lanjutkan untuk menggandakan x, pertama kali menggunakan x+=ydan kemudian menggunakan x+=x.

Apa pun aitu, dibutuhkan 16-apergeseran xuntuk mendapatkan y=mdan apergeseran tambahan untuk mengatur ulang x=0. aPergeseran lain xakan terjadi setelah x=m. Jadi total 16+ashift digunakan. Ada 16-abit hingga yang perlu diatur untuk mendapatkan m, dan masing-masing akan mengambil satu y+=x. Akhirnya kita membutuhkan langkah tambahan kapan x=0harus mengaturnya ke m x+=y,. Jadi dibutuhkan paling banyak 33 langkah untuk mendapatkan angka genap.

Anda dapat, tentu saja, menggeneralisasi ini ke register ukuran apa pun, dalam hal ini selalu dibutuhkan paling banyak 2n-1dan 2n+1ops untuk nbilangan bulat ganjil dan genap , masing-masing.

Optimalitas

Algoritma ini menghasilkan program yang mendekati optimal (yaitu di dalam 2n+2jika nadalah jumlah minimum langkah) untuk angka ganjil. Untuk bilangan ganjil tertentu n, jika mbit ke-1 adalah yang terdepan, maka setiap program mengambil setidaknya mlangkah untuk sampai ke , x=natau y=nkarena operasi yang meningkatkan nilai register paling cepat adalah x+=xatau y+=y(yaitu penggandaan) dan dibutuhkan mpenggandaan untuk mencapai yang mbit th dari 1. Sejak algoritma ini memakan waktu paling 2mlangkah (paling banyak dua per dua kali lipat, satu untuk pergeseran dan satu y+=x), setiap ganjil diwakili dekat-optimal.

Bahkan angkanya tidak begitu baik, karena selalu menggunakan 16 ops untuk mengatur ulang xsebelum yang lain, dan 8, misalnya, dapat dicapai dalam 5 langkah.

Menariknya, algoritma di atas tidak pernah menggunakan y+=ysama sekali, karena yselalu dibuat aneh. Dalam hal ini, ia sebenarnya dapat menemukan program terpendek untuk rangkaian terbatas hanya 3 operasi.

Pengujian

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

Saya menulis tes sederhana untuk memeriksa apakah solusi saya memang menghasilkan hasil yang benar, dan tidak pernah melewati 33 langkah, untuk semua input yang valid ( 0 <= n < 65536).

Selain itu, saya mencoba melakukan analisis empiris untuk membandingkan output solusi saya terhadap output optimal - namun, ternyata pencarian pertama yang terlalu luas tidak efisien untuk mendapatkan panjang output minimum untuk setiap input yang valid n. Misalnya, menggunakan BFS untuk menemukan output n = 65535tidak berakhir dalam jumlah waktu yang wajar. Meskipun demikian, saya telah meninggalkan bfs()dan terbuka untuk saran.

Saya lakukan, bagaimanapun, menguji solusi saya sendiri terhadap @ CChak (diimplementasikan di Python di sini sebagai U). Saya perkirakan tambang saya akan menjadi lebih buruk, karena secara drastis tidak efisien untuk angka genap yang lebih kecil, tetapi rata-rata di seluruh jajaran dalam dua cara, tambang menghasilkan keluaran panjang rata-rata 10,8% hingga 12,3% lebih pendek. Saya pikir mungkin ini karena efisiensi yang lebih baik dari solusi saya sendiri pada angka ganjil, jadi Vgunakan milik saya pada angka ganjil dan @ CChak pada angka genap, tetapi Vada di antara (sekitar 10% lebih pendek dari U, 3% lebih lama dari S).