23

Последовательность двоичного треугольника Серпинского - это последовательность чисел, двоичные представления которой дают строки двоичного треугольника Серпинского, которые задаются, начиная с 1 в бесконечном ряду нулей, а затем многократно заменяя каждую пару бит на xor этих битов , вот так:

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

Дополнительные цифры приведены в OEIS: https://oeis.org/A001317

Ввод: неотрицательное целое число n в любом формате, который вам нравится. (Должно работать для всех n до 30.)

Выходные данные: n-й член (0-индексированный) последовательности в виде десятичного числа.

Это код-гольф, поэтому постарайтесь дать кратчайший ответ в байтах, на который способен ваш язык. Ответ не будет принят. Применяются стандартные лазейки (например, нет жесткого кодирования последовательности), за исключением того, что вы можете использовать язык, созданный / измененный после публикации этого запроса. (Старайтесь не публиковать другое решение на языке, который уже использовался, если ваше решение не короче.)

Leaderboard

Фрагмент стека в нижней части этого поста создает каталог из ответов а) в виде списка кратчайшего решения для каждого языка и б) в качестве общей таблицы лидеров.

Чтобы убедиться, что ваш ответ обнаружен, начните его с заголовка, используя следующий шаблон уценки:

## Language Name, N bytes

где Nразмер вашего представления. Если вы улучшите свой счет, вы можете сохранить старые результаты в заголовке, вычеркнув их. Например:

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

Если вы хотите включить в заголовок несколько чисел (например, потому что ваш результат равен сумме двух файлов или вы хотите перечислить штрафы за флаг интерпретатора отдельно), убедитесь, что фактический результат является последним числом в заголовке:

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

Вы также можете сделать имя языка ссылкой, которая будет отображаться во фрагменте кода:

## [><>](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>

Expand snippet

code-golf sequence binary bitwise quintopia
источник

8

Я не большой поклонник не должен выводить неправильный ответ для любого n . Это в основном заставляет языки, которые не используют произвольные целочисленные значения точности по умолчанию, проверять, является ли ввод достаточно маленьким ...

Деннис

Пожалуйста, уточните, правильно ли поняты правила (см. Комментарии здесь и здесь ) и если округленное значение (например, 1.288490189e10 для ввода 33) считается неправильным .

Деннис

«Должно работать для всех n до 30, и не должно выводить неправильный ответ для любого n». , Это противоречиво - конечно, «не должен выводить неправильный ответ» - это то же самое, что и «Должен работать» ???

Цифровая травма

5

Из-за подавляющего общественного возражения против необоснованного и душераздирающего бремени проверки ввода это требование было снято. Вы можете вывести любой мусор, который хотите для больших n. Наслаждайтесь!

Quintopia

2

Вместо того, чтобы говорить, что вывод не должен быть неправильным, я бы порекомендовал просто сказать, что представления должны поддерживать ввод до самого большого, nдля которого ничего не переполняется.

Алекс А.

14

05AB1E , 5 4 байта

Я с гордостью представляю вам, 05AB1E. Хотя он очень короткий, он, вероятно, очень плохо справляется с длительными испытаниями.

Спасибо ETHproductions за то, что сбрил 1 байт :)

$Fx^

Объяснение:

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

Аднан
источник

Вы знаете, хороший способ отыграть байт от многих программ на пользовательском языке - это сделать трейлинг } автоматически вставить . Тогда это будет 4 байта. :)

ETHproductions

1

@ETHproductions Подожди, это уже реализовано :). Спасибо, что сбрил 1 байт, ха-ха.

Аднан

2

В этом коде есть ошибка. Откуда мне знать? Это бьет Денниса.

Арктур

2

@Ampora Мало того, что это бьет Денниса, это бьет пользовательский язык игры в гольф Денниса. ;)

ETHproductions

@ Аднан Вау. Вы к чему-то.

РК.

12

Пари / ГП , 27 байт

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

Функция берет n-ую степень многочлена x + 1 в кольце F ₂ [x], поднимает его до Z [x], а затем оценивает его как 2.

Попробуйте онлайн!

alephalpha
источник

6

Желе , 6 байт

1Ḥ^$³¡

Попробуйте онлайн!

Двоичная версия, которая работает с этой ревизией интерпретатора Jelly, имеет дамп xxd

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

Как это работает

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.

Деннис
источник

5

Haskell, 44 байта

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

В ((->) r)монаде (f >>= g) xравно g (f x) x.

Линн
источник

Я думаю, что вы можете анонимизировать последнюю строку(iterate((2*)>>=xor)1!!)

xnor

Я пробовал это, но это не работает, из-за страшных ограничений мономорфизма .

Линн

Однако это может применяться как юридическое выражение, поскольку ограничение мономорфизма применяется не к выражениям, а к декларациям. И выражения считаются легальными ответами, если я не ошибаюсь.

гордый haskeller

4

Matlab, 45 байт

Решение:

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

Тест:

ans(10)
ans =
1285

Объяснение: pascalстроит треугольник Паскаля, но он начинается с 1, поэтому ввод должен быть i+1. fliplrпереворачивает массив слева направо. mod(_,2)принимает остаток после деления на 2. diagизвлекает основную диагональ. Умножение с использованием 2.^[0:i]вектора преобразует в десятичную

Я рад, @flawr, что я нашел здесь конкурента Matlab :)

brainkz
источник

Кажется, работает и с Октавой.

Деннис

4

JavaScript (ES6), 23 байта

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

