Binarna sekwencja trójkąta Sierpińskiego jest sekwencją liczb, których reprezentacje binarne dają rzędy binarnego trójkąta Sierpińskiego, którą podaje się zaczynając od 1 w nieskończonym rzędzie zer, a następnie wielokrotnie zastępując każdą parę bitów xor tych bitów , tak jak:
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
Więcej cyfr podano w OEIS: https://oeis.org/A001317
Dane wejściowe: nieujemna liczba całkowita n w dowolnym formacie. (Musi działać dla wszystkich n do 30.)
Wyjście: n-ty składnik (indeksowany 0) sekwencji jako liczba dziesiętna.
To jest golf golfowy, więc postaraj się udzielić najkrótszej odpowiedzi w bajtach, jaką potrafi Twój język. Żadna odpowiedź nie zostanie zaakceptowana. Obowiązują standardowe luki (np. Brak kodowania sekwencji na stałe), z wyjątkiem ciebie mogą używać języka utworzone / zmodyfikowane po to wyzwanie została wysłana. (Unikaj publikowania innego rozwiązania w języku, który był już używany, chyba że twoje rozwiązanie jest krótsze).
Tabela liderów
Fragment kodu na dole tego postu generuje katalog na podstawie odpowiedzi a) jako listy najkrótszych rozwiązań według języka oraz b) jako ogólnej tabeli wyników.
Aby upewnić się, że twoja odpowiedź się pojawi, zacznij od nagłówka, korzystając z następującego szablonu Markdown:
## Language Name, N bytes
gdzie N
jest rozmiar twojego zgłoszenia. Jeśli poprawić swój wynik, to może zachować stare porachunki w nagłówku, uderzając je przez. Na przykład:
## Ruby, <s>104</s> <s>101</s> 96 bytes
Jeśli chcesz umieścić w nagłówku wiele liczb (np. Ponieważ twój wynik to suma dwóch plików lub chcesz osobno wymienić kary za flagi tłumacza), upewnij się, że rzeczywisty wynik jest ostatnią liczbą w nagłówku:
## Perl, 43 + 2 (-p flag) = 45 bytes
Możesz także ustawić nazwę języka jako link, który pojawi się we fragmencie:
## [><>](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
dla której nic się nie przelewa.Odpowiedzi:
05AB1E ,
54 bajtówZ dumą przedstawiam wam, 05AB1E. Chociaż jest bardzo krótki, prawdopodobnie jest bardzo zły przy długich wyzwaniach.
Dzięki produktom ETH za golenie 1 bajtu :)
Wyjaśnienie:
źródło
}
automatyczne wstawianie trailingu . To byłyby 4 bajty. :)Pari / GP , 27 bajtów
Funkcja przyjmuje n-tą potęgę wielomianu x + 1 w pierścieniu F 2 [x], podnosi ją do Z [x], a następnie ocenia na 2.
Wypróbuj online!
źródło
Galaretka , 6 bajtów
Wypróbuj online!
Wersja binarna, która działa z tą wersją interpretera Jelly, ma zrzut xxd
Jak to działa
źródło
Haskell, 44 bajty
W
((->) r)
monadzie(f >>= g) x
równa sięg (f x) x
.źródło
(iterate((2*)>>=xor)1!!)
Matlab, 45 bajtów
Rozwiązanie:
Test:
Objaśnienie:
pascal
konstruuje trójkąt Pascala, ale zaczyna się od 1, więc wejście powinno byći+1
.fliplr
odwraca tablicę od lewej do prawej.mod(_,2)
przyjmuje resztę po podzieleniu przez 2.diag
wyodrębnia główną przekątną. Mnożenie za pomocą2.^[0:i]
przekształca wektor na dziesiętnyCieszę się, @flawr, że znalazłem tutaj konkurenta Matlaba :)
źródło
JavaScript (ES6), 23 bajty
Na podstawie pierwszej formuły na stronie OEIS. Jeśli nie przeszkadza ci to, że kod zajmuje prawie wieczność, gdy dane wejściowe wynoszą 30, możemy zgolić bajt:
Oto wersja nierekurencyjna, wykorzystująca
for
pętlę weval
: (32 bajty)źródło
f(35)
zwraca15
. Ponadto, ostrzeżenie o bombach widłowych: musiałem wymusić zamknięcie Chromium, aby zatrzymaćf(30)
(oryginalną wersję) od uruchomienia. : Pf=x=>x?(y=f(x-(x<31)))^y*2:1
działałoby.Matlab,
7770 bajtówTa funkcja oblicza n-ty rząd trójkąta Pascala za pomocą powtarzalnego splotu z
[1,1]
(aka ekspansji dwumianowej lub powtarzanego mnożenia przez dwumianowy) i na tej podstawie oblicza liczbę.źródło
Rubinowy, 26 bajtów
anonimowa funkcja z iteracją.
ta funkcja rekurencyjna jest o jeden bajt krótsza, ale ponieważ należy ją nazwać, aby móc się do niej odwoływać, kończy się o jeden bajt dłużej.
źródło
Rubin, 25 bajtów
Krótszy niż inne dotychczasowe odpowiedzi tutaj. Konstruuje ten ciąg:
Następnie ustawia się
n=1
(dzieje się tak podczas tworzenia łańcucha) i ocenia powyższy ciąg, zwracając wynik.źródło
*n=1
naprawdę cos oszczędzam=1;"m^=2*"*n+?1
Samau , 4 bajty
Teraz Samau ma wbudowane funkcje mnożenia XOR i mocy XOR.
Zrzut szesnastkowy (Samau używa kodowania CP737):
Wyjaśnienie:
źródło
▌
odczytuje liczbę z ciągu. Jeśli zamienimy pierwsze dwa polecenia, spróbuje odczytać liczbę3
, która nie jest łańcuchem.CJam, 10 bajtów
Sprawdź to tutaj.
Proste iteracyjne rozwiązanie wykorzystujące bitowe XOR.
źródło
Pure Bash (bez zewnętrznych narzędzi), 37
Liczby całkowite Bash są podpisane 64-bit, więc działa to na dane wejściowe do 62 włącznie:
źródło
Python 2.7.6,
3833 bajtówDzięki Dennisowi za zgolenie kilku bajtów!
źródło
exec'x^=x*2;'*input()
oszczędza kilka bajtów nadfor
podejściem.f=lambda n:f(n-1)^2*f(n-1)if n>0 else 1
Pyth, 7 bajtów
Wypróbuj online: demonstracja
Wyjaśnienie:
źródło
Perl 5, 23 bytes
Try it online!
źródło
MIPS, 28 bytes
Input in
$a0
, output in$v0
.źródło
Mathematica,
4024 bytesźródło
k4, 26 bytes
0b\:
converts a number to a boolean vector (i.e. bitstring), XOR is implemented as "not equal",2/:
converts a bitstring back to a number by treating it as a polynomial to evaluate, andx f/y
withx
an integer isf
applied toy
first, and then to its successive outputsx
times.Sample run:
źródło
Ruby,
3126 bytesEDIT: Changed to a different language entirely! All golfing suggestions welcome!
This program bitwise XORs the previous element of the sequence with twice itself, i.e.
f(n) = f(n-1) ^ 2*f(n-1)
.źródło
MATL, 15 bytes
Similar to @flawr's answer:
EDIT (May 20, 2016) Try it online! with
X+
replaced byY+
to conform to version 18.0.0 of the language.Example
Explanation
źródło
brainfuck, 87 bytes
Try it online!
Assumes infinite sized cells (otherwise it can’t get past 7, which is conveniently 255). The Pascal’s triangle mod 2 method is actually much longer because of the costly mod 2 operation, while XOR is much easier to implement.
źródło
APL, 31 bytes
This is almost certainly awful code, but I'm a complete APL newb. I expect anyone with any skill could get rid of all the D-functions and shorten it considerably. The logic is more or less the same as my
k4
answer -- multiply by1
or2
, convert to bits with⊤
, XOR using not equals, convert back to a number with⊥
, wrap the whole thing in a function and ask for a specific number of iterations using⍣
. I have no idea why the result coming out of the inner product is enclosed, but⊃
cleans that up.źródło
~1 2=.
to1 2≠.
{({2⊥⊃1 2≠.((64⍴2)⊤×)⍵}⍣⍵)1}
[28 bytes]Seriously, 12 bytes
Hex Dump:
Try it online
Since Seriously does not include any means of doing a bitwise xor, this solution takes the challenge completely literally, directly computing the given row of the triangle. This method gives correct answers up to n=1029 (after which there is not enough memory to compute the given row of Pascal's triangle).
Explanation:
źródło
Pyt,
4010 bytesExplanation:
Observing that the Binary Sierpinski Triangle is equivalent to Pascal's Triangle mod 2,
Try it online!
źródło
Stax, 5 bytes
Run and debug online!
Port of the Jelly answer.
Uses ASCII representation to explain:
źródło