Reverse-Engineer urutan N-Bonacci [s]

15

EDIT: Saya akan menerima jawaban Senin, 15/2/2016. Semoga byte selalu menguntungkan Anda!

Dalam tantangan "Print the N-Bonacci Sequence" , @DJMcGoathem menjelaskan urutan N-bonacci, di mana angka-angka N sebelumnya dijumlahkan, alih-alih angka 2 tradisional dari urutan Fibonacci (dikatakan sebagai " urutan duo nacci"). Dia kemudian diminta mengambil dua input, X dan N, lalu mengeluarkan X th N nomor -nacci.

Saya mengusulkan yang sebaliknya.
Diberikan urutan, output yang N urutan -nacci itu adalah bagian dari. Saya mengatakan "bagian dari" karena:

  • A) urutan ini tidak terbatas
  • B) jika diberi awal urutan, Anda bisa menghitung jumlah 1s terkemuka

Dalam hal itu bisa menjadi milik beberapa urutan N -nacci, pilih yang terendah.
Dalam hal itu bukan milik urutan N-nacci , maka program Anda dapat melakukan apa pun selain mencetak sesuatu yang bisa keliru untuk output. Perilaku ini termasuk (tetapi tidak terbatas pada): infinite loop, error, crash, hapus sendiri (* cough cough * vigil * cough cough *), atau membuat lubang hitam (selama lubang hitam ini tidak menghasilkan apa pun yang bisa keliru untuk output yang valid).
Demi tantangan ini, urutan ini mulai dengan 1. Ini cara apapun N urut -nacci dimulai dengan N yang. Selanjutnya, N harus bilangan bulat positif. Jadi tidak -1-nacci, dll.

Kasus uji:

1,1,1 -> 1
49, 97 -> 7
55, 89, 144 -> 2
1 -> 1
6765 -> 2
12, 23, 45, 89 -> 12
100, 199 -> 100
Cyoce
sumber
1
create a black hole (as long as this black hole does not produce anything that could be mistaken for valid output).Ya ampun, spiral lubang hitam bertemu dengan rasio emas! Itu harus output yang valid untuk urutan duoacci!
Conor O'Brien
1
@ CᴏɴᴏʀO'Bʀɪᴇɴ Ini mungkin rasio emas yang indah, tapi JANGAN mendekati lubang hitam! youtube.com/watch?v=TTUQyEr-sg0
Level River St
1
Ya ampun, ini jauh lebih sulit daripada yang saya kira awalnya ...
GamrCorps
@ mbomb007 apa perbedaan antara bilangan bulat positif dan bilangan asli?
Bukan Charles
1
@ mbomb007 ah. Saya pikir 1 adalah bilangan alami pertama. Saya pasti berpikir untuk menghitung angka
Bukan Charles

Jawaban:

7

Ruby, 94

Saya cukup terkejut seberapa jauh saya bisa bermain golf ini dalam algoritma yang sama! Saya mulai dengan lebih dari 200!

->a{1.step.find{|s|x=[1]*(s+z=a.size)
x<<x[-s,s].inject(:+)while x.max<a.max&&s>1
x[-z,z]==a}}

Tidak Disatukan:

l=->a{
    # ooh! a built-in infinite incrementer!
    1.step.find{|s|
        # if n == 1, z is important, otherwise s.
        x=[1]*(s+z=a.size)
        ## add the next nacci number until we hit or overshot max. 
        ## if s == 1, we don't increment, so don't bother
        x<<x[-s,s].inject(:+)while x.max<g&&s>1
        # eval to true if there's a match, false if not
        x[-z,z]==a
    }
}
Bukan itu Charles
sumber
Bagaimana cara x=[1]*(s+z=a.size)kerjanya?
Cyoce
@Cyoce Jika n == 1, maka kita tidak akan pernah naik, jadi kita perlu array 1 berapa lama inputnya. Jika n > 1, maka kita membutuhkan setidaknya n1 untuk urutannya. Jadi s+a.sizemencakup n == 1untuk setiap panjang a, dan itu mencakup awal dari urutan lain sehingga kita bisa mulai menambahkan sangka dari batt. Apakah itu masuk akal?
Bukan karena Charles
@Cyoce dan jika Anda mengajukan pertanyaan yang berbeda, di Ruby, [1]*numberberikan array 1 dengan panjang number. Jadi x=[1]*(s+z=a.size)tetapkan a.sizeke z, lalu tetapkan ke xarray dengan panjang 1's s+z.
Bukan berarti Charles
3

Python 2, 176 byte

def r(n,x):i,f=n,[1]*n;exec"f+=sum(f[i-n:]),;i+=1;"*(x-n);return f
l=input()
m=max(l)+len(l)
for i in range(1,m):
 if any(l==r(i,m)[b:b+len(l)]for b in range(m)):print i;break;

