23

La secuencia del Triángulo de Sierpinski binario es la secuencia de números cuyas representaciones binarias dan las filas del Triángulo de Sierpinski binario, que se obtiene al comenzar con un 1 en una fila infinita de ceros, y luego reemplazar repetidamente cada par de bits con el xor de esos bits , al igual que:

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

Se dan más dígitos en OEIS: https://oeis.org/A001317

Entrada: Un número entero no negativo n en cualquier formato que desee. (Debe funcionar para todos n hasta 30.)

Salida: el enésimo término (indexado a 0) de la secuencia como un número decimal.

Este es el código de golf, así que trate de dar la respuesta más corta en bytes de los que su idioma es capaz. No se aceptarán respuestas. Se aplican las lagunas estándar (por ejemplo, sin codificar la secuencia), excepto que puede usar un lenguaje creado / modificado después de que se publique este desafío. (Evite publicar otra solución en un idioma que ya se haya utilizado a menos que su solución sea más corta).

Tabla de clasificación

El Fragmento de pila al final de esta publicación genera el catálogo a partir de las respuestas a) como una lista de la solución más corta por idioma yb) como una tabla de clasificación general.

Para asegurarse de que su respuesta se muestre, comience con un título, usando la siguiente plantilla de Markdown:

## Language Name, N bytes

¿Dónde Nestá el tamaño de su envío? Si mejora su puntaje, puede mantener los puntajes antiguos en el título, tachándolos. Por ejemplo:

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

Si desea incluir varios números en su encabezado (por ejemplo, porque su puntaje es la suma de dos archivos o desea enumerar las penalizaciones de la bandera del intérprete por separado), asegúrese de que el puntaje real sea el último número en el encabezado:

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

También puede hacer que el nombre del idioma sea un enlace que luego aparecerá en el fragmento:

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

Mostrar fragmento de código

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

8

No soy un gran admirador de no debe dar una respuesta incorrecta para cualquier n . Básicamente, esto fuerza a los idiomas que no usan enteros de precisión arbitraria de forma predeterminada para verificar si la entrada es lo suficientemente pequeña ...

Dennis

Aclare si comprende las reglas correctamente (vea los comentarios aquí y aquí ) y si la salida redondeada (por ejemplo, 1.288490189e10 para la entrada 33) cuenta como incorrecta .

Dennis

"Debe funcionar para todos los n hasta 30, y no debe dar una respuesta incorrecta para ningún n". . Esto es contradictorio: seguramente "no debe dar una respuesta incorrecta" es lo mismo que "¿Debe funcionar" ?

Trauma digital

55

Debido a la abrumadora oposición popular a la carga irrazonable y aplastante de la validación de entrada, este requisito se ha eliminado. Puede generar la basura que desee para n grande. ¡Disfrutar!

quintopia

2

En lugar de decir que la salida no debería estar equivocada, recomendaría simplemente decir que las presentaciones tienen que admitir la entrada hasta la más grande npara la que nada se desborda.

Alex A.

14

05AB1E , 5 4 bytes

Os presento con orgullo, 05AB1E. Aunque es muy corto, probablemente sea muy malo en desafíos largos.

Gracias a ETHproductions por eliminar 1 byte :)

$Fx^

Explicación:

$      # 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
fuente

Ya sabes, una buena forma de jugar un byte de muchos programas en un idioma personalizado es }insertar automáticamente un final . Entonces esto sería de 4 bytes. :)

ETHproductions

1

@ETHproductions Espere un minuto, eso ya se ha implementado :). Gracias por afeitarse 1 byte jaja.

Adnan

2

Hay un error en este código. ¿Cómo puedo saber? Está golpeando a Dennis.

Arcturus

2

@Ampora No solo está venciendo a Dennis, está venciendo el lenguaje de golf personalizado de Dennis. ;)

ETHproductions

@Adnan Wow. Estás en algo.

RK.

12

Pari / GP , 27 bytes

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

La función toma la enésima potencia del polinomio x + 1 en el anillo F ₂ [x], la eleva a Z [x] y luego la evalúa en 2.

Pruébalo en línea!

alephalpha
fuente

6

Jalea , 6 bytes

1Ḥ^$³¡

Pruébalo en línea!

La versión binaria que funciona con esta revisión del intérprete Jelly tiene el volcado xxd

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

Cómo funciona

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
fuente

5

Haskell, 44 bytes

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

En la ((->) r)mónada, (f >>= g) xes igual g (f x) x.

Lynn
fuente

Creo que puedes anonimizar la última línea a(iterate((2*)>>=xor)1!!)

xnor

