23

La séquence du triangle binaire de Sierpinski est la séquence de nombres dont les représentations binaires donnent les lignes du triangle binaire de Sierpinski, qui est donnée en commençant par un 1 dans une ligne infinie de zéros, puis en remplaçant de façon répétée chaque paire de bits par le xor de ces bits. , ainsi:

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

Plus de chiffres sont donnés à OEIS: https://oeis.org/A001317

Entrée: Un entier non négatif n dans le format de votre choix. (Doit fonctionner pour tous n jusqu'à 30.)

Sortie: Le nième terme (indexé 0) de la séquence sous forme de nombre décimal.

Il s'agit de code-golf , essayez donc de donner la réponse la plus courte en octets dont votre langue est capable. Aucune réponse ne sera acceptée. Les failles standard s'appliquent (par exemple, pas de codage en dur de la séquence), sauf que vous pouvez utiliser une langue créée / modifiée après la publication de ce défi. (Évitez de publier une autre solution dans une langue qui a déjà été utilisée, sauf si votre solution est plus courte.)

Classement

L'extrait de pile au bas de cet article génère le catalogue à partir des réponses a) en tant que liste des solutions les plus courtes par langue et b) en tant que classement général.

Pour vous assurer que votre réponse s'affiche, veuillez commencer votre réponse avec un titre, en utilisant le modèle Markdown suivant:

## Language Name, N bytes

où Nest la taille de votre soumission. Si vous améliorez votre score, vous pouvez conserver les anciens scores dans le titre, en les rayant. Par exemple:

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

Si vous souhaitez inclure plusieurs nombres dans votre en-tête (par exemple, parce que votre score est la somme de deux fichiers ou que vous souhaitez répertorier les pénalités de drapeau d'interprète séparément), assurez-vous que le score réel est le dernier numéro de l'en-tête:

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

Vous pouvez également faire du nom de la langue un lien qui apparaîtra ensuite dans l'extrait de code:

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

Afficher l'extrait de code

/* 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>

Expand snippet

code-golf sequence binary bitwise quintopie
la source

8

Je ne suis pas un grand fan de ne doit pas sortir une mauvaise réponse pour tout n . Cela oblige essentiellement les langages qui n'utilisent pas d'entiers de précision arbitraire par défaut à vérifier si l'entrée est suffisamment petite ...

Dennis

Veuillez clarifier si vous avez bien compris les règles (voir les commentaires ici et ici ) et si la sortie arrondie (par exemple, 1.288490189e10 pour l'entrée 33) compte comme incorrecte .

Dennis

"Doit fonctionner pour tous les n jusqu'à 30, et ne doit pas produire de mauvaise réponse pour tout n." . C'est contradictoire - sûrement "ne doit pas sortir une mauvaise réponse" est la même chose que "Doit fonctionner" ???

Digital Trauma

5

En raison de l'opposition populaire écrasante au fardeau déraisonnable et écrasant de la validation des entrées, cette exigence a été supprimée. Vous pouvez afficher les ordures que vous voulez pour les gros n Prendre plaisir!

quintopie

2

Plutôt que de dire que la sortie ne devrait pas être fausse, je recommanderais simplement de dire que les soumissions doivent prendre en charge l'entrée jusqu'à la plus grande npour laquelle rien ne déborde.

Alex A.

14

05AB1E , 5 4 octets

Je vous présente fièrement, 05AB1E. Bien qu'il soit très court, il est probablement très mauvais lors de longs défis.

Merci à ETHproductions d'avoir rasé 1 octet :)

$Fx^

Explication:

$      # 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
la source

Vous savez, un bon moyen d'exploiter un octet de nombreux programmes dans un langage personnalisé consiste à }insérer automatiquement un caractère de fin . Ce serait alors 4 octets. :)

ETHproductions

1

@ETHproductions Attendez une minute, cela a déjà été implémenté :). Merci d'avoir rasé 1 octet haha.

Adnan

2

Il y a un bug dans ce code. Comment puis-je savoir? Il bat Dennis.

Arcturus

2

@Ampora Non seulement il bat Dennis, mais il bat le langage de golf personnalisé de Dennis. ;)

ETHproductions

@Adnan Wow. Vous êtes sur quelque chose.

RK.

12

Pari / GP , 27 octets

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

La fonction prend la n-ième puissance du polynôme x + 1 dans l'anneau F ₂ [x], la porte à Z [x], puis l'évalue à 2.

Essayez-le en ligne!

alephalpha
la source

6

Gelée , 6 octets

1Ḥ^$³¡

Essayez-le en ligne!

La version binaire qui fonctionne avec cette révision de l'interpréteur Jelly a le vidage xxd

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

Comment ça marche

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
la source

5

Haskell, 44 octets

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

Dans la ((->) r)monade, c'est (f >>= g) xégal g (f x) x.

Lynn
la source

Je pense que vous pouvez anonymiser la dernière ligne pour(iterate((2*)>>=xor)1!!)

xnor

J'ai essayé cela, mais cela ne fonctionne pas, pour des raisons de restriction de monomorphisme redoutées .

Lynn

Cependant, cela pourrait s'appliquer en tant qu'expression légale, car la restriction du monomorphisme ne s'applique pas aux expressions, mais aux déclarations. Et les expressions sont considérées comme des réponses légales, si je ne me trompe pas.

fier haskeller

4

Matlab, 45 octets

Solution:

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

Tester:

ans(10)
ans =
1285

Explication: pascalconstruit un triangle Pascal, mais il commence à 1, donc l'entrée devrait l'être i+1.fliplrretourne le tableau de gauche à droite. mod(_,2)prend le reste après la division par 2. diagextrait la diagonale principale.2.^[0:i] convertit le vecteur en décimal

Je suis content, @flawr, d'avoir trouvé un concurrent Matlab ici :)

brainkz
la source

Semble également fonctionner avec Octave.

Dennis

4

JavaScript (ES6), 23 octets

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

Basé sur la première formule sur la page OEIS. Si cela ne vous dérange pas que le code prenne presque une éternité pour terminer pour une entrée de 30, nous pouvons raser un octet:

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

Voici une version non récursive, utilisant une forboucle dans un eval: (32 octets)

x=>eval("for(a=1;x--;a^=a*2);a")

ETHproductions
la source

Les règles, telles qu'elles sont actuellement écrites, invalident cette réponse, car elle f(35)revient 15. Aussi, alerte à la bombe à la fourche: j'ai dû forcer la fermeture de Chromium pour arrêter f(30)(révision d'origine) de fonctionner. : P

Dennis

1

@Dennis Attendez, donc si je ne peux pas sortir de valeur erronée, que dois-je faire avec des entrées supérieures à 30?

ETHproductions

Je ne suis pas sûr (et j'espère que la règle sera modifiée ), mais quelque chose comme ça f=x=>x?(y=f(x-(x<31)))^y*2:1marcherait.

Dennis

@ Dennis Ah, recurse infiniment = pas de sortie. Je vais résoudre ce problème lorsque je reviens à mon ordinateur. J'espère que cette règle sera également modifiée.

ETHproductions

La règle a été supprimée de la question.

Dennis

3

Matlab, 77 70 octets

Cette fonction calcule la n-ième ligne du triangle Pascal par convolution répétée avec [1,1](aka expansion binomiale ou multiplication répétée avec un binôme), et calcule le nombre à partir de cela.

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

flawr
la source

3

Rubis, 26 octets

fonction anonyme avec itération.

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

cette fonction récursive est d'un octet plus courte, mais comme elle doit être nommée pour pouvoir se référer à elle-même, elle finit par un octet de plus.

f=->n{n<1?1:(s=f[n-1])^s*2}

Level River St
la source

3

Rubis, 25 octets

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

Plus court que les autres réponses jusqu'ici. Il construit cette chaîne:

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

Ensuite, il définit n=1(cela se produit en fait pendant la création de la chaîne) et évalue la chaîne ci-dessus, retournant le résultat.

Lynn
la source

Est-ce que cela *n=1sauve réellement quelque chosem=1;"m^=2*"*n+?1

Martin Ender

Non, mais le faire avec une seule variable est très voyant :)

Lynn

3

Samau , 4 octets

Maintenant Samau a des fonctions intégrées pour la multiplication XOR et la puissance XOR.

▌3$ⁿ

Vidage hexadécimal (Samau utilise le codage CP737):

dd 33 24 fc

Explication:

▌       read a number
 3      push 3
  $     swap
   ⁿ    take the XOR power

alephalpha
la source

Cela pourrait-il être réduit à 3 octets en échangeant les deux premières commandes et en éliminant l'échange?

quintopie du

@quintopia No. Samau pousse automatiquement l'entrée sur la pile sous forme de chaîne et ▌lit un nombre dans la chaîne. Si nous échangeons les deux premières commandes, il essaiera de lire un nombre 3, qui n'est pas une chaîne.

alephalpha

pourquoi samau n'essaie-t-il pas d'évaluer la chaîne si possible?

quintopie

2

CJam, 10 octets

1ri{_2*^}*

Testez-le ici.

Solution itérative simple utilisant XOR au niveau du bit.

Martin Ender
la source

2

Pure Bash (pas d'utilitaires externes), 37

Les entiers bash sont signés 64 bits, donc cela fonctionne pour les entrées jusqu'à 62 inclusivement:

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

Traumatisme numérique
la source

2

Python 2.7.6, 38 33 bytes

Merci à Dennis d'avoir rasé quelques octets!

x=1
exec'x^=x*2;'*input()
print x

MCS-Kaijin
la source

1

Bienvenue sur Programmation Puzzles & Code Golf! exec'x^=x*2;'*input()enregistre quelques octets sur l' forapproche.

Dennis

Cela bat mon entrée Python, que je vais laisser ici pour la postérité:f=lambda n:f(n-1)^2*f(n-1)if n>0 else 1

Jack Brounstein

2

Pyth, 7 octets

uxyGGQ1

Essayez-le en ligne: Démonstration

Explication:

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

Jakube
la source

2

Perl 5 , 23 octets

$.^=2*$.for 1..<>;say$.

Essayez-le en ligne!

Xcali
la source

2

MIPS, 28 bytes

Input in $a0, output in $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
la source

1

Mathematica, 40 24 bytes

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

alephalpha
la source

1

k4, 26 bytes

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

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, and x f/y with x an integer is f applied to y first, and then to its successive outputs x times.

Sample run:

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

Aaron Davies
la source

1

Ruby, 31 26 bytes

EDIT: 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).

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

Sherlock9
la source

1

MATL, 15 bytes

Similar to @flawr's answer:

i:1w"TToX+]2\XB

EDIT (May 20, 2016) Try it online! with X+ replaced by Y+ to conform to version 18.0.0 of the language.

Example

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

Explanation

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
la source

1

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.

Jo King
la source

0

APL, 31 bytes

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

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 by 1 or 2, 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.

Aaron Davies
la source

You should be able to save a byte by changing ~1 2=. to 1 2≠.

Zacharý

And, which APL system is this on? If it's on Dyalog, you should be able to make it {({2⊥⊃1 2≠.((64⍴2)⊤×)⍵}⍣⍵)1} [28 bytes]

Zacharý

0

Seriously, 12 bytes

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

Hex Dump:

322cb960324025604dee6aa8

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:

 ,                       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

quintopia
la source

0

Pyt, 40 10 bytes

Đ0⇹Řć2%ǰ2Ĩ

Explanation:

Observing that the Binary Sierpinski Triangle is equivalent to 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

Try it online!

mudkip201
la source

0

Stax, 5 bytes

±s┤ε─

Run and debug online!

Port of the Jelly answer.

Uses ASCII representation to explain:

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
la source

Calculer la séquence binaire de triangle de Sierpinski

Classement

Réponses:

05AB1E , 5 4 octets

Pari / GP , 27 octets

Gelée , 6 octets

Comment ça marche

Haskell, 44 octets

Matlab, 45 octets

JavaScript (ES6), 23 octets

Matlab, 77 70 octets

Rubis, 26 octets

Rubis, 25 octets

Samau , 4 octets

CJam, 10 octets

Pure Bash (pas d'utilitaires externes), 37

Python 2.7.6, 38 33 bytes

Pyth, 7 octets

Explication:

Perl 5 , 23 octets

MIPS, 28 bytes

Mathematica, 40 24 bytes

k4, 26 bytes

Ruby, 31 26 bytes

MATL, 15 bytes

Example

Explanation

brainfuck, 87 bytes

APL, 31 bytes

Seriously, 12 bytes

Pyt, 40 10 bytes

Stax, 5 bytes