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
100001011000
est a0
. Voulez-vous dire le moins important1
?Réponses:
Mathematica 25 octets
Autres façons de procéder:
56 octets
58 octets
la source
Python 3 ,
2221 octets1 octet grâce à ETHproductions.
Essayez-le en ligne!
Ftw arithmétique bit à bit.
la source
0+(...)
?n&1
être mis entre parenthèses? Ou est-ce1+(n^~-n)<1
que cela peut être mis entre parenthèses? Ou est-ce1+(n^~-n)
...&
a la priorité la plus faible, il en est ainsi1+(n^~-n)
Retina ,
383429 octetsEssayez-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.
la source
Gelée , 5 octets
Essayez-le en ligne!
Comment ça marche
la source
Alice , 8 octets
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):
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
la source
05AB1E , 6 octets
Essayez-le en ligne!
la source
Sage ,
282016 octetsEssayez-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 aurons0
si ce bit était désactivé et une puissance de 2 si ce bit était activé, nous pouvons le changer en un seul1
ou0
avec:[?>]
. Une fois cela fait, il suffit de nier le bit~-^
et nous avons terminé.la source
Python 2 , 19 octets
Essayez-le en ligne!
la source
Haskell ,
454339 octets6 octets économisés grâce à nimi
Essayez-le en ligne!
la source
div
place dequot
.divMod
:f x|(d,m)<-divMod x 2=[mod(1+d)2,f d]!!m
|(d,m)<-divMod x 2
Est un garde de modèle pour se lierd
àdiv x 2
etm
àmod x 2
. Nous utilisonsm
pour indexer la liste des deux éléments[...,...]!!m
. En cas dem==0
retourmod(1+d)2
et en cas dem==1
f d
.[f d,mod(1+d)2]
. Essayez-le en ligne! .Code machine x86,
171615 octets:Suppose un ABI où les paramètres sont poussés sur la pile et la valeur de retour est dans le
AL
registre.Ceci est démonté comme suit:
la source
JavaScript (ES6),
1714 octetsEdit: enregistré 3 octets en portant la réponse de @ Dennis une fois que j'ai remarqué que la sortie booléenne était acceptable.
la source
C (gcc) , 20 octets
Essayez-le en ligne!
la source
INTERCAL , 50 octets
Les opérateurs unaires INTERCAL sont tout à fait appropriés pour cela, j'ai donc décidé d'écrire mon premier article.
la source
Haskell , 33 octets
Essayez-le en ligne!
Utilise l'indexation 0.
la source
~
dans ce contexte? Je comprends que c'est un match paresseux, mais pourquoi avez-vous besoin d'un match paresseux?Gelée ,
76 octets1 octet merci à Erik l'Outgolfer.
Essayez-le en ligne!
Programmes plus longs
Họ¡2&2Ị
Bt0ṫ-ḄỊ
la source
ṖṪṆ
(comme ma réponse supprimée) au lieu deṫ-ḄỊ
.BUḌDḊḢ¬
,,, ,
109 octetsExplication
Prenez l'entrée 3 par exemple.
la source
Haskell , 26 octets
Essayez-le en ligne!
Sortie booléenne.
la source
Octave , 34 octets
Essayez-le en ligne!
Explication:
la source
Soumission:
Python 2 ,
4139 octetsEssayez-le en ligne!
-2 octets grâce à FryAmTheEggman
Solution initiale:
Python 2 , 43 octets
Essayez-le en ligne!
la source
~-x&1
fonctionne pour la condition while à la place, je pense.MATL ,
1110 octetsEssayez-le en ligne! Ou consultez les 100 premières sorties .
Explication
la source
Pari / GP , 20 octets
Utilisation du symbole Kronecker .
Essayez-le en ligne!
la source
Befunge-98 , 19 octets
Essayez-le en ligne!
la source
SCALA, 99 (78?) Caractères, 99 (78?) Octets
où
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):
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.
la source
C (gcc) ,
3531 octetsPassé à une implémentation récursive. Essayez-le en ligne!
la source
Java 8, 17 octets
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?
la source
Japt ,
10 89 octetsEssayez-le en ligne!
Explication
la source
false
pour tout parce que le caractère (0 ou 1) est toujours une chaîne.1
instant.JavaScript (ES6),
5334 octetsla source
a=>!+(a=a.toString(2))[a.lastIndexOf(1)-1]
PHP> = 7.1, 32 octets
PHP Sandbox Online
PHP , 40 octets
Essayez-le en ligne!
PHP , 41 octets
Essayez-le en ligne!
la source
Lisp commun, 56 octets
Essayez-le en ligne!
la source
Puce , 93 octets
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
0x0
ou0x1
. (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:
Ce sont
HZ
, le bit haut de l'octet précédent (s'il y en avait un), etA
-G
, les sept bits inférieurs de l'octet actuel. Ils sont utilisés pour localiser le bit le plus bas du nombre.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 deS
supprimer la sortie ett
terminez après avoir imprimé la réponse.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
).la source