Последовательность кривой Дракона

23

Последовательность кривой дракона (или обычная последовательность складывания бумаги) является двоичной последовательностью. a(n)задается отрицанием бита слева от младшего значащего 1 из n. Например, для вычисления a(2136)мы сначала преобразуем в двоичный файл:

100001011000

Мы находим наш наименее значимый бит

100001011000
        ^

Возьмите немного налево

100001011000
       ^

И вернуть свое отрицание

0

задача

Учитывая положительное целое число в качестве ввода, вывода a(n). (Вы можете вывести целочисленный или логический). Вы должны стремиться к тому, чтобы ваш код был как можно меньше, измеряемым байтами.

Тестовые случаи

Вот первые 100 записей в порядке

1 1 0 1 1 0 0 1 1 1 0 0 1 0 0 1 1 1 0 1 1 0 0 0 1 1 0 0 1 0 0 1 1 1 0 1 1 0 0 1 1 1 0 0 1 0 0 0 1 1 0 1 1 0 0 0 1 1 0 0 1 0 0 1 1 1 0 1 1 0 0 1 1 1 0 0 1 0 0 1 1 1 0 1 1 0 0 0 1 1 0 0 1 0 0 0 1 1 0 1
Мастер пшеницы
источник
9
Наименее значимым 100001011000является 0. Вы имеете в виду наименее значимый 1?
разброс

Ответы:

16

Mathematica 25 байт

