Hitung Urutan Segitiga Binary Sierpinski

23

Urutan Binary Sierpinski Triangle adalah urutan angka yang representasi binernya memberikan barisan Binary Sierpinski Triangle, yang diberikan dengan memulai dengan 1 dalam deretan nol tanpa batas, kemudian berulang kali mengganti setiap pasangan bit dengan xor bit-bit tersebut. , seperti:

f(0)=      1                    =1
f(1)=     1 1                   =3
f(2)=    1 0 1                  =5
f(3)=   1 1 1 1                 =15
f(4)=  1 0 0 0 1                =17

Lebih banyak digit diberikan di OEIS: https://oeis.org/A001317

Input: Bilangan bulat non-negatif dalam format apa pun yang Anda suka. (Harus bekerja untuk semua hingga 30.)

Output: Istilah ke-n (0-diindeks) dari urutan sebagai angka desimal.

Ini adalah jadi coba berikan jawaban terpendek dalam byte yang mampu digunakan bahasa Anda. Tidak ada jawaban yang akan diterima. Celah standar berlaku (mis. Tidak ada pengodean urutan), kecuali bahwa Anda dapat menggunakan bahasa yang dibuat / dimodifikasi setelah tantangan ini diposting. (Jangan menghindari memposting solusi lain dalam bahasa yang telah digunakan kecuali jika solusi Anda lebih pendek.)

Papan peringkat

Cuplikan Stack di bagian bawah posting ini menghasilkan katalog dari jawaban a) sebagai daftar solusi terpendek per bahasa dan b) sebagai leaderboard keseluruhan.

Untuk memastikan bahwa jawaban Anda muncul, silakan mulai jawaban Anda dengan tajuk utama, menggunakan templat Penurunan harga berikut:

## Language Name, N bytes

di mana Nukuran kiriman Anda. Jika Anda meningkatkan skor Anda, Anda bisa menyimpan skor lama di headline, dengan mencoretnya. Contohnya:

## Ruby, <s>104</s> <s>101</s> 96 bytes

Jika Anda ingin memasukkan beberapa angka dalam tajuk Anda (mis. Karena skor Anda adalah jumlah dari dua file atau Anda ingin membuat daftar hukuman penterjemah secara terpisah), pastikan bahwa skor sebenarnya adalah angka terakhir di tajuk:

## Perl, 43 + 2 (-p flag) = 45 bytes

Anda juga dapat membuat nama bahasa menjadi tautan yang kemudian akan muncul di cuplikan:

## [><>](http://esolangs.org/wiki/Fish), 121 bytes

kuintopia
sumber
8
Saya bukan penggemar berat harus tidak menghasilkan jawaban yang salah untuk n . Ini pada dasarnya memaksa bahasa yang tidak menggunakan bilangan bulat presisi arbitrer secara default untuk memeriksa apakah inputnya cukup kecil ...
Dennis
Harap klarifikasi jika memahami aturan dengan benar (lihat komentar di sini dan di sini ) dan jika output bulat (mis. 1.288490189e10 untuk input 33) dianggap salah .
Dennis
"Harus bekerja untuk semua n hingga 30, dan tidak boleh menghasilkan jawaban yang salah untuk n." . Ini kontradiktif dengan diri sendiri - tentunya "tidak boleh mengeluarkan jawaban yang salah" sama dengan "Harus bekerja" ???
Digital Trauma
5
Karena oposisi rakyat yang sangat besar terhadap beban validasi input yang tidak masuk akal dan menghancurkan jiwa, persyaratan ini telah dihapus. Anda dapat menampilkan sampah apa pun yang Anda inginkan untuk besar n. Nikmati!
kuintopia
2
Daripada mengatakan bahwa output seharusnya tidak salah, saya akan merekomendasikan hanya mengatakan bahwa pengiriman harus mendukung input hingga yang terbesar nyang tidak ada yang meluap.
Alex A.

Jawaban:

14

05AB1E , 5 4 byte

Saya dengan bangga mempersembahkan untuk Anda, 05AB1E. Meskipun sangat pendek, mungkin sangat buruk pada tantangan yang panjang.

Terima kasih kepada ETHproductions untuk mencukur 1 byte :)

$Fx^

Penjelasan:

$      # Pushes 1 and input
 F     # Pops x, creates a for-loop in range(0, x)
  x    # Pops x, pushes x and 2x
   ^   # Bitwise XOR on the last two elements
       # Implicit, ends the for-loop
       # Implicit, nothing has printed so the last element is printed automatically