На основании первой формулы на странице OEIS. Если вы не возражаете против того, чтобы код вводился почти 30 раз, мы можем сбрить байт:

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

Вот нерекурсивная версия, использующая forцикл в eval: (32 байта)

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

ETHproductions
источник

Правила, как написано в настоящее время, лишают законной силы этот ответ, так как f(35)возвращается 15. Кроме того, предупреждение о бомбе-вилке: мне пришлось принудительно закрыть Chromium, чтобы остановить f(30)запуск (оригинальная версия). : P

Деннис

1

@ Денис Подожди, так что, если я не могу вывести неправильное значение, что я должен делать с входами выше 30?

ETHproductions

Я не уверен (и я надеюсь, что правило будет изменено ), но что-то вроде f=x=>x?(y=f(x-(x<31)))^y*2:1бы сработало.

Деннис

@ Денис Ах, рекурсивно бесконечно = нет выхода. Я исправлю это, когда вернусь к своему компьютеру. Я надеюсь, что это правило также будет изменено.

ETHproductions

Правило было удалено из вопроса.

Деннис

3

Matlab, 77 70 байт

Эта функция вычисляет n-ую строку треугольника Паскаля посредством повторяющейся свертки с [1,1](расширение бинома или многократное умножение на бином) и вычисляет число из этого.

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

flawr
источник

3

Рубин, 26 байт

анонимная функция с итерацией.

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

эта рекурсивная функция на один байт короче, но так как ее нужно называть, чтобы иметь возможность ссылаться на себя, она заканчивается на один байт длиннее.

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

Уровень реки St
источник

3

Рубин, 25 байт

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

Короче других ответов здесь пока нет. Он строит эту строку:

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

Затем он устанавливает n=1(это фактически происходит во время создания строки) и оценивает приведенную выше строку, возвращая результат.

Линн
источник

Действительно ли это что-то *n=1спасаетm=1;"m^=2*"*n+?1

Мартин Эндер

Нет, но делать это только с одной переменной очень эффектно :)

Линн

3

Samau , 4 байта

Теперь Samau имеет встроенные функции для умножения XOR и мощности XOR.

▌3$ⁿ

Шестнадцатеричный дамп (Samau использует кодировку CP737):

dd 33 24 fc

Объяснение:

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

alephalpha
источник

Может ли это быть уменьшено до 3 байтов путем замены первых двух команд и устранения замены?

Quintopia

@quintopia Нет. Samau автоматически помещает ввод в стек в виде строки и ▌считывает число из строки. Если мы поменяем первые две команды, он попытается прочитать число 3, которое не является строкой.

алефальфа

почему самау не пытается вывести строку, когда это возможно?

Quintopia

2

CJam, 10 байтов

1ri{_2*^}*

Проверьте это здесь.

Простое итеративное решение с использованием побитового XOR.

Мартин Эндер
источник

2

Pure Bash (без внешних утилит), 37

Целые числа Bash имеют 64-битную подпись, поэтому это работает для входных данных до 62 включительно:

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

Цифровая травма
источник

2

Python 2.7.6, 38 33 байта

Спасибо Деннису за то, что он сбрил несколько байтов!

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

MCS-KaiJin
источник

1

Добро пожаловать в Программирование Пазлов и Code Golf! exec'x^=x*2;'*input()экономит несколько байтов над forподходом.

Деннис

Это превосходит мою запись на Python, которую я оставлю здесь для потомков:f=lambda n:f(n-1)^2*f(n-1)if n>0 else 1

Джек Браунштейн

2

Pyth, 7 байт

uxyGGQ1

Попробуйте онлайн: демонстрация

Объяснение:

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

Jakube
источник

2

Perl 5 , 23 байта

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

Попробуйте онлайн!

Xcali
источник

2

MIPS, 28 байт

Вход в $a0, выход в $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
источник

1

Mathematica, 40 24 байта

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

alephalpha
источник

1

k4, 26 байтов

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

0b\:преобразует число к булеву вектору (т.е. битовый), исключающий реализована в виде «не равно», 2/:преобразует битовую обратно к ряду, рассматривая ее как полином для оценки, и x f/yс xцелым числом будет fприменен к yпервому, а затем к его последовательные выходы xраз.

Образец прогона:

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

Аарон Дэвис
источник

1

Рубин, 31 26 байт

РЕДАКТИРОВАТЬ: полностью изменен на другой язык! Все предложения по игре в гольф приветствуются!

Эта программа побитового операцию XOR предыдущий элемент последовательности с дважды самим, то есть f(n) = f(n-1) ^ 2*f(n-1).

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

Sherlock9
источник

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
источник

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
источник

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
источник

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
источник

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
источник

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
источник

Вычислить двоичную последовательность треугольника Серпинского

Leaderboard

Ответы:

05AB1E , 5 4 байта

Пари / ГП , 27 байт

Желе , 6 байт

Как это работает

Haskell, 44 байта

Matlab, 45 байт

JavaScript (ES6), 23 байта

Matlab, 77 70 байт

Рубин, 26 байт

Рубин, 25 байт

Samau , 4 байта

CJam, 10 байтов

Pure Bash (без внешних утилит), 37

Python 2.7.6, 38 33 байта

Pyth, 7 байт

Объяснение:

Perl 5 , 23 байта

MIPS, 28 байт

Mathematica, 40 24 байта

k4, 26 байтов

Рубин, 31 26 байт

MATL, 15 bytes

Example

Explanation

brainfuck, 87 bytes

APL, 31 bytes

Seriously, 12 bytes

Pyt, 40 10 bytes

Stax, 5 bytes