Lo intenté, pero no funciona, por temidas razones de restricción de monomorfismo .

Lynn

Sin embargo, eso podría aplicarse como una expresión legal, ya que la restricción de monomorfismo no se aplica a las expresiones, sino a las declaraciones. Y las expresiones se consideran respuestas legales, si no me equivoco.

orgulloso Haskeller

4

Matlab, 45 bytes

Solución:

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

Prueba:

ans(10)
ans =
1285

Explicación: pascalconstruye el triángulo de Pascal, pero comienza desde 1, por lo que la entrada debe ser i+1. fliplrvoltea la matriz de izquierda a derecha. mod(_,2)toma el resto después de la división por 2. diagextrae la diagonal principal. Multiplicación usando 2.^[0:i]convierte el vector a decimal

Me alegro, @flawr de haber encontrado al competidor de Matlab aquí :)

brainkz
fuente

Parece trabajar con Octave también.

Dennis

4

JavaScript (ES6), 23 bytes

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

Basado en la primera fórmula en la página OEIS. Si no le importa que el código tarde casi una eternidad en terminar para una entrada de 30, podemos eliminar un byte:

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

Aquí hay una versión no recursiva, que usa un forbucle en un eval: (32 bytes)

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

ETHproducciones
fuente

Las reglas, tal como están escritas actualmente, invalidan esta respuesta, ya que f(35)regresa 15. Además, alerta de bomba tenedor: tuve que forzar el cierre de Chromium para detener la f(30)ejecución (revisión original). : P

Dennis

1

@Dennis Espere, así que si no puedo generar ningún valor incorrecto, ¿qué se supone que debo hacer con entradas superiores a 30?

ETHproductions

No estoy seguro (y espero que la regla cambie ), pero algo así f=x=>x?(y=f(x-(x<31)))^y*2:1funcionaría.

Dennis

@ Dennis Ah, recurse infinitamente = sin salida. Arreglaré esto cuando regrese a mi computadora. Espero que esa regla cambie también.

ETHproductions

La regla ha sido eliminada de la pregunta.

Dennis

3

Matlab, 77 70 bytes

Esta función calcula la enésima fila del triángulo de Pascal mediante una convolución repetida con [1,1](también conocida como expansión binomial o multiplicación repetida con un binomio) y calcula el número a partir de eso.

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

falla
fuente

3

Rubí, 26 bytes

Función anónima con iteración.

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

esta función recursiva es un byte más corta, pero como necesita ser nombrada para poder referirse a sí misma, termina un byte más.

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

Level River St
fuente

3

Rubí, 25 bytes

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

Más corto que las otras respuestas aquí hasta ahora. Construye esta cadena:

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

Luego se establece n=1(esto realmente sucede mientras se hace la cadena) y evalúa la cadena anterior, devolviendo el resultado.

Lynn
fuente

¿Eso *n=1realmente ahorra algo?m=1;"m^=2*"*n+?1

Martin Ender

No, but doing it with just one variable is very showy :)

Lynn

3

Samau, 4 bytes

Now Samau has built-in functions for XOR multiplication and XOR power.

▌3$ⁿ

Hex dump (Samau uses CP737 encoding):

dd 33 24 fc

Explanation:

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

alephalpha
fuente

¿Podría esto reducirse a 3 bytes intercambiando los dos primeros comandos y eliminando el intercambio?

quintopia

@quintopia No. Samau empuja automáticamente la entrada en la pila como una cadena y ▌lee un número de la cadena. Si intercambiamos los dos primeros comandos, intentaría leer un número 3, que no es una cadena.

alephalpha

¿Por qué Samau no intenta evaluar la cadena cuando es posible?

quintopia

2

CJam, 10 bytes

1ri{_2*^}*

Pruébalo aquí.

Solución iterativa simple usando XOR bit a bit.

Martin Ender
fuente

2

Pure Bash (sin utilidades externas), 37

Los enteros Bash están firmados de 64 bits, por lo que esto funciona para entradas de hasta 62 inclusive:

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

Trauma digital
fuente

2

Python 2.7.6, 38 33 bytes

¡Gracias a Dennis por reducir unos pocos bytes!

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

MCS-Kaijin
fuente

1

¡Bienvenido a Programming Puzzles & Code Golf! exec'x^=x*2;'*input()guarda algunos bytes sobre el forenfoque.

Dennis

Esto supera mi entrada de Python, que dejaré aquí para la posteridad:f=lambda n:f(n-1)^2*f(n-1)if n>0 else 1

Jack Brounstein

2

Pyth, 7 bytes

uxyGGQ1

Pruébelo en línea: demostración