Adnan
sumber
Anda tahu, cara yang baik untuk bermain golf byte dari banyak program dalam bahasa kustom adalah membuat trailing }secara otomatis dimasukkan. Maka ini akan menjadi 4 byte. :)
ETHproductions
1
@ ETHproductions Tunggu sebentar, itu sudah diterapkan :). Terima kasih telah mencukur 1 byte haha.
Adnan
2
Ada bug dalam kode ini. Bagaimana aku tahu? Ini mengalahkan Dennis.
Arcturus
2
@ Ampora Tidak hanya mengalahkan Dennis, ia mengalahkan bahasa golf kebiasaan Dennis. ;)
ETHproductions
@ Adnan Wow. Anda sedang melakukan sesuatu.
RK.
12

Pari / GP , 27 byte

n->lift(Mod(x+1,2)^n)%(x-2)

Fungsi mengambil n-th kekuatan polinomial x + 1 di ring F 2 [x], mengangkatnya ke Z [x], dan kemudian mengevaluasi itu pada 2.

Cobalah online!

alephalpha
sumber
6

Jelly , 6 byte

1Ḥ^$³¡

Cobalah online!

Versi biner yang berfungsi dengan revisi penerjemah Jelly ini memiliki dump xxd

0000000: 31 a8 5e 24 8b 80  1.^$..

Bagaimana itu bekerja

1Ḥ^$³¡    Input: n

1         Set the left argument to 1.
 Ḥ        Multiple the left argument by two.
  ^       Hook; XOR it with its initial value.
   $      Create a monadic chain from the last two insructions.
    ³¡    Call the chain n times, updating the left argument after each call.
Dennis
sumber
5

Haskell, 44 byte

import Data.Bits
f n=iterate((2*)>>=xor)1!!n

Di ((->) r)monad, (f >>= g) xsama dengan g (f x) x.

Lynn
sumber
Saya pikir Anda dapat menganonimkan baris terakhir ke(iterate((2*)>>=xor)1!!)
xnor
Saya mencobanya, tetapi tidak berhasil, karena alasan pembatasan monomorfisme yang menakutkan .
Lynn
Namun, itu mungkin berlaku sebagai ekspresi hukum, karena pembatasan monomorfisme tidak berlaku pada ekspresi, tetapi deklarasi. Dan ekspresi dianggap sebagai jawaban hukum, jika saya tidak salah.
haskeller bangga
4

Matlab, 45 byte

Larutan:

@(i)2.^[0:i]*diag(mod(fliplr(pascal(i+1)),2))

Uji:

ans(10)
ans =
1285

Penjelasan: pascalmembangun segitiga Pascal, tetapi dimulai dari 1, jadi input seharusnya i+1. fliplrmembalik array dari kiri ke kanan. mod(_,2)Dibutuhkan sisa setelah pembagian dengan 2. diagmengekstrak diagonal utama. Penggandaan menggunakan 2.^[0:i]konversi vektor ke desimal

Saya senang, @ flawr saya menemukan pesaing Matlab di sini :)

brainkz
sumber
Tampaknya bekerja dengan Oktaf juga.
Dennis
4

JavaScript (ES6), 23 byte

f=x=>x?(y=f(x-1))^y*2:1

Berdasarkan formula pertama pada halaman OEIS. Jika Anda tidak keberatan kode menghabiskan hampir selamanya untuk menyelesaikan untuk input 30, kami dapat memotong satu byte:

f=x=>x?f(--x)^f(x)*2:1

Berikut adalah versi non-rekursif, menggunakan forloop dalam eval: (32 byte)

x=>eval("for(a=1;x--;a^=a*2);a")
Produksi ETH
sumber
Aturan, seperti yang ditulis saat ini, membatalkan jawaban ini, sejak f(35)kembali 15. Juga, peringatan bom fork: Saya harus menutup paksa Chromium untuk berhenti f(30)(revisi asli) agar tidak berjalan. : P
Dennis
1
@ Dennis Tunggu, jadi jika saya tidak dapat menampilkan nilai yang salah, apa yang harus saya lakukan dengan input yang lebih tinggi dari 30?
ETHproductions
Saya tidak yakin (dan saya harap aturannya diubah ), tetapi sesuatu seperti itu f=x=>x?(y=f(x-(x<31)))^y*2:1akan berhasil.
Dennis
@ Dennis Ah, berulang berulang = tidak ada output. Saya akan memperbaikinya ketika saya kembali ke komputer saya. Saya berharap aturan itu berubah juga.
ETHproduk
Aturan telah dihapus dari pertanyaan.
Dennis
3

Matlab, 77 70 byte

