La séquence Dragon Curve

23

La séquence de la courbe du dragon (ou la séquence de pliage de papier ordinaire) est une séquence binaire. a(n)est donné par négation du bit gauche du 1 le moins significatif de n. Par exemple, pour calculer, a(2136)nous convertissons d'abord en binaire:

100001011000

Nous trouvons notre bit le moins significatif

100001011000
        ^

Prenez le mors à sa gauche

100001011000
       ^

Et retourner sa négation

0

Tâche

Étant donné un entier positif en entrée, en sortie a(n). (Vous pouvez sortir par entier ou par booléen). Vous devez viser à rendre votre code aussi petit que possible, mesuré en octets.

Cas de test

Voici les 100 premières entrées dans l'ordre

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
Assistant de blé
la source
9
Le bit le moins significatif 100001011000est a 0. Voulez-vous dire le moins important 1?
diffusion le

Réponses:

16

Mathematica 25 octets

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

Autres façons de procéder:

56 octets

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

58 octets

1-Nest[Join[#,{0},Reverse[1-#]]&,{0},Floor@Log[2,#]][[#]]&
Kelly Lowder
la source
3
Hou la la! Une réponse mathématique et ce n'est pas seulement intégré. Ayez un vote positif!
KeyWeeUsr
2
La seule chose qui pourrait améliorer cette réponse est d'expliquer pourquoi et comment cela fonctionne. : P
Martin Ender
2
@MartinEnder arxiv.org/pdf/1408.5770.pdf Voir la remarque après l'exemple 13.
alephalpha
7

Python 3 , 22 21 octets

1 octet grâce à ETHproductions.

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

Essayez-le en ligne!

Ftw arithmétique bit à bit.

Leaky Nun
la source
2
"Vous pouvez sortir par entier ou par booléen" donc je suppose que vous n'avez pas besoin du 0+(...)?
Martin Ender
L'ordre des opérations ici me dérange vraiment. Pourrait n&1être mis entre parenthèses? Ou est-ce 1+(n^~-n)<1que cela peut être mis entre parenthèses? Ou est-ce 1+(n^~-n)...
ETHproductions
oh mon dieu quoi. c'est ce que je cherchais: o sympa!
HyperNeutrino
&a la priorité la plus faible, il en est ainsi1+(n^~-n)
Leaky Nun
Ah, trouvé la table de priorité. Maintenant, tout a du sens: P
ETHproductions
6

Retina ,38 34 29 octets

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

Essayez-le en ligne!

Martin et Leaky ont essentiellement proposé cette idée, pour 5 octets de plus!

Convertit l'entrée en unaire, puis divise progressivement le nombre par 2. Une fois qu'il ne peut plus le faire uniformément (c'est-à-dire que le nombre est impair), il supprime ensuite les correctifs de 4 de l'entrée, calculant le résultat de la dernière opération mod 4 Enfin, cela vérifie si le résultat était 1, ce qui signifie que le chiffre à gauche du bit le moins significatif était zéro. Si c'est vrai, le résultat final est 1, sinon il est nul.

FryAmTheEggman
la source
31 octets (dois-je le poster moi-même?)
Leaky Nun
J'ai trouvé un moyen d'éviter la conversion binaire complète et de diviser les facteurs de 2 et de vérifier l'égalité avec 1 (mod 4): tio.run/##K0otycxL/…
Martin Ender
@MartinEnder essentiellement mon algorithme ... avec 2 octets de moins
Leaky Nun
@LeakyNun Oh oui, ils sont tous les deux la même idée. De grands esprits et des trucs ...;)
Martin Ender
Je vais le modifier dans, mais si l'un de vous veut le poster, je reviendrai, car je n'y aurais probablement pas pensé moi-même;)
FryAmTheEggman
6

Gelée , 5 octets

&N&HṆ

Essayez-le en ligne!

Comment ça marche

&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.
Dennis
la source
4

Alice , 8 octets

I2z1xnO@

Essayez-le en ligne!

Prend l'entrée comme point de code d'un caractère Unicode et sort le résultat sous la forme d'un octet 0x00 ou 0x01 en conséquence.

Pour la testabilité, voici une version d'E / S décimale à 12 octets qui utilise exactement le même algorithme (seule l'E / S est différente):

/o
\i@/2z1xn

