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 kode-golf 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 N
ukuran 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
/* Configuration */
var QUESTION_ID = 67497; // Obtain this from the url
// It will be like http://XYZ.stackexchange.com/questions/QUESTION_ID/... on any question page
var ANSWER_FILTER = "!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe";
var COMMENT_FILTER = "!)Q2B_A2kjfAiU78X(md6BoYk";
var OVERRIDE_USER = 47050; // This should be the user ID of the challenge author.
/* App */
var answers = [], answers_hash, answer_ids, answer_page = 1, more_answers = true, comment_page;
function answersUrl(index) {
return "http://api.stackexchange.com/2.2/questions/" + QUESTION_ID + "/answers?page=" + index + "&pagesize=100&order=desc&sort=creation&site=codegolf&filter=" + ANSWER_FILTER;
}
function commentUrl(index, answers) {
return "http://api.stackexchange.com/2.2/answers/" + answers.join(';') + "/comments?page=" + index + "&pagesize=100&order=desc&sort=creation&site=codegolf&filter=" + COMMENT_FILTER;
}
function getAnswers() {
jQuery.ajax({
url: answersUrl(answer_page++),
method: "get",
dataType: "jsonp",
crossDomain: true,
success: function (data) {
answers.push.apply(answers, data.items);
answers_hash = [];
answer_ids = [];
data.items.forEach(function(a) {
a.comments = [];
var id = +a.share_link.match(/\d+/);
answer_ids.push(id);
answers_hash[id] = a;
});
if (!data.has_more) more_answers = false;
comment_page = 1;
getComments();
}
});
}
function getComments() {
jQuery.ajax({
url: commentUrl(comment_page++, answer_ids),
method: "get",
dataType: "jsonp",
crossDomain: true,
success: function (data) {
data.items.forEach(function(c) {
if (c.owner.user_id === OVERRIDE_USER)
answers_hash[c.post_id].comments.push(c);
});
if (data.has_more) getComments();
else if (more_answers) getAnswers();
else process();
}
});
}
getAnswers();
var SCORE_REG = /<h\d>\s*([^\n,<]*(?:<(?:[^\n>]*>[^\n<]*<\/[^\n>]*>)[^\n,<]*)*),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/;
var OVERRIDE_REG = /^Override\s*header:\s*/i;
function getAuthorName(a) {
return a.owner.display_name;
}
function process() {
var valid = [];
answers.forEach(function(a) {
var body = a.body;
a.comments.forEach(function(c) {
if(OVERRIDE_REG.test(c.body))
body = '<h1>' + c.body.replace(OVERRIDE_REG, '') + '</h1>';
});
var match = body.match(SCORE_REG);
if (match)
valid.push({
user: getAuthorName(a),
size: +match[2],
language: match[1],
link: a.share_link,
});
else console.log(body);
});
valid.sort(function (a, b) {
var aB = a.size,
bB = b.size;
return aB - bB
});
var languages = {};
var place = 1;
var lastSize = null;
var lastPlace = 1;
valid.forEach(function (a) {
if (a.size != lastSize)
lastPlace = place;
lastSize = a.size;
++place;
var answer = jQuery("#answer-template").html();
answer = answer.replace("{{PLACE}}", lastPlace + ".")
.replace("{{NAME}}", a.user)
.replace("{{LANGUAGE}}", a.language)
.replace("{{SIZE}}", a.size)
.replace("{{LINK}}", a.link);
answer = jQuery(answer);
jQuery("#answers").append(answer);
var lang = a.language;
lang = jQuery('<a>'+lang+'</a>').text();
languages[lang] = languages[lang] || {lang: a.language, lang_raw: lang, user: a.user, size: a.size, link: a.link};
});
var langs = [];
for (var lang in languages)
if (languages.hasOwnProperty(lang))
langs.push(languages[lang]);
langs.sort(function (a, b) {
if (a.lang_raw.toLowerCase() > b.lang_raw.toLowerCase()) return 1;
if (a.lang_raw.toLowerCase() < b.lang_raw.toLowerCase()) return -1;
return 0;
});
for (var i = 0; i < langs.length; ++i)
{
var language = jQuery("#language-template").html();
var lang = langs[i];
language = language.replace("{{LANGUAGE}}", lang.lang)
.replace("{{NAME}}", lang.user)
.replace("{{SIZE}}", lang.size)
.replace("{{LINK}}", lang.link);
language = jQuery(language);
jQuery("#languages").append(language);
}
}
body { text-align: left !important}
#answer-list {
padding: 10px;
width: 290px;
float: left;
}
#language-list {
padding: 10px;
width: 290px;
float: left;
}
table thead {
font-weight: bold;
}
table td {
padding: 5px;
}
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>
<link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b">
<div id="language-list">
<h2>Shortest Solution by Language</h2>
<table class="language-list">
<thead>
<tr><td>Language</td><td>User</td><td>Score</td></tr>
</thead>
<tbody id="languages">
</tbody>
</table>
</div>
<div id="answer-list">
<h2>Leaderboard</h2>
<table class="answer-list">
<thead>
<tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr>
</thead>
<tbody id="answers">
</tbody>
</table>
</div>
<table style="display: none">
<tbody id="answer-template">
<tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr>
</tbody>
</table>
<table style="display: none">
<tbody id="language-template">
<tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr>
</tbody>
</table>
n
yang tidak ada yang meluap.Jawaban:
05AB1E ,
54 byteSaya dengan bangga mempersembahkan untuk Anda, 05AB1E. Meskipun sangat pendek, mungkin sangat buruk pada tantangan yang panjang.
Terima kasih kepada ETHproductions untuk mencukur 1 byte :)
Penjelasan:
sumber
}
secara otomatis dimasukkan. Maka ini akan menjadi 4 byte. :)Pari / GP , 27 byte
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!
sumber
Jelly , 6 byte
Cobalah online!
Versi biner yang berfungsi dengan revisi penerjemah Jelly ini memiliki dump xxd
Bagaimana itu bekerja
sumber
Haskell, 44 byte
Di
((->) r)
monad,(f >>= g) x
sama dengang (f x) x
.sumber
(iterate((2*)>>=xor)1!!)
Matlab, 45 byte
Larutan:
Uji:
Penjelasan:
pascal
membangun segitiga Pascal, tetapi dimulai dari 1, jadi input seharusnyai+1
.fliplr
membalik array dari kiri ke kanan.mod(_,2)
Dibutuhkan sisa setelah pembagian dengan 2.diag
mengekstrak diagonal utama. Penggandaan menggunakan2.^[0:i]
konversi vektor ke desimalSaya senang, @ flawr saya menemukan pesaing Matlab di sini :)
sumber
JavaScript (ES6), 23 byte
Berdasarkan formula pertama pada halaman OEIS. Jika Anda tidak keberatan kode menghabiskan hampir selamanya untuk menyelesaikan untuk input 30, kami dapat memotong satu byte:
Berikut adalah versi non-rekursif, menggunakan
for
loop dalameval
: (32 byte)sumber
f(35)
kembali15
. Juga, peringatan bom fork: Saya harus menutup paksa Chromium untuk berhentif(30)
(revisi asli) agar tidak berjalan. : Pf=x=>x?(y=f(x-(x<31)))^y*2:1
akan berhasil.Matlab,
7770 byteFungsi 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.sumber
Ruby, 26 byte
fungsi anonim dengan iterasi.
fungsi rekursif ini satu byte lebih pendek, tetapi karena perlu dinamai untuk dapat merujuk pada dirinya sendiri, ia berakhir satu byte lebih lama.
sumber
Ruby, 25 byte
Lebih pendek dari jawaban lain di sini sejauh ini. Itu membangun string ini:
Lalu set
n=1
(ini benar-benar terjadi saat string sedang dibuat) dan mengevaluasi string di atas, mengembalikan hasilnya.sumber
*n=1
benar - benar menyelamatkan sesuatum=1;"m^=2*"*n+?1
Samau , 4 byte
Sekarang Samau memiliki fungsi bawaan untuk perkalian XOR dan daya XOR.
Hex dump (Samau menggunakan pengkodean CP737):
Penjelasan:
sumber
▌
membaca angka dari string. Jika kita menukar dua perintah pertama, itu akan mencoba membaca nomor dari3
, yang bukan string.CJam, 10 byte
Uji di sini.
Solusi iteratif sederhana menggunakan bitor XOR.
sumber
Bash Murni (tanpa utilitas eksternal), 37
Bash integer ditandatangani 64-bit, jadi ini berfungsi untuk input hingga dan termasuk 62:
sumber
Python 2.7.6,
3833 byteTerima kasih kepada Dennis karena telah memangkas beberapa byte!
sumber
exec'x^=x*2;'*input()
menghemat beberapa byte selamafor
pendekatan.f=lambda n:f(n-1)^2*f(n-1)if n>0 else 1
Pyth, 7 byte
Cobalah online: Demonstrasi
Penjelasan:
sumber
Perl 5 , 23 byte
Cobalah online!
sumber
MIPS, 28 byte
Input masuk
$a0
, keluaran masuk$v0
.sumber
Mathematica,
4024 bytesumber
k4, 26 byte
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, danx f/y
denganx
bilangan bulatf
diterapkany
pertama, dan kemudian ke output berturut-turutx
kali.Contoh dijalankan:
sumber
Ruby,
3126 byteEDIT: 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)
.sumber
MATL , 15 byte
Mirip dengan jawaban @ flawr :
EDIT (20 Mei 2016) Cobalah online! dengan
X+
digantikan olehY+
agar sesuai dengan versi 18.0.0 bahasa.Contoh
Penjelasan
sumber
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.
sumber
APL, 31 byte
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 saya
k4
jawaban - kalikan dengan1
atau2
, 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.sumber
~1 2=.
ke1 2≠.
{({2⊥⊃1 2≠.((64⍴2)⊤×)⍵}⍣⍵)1}
[28 byte]Serius, 12 byte
Hex Dump:
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:
sumber
Pyt ,
4010 bytePenjelasan:
Mengamati bahwa Binary Sierpinski Triangle setara dengan Pascal's Triangle mod 2,
Cobalah online!
sumber
Stax , 5 byte
Jalankan dan debug online!
Port jawaban Jelly.
Menggunakan representasi ASCII untuk menjelaskan:
sumber