Fungsi ini menghitung deretan ke-n dari segitiga Pascal melalui konvolusi berulang dengan [1,1](alias ekspansi binomial atau perkalian berulang dengan binomial), dan menghitung angka dari itu.

function r=c(n);k=1;for i=1:n;k=conv(k,[1,1]);end;r=2.^(0:n)*mod(k,2)'
cacat
sumber
3

Ruby, 26 byte

fungsi anonim dengan iterasi.

->n{a=1;n.times{a^=a*2};a}

fungsi rekursif ini satu byte lebih pendek, tetapi karena perlu dinamai untuk dapat merujuk pada dirinya sendiri, ia berakhir satu byte lebih lama.

f=->n{n<1?1:(s=f[n-1])^s*2}
Level River St
sumber
3

Ruby, 25 byte

->n{eval"n^=2*"*n+?1*n=1}

Lebih pendek dari jawaban lain di sini sejauh ini. Itu membangun string ini:

n^=2*n^=2*n^=2*n^=2*1

Lalu set n=1(ini benar-benar terjadi saat string sedang dibuat) dan mengevaluasi string di atas, mengembalikan hasilnya.

Lynn
sumber
Apakah itu *n=1benar - benar menyelamatkan sesuatum=1;"m^=2*"*n+?1
Martin Ender
Tidak, tetapi melakukannya hanya dengan satu variabel sangat mencolok :)
Lynn
3

Samau , 4 byte

Sekarang Samau memiliki fungsi bawaan untuk perkalian XOR dan daya XOR.

▌3$ⁿ

Hex dump (Samau menggunakan pengkodean CP737):

dd 33 24 fc

Penjelasan:

▌       read a number
 3      push 3
  $     swap
   ⁿ    take the XOR power
alephalpha
sumber
Mungkinkah ini dikurangi menjadi 3 byte dengan menukar dua perintah pertama dan menghilangkan swap?
kuintopia
@quintopia No. Samau secara otomatis mendorong input ke stack sebagai string, dan membaca angka dari string. Jika kita menukar dua perintah pertama, itu akan mencoba membaca nomor dari 3, yang bukan string.
alephalpha
mengapa tidak samau mencoba untuk mengevaluasi string jika memungkinkan?
kuintopia
2

CJam, 10 byte

1ri{_2*^}*

Uji di sini.

Solusi iteratif sederhana menggunakan bitor XOR.

Martin Ender
sumber
2

Bash Murni (tanpa utilitas eksternal), 37

Bash integer ditandatangani 64-bit, jadi ini berfungsi untuk input hingga dan termasuk 62:

for((x=1;i++<$1;x^=x*2)){
:
}
echo $x
Trauma Digital
sumber
2

Python 2.7.6, 38 33 byte

Terima kasih kepada Dennis karena telah memangkas beberapa byte!

x=1
exec'x^=x*2;'*input()
print x
MCS-Kaijin
sumber
1
Selamat Datang di Programming Puzzles & Code Golf! exec'x^=x*2;'*input()menghemat beberapa byte selama forpendekatan.
Dennis
Ini mengalahkan entri Python saya, yang saya akan tinggalkan di sini untuk anak cucu:f=lambda n:f(n-1)^2*f(n-1)if n>0 else 1
Jack Brounstein
2

Pyth, 7 byte

uxyGGQ1

Cobalah online: Demonstrasi

Penjelasan:

u    Q1   apply the following statement input-times to G=1:
 xyGG        update G with (2*G xor G)
Jakube
sumber
2

MIPS, 28 byte

Input masuk $a0, keluaran masuk $v0.

0x00400004  0x24020001          li      $v0, 1
0x00400008  0x10800005  loop:   beqz    $a0, exit
0x0040000c  0x00024021          move    $t0, $v0
0x00400010  0x00021040          sll     $v0, $v0, 1
0x00400014  0x00481026          xor     $v0, $v0, $t0
0x00400018  0x2084ffff          addi    $a0, $a0, -1
0x0040001c  0x08100002          j       loop
qwr
sumber
1

Mathematica, 40 24 byte