Essayez-le en ligne!

Si Alice était un langage de golf et ne nécessitait pas d'E / S explicites et de terminaison de programme, cela se terminerait à 5 octets ( 2z1xn) en battant à la fois 05AB1E et Jelly.

Explication

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.
Martin Ender
la source
3

Sage , 28 20 16 octets

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

Essayez-le en ligne!

Explication

Il s'agit d'un portage de la réponse Python de Leaky Nun. Malheureusement, cela ne fonctionne pas sur TIO car la version de TIO de l'interpréteur est un peu dépassée.

Nous commençons par faire 3 copies de notre entrée avec ::, nous décrémentons ensuite la copie du haut par 1. Cela retournera tous les bits jusqu'au premier 1. Nous allons ensuite xor ceci avec une autre copie de notre entrée. Puisque tous les bits jusqu'au premier 1 sur notre entrée ont été inversés, tous ces bits seront 1 sur le résultat. Si nous ajoutons ensuite un ~-au résultat, nous obtiendrons un seul 1 à la gauche de notre 1. le moins significatif. Nous ET ceci avec l'entrée pour obtenir ce bit de l'entrée. Maintenant, nous aurons 0si ce bit était désactivé et une puissance de 2 si ce bit était activé, nous pouvons le changer en un seul 1ou 0avec :[?>]. Une fois cela fait, il suffit de nier le bit ~-^et nous avons terminé.

Assistant de blé
la source
3

Haskell , 45 43 39 octets

6 octets économisés grâce à nimi

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

Essayez-le en ligne!

Assistant de blé
la source
Vous pouvez utiliser à la divplace de quot.
nimi
Mieux encore: divMod:f x|(d,m)<-divMod x 2=[mod(1+d)2,f d]!!m
Nimi
@nimi Je ne comprends même pas comment cela fonctionne. Vous devriez probablement le poster vous-même.
Wheat Wizard
Il est toujours le même algorithme, mais juste une autre façon de choisir la branche (appel récursive f nouveau contre cas de base), donc ne hésitez pas à modifier en. |(d,m)<-divMod x 2Est un garde de modèle pour se lier dà div x 2et mà mod x 2. Nous utilisons mpour indexer la liste des deux éléments [...,...]!!m. En cas de m==0retour mod(1+d)2et en cas de m==1 f d.
nimi
1
Oh, désolé, vous devez retourner les éléments de la liste: [f d,mod(1+d)2]. Essayez-le en ligne! .
nimi
3

Code machine x86, 17 16 15 octets:

Suppose un ABI où les paramètres sont poussés sur la pile et la valeur de retour est dans le ALregistre.

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

Ceci est démonté comme suit:

_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
Govind Parmar
la source
1
@PeterTaylor Je compte la taille de l'instruction CPU en octets pour ma réponse; c'est une pratique assez courante sur PPCG pour les réponses d'assemblage.
Govind Parmar
1
Je ne pourrais pas dire à quel point c'est courant, mais c'est définitivement faux
Peter Taylor
1
Ce n'est pas seulement pédant, c'est aussi vide de sens. Il n'y a pas de distinction entre "code machine" et "code assembleur" en ce qui concerne un ordinateur. La différence n'est qu'une question d'interprétation. Nous attribuons des mnémoniques aux octets de code machine pour les rendre plus faciles à lire pour les humains. En d'autres termes, nous dissolvons les octets pour les rendre plus faciles à comprendre.
Cody Gray
3
Ce n'est pas pertinent, @Peter. Le code assembleur n'est qu'une traduction lisible par l'homme du code machine. Ils sont exactement le même langage, juste sous deux formes / représentations différentes. Ce n'est pas différent de TI BASIC, où il est communément admis que nous comptons les jetons , au lieu des octets de caractères, car c'est ainsi que le système les stocke en interne. La même chose serait vraie avec le langage d'assemblage: les mnémoniques d'instructions ne sont pas stockées sous forme de caractères individuels, mais plutôt représentées sous forme d'octets de code machine équivalent.
Cody Gray
2
En outre, pratiquement, pourquoi quelqu'un entrerait-il jamais des mnémoniques étendus en langage assembleur dans une compétition de code-golf, alors qu'il pourrait les traduire en code machine 100% équivalent, où l'entrée est garantie d'être plus courte gratuitement? Cela seul fait une distinction entre les deux inutiles, sinon entièrement absurdes.
Cody Gray
3