Explicación:

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

Jakube
fuente

2

Perl 5 , 23 bytes

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

Pruébalo en línea!

Xcali
fuente

2

MIPS, 28 bytes

Entrada $a0, salida en $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
fuente

1

Mathematica, 40 24 bytes

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

alephalpha
fuente

1

k4, 26 bytes

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

0b\:convierte un número en un vector booleano (es decir, una cadena de bits), XOR se implementa como "no igual", 2/:convierte una cadena de bits en un número al tratarlo como un polinomio para evaluar, y x f/ycon xun número entero se faplica yprimero, y luego a su salidas sucesivasx veces.

Ejecución de muestra:

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

Aaron Davies
fuente

1

Ruby, 31 26 bytes

EDITAR: ¡ Cambiado a un idioma completamente diferente! ¡Todas las sugerencias de golf son bienvenidas!

Este programa XOR bit a bit el elemento anterior de la secuencia con el doble de sí mismo, es decir f(n) = f(n-1) ^ 2*f(n-1).

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

Sherlock9
fuente

1

MATL , 15 bytes

Similar a la respuesta de @ flawr :

i:1w"TToX+]2\XB

EDITAR (20 de mayo de 2016) ¡ Pruébelo en línea! con X+reemplazado por Y+para cumplir con la versión 18.0.0 del lenguaje.

Ejemplo

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

Explicación

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
fuente

1

brainfuck , 87 bytes

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

Pruébalo en línea!

Asume celdas de tamaño infinito (de lo contrario no puede pasar de 7, que es convenientemente 255). El método de Mod 2 del triángulo de Pascal es en realidad mucho más largo debido a la costosa operación de Mod 2, mientras que XOR es mucho más fácil de implementar.

Jo King
fuente

0

APL, 31 bytes

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

Es casi seguro que es un código horrible, pero soy un APL completamente nuevo. Espero que cualquier persona con alguna habilidad pueda deshacerse de todas las funciones D y acortarla considerablemente. La lógica es más o menos la misma que mi k4respuesta: multiplique por 1o 2, convierta a bits con ⊤XOR usando no es igual, vuelva a convertir a un número con ⊥, envuelva todo en una función y solicite un número específico de iteraciones usando ⍣. No tengo idea de por qué el resultado que sale del producto interno está incluido, pero lo ⊃limpia.

Aaron Davies
fuente

Debería poder guardar un byte cambiando ~1 2=.a1 2≠.

Zacharý

¿Y en qué sistema APL está funcionando? Si está en Dyalog, debería poder hacerlo {({2⊥⊃1 2≠.((64⍴2)⊤×)⍵}⍣⍵)1}[28 bytes]

Zacharý

0

En serio, 12 bytes

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

Hex Dump:

322cb960324025604dee6aa8

Pruébalo en línea

Dado que Seriamente no incluye ningún medio para hacer un xor bit a bit, esta solución toma el desafío completamente literalmente, calculando directamente la fila dada del triángulo. Este método da respuestas correctas hasta n = 1029 (después de lo cual no hay suficiente memoria para calcular la fila dada del triángulo de Pascal).

Explicación:

 ,                       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

quintapia
fuente

0

Pyt , 40 10 bytes

Đ0⇹Řć2%ǰ2Ĩ

Explicación:

Observando que el Triángulo de Sierpinski binario es equivalente al Triángulo de Pascal 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

Pruébalo en línea!

mudkip201
fuente

0

Stax , 5 bytes

±s┤ε─

¡Ejecute y depure en línea!

La respuesta de Port of the Jelly.

Utiliza representación ASCII para explicar:

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
fuente

Calcule la secuencia binaria del triángulo de Sierpinski

Tabla de clasificación

Respuestas:

05AB1E , 5 4 bytes

Pari / GP , 27 bytes

Jalea , 6 bytes

Cómo funciona

Haskell, 44 bytes

Matlab, 45 bytes

JavaScript (ES6), 23 bytes

Matlab, 77 70 bytes

Rubí, 26 bytes

Rubí, 25 bytes

Samau, 4 bytes

CJam, 10 bytes

Pure Bash (sin utilidades externas), 37

Python 2.7.6, 38 33 bytes

Pyth, 7 bytes

Explicación:

Perl 5 , 23 bytes

MIPS, 28 bytes

Mathematica, 40 24 bytes

k4, 26 bytes

Ruby, 31 26 bytes

MATL , 15 bytes

Ejemplo

Explicación

brainfuck , 87 bytes

APL, 31 bytes

En serio, 12 bytes

Pyt , 40 10 bytes

Stax , 5 bytes