Nest[BitXor[#,2#]&,1,#]&
alephalpha
sumber
1

k4, 26 byte

{x{2/:~(=). 0b\:'1 2*x}/1}

0b\:mengubah angka menjadi vektor boolean (yaitu bitstring), XOR diimplementasikan sebagai "tidak sama", 2/:mengubah bitstring kembali ke angka dengan memperlakukannya sebagai polinomial untuk mengevaluasi, dan x f/ydengan xbilangan bulat fditerapkan ypertama, dan kemudian ke output berturut-turut xkali.

Contoh dijalankan:

  {x{2/:~(=). 0b\:'1 2*x}/1}'!5                                                                                                                                                                                    
1 3 5 15 17
Aaron Davies
sumber
1

Ruby, 31 26 byte

EDIT: Diubah ke bahasa yang berbeda sama sekali! Semua saran golf, selamat datang!

Program ini bitwise XOR elemen sebelumnya dari urutan dengan dua kali sendiri, yaitu f(n) = f(n-1) ^ 2*f(n-1).

->n{v=1;n.times{v^=2*v};v}
Sherlock9
sumber
1

MATL , 15 byte

Mirip dengan jawaban @ flawr :

i:1w"TToX+]2\XB

EDIT (20 Mei 2016) Cobalah online! dengan X+digantikan oleh Y+agar sesuai dengan versi 18.0.0 bahasa.

Contoh

>> matl i:1w"TToX+]2\XB
> 5
51

Penjelasan

i              % input                                                     
:              % vector of values 1, 2, ... to previous input                           
1              % number literal                                            
w              % swap elements in stack                                    
"              % for                                                       
    TTo        % vector [1 1]
    X+         % convolution                                               
]              % end                                                       
2\             % modulo 2
XB             % convert from binary to decimal              
Luis Mendo
sumber
1

brainfuck , 87 byte

,[>>[>]++<[[->+>+<<]>-->[-<<+>>]<[>+<-[>-<-]]>+<<<]>>>[[-<+>]>]<<[<]<-]>>[<[->++<]>>]<+

Cobalah online!

Diasumsikan sel berukuran tak terbatas (jika tidak, ia tidak bisa melewati 7, yang berarti 255). Metode segitiga mod 2 Pascal sebenarnya jauh lebih lama karena operasi mod 2 yang mahal, sedangkan XOR jauh lebih mudah diimplementasikan.

Jo King
sumber
0

APL, 31 byte

{({2⊥⊃~1 2=.{(64⍴2)⊤⍺×⍵}⍵}⍣⍵)1}

Ini hampir pasti kode yang mengerikan, tapi saya seorang pemula APL yang lengkap. Saya berharap siapa pun dengan keterampilan apa pun dapat menyingkirkan semua fungsi-D dan mempersingkatnya. Logikanya kurang lebih sama dengan sayak4 jawaban - kalikan dengan 1atau 2, konversikan ke bit dengan , XOR menggunakan tidak sama dengan, konversikan kembali ke angka dengan , bungkus semuanya dalam suatu fungsi dan minta jumlah iterasi tertentu menggunakan . Saya tidak tahu mengapa hasil yang keluar dari produk dalam tertutup, tetapi membersihkannya.

Aaron Davies
sumber
Anda harus dapat menyimpan byte dengan mengubah ~1 2=.ke1 2≠.
Zacharý
Dan, di mana sistem APL ini? Jika ada di Dyalog, Anda harus bisa membuatnya {({2⊥⊃1 2≠.((64⍴2)⊤×)⍵}⍣⍵)1}[28 byte]
Zacharý
0

Serius, 12 byte

2,╣`2@%`Mεj¿

Hex Dump:

322cb960324025604dee6aa8

Cobalah online

Karena Serius tidak termasuk cara melakukan bitwise xor, solusi ini mengambil tantangan sepenuhnya secara harfiah, langsung menghitung deretan segitiga yang diberikan. Metode ini memberikan jawaban yang benar hingga n = 1029 (setelah itu tidak ada cukup memori untuk menghitung baris yang diberikan dari segitiga Pascal).

Penjelasan:

 ,                       get input
  ╣                 push the nth row of pascal's triangle
   `2@%`M           take each element of the row mod 2
         εj         join all the binary digits into a string
2          ¿        interpret it as a base 2 number
kuintopia
sumber
0

Pyt , 40 10 byte

Đ0⇹Řć2%ǰ2Ĩ

Penjelasan:

Mengamati bahwa Binary Sierpinski Triangle setara dengan Pascal's Triangle mod 2,

                      Implicit input
Đ                     Duplicate input
 0⇹Ř                  Push [0,1,2,...,input]
    ć2%               Calculate the input-th row of Pascal's Triangle mod 2
       ǰ              Join elements of the array into a string
        2Ĩ            Interpret as a binary number
                      Implicit print

Cobalah online!

mudkip201
sumber
0

Stax , 5 byte

±s┤ε─

Jalankan dan debug online!

Port jawaban Jelly.

Menggunakan representasi ASCII untuk menjelaskan:

ODcH|^
O         Put 1 under top of stack
 D        Repeat for times specified by input
  cH|^    Xor the number with itself doubled
          Implicit output
Weijun Zhou
sumber