1/2+JacobiSymbol[-1,#]/2&

Другие способы сделать это:

56 байт

(v:=1-IntegerDigits[#,2,i][[1]];For[i=1,v>0,i++];i++;v)&

58 байт

1-Nest[Join[#,{0},Reverse[1-#]]&,{0},Floor@Log[2,#]][[#]]&
Келли Лоудер
источник
3
Вот Это Да! Ответ Mathematica, и он не только встроенный. Имейте upvote!
KeyWeeUsr
2
Единственное, что может сделать этот ответ еще лучше, - это объяснение, почему и как он работает. : P
Мартин Эндер
2
@MartinEnder arxiv.org/pdf/1408.5770.pdf См. Примечание после примера 13.
alephalpha
7

Python 3 , 22 21 байт

1 байт благодаря ETHproductions.

lambda n:n&2*(n&-n)<1

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

Побитовая арифметика

Дрянная Монахиня
источник
2
«Вы можете вывести по целому или логическому значению», так что я думаю, вам не нужен 0+(...)?
Мартин Эндер
Порядок действий здесь действительно смущает меня. Может n&1быть в скобках? Или 1+(n^~-n)<1это можно заключить в скобки? Или это 1+(n^~-n)...
ETHproductions
о боже что. это то, что я искал: о приятно!
HyperNeutrino
&имеет самый низкий приоритет, так что это1+(n^~-n)
Leaky Nun
Ах, нашел таблицу приоритетов. Теперь все это имеет смысл: P
ETHproductions
6

Сетчатка ,38 34 29 байт

\d+
$*
+`^(1+)\1$|1111
$1
^1$

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

Мартин и Лики, по сути, выдвинули эту идею еще на 5 байтов!

Преобразует входной сигнал в унарный, а затем постепенно делит число на 2. Как только он больше не может делать это равномерно (т. Е. Число нечетное), он затем удаляет патчи 4 из входа, вычисляя результат последней операции mod 4 Наконец, это проверяет, был ли результат равен 1, что означает, что цифра слева от младшего значащего 1 бита была равна нулю. Если это правда, конечный результат равен 1, в противном случае он равен нулю.

FryAmTheEggman
источник
31 байт (я должен опубликовать это сам?)
Leaky Nun
Я нашел способ избежать полного двоичного преобразования и вместо этого просто разделить множители на 2 и проверить равенство с 1 (мод 4): tio.run/##K0otycxL/…
Martin Ender
@MartinEnder по сути мой алгоритм ... с выключенными 2 байтами
Leaky Nun
@ LeakyNun О, да, они оба одна и та же идея. Великие умы и прочее ...;)
Мартин Эндер
Я отредактирую это, но если кто-то из вас захочет опубликовать это, я вернусь, поскольку я, вероятно, сам не подумал бы об этом;)
FryAmTheEggman
6

Желе , 5 байт

&N&HṆ

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

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

&N&HṆ  Main link. Argument: n

 N     Negate; yield -n.
&      Bitwise AND; compute n&-n.
       This yields the highest power of 2 that divides n evenly.
   H   Halve; yield n/2.
  &    Bitwise AND; compute n&-n&n/2. This rounds n/2 down if n is odd.
    Ṇ  Take the logical NOT of the result.
Деннис
источник
4

Алиса , 8 байт

I2z1xnO@

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

Принимает ввод как кодовую точку символа Юникод и выводит результат в виде байта 0x00 или 0x01 соответственно.

Для тестируемости вот десятичная версия ввода / вывода с 12 байтами, которая использует точно такой же алгоритм (отличается только ввод / вывод):

/o
\i@/2z1xn

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

Если бы Алиса была языком игры в гольф и не требовала явного ввода-вывода и завершения программы, это заняло бы всего 5 байтов (2z1xn ), превосходя и 05AB1E, и Jelly.

объяснение

I    Read input.
2z   Drop all factors of 2 from the input, i.e. divide it by 2 as long
     as its even. This shifts the binary representation to the right
     until there are no more trailing zeros.
1x   Extract the second-least significant bit.
n    Negate it.
O    Output it.
@    Terminate the program.
Мартин Эндер
источник
3

Мудрый , 28 20 16 байт

::-~^~-&:[?>]~-^

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

объяснение

Это порт ответа Python про Лаки Нун. К сожалению, он не работает на TIO, потому что версия интерпретатора TIO немного устарела.

Мы начинаем с того, что делаем 3 копии нашего ввода ::, затем уменьшаем верхнюю копию на 1. Это перевернет все биты до первого 1. Затем мы зафиксируем это с другой копией нашего ввода. Поскольку все биты вплоть до первой 1 на нашем входе были перевернуты, это приведет к тому, что все эти биты будут равны 1 в результате. Если мы затем добавим единицу ~-к результату, мы получим единицу 1 в месте слева от нашего наименее значимого 1. Мы И это с помощью ввода, чтобы получить этот бит из ввода. Теперь у нас будет, 0если этот бит был выключен, и степень 2, если этот бит был включен, мы можем изменить это на сингл 1или 0с :[?>]. Как только это будет сделано, нам нужно только отменить бит, ~-^и все готово.

Мастер пшеницы
источник
3

Haskell , 45 43 39 байт

6 байтов сохранено благодаря nimi

f x|d<-div x 2=[f d,mod(1+d)2]!!mod x 2

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

Мастер пшеницы
источник
Вы можете использовать divвместо quot.
Ними
Еще лучше: divMod:f x|(d,m)<-divMod x 2=[mod(1+d)2,f d]!!m
Ними
@nimi Я даже не понимаю, как это работает. Вы должны, вероятно, просто опубликовать это самостоятельно.
Пшеничный волшебник
Это все тот же алгоритм, но просто другой способ , чтобы выбрать ветвь (рекурсивный вызов е снова против базового случая), так что не стесняйтесь редактировать его. |(d,m)<-divMod x 2Это шаблон охранник для привязки dк div x 2и mк mod x 2. Мы используем mдля индексации двухэлементный список [...,...]!!m. В случае m==0возвращения mod(1+d)2и в случае m==1 f d.
Ними
1
Ой, извините, вы должны перевернуть элементы списка: [f d,mod(1+d)2]. Попробуйте онлайн! ,
Ними
3

Машинный код x86, 17 16 15 байт:

Предполагается ABI, где параметры помещаются в стек, а возвращаемое значение находится в ALрегистре.

8B 44 24 04 0F BC C8 41 0F BB C8 0F 93 C0 C3

Это разбирается следующим образом:

_dragoncurve:
  00000000: 8B 44 24 04        mov         eax,dword ptr [esp+4]
  00000004: 0F BC C8           bsf         ecx,eax
  00000007: 41                 inc         ecx
  00000008: 0F BB C8           btc         eax,ecx
  0000000B: 0F 93 C0           setae       al
  0000000E: C3                 ret
Говинд Пармар
источник
1
@PeterTaylor Я рассчитываю размер инструкции процессора в байтах для моего ответа; Это довольно распространенная практика в PPCG для ответов на сборки.
Говинд Пармар
1
Я не могу сказать, насколько это распространено, но это определенно неправильно
Питер Тейлор
1
Это не просто педантично, это также бессмысленно. Нет никакого различия между «машинным кодом» и «кодом сборки» в том, что касается компьютера. Разница лишь в интерпретации. Мы назначаем мнемонику байтам машинного кода, чтобы людям было легче их читать. Другими словами, мы распускаем байты, чтобы их было легче понять.
Коди Грей
3
Это не имеет значения, @Peter. Ассемблерный код - это просто понятный человеку перевод машинного кода. Это один и тот же язык, только в двух разных формах / представлениях. Он ничем не отличается от TI BASIC, где принято считать токены вместо символьных байтов, потому что именно так система хранит их внутри. То же самое можно сказать и о языке ассемблера: мнемоника команд не хранится как отдельные символы, а представляется как байты эквивалентного машинного кода.
Коди Грей
2
Кроме того, практически говоря, почему бы кто - нибудь когда - либо вводите расширить ассемблере мнемоники в конкуренции кода для гольфа, когда они могли бы перевести их на 100% кода эквивалентна машине, где запись гарантированно будет короче бесплатно? Уже одно это делает различие между двумя бессмысленными, если не совсем абсурдными.
Коди Грей
3

JavaScript (ES6), 17 14 байт

f=
n=>!(n&-n&n/2)
<input type=number min=0 oninput=o.textContent=f(this.value)><pre id=o>

Изменить: Сохранение 3 байтов путем переноса ответа @ Деннис, как только я заметил, что логический вывод был приемлемым.

Нил
источник
3

C (gcc) , 20 байтов

f(n){n=!(n&-n&n/2);}

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

Деннис
источник
Это на самом деле не «работает»; вы полагаетесь на причуду генератора кода для одной конкретной версии компилятора, ориентированной на одну конкретную архитектуру, где промежуточные вычисления выполняются в том же регистре, который используется для возвращаемых значений. Включение любого типа оптимизации, изменение целевой архитектуры или использование другой версии GCC сломает это. С таким же успехом вы можете просто сказать, что «мусор в моем стеке содержит правильные выходные данные, когда 13 октября полная луна».
Коди Грей
Хотя все, что вы говорите, является правдой, и подобный код никогда не будет использоваться в производственном коде, мы определяем языки по их реализациям для целей гольфа кода. Без дополнительных флагов это работает во всех последних версиях gcc и tcc и должно работать только в одной версии, чтобы считаться действительной.
Деннис
«Мы определяем языки по их реализациям для целей гольф-кода». Подожди, что? Таким образом, каждый флаг компилятора и каждая версия GCC определяет свой язык? Вы понимаете, что это безумие, верно? Стандарт языка C - это то, что определяет язык.
Коди Грей
Не здесь. Если бы существовал стандарт C, но не было реализации, мы бы даже не считали его языком. Как я уже говорил, компилятор определяет язык . В результате можно полагаться на неопределенное поведение . Другой набор флагов не считается другим языком, но если вы не добавите их к количеству байтов, все ответы используют стандартные флаги компиляции.
Деннис
Вау. Это безумие. Я имею в виду, я мог бы понять, если бы вы говорили, что поведение, определяемое реализацией, разрешено, но неопределенное поведение не определяется реализацией. Это буквально не определено. Реализация позволяет делать случайные вещи каждый раз. И это понятие «стандартные флаги компиляции» - это то, что вы только что изобрели. Мои стандартные флаги компиляции включают несколько, которые нарушают ваш код. И вряд ли оптимизатор нестандартный. Ну понятно этот сайт не для меня.
Коди Грей
3

INTERCAL , 50 байтов

DOWRITEIN.1DO.1<-!?1~.1'~#1DOREADOUT.1PLEASEGIVEUP

Унарные операторы INTERCAL вполне подходят для этого, поэтому я решил написать свой первый пост.

DO WRITE IN .1
DO .1 <- !?1~.1'~#1
DO READ OUT .1
PLEASE GIVE UP
Бернд Фишер
источник
3

Haskell , 33 байта

g~(a:b:c)=1:a:0:b:g c
d=g d
(d!!)

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

Использует 0-индексацию.

Андерс Касеорг
источник
1
Что делает ~в этом контексте? Я понимаю, что это ленивый матч, но зачем тебе ленивый матч?
Пшеничный волшебник
2

Желе , 7 6 байт

1 байт благодаря Эрику Аутгольферу.

Bt0ṖṪṆ

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

Более длинные программы

Дрянная Монахиня
источник
Хм ... ну, вы можете просто сделать ṖṪṆ(как мой удаленный ответ) вместо ṫ-ḄỊ.
Эрик Outgolfer
1
Еще один для вашего 7-байтового списка:BUḌDḊḢ¬
Steenbergh
2

,,, , 10 9 байт

::0-&2*&¬

объяснение

Возьмите вход как 3 например.

::0-&2*&1≥
               implicitly push command line argument       [3]
::             duplicate twice                             [3, 3, 3]
  0            push 0 on to the stack                      [3, 3, 3, 0]
   -           pop 0 and 3 and push 0 - 3                  [3, 3, -3]
    &          pop -3 and 3 and push -3 & 3 (bitwise AND)  [3, 1]
     2         push 2 on to the stack                      [3, 1, 2]
      *        pop 2 and 1 and push 2 * 1                  [3, 2]
       &       pop 2 and 3 and push 2 & 3                  [2]
        ¬      pop 2 and push ¬ 2 (logical NOT)            [0]
               implicit output                             []
totallyhuman
источник
2

Октава , 34 байта

@(x)~(k=[de2bi(x),0])(find(k,1)+1)

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

Объяснение:

@(x)                               % Anonymous function taking a decimal number as input
    ~....                          % Negate whatever comes next
     (   de2bi(x)   )              % Convert x to a binary array that's conveniently 
                                   % ordered with the least significant bits first
        [de2bi(x),0]               % Append a zero to the end, to avoid out of bound index
     (k=[de2bi(x),0])              % Store the vector as a variable 'k'
                     (find(k,1)    % Find the first '1' in k (the least significant 1-bit)
                               +1  % Add 1 to the index to get the next bit
     (k=[de2bi(x),0])(find(k,1)+1) % Use as index to the vector k to get the correct bit
Стьюи Гриффин
источник
Почему я никогда не слышал о de2bi ...: O
Sanchises
1

Подача конкурсных предложений:

Python 2 , 41 39 байт

x=input()
while~-x&1:x/=2
print 1-x/2%2

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

-2 байта благодаря FryAmTheEggman

Начальное решение:

Python 2 , 43 байта

lambda x:1-int(bin(x)[bin(x).rfind('1')-1])

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

HyperNeutrino
источник
Итак, какое ваше представление?
Утренняя монахиня
@LeakyNun Первый, потому что он короче; вторая была моей оригинальной подачей. Должен ли я разместить их отдельно?
HyperNeutrino
~-x&1Я думаю, что вместо этого работает в то время как условия.
FryAmTheEggman
(Я забыл имя пользователя); Я отклонил вашу правку, потому что правка на чужой код не рекомендуется для PPCG. Вы можете публиковать предложения (кстати, спасибо @FryAmTheEggman), но, пожалуйста, не вносите изменения в гольф. Благодарность!
HyperNeutrino
@ StewieGriffin Ах, да, спасибо. К сожалению, я не могу пропинговать пользователя, потому что редактирование было отклонено.
HyperNeutrino
1

MATL , 11 10 байт

t4*YF1)Z.~

Попробуйте онлайн! Или посмотрите первые 100 выходов .

объяснение

t    % Implicit input. Duplicate
4*   % Multiply by 4. This ensures that the input is a multiple of 2, and
     % takes into account that bit positions are 1 based
YF   % Exponents of prime factorization
1)   % Get first exponent, which is that of factor 2
Z.   % Get bit of input at that (1-based) position
~    % Negate. Implicit display
Луис Мендо
источник
1

Befunge-98 , 19 байт

&#;:2%\2/\#;_;@.!%2

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

&#                       Initial input: Read a number an skip the next command
  ;:2%\2/\#;_;           Main loop: (Direction: East)
   :2%                    Duplicate the current number and read the last bit
      \2/                 Swap the first two items on stack (last bit and number)
                          and divide the number by two => remove last bit
         \                swap last bit and number again
          #;_;            If the last bit is 0, keep going East and jump to the beginning of the loop
                          If the last bit is 1, turn West and jump to the beginning of the loop, but in a different direction.
&#;           @.!%2      End: (Direction: West)
&#                        Jump over the input, wrap around
                 %2       Take the number mod 2 => read the last bit
               .!         Negate the bit and print as a number
              @          Terminate
овс
источник
1

SCALA, 99 (78?) Символов, 99 (78?) Байтов

if(i==0)print(1)else
print(if(('0'+i.toBinaryString).reverse.dropWhile(x=>x=='0')(1)=='1')0 else 1)

где iвход.

Как видите, я сохраняю 21 байт, если не позабочусь о нуле (как это сделал автор в своем тестовом примере):

print(if(('0'+i.toBinaryString).reverse.dropWhile(x=>x=='0')(1)=='1')0 else 1)

Это мой первый Codegolf, поэтому я надеюсь, что у меня все получилось :)

Попробуйте онлайн! Хотя довольно долго вычислять лол.

В. Куртуа
источник
Добро пожаловать на сайт!
DJMcMayhem
1

Java 8, 17 байт

n->(n&2*(n&-n))<1

Прямой порт ответа LeakyNun's Python 3 . Я недостаточно знаком с побитовыми операциями и приоритетами операторов, чтобы увидеть более короткое решение; может быть, есть способ избежать лишних парентезов?

JollyJoker
источник
0

Japt , 10 8 9 байт

!+¢g¢a1 É

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

объяснение

!+¢   g    a1 É
!+Us2 gUs2 a1 -1 # Implicit input (U) as number
!+               # Return the boolean NOT of
      g          #   the character at index
       Us2       #     the input converted to binary
           a1    #     the index of its last 1
              -1 #     minus 1
      g          #   in string
  Us2            #     the input converted to binary
Люк
источник
Это возвращается falseдля всего, потому что символ (0 или 1) всегда является строкой.
Лохматый
К сожалению, должен был заметить, что ... Исправлено сейчас
Люк
Похоже, пока что не получается1 .
Лохматый
0

JavaScript (ES6), 53 34 байта

a=>eval("for(;~a&1;a/=2);~a>>1&1")
Люк
источник
42 байта: a=>!+(a=a.toString(2))[a.lastIndexOf(1)-1]
Лохматый
Я уже нашел более короткое (математическое) решение ...
Люк
Здорово :) Не возражаете, если я выложу 42 байта?
Лохматый
@ Шэгги, нет, совсем нет
Люк
0

Чип , 93 байта

HZABCDEFG,t
 ))))))))^~S
H\\\\\\\/v~a
G\\\\\\/v'
F\\\\\/v'
E\\\\/v'
D\\\/v'
C\\/v'
B\/v'
A/-'

Принимает входные данные как байты с прямым порядком байтов. (TIO имеет немного Python, который делает это для вас). Дает выход либо как 0x0или0x1 . (TIO использует xxd для проверки значения).

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

Как это сделать?

Чип просматривает ввод по одному байту за раз, поэтому обработка многобайтового ввода добавляет объем, но не так сильно, как я опасался.

Давайте углубимся в это:

HZABCDEFG

Это HZстарший бит предыдущего байта (если он был) и A- Gсемь младших бит текущего байта. Они используются для определения младшего установленного бита числа.

        ,t
))))))))^~S

Когда найден младший установленный бит, у нас есть несколько дел. Этот первый фрагмент говорит: «если у нас есть установленный бит ( )s), то прекратите Sподавлять вывод и tзавершите работу после того, как мы напечатаем ответ.

H\\\\\\\/v~a
G\\\\\\/v'
...
A/-'

Какой бы бит текущего байта ( A- H) предшествовал только группе нулей, затем единица ( \и /: они смотрят на биты непосредственно к северу от них; мы можем верить, что все предыдущие биты были нулевыми) передаются на провода на право ( v, ', ...), то в зависимости от того значения она переворачивается и дается как младший бит выхода ( ~a).

Phlarx
источник