Tâche
Recherchez l'ensemble de nombres de telle sorte que la représentation binaire contient deux ou plusieurs exécutions 1
séparées par au moins une 0
.
Par exemple, pour les nombres de 4 bits:
0 0000 (no ones)
1 0001 (only one run)
2 0010 (only one run)
3 0011 (only one run)
4 0100 (only one run)
5 0101 Valid
6 0110 (only one run)
7 0111 (only one run)
8 1000 (only one run)
9 1001 Valid
10 1010 Valid
11 1011 Valid
12 1100 (only one run)
13 1101 Valid
14 1110 (only one run)
15 1111 (only one run)
Contribution
Un entier fourni à l'application via une entrée dans la plage 3 .. 32
. Cela représente le nombre maximal de bits à compter.
L'entrée de n
indique que les chiffres doivent être examinés.0 .. 2n-1
Sortie
Une liste délimitée (au choix) de tous les numéros répondant aux critères. Les chiffres doivent être présentés dans l'ordre numérique. Un délimiteur de fin supplémentaire est acceptable. Les enceintes de structure de données (par exemple []
et similaires) sont également acceptables.
Exemple
Input: 3
Output: 5
Input: 4
Output: 5, 9, 10, 11, 13
Input: 5
Output: 5, 9, 10, 11, 13, 17, 18, 19, 20, 21, 22, 23, 25, 26, 27, 29
C'est le code-golf - la réponse avec le moins d'octets gagne.
\n
délimite et met un\n
sur la dernière ligne, alors,
délimité par un,
suivi devrait également être acceptable. Mis à jour.[1, 2, 3]
?Réponses:
Pyth, 12 octets
Essayez-le en ligne.
Idée
La représentation binaire de tout nombre positif commence toujours par une séquence de 1 s, éventuellement suivie par d'autres séquences alternées de 0 s et de 1 s. S'il y a au moins trois cycles séparés, deux d'entre eux sont garantis comme des cycles de 1 s.
Code
la source
Python, 48
J'avais largement réfléchi à cela. Nous avons juste besoin de vérifier si l'expansion binaire contient
'01'
.Pour qu'il y ait deux séries d'unités, celle de droite doit être précédée d'un
0
. S'il n'y a qu'un seul run, il n'y aura pas de premier0
, donc ça n'arrivera pas.Ancienne réponse:
La représentation binaire Python fonctionne très bien ici. Un nombre binaire s'écrit comme
bin(9)=='0b10110'
. Fractionnement des'0'
résultats dans une liste de0
, entre deux consécutives0
et à droite de toute finale0
b
suivie d'un ou plusieurs principaux1
qui ne mènent pasLes deux premières catégories existent toujours, mais la dernière n'existe que s'il y en a une
1
qui ne contient pas le début'1'
, et donc seulement s'il y en a plus d'une1
. Il suffit donc de vérifier si la liste contient plus que2
des éléments distincts.Python 3.5 enregistre 2 caractères en déballant
{*_}
à la place deset(_)
.la source
/01/
place de/10+1/
. J'en ai profité en Perl .Rubis,
444038 caractèresbarré 44 est toujours régulier 44;
Une fonction anonyme (proc, en fait) qui prend un entier et retourne un tableau.
Utilise l'expression régulière@histocrat souligne que si/10+1/
: a1
, au moins une0
, puis une autre1
.01
est n'importe où dans la chaîne, il doit y avoir un1
quelque part avant.la source
/10+1/=~'%b'%x
. En outre, vous pouvez enregistrer un personnage en utilisant une plage inclusive (0..2**n
) car il2**n
n'aura jamais plusieurs exécutions.=~
. Merci!/01/
fonctionne aussi bien. S'il y a un01
, il doit y avoir un 1 à gauche quelque part.Julia,
4341 octetsCela crée une fonction sans nom qui accepte un entier et renvoie un tableau. Il utilise l'astuce regex des histocrates (utilisée dans la réponse de Doorknob), où
01
ne correspondra que s'il y a un 1 précédent.Non golfé:
la source
Matlab,
79 68 6459L'idée est d'interpréter le nombre binaire comme un tableau de zéros et de uns, puis de calculer la différence absolue entre chaque paire de voisins. Si nous avons deux ou plusieurs fois une différence de 1, alors nous avons évidemment une série de deux ou plus. Notez que cela ne fonctionne que si nous représentons le nombre binaire sans zéros de tête.
Anciennes versions:
la source
JavaScript (ES7),
8985726962 octetsHoly Cow, créer des gammes dans JS n'est pas facile.
Ce serait peut-être plus court avec uneNon, j'ai menti; c'est en fait un peu plus long. Tant pis. Je suppose que je vais devoir me contenter de 27 octets enregistrés. (7 grâce à Mwr247!)for
boucle réelle .Fonctionne correctement dans les dernières versions de Firefox, mais probablement pas dans aucun autre navigateur. Essaye le:
(Extrait extrait de cette page )
Bienvenue suggestions!
la source
.keys()
place de.fill()
eta
au lieu dei
lier le mien pour 62:x=>[for(a of Array(1<<x).keys())if(/01/.test(a.toString(2)))a]
Haskell,
686153 octetsAmélioration de Damien
Histoire:
Cela corrige le bug (Switched == et =, et carré au lieu de la puissance de deux). Et remplacez true par 2> 1 et false par 1> 2. Merci également de souligner que 2 ^ x est toujours un échec. Merci à Thomas Kwa et nimi
À l'origine
S'il doit s'agir d'un programme complet,
la source
1..(2^x-1)
ce qui peut être juste1.. (2^x)
car 2 ^ x échoue toujours.False
etTrue
par1>2
et1<2
. Pas besoin de parenthèses autour2^x-1
. (BTW: vous avez une faute de frappe: ça doit être4==1=True
).mod
4 == 1 = x> 4 | 2> 1 = g $ xdiv
2APL,
3427 octetsCela crée une fonction monadique sans nom qui accepte un entier à droite et renvoie un tableau.
Explication:
7 octets enregistrés grâce à Dennis!
la source
R,
5547 octets(avec l'aide de @ Alex.A)
R n'a pas de fonction intégrée pour afficher les nombres convertis d'une manière pratique, donc j'utilise
R.utils::intToBin
pour cela, alors que tout le reste est à peu près simplement signaler l'emplacement de l'expression d'expression rationnelle correspondante et imprimer sur STDOUT tout en étant séparé par un espace.la source
cat
est un espace, vous pouvez donc l'omettre,sep=","
entièrement, en économisant 7 octets.CJam, 14
3 octets plus court grâce à Dennis. Essayez-le en ligne
la source
2be`,2>
.2be`2>
et2,#)
devrait également fonctionner. De plus, l'OP a précisé que la sortie peut être imprimée sous forme de liste.JavaScript (ES6),
69686762 octetsAujourd'hui, j'ai découvert un nouveau moyen plus court de remplir dynamiquement des tableaux sans utiliser de remplissage ou de carte. Faire
x=>[...Array(x).keys()]
retournera un tableau de plage de 0 à x. Si vous souhaitez définir votre propre plage / valeurs, utilisezx=>[...Array(x)].map((a,i)=>i)
, car elle ne fait que quelques octets de plus.la source
Java,
214165155154 154148141110 octetsCette soumission exploite le fait qu'une représentation sous forme de chaîne binaire d'un nombre en Java n'a jamais de zéro de tête. Si la chaîne "01" apparaît dans la représentation binaire d'un nombre, cela doit marquer la deuxième occurrence du nombre "1".
Golfé:
Non golfé:
Sortie du programme (rappelez-vous, les délimiteurs de fin sont acceptables):
la source
int
la variable compteur?long
est requis. De plus, en utilisant unint
serait en fait augmenter la taille du code en raison de la référence à laInteger
classe d'emballage qui fait l'analyse numérique. Je pense que l'endroit le plus susceptible d'économiser de l'espace serait le regex, mais mes tests ont montré que je devais avoir le.*
Long
emballage avecint
? (Enfin pas dans ce cas mais en général?)int
sera promulong
lorsqu'il sera utilisé comme paramètre avecLong
. Dans ce cas, il n'y a pas vraiment de moyen d'utiliser un enint
raison du bit de signe, et ilInteger
est plus long queLong
. Pourtant, j'ai trouvé quelques façons de tirer un peu d'espace supplémentaire d'un langage aussi verbeux que Java.new Long()
place deLong.parseLong()
?C (gcc) ,
11199 octetsEssayez-le en ligne!
12 octets rasés grâce à @ceilingcat!
Non golfé:
La fonction ffsl () vous donne l'index du premier bit qui est défini dans un entier long. Nous bouclons donc de
i = 1
à 2 ^ nombre_de_bits. Nous avons définix
lei
décalage vers la droite jusqu'à ce que nous ayons supprimé tous les bits zéro consécutifs à l'extrémité la moins significative. Ensuite, nous décalons vers lax
droite jusqu'à ce que nous ayons supprimé tous les bits 1 consécutifs à l'extrémité la moins significative. Si le résultat n'est toujours pas nul, nous avons trouvé une correspondance.la source
if (popcount(i ^ (i*2))>3)
:, et étendre popcount () à une série de AND au niveau du bit et d'opérations de décalage. Mais cela entraînerait un code assez long.JavaScript (ES6) 76
la source
,,,,,5,,,,9,10,11,,13,,,,17,18,19,20,21,22,23,,25,26,27,,29,,
K5, 19 octets
Cela fonctionne selon des principes similaires à ceux de la solution de Dennis, mais avec moins de fonctionnalités intégrées à exploiter.
Tout d'abord, générez une série de x-tuples binaires (
+!x#2
), puis pour chaque tuple, trouvez chaque point qu'un chiffre ne correspond pas au précédent si nous traitons le -1e élément de la liste comme 0 à cet effet (~0=':'
). Nos solutions sont là où deux est inférieur à la somme de chaque nombre d'exécutions. (&2<+/'
).Montrer chaque étape intermédiaire est plus clair:
Et tous ensemble:
la source
Pip, 13 + 1 = 14 octets
Prend l'entrée de la ligne de commande et utilise l'
-s
indicateur pour les espaces entre les numéros de sortie.Assez simple: construire
range(2**a)
et filtrerlambda _: "01" in toBinary(_)
. J'étais assez content de penser l'01
idée de façon indépendante. Aucun guillemet n'est nécessaire01
car il scanne comme un littéral numérique (les nombres et les chaînes sont du même type dans Pip).la source
Julia, 40 octets
Cela utilise une approche quelque peu différente de l'autre solution Julia - plutôt que de faire une recherche de chaîne pour "01" dans la chaîne de bits, elle utilise des mathématiques pour déterminer si le nombre satisfait la condition.
i$i>>1
n'en aura que dans les endroits où le chiffre passe de zéro à un, ou de un à zéro. En tant que tel, il doit y en avoir au moins trois pouri
basculer entre zéro et une fois suffisamment.count_ones
trouve le nombre de ceux, puisfilter
supprime ceux qui n'en ont pas assez.la source
C ++,
197188141 octetsRemarque: cela a été écrit et testé à l'aide de MSVC ++ 2013. Il semble que
#include
ing<iostream>
inclut tous les en-têtes C nécessaires pour que cela fonctionne. Il semble également que le code ne soit plus vraiment C ++, mais la compilation à l'aide de C ++ permet cette astuce d'en-tête qui réduit la taille du code par rapport à l'inclusion de plusieurs en-têtes C.Utiliser
printf
au lieu decout
permet également d'économiser quelques octets.Golfé:
Non golfé:
la source
'\n'
place de std :: endl (en général), ou','
puisque tout séparateur est valide et qu'un séparateur est correct .strstr(c,"01")
.1<<atol(b[1])
devraient être1L<<atol(b[1])
, sinon le résultat de cette expression sera un entier signé de 32 bits, ce qui signifie que le code ne fonctionnera que jusqu'à 2 ^ 30. Le printf doit utiliser%ld
pour imprimer correctement les nombres entre 2 ^ 31 et 2 ^ 32.Perl 5,
5553494741 octets5452484640 octets, plus un pour le-E
drapeau au lieu de-e
.Merci à xnor pour l'astuce d'utiliser
/01/
au lieu de/10+1/
, qui a économisé deux octets.Merci à Dennis pour les conseils à utiliser
<>
au lieu de$ARGV[0]
, ce qui a permis d'économiser six octets.la source
C,
8481 octetsCeci est basé sur les commentaires que j'ai faits sur une autre réponse C à cette question sur la possibilité d'utiliser de simples opérateurs au niveau du bit. Il fonctionne en commutant tous les bits de fin 0 à 1 dans l'instruction i | (i-1). Ensuite, il passe tous les bits de fin 1 à 0 en utilisant k & (k + 1). Cela se traduira par un zéro s'il n'y a qu'une seule série de uns et différent de zéro sinon. Je fais l'hypothèse que long est 64 bits, mais je pourrais corriger cela au détriment de trois octets en utilisant int64_t à la place.
Non golfé
la source
int64_t
n'est défini que si vous#include<stdint.h>
. assurer un fonctionnement 64 bits nécessite unlong long
type au coût de 5 octets.long i
pour le%d
format. Notez également que()
sont superflus pour les opérateurs&
et|
. La correction de ceci économise 3 octets!long i,j,k;main(){for(scanf("%ld",&j);++i<1L<<j;k&k+1&&printf("%ld ",i))k=i|i-1;}
Pyth,
201716 octetsDémo en direct.
la source
"01"
. Sauf pour 0, le repr binaire. commencera toujours par un 1.Python 2.7, 89 octets
Je pense que cela pourrait être un peu joué au golf.
la source
0
dans la sortie.print[i for i in range(2**input())if[n[:1]for n in bin(i)[2:].split("0")].count("1")-1]
plus court de deux octets. Mais avec le correctif pour0
serait la même longueur (89), si vous utilisezrange(1,2**input())
.TI-BASIC,
343230 octetsPour une calculatrice de la série TI-83 + / 84 +.
Pour qu'un nombre contienne deux séries de 1, il doit contenir deux
10
s lorsque nous plaçons un zéro de fin sur la représentation binaire.Plutôt que de générer la représentation binaire et de vérifier a
10
, nous testons mathématiquement des paires de bits en utilisant le reste de 4 (int(4fPart(
), ce qui donnera2
où il y a a10
. Parce que nous ne nous soucions pas de l'ordre,randIntNoRep(
est le moyen le plus court de générer la liste des exposants.Nous utilisons
log(
pour vérifier le nombre d'exécutions:S'il y a au moins 2 exécutions, le
log(
est positif et le nombre s'affiche.S'il y a un essai, le
log(
est 0 et le nombre ne s'affiche pas.S'il n'y a pas de parcours (ce qui se produit d'abord à X = 2 ^ Ans), alors
log(
lance un ERR: DOMAIN, arrêtant la sortie exactement au bon point.Nous utilisons
e^(Ans
comme argument de fin de laFor(
boucle - il est toujours supérieur à2^Ans
, maise^(
c'est un seul jeton, donc c'est un octet plus court.Entrée / sortie pour N = 4:
Ensuite, la calculatrice lance une erreur; l'écran d'erreur ressemble à ceci:
Lorsque vous appuyez sur 1, l'écran d'accueil s'affiche à nouveau:
Les calculatrices TI stockent tous les nombres dans un flottant BCD avec 14 chiffres de précision, pas un flottant int ou binaire. Par conséquent, les divisions par des pouvoirs de deux supérieurs à
2^14
peuvent ne pas être exactes. Même si j'ai vérifié que les nombres les plus délicats3*2^30-1
et2^32-1
sont correctement gérés, je n'ai pas exclu la possibilité d'erreurs d'arrondi. Je serais cependant surpris s'il y avait des erreurs pour toute entrée.la source
matlab
(90)(70)exécution
4
ans =
ans =
ans =
principe
N'importe quel nombre pris dans l'intervalle] f (n, l), f (n, l) + 2 ^ (l-1) [où l> 1 vérifie cette condition, donc le résultat est le résultat de la négation de cette série dans termes de n.
x = 1
x = x + 1 =
01
,x = x + 2 ^ 0 =
11
,x = x + 1 =
001
,x = x + 2 ^ 1 =
011
,x = x + 2 ^ 0 =
111
,x = x + 1 =
0001
,x = x + 2 ^ 2 =
0011
,x = x + 2 ^ 1 =
0111
,x = x + 2 ^ 0 =
0111
,x = x + 1 =
1111
...x + 1, x = x + 2 ^ n, x = x + 2 ^ (n-1) ... x = x + 2 ^ 0
Mon programme imprime la plage entre chacune des deux lignes (si elle existe)
après une période de lutte, j'ai réussi à trouver une représentation mathématique pour cette série qui est:
2 ^ l (0 + 1 + 2 ^ 1 + ... 2 ^ k) avec l + k <n
= 2 ^ l (2 ^ k-1)
score = 90
la source
C,
103102 octetsExpansion (en fait contractante) sur l'entrée G.Sliepen, profitant de la remarque xnor sur le
01
modèle dans la représentation binaire, mais en utilisant uniquement des fonctions standard et un peu de twiddling.Version non golfée:
La boucle interne recherche
i
le motif binaire01
en se déplaçant itérativementx
vers la droite tant qu'il reste 3 bits.printf
renvoie le nombre de caractères imprimés, donc jamais0
, donc le test de la boucle interne échoue après leprintf
, évitant ainsi la nécessité d'unebreak
instruction.C ++,
129128 octetsAdaptant la même idée, la variante C ++ est ici:
Techniquement, je devrais faire
i
unlong long
pour assurer un fonctionnement 64 bits et calculer jusqu'à2^32
5 octets supplémentaires, mais les plates-formes modernes ont des entrées 64 bits.la source
JavaScript ES6, 60 octets
Code
Essayez-le en ligne!
Explication
la source
C (en quelque sorte - compile avec les avertissements dans GCC) - 103
Cela n'utilise aucune fonction de bibliothèque d'aucune sorte, sauf printf. Vous pouvez voir en regardant cela qu'aucun effort n'a été épargné pour le rendre conforme aux normes ou éviter l'UB.
Pour le rendre conforme, vous devrez faire beaucoup de choses comme inclure stdio.h, ce qui serait contraire à l'esprit de le rendre aussi petit que possible.
Si quelqu'un a des suggestions pour le raccourcir, faites-le moi savoir.
la source
PowerShell, 80 octets
la source
Python, 44 octets
D'accord, cela pourrait probablement être plus court mais c'est mon premier codegolf:
Pensez que cela répond à la question, veuillez ne pas voter contre si ce n'est pas le cas, affichez simplement ce qui ne va pas ci-dessous.
la source
input()
est idéal) pour obtenirn
, puis compter uniquement jusqu'à2^n-1
, plutôt que de boucler indéfiniment. En outre, vous pouvez utiliser 1 et 2 espaces pour l'imbrication, plutôt que 4 et 8, et l'utilisationmap
ou une compréhension de liste raccourcirait probablement considérablement votre code.une autre réponse matlab différente de bon score.
matlab
60(57)exécution
ans =
>> ans(5)
ans =
1
Exemple:
0000111
est rejeté car ~ x =1111
, ~ x + 1 =00001
contient un chiffre = 10100111
est accepté car ~ x =1011
, ~ x + 1 =0111
contient plusieurs 1la source