Perhatikan bahwa ini membutuhkan input dalam format ini:

[1, 1, 2, 3...]

daripada

1, 1, 2, 3...

Solusi yang cukup mudah, hanya untuk membuat segalanya bergulir. Saya akan bekerja lebih banyak untuk bermain golf setelah orang lain menjawab. Ini menggunakan versi generator N-Bonnaci yang sedikit dimodifikasi dari jawaban @ Data , jadi bantu dia. Kemudian untuk setiap N-Bonnaci dalam kisaran input, periksa apakah input tersebut merupakan urutan selanjutnya.

DJMcMayhem
sumber
coba saran yang sama yang saya berikan kepadanya: ganti f.appenduntukf+=
Cyoce
@ Ayo oh, ya. Aku tidak percaya aku melewatkan sesuatu yang mendasar. fp
DJMcMayhem
Apakah trailing itu ;perlu?
Cyoce
1

Lua, 324 323 Bytes

Ketika saya melihat kiriman lainnya, saya merasa ada yang salah dengan kode saya ... Tapi kemudian, saya ingat itu Lua, dan tidak ada semua fungsi mewah ini: '(

Itu sangat menyenangkan, butuh waktu sebenarnya.

Sunting: Disimpan 1 byte dengan trik sederhana: menggunakan ::label::+ goto labelsebagai ganti infinite loop dilakukan dengan while''.

function f(l)c=2 y,z=table.remove,os.exit while(l[1]<2)do y(l,1)if(#l<1)then print(1)z()end end ::q:: a={}for i=1,c do a[i]=1 end b={}for i=1,#l do b[i]=l[i]end while(a[#a]<b[1])do x=0 for i=(#a-c+1>0 and #a-c+1 or 1),#a do x=x+a[i]end a[#a+1]=x if a[#a]==b[1]then y(b,1)end if #b<1 then print(c)z()end end c=c+1 goto q end

Tidak Disatukan dan Penjelasan

Lua tidak memiliki cara untuk mendefinisikan set, subset, atau bahkan memeriksa apakah array / tabel berisi nilai tanpa menggunakan indeks / kunci. Itu sebabnya saya memutuskan untuk menghapus elemen dari array yang saya ambil sebagai parameter. begitulah cara saya mencatat elemen mana yang telah dihitung, dan jika cocok.

  function f(l)
  c=2
  y,z=table.remove,os.exit           -- Create pointers on table.remove and os.exit
                                     -- saves a total of 9 bytes
  while(l[1]<2)                      -- loop used to remove leading 1
  do 
    y(l,1)
    if(#l<1)                         -- we also check if it was a 1-only array
    then 
      print(1)                       -- if so, we print 1 and exit
      z()
    end 
  end

  ::q::                              -- label q, start of the infinite loop
    a={}for i=1,c do a[i]=1 end      -- fill an array with c 1s
    b={}for i=1,#l do b[i]=l[i]end   -- copy the sequence array
    while(a[#a]<b[1])                -- while max(a)<min(b)
    do
      x=0 for i=(#a-c+1>0            -- iterate from index a.length-c to
                    and #a-c+1       -- to a.length
                    or 1),#a 
      do 
        x=x+a[i]                     -- summing a's elements
      end
      a[#a+1]=x                      -- append x to a
      if a[#a]==b[1]then y(b,1)end   -- if x is equal ot a member of the sequence
                                     -- remove it
      if #b<1 then print(c)z()end    -- if b is empty, it means the subset is in a
                                     -- we print c and exit
    end                              -- else we loop again
    c=c+1                            -- with c+1
  goto q                             -- return to the start of this block
end

Anda dapat mencoba Lua online , dan Anda dapat menyalin / menempelkan contoh kode berikut untuk menjalankan beberapa tes. Ketika fungsi ini keluar ketika menemukan jawaban (infinite loop sebaliknya), Anda harus mengubah indeks yang test[]digunakan (jangan lupa lua adalah 1-diindeks :)).

function f(l)c=2 y,z=table.remove,os.exit while(l[1]<2)do y(l,1)if(#l<1)then print(1)z()end end ::q:: a={}for i=1,c do a[i]=1 end b={}for i=1,#l do b[i]=l[i]end while(a[#a]<b[1])do x=0 for i=(#a-c+1>0 and #a-c+1 or 1),#a do x=x+a[i]end a[#a+1]=x if a[#a]==b[1]then y(b,1)end if #b<1 then print(c)z()end end c=c+1 goto q end

test={{1,1,1},
{49, 97},
{55, 89, 144},
{1},
{6765},
{12, 23, 45, 89},
{100, 199}}

print(f(test[1]))
Katenkyo
sumber