L'expansion binaire binaire

9

Normalement, nous décomposons un nombre en chiffres binaires en lui affectant des puissances de 2, avec un coefficient de 0ou 1pour chaque terme:

25 = 1*16 + 1*8 + 0*4 + 0*2 + 1*1

Le choix de 0et 1n'est ... pas très binaire. Nous effectuerons la véritable expansion binaire en développant avec des puissances de 2, mais avec un coefficient de 1ou à la -1place:

25 = 1*16 + 1*8 + 1*4 - 1*2 - 1*1

Maintenant, cela semble binaire.

Étant donné un nombre positif, il devrait être trivial de voir que:

  • Chaque nombre impair a une infinité de véritables extensions binaires
  • Chaque nombre pair n'a pas de véritables extensions binaires

Par conséquent, pour qu'une véritable expansion binaire soit bien définie, nous avons besoin que l'expansion soit la plus petite , c'est-à-dire avec la plus courte longueur.

Étant donné un entier positif et impair n, retournez sa véritable expansion binaire, du chiffre le plus significatif au chiffre le moins significatif (ou dans l'ordre inverse).

Règles:

  • Comme il s'agit de code-golf , vous devez viser à le faire dans le nombre d'octets le plus court possible. Les Builtins sont autorisés.
  • Toute sortie pouvant représenter et lister les coefficients est acceptable: un tableau, une chaîne de coefficients avec séparateurs, etc ...
  • Des échappatoires de golf standard s'appliquent.
  • Votre programme devrait fonctionner pour les valeurs comprises dans la taille entière standard de votre langue.

Cas de test

25 -> [1,1,1,-1,-1]
47 -> [1,1,-1,1,1,1]
1 -> [1]
3 -> [1,1]
1234567 -> [1,1,-1,-1,1,-1,1,1,-1,1,-1,1,1,-1,1,-1,-1,-1,-1,1,1]
code-golf integer binary base-conversion Voile
la source
Connexes mais assez différentes.
Giuseppe
4
Algorithme simple: convertir en base 2, remplacer les 0 par des -1, mettre le LSD à l'avant.
Josiah Winslow
Voile: Je n'expliquais pas les votes négatifs, je décrivais simplement un algorithme pour les personnes qui ont des commandes de conversion de base dans leur langue.
Josiah Winslow
Puisque vous êtes si désireux d'être vraiment binaire, pouvons-nous renvoyer la valeur sous forme de bits compressés avec la valeur de position habituelle, mais la nouvelle interprétation des deux états? c'est-à-dire, électriquement, c'est juste une tension haute ou basse (ou autre), et ce n'est pas de ma faute si les débogueurs standard s'impriment 0au lieu de -1l'état basse tension. L'appelant qui reçoit les bits sait ce qu'ils signifient. (C'est toujours un exercice de manipulation de bits non trivial, car une rotation à droite ne fonctionne que si elle a 32 bits significatifs. Par exemple, un nombre à 5 bits a besoin d'une largeur de rotation de 5.)
Peter Cordes
La sortie doit-elle inclure des séparateurs? Une 111-1-1sortie valide est-elle pour 25?
Oliver

Réponses:

7

Japt , 6 octets

¤é r0J

Essayez-le en ligne!

Explication:

¤é r0J  // Test input:                  25
¤       // Binary the input:            11001
 é      // Rotate 1 chars to the right: 11100
   r0J  // Replace 0s with -1:          111-1-1
Oliver
la source
1
Ah, la rotation; c'est pourquoi cela ne fonctionnait pas pour moi.
Shaggy
2
Tourner??? dagnabbit.
Giuseppe
3

Pyth ,  12  11 octets

|R_1.>jQ2 1

Essayez-le ici!

Comment?

| R_1.> JQ2 1 Programme complet.

      jQ2 Convertir l'entrée en une liste binaire.
     .> 1 Faites tourner la liste ci-dessus de façon cyclique de 1 place vers la droite.
| R_1 Remplacez 0 par -1.
               Sortie implicite.

Tout d'abord, nous remarquons que la tâche consiste simplement à "remplacer le 0s dans l'écriture binaire par -1s et à le déplacer vers la droite de 1 place". - C'est exactement ce que nous devons faire! La conversion binaire nous donne une liste de 0s et 1s. Tout ce que nous devons faire ici est de trouver un moyen de se convertir 0au golf -1. L'opérateur au niveau du bit |(OR au niveau du bit) est notre ami. La carte de la représentation binaire s'est déplacée avec |et -1. Si le nombre actuel est 0, il est converti en -1.

M. Xcoder
la source
Je ne pense pas qu'il y ait une meilleure façon. ;)
Josiah Winslow
@JosiahWinslow Je fais ... Essayer de le trouver
M. Xcoder
Hm? L'algorithme semble optimal, c'est peut-être parce que je ne connais pas Pyth.
Josiah Winslow
@JosiahWinslow Trouvé la meilleure façon. Meilleure façon syntaxique, pas meilleure méthode algorithmique.
M. Xcoder
@ Mr.Xcoder Et maintenant il n'y en a vraiment pas du moins pour moi.
Erik the Outgolfer
3

JavaScript (ES6), 35 34 octets

f=n=>n?[...f(n>>=1),!n|n%2||-1]:[]

Extrait de test

Afficher l'extrait de code

ETHproductions
la source
2

Perl 6 , 72 octets

Il y a sûrement une meilleure façon, mais c'est ce que j'ai ... 

->$a {grep {$a==[+] @^a.reverse Z+< ^∞},[X] (1,-1)xx $a.base(2).chars}

Essayez-le en ligne!

Explication : C'est une fonction qui prend un argument ( ->$a). Nous obtenons d'abord le nombre de coefficients nécessaires ( $a.base(2).chars= nombre de caractères dans la représentation de base 2), puis faisons un produit cartésien ( X) de ce nombre de paires (1,-1). (Le [X]moyen: réduisez la liste suivante avec X.) Nous obtenons donc une liste de toutes les combinaisons possibles de 1 et -1. Ensuite, nous filtrons ( grep) uniquement les listes qui codent le nombre donné $a. Il n'y en a qu'une, nous obtenons donc une liste d'une liste avec les coefficients.

Le bloc grep fait ceci: prend son argument comme une liste ( @^a), l'inverse et le zippe avec une liste infinie en 0,1,2,...utilisant l'opérateur "left bit shift" +<. Le zip s'arrête dès que la liste la plus courte est épuisée (bon pour nous!) Nous additionnons ensuite tous les résultats et les comparons avec le nombre donné. Nous avons dû utiliser .reverseparce que le PO exige que les coefficients soient dans l'ordre du plus significatif au moins significatif.

Ramillies
la source
1

05AB1E , 6 5 octets

bÁ0®:

Essayez-le en ligne!

Okx
la source
D<peut être ®( ®par défaut -1).
Erik the Outgolfer
@EriktheOutgolfer Merci! Je ne m'en étais pas rendu compte.
Okx
1

J, 11 octets

1-~2*_1|.#:

Essayez-le en ligne!

Merci à @JosiahWinslow pour l'algorithme.

Avez-vous des idées pour raccourcir la conversion? Mes pensées vont à l'utilisation de !.-fit (nvm, cela change juste la tolérance de la conversion).

L'utilisation de {-take est plus longue d'un caractère.

_1 1{~_1|.#:
cole
la source
1

Java 8, 101 octets

n->{String s=n.toString(n,2);return(s.charAt(s.length()-1)+s.replaceAll(".$","")).replace("0","-1");}

Port de @Oliver réponse Japt de , avec quelques octets de plus ..;)

Peut certainement être joué au golf en utilisant une approche mathématique au lieu de cette approche String.

Explication:

Essayez-le ici.

n->{                             // Method with Integer parameter and String return-type
  String s=n.toString(n,2);      //  Convert the Integer to a binary String
  return(s.charAt(s.length()-1)  //  Get the last character of the binary String
    +s.replaceAll(".$","")       //   + everything except the last character
   ).replace("0","-1");          //  Then replace all zeroes with -1, and return the result
}                                // End of method
Kevin Cruijssen
la source
1

R , 90 88 46 octets

function(n)c((n%/%2^(0:log2(n))%%2)[-1],1)*2-1

Essayez-le en ligne!

Implémente l'algorithme d'Oliver , mais renvoie les chiffres dans l'ordre inverse. Comme nous sommes garantis que ce nn'est jamais pair, le bit le moins significatif (le premier) est toujours 1, alors nous le supprimons et ajoutons un 1à la fin pour simuler la rotation en R. Merci à Shaggy de m'avoir permis de corriger mes calculs .

En termes simples rev( ) les appels de fonction dans le pied de page devrait renvoyer les valeurs dans le même ordre.

réponse originale, 88 octets:

function(n,b=2^(0:log2(n)))(m=t(t(expand.grid(rep(list(c(-1,1)),sum(b|1))))))[m%*%b==n,]

Fonction anonyme; renvoie les valeurs dans l'ordre inverse avec les noms de colonne attachés.

Essayez-le en ligne!

Explication:

function(n){
 b <- 2^(0:log2(n))         # powers of 2 less than n
 m <- expand.grid(rep(list(c(-1,1)),sum(b|1))) # all combinations of -1,1 at each position in b, as data frame
 m <- t(t(m))               # convert to matrix
 idx <- m%*%b==n            # rows where the matrix product is `n`
 m[idx,]                    # return those rows
}
Giuseppe
la source
Je ne considérerais pas cette sortie comme valide; suggérer de demander à l'auteur du défi de confirmer.
Shaggy
L'ordre inversé @Shaggy est explicitement autorisé: from the most significant digit to the least significant digit (or in reversed order).cela devrait donc être parfaitement acceptable.
Giuseppe
1
Inversé ordre , pas inversé les signes. Signification d'une sortie valide pour 25, par exemple, serait [1,1,1,-1,-1]ou [-1,-1,1,1,1].
Shaggy
1
@Shaggy ah, tu as raison, je viens de mal faire le calcul! devrait être 2*bits - 1au lieu de 1-2*bits. Je vous remercie.
Giuseppe
0

CJam, 12 octets

Un portage de ma réponse Golfscript.

qi2b{_+(}%)\
Josiah Winslow
la source
0

Golfscript, 14 13 14 octets

-1 octet car j'ai oublié qu'il %existait. +1 octet car j'ai également oublié que l'entrée est une chaîne.

~2base{.+(}%)\
Josiah Winslow
la source
1
Si vous supposez que l'entrée est un entier, vous devez envelopper le code {}pour en faire un bloc. Les programmes complets ne peuvent être saisis que sous forme de chaînes.
Peter Taylor
Euh, quoi? Je voulais dire, le nombre est poussé comme un entier, au lieu d'une chaîne contenant un nombre.
Josiah Winslow
Dans ce cas, votre réponse n'est pas un programme complet et doit donc être une "fonction" , ou dans le cas de GolfScript un bloc. C'est donc {2base{.+(}%\}pour 15 octets. De même, votre réponse CJam.
Peter Taylor
Ceci est un programme complet. Les entrées dans Golfscript sont implicitement poussées sur la pile au début du programme, et les entrées dans CJam sont spécifiées avant l'exécution et accessibles avec la commande q.
Josiah Winslow
J'ai une certaine familiarité avec GolfScript . ( Et CJam ). Si vous voulez prétendre qu'il s'agit d'un programme complet, vous devez le préfixer avec ~.
Peter Taylor