JavaScript (ES6), 17 14 octets

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

Edit: enregistré 3 octets en portant la réponse de @ Dennis une fois que j'ai remarqué que la sortie booléenne était acceptable.

Neil
la source
3

C (gcc) , 20 octets

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

Essayez-le en ligne!

Dennis
la source
Cela ne fonctionne pas réellement; vous vous appuyez sur une bizarrerie du générateur de code pour une version particulière du compilateur ciblant une architecture particulière, où les calculs intermédiaires sont effectués dans le même registre qui est utilisé pour les valeurs de retour. L'activation de tout type d'optimisation, la modification de l'architecture cible ou l'utilisation d'une version différente de GCC rompra cela. Vous pourriez tout aussi bien dire "les ordures sur ma pile contiennent la bonne sortie quand il y a une pleine lune le 13 octobre".
Cody Gray
Bien que tout ce que vous dites soit vrai et qu'un code comme celui-ci ne soit jamais utilisé dans le code de production, nous définissons les langages par leurs implémentations à des fins de code golf. Sans drapeaux supplémentaires, cela fonctionne dans toutes les versions récentes de gcc et tcc, et il ne doit fonctionner que dans une seule version pour être considéré comme valide.
Dennis
"nous définissons les langages par leurs implémentations à des fins de code golf" Attendez, quoi? Donc, chaque drapeau du compilateur et chaque version de GCC définit un langage différent? Vous réalisez que c'est fou, non? La norme du langage C est ce qui définit le langage.
Cody Gray
Pas ici. S'il y avait une norme C mais pas d'implémentation, nous ne la considérerions même pas comme un langage. Comme je l'ai déjà dit, le compilateur définit le langage . Par conséquent, s'appuyer sur un comportement non défini est autorisé . Un ensemble différent d'indicateurs n'est pas considéré comme une langue différente, mais à moins que vous ne les ajoutiez à votre nombre d'octets, toutes les réponses utilisent des indicateurs de compilation standard.
Dennis
Sensationnel. C'est fou. Je veux dire, je pourrais comprendre si vous disiez que défini par l' implémentation comportement est permis, mais le comportement non défini est pas défini par la mise en œuvre. C'est littéralement indéfini. L'implémentation est autorisée à faire des choses aléatoires à chaque fois. Et cette notion de "drapeaux de compilation standard" est quelque chose que vous venez d'inventer. Mes indicateurs de compilation standard incluent plusieurs qui cassent votre code. Et je pense à peine que l'optimiseur n'est pas standard. Eh bien, ce site n'est clairement pas pour moi.
Cody Gray
3

INTERCAL , 50 octets

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

Les opérateurs unaires INTERCAL sont tout à fait appropriés pour cela, j'ai donc décidé d'écrire mon premier article.

DO WRITE IN .1
DO .1 <- !?1~.1'~#1
DO READ OUT .1
PLEASE GIVE UP
Bernd Fischer
la source
3

Haskell , 33 octets

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

Essayez-le en ligne!

Utilise l'indexation 0.

Anders Kaseorg
la source
1
Que fait le ~dans ce contexte? Je comprends que c'est un match paresseux, mais pourquoi avez-vous besoin d'un match paresseux?
Wheat Wizard
2

Gelée , 7 6 octets

1 octet merci à Erik l'Outgolfer.

Bt0ṖṪṆ

Essayez-le en ligne!

Programmes plus longs

Leaky Nun
la source
Hmm ... eh bien, vous pouvez simplement faire ṖṪṆ(comme ma réponse supprimée) au lieu de ṫ-ḄỊ.
Erik the Outgolfer le
1
Un autre pour votre liste de 7 octets:BUḌDḊḢ¬
steenbergh
2

,,, , 10 9 octets

::0-&2*&¬

Explication

Prenez l'entrée 3 par exemple.

::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                             []
totalement humain
la source
2

Octave , 34 octets

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

Essayez-le en ligne!

Explication:

@(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
Stewie Griffin
la source
Comment se fait-il que je n'ai jamais entendu parler de de2bi ...: O
Sanchises
1

Soumission:

Python 2 , 41 39 octets

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

Essayez-le en ligne!

-2 octets grâce à FryAmTheEggman

Solution initiale:

Python 2 , 43 octets

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

Essayez-le en ligne!

HyperNeutrino
la source
Alors, lequel est votre soumission?
Leaky Nun
@LeakyNun Le premier parce qu'il est plus court; la seconde était ma soumission originale. Dois-je les publier séparément?
HyperNeutrino
~-x&1fonctionne pour la condition while à la place, je pense.
FryAmTheEggman
(J'oublie le nom d'utilisateur); J'ai rejeté votre modification, car les modifications apportées au code de golf d'autres personnes ne sont pas conseillées sur PPCG. Vous pouvez publier des suggestions (btw, merci @FryAmTheEggman), mais veuillez ne pas apporter de modifications au golf. Merci!
HyperNeutrino
@StewieGriffin Ah oui, merci. Malheureusement, je ne peux pas cingler l'utilisateur car la modification a été rejetée.
HyperNeutrino
1

MATL , 11 10 octets

t4*YF1)Z.~

Essayez-le en ligne! Ou consultez les 100 premières sorties .

Explication

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
Luis Mendo
la source
1

Befunge-98 , 19 octets

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

Essayez-le en ligne!

&#                       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
ovs
la source
1

SCALA, 99 (78?) Caractères, 99 (78?) Octets

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

i est l'entrée.

Comme vous pouvez le voir, j'économise 21 octets si je ne m'occupe pas du zéro (comme l'auteur l'a fait dans son cas de test):

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

Ceci est mon premier codegolf donc j'espère avoir bien fait :)

Essayez-le en ligne! Bien qu'il soit assez long pour calculer lol.

V. Courtois
la source
Bienvenue sur le site!
DJMcMayhem
1

Java 8, 17 octets

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

Port simple de la réponse Python 3 de LeakyNun . Je ne connais pas suffisamment les opérations au niveau du bit et la priorité des opérateurs pour voir une solution plus courte; peut-être qu'il y a un moyen d'éviter la parenthèse supplémentaire?

JollyJoker
la source
0

Japt , 10 8 9 octets

!+¢g¢a1 É

Essayez-le en ligne!

Explication

!+¢   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
Luc
la source
Cela renvoie falsepour tout parce que le caractère (0 ou 1) est toujours une chaîne.
Shaggy
Oups, j'aurais dû remarquer que ... Corrigé maintenant
Luke
On dirait que ça échoue pour l'1 instant.
Shaggy
0

JavaScript (ES6), 53 34 octets

a=>eval("for(;~a&1;a/=2);~a>>1&1")
Luc
la source
42 octets:a=>!+(a=a.toString(2))[a.lastIndexOf(1)-1]
Shaggy
J'ai déjà trouvé une solution (mathématique) plus courte ...
Luke
Nice :) Ça vous dérange si je poste celui de 42 octets?
Shaggy
@Shaggy, non pas du tout
Luke
0

Puce , 93 octets

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

Prend les entrées sous forme de petits octets endiens. (Le TIO a un peu de python qui fait ça pour vous). Donne la sortie en tant que 0x0ou 0x1. (Le TIO utilise xxd pour inspecter la valeur).

Essayez-le en ligne!

Comment ça?

Chip examine l'entrée un octet à la fois, donc la gestion de l'entrée multi-octets ajoute du volume, mais pas autant que je le craignais.

Allons-y:

HZABCDEFG

Ce sont HZ, le bit haut de l'octet précédent (s'il y en avait un), et A- G, les sept bits inférieurs de l'octet actuel. Ils sont utilisés pour localiser le bit le plus bas du nombre.

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

Lorsque le bit le plus bas est trouvé, nous avons quelques choses à faire. Ce premier morceau dit "si nous avons un bit défini (le )'s), alors arrêtez de Ssupprimer la sortie et tterminez après avoir imprimé la réponse.

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

Le bit de l'octet en cours ( A- H) n'est précédé que d'un tas de zéros, puis d'un ( \et /: ceux-ci regardent les bits directement au nord d'eux; nous pouvons être sûrs que tous les bits précédents étaient nuls) est transmis aux fils sur le droit ( v, ', ...), alors quelle que soit la valeur Augmentin est inversé et étant donné que le bit faible de la production ( ~a).

Phlarx
la source