Sur la base de la notation "binaire, mais avec deux" mentionnée dans cette vidéo numérique , écrivez une fonction qui prend un seul numéro en entrée et génère toutes les variations de ce nombre dans un système "binaire" où les deux sont autorisés.
Règles
- Le code ne doit être qu'une fonction / méthode, pas un programme complet
- L'entrée est un entier transmis comme seul paramètre à la fonction
- La sortie est toutes les variations valides du nombre d'entrée converties en notation "binaire, mais avec deux"
- La sortie est la valeur de retour de la fonction, mais peut être dans n'importe quel format qui convient à condition qu'elle soit évidente (par exemple, 3 ints, 3 chaînes, chaîne délimitée par des virgules / espaces, tableau d'ints, etc.), l'ordre est sans importance
- Dans le cas peu probable où une langue contiendrait une fonction intégrée pour obtenir le résultat, elle est interdite
- Le code le plus court en octets est le gagnant
Explication de la sortie
Par exemple, si vous passez le nombre 9
, vous pouvez le convertir en binaire en tant que 1001
, mais si vous avez autorisé 2
s dans chaque position, vous pouvez également l'écrire comme 201
(ie 2*4 + 0*2 + 1*1
), ou 121
(ie 1*4 + 2*2 + 1*1
), comme indiqué dans ce tableau:
+----+----+----+----+
| 8s | 4s | 2s | 1s |
+----+----+----+----+
| 1 | 0 | 0 | 1 |
| 0 | 2 | 0 | 1 |
| 0 | 1 | 2 | 1 |
+----+----+----+----+
Donc, si elle est réussie 9
, votre fonction devra renvoyer les trois nombres 1001
, 201
et 121
.
Le format et l'ordre ne sont pas pertinents, tant qu'ils sont évidents (c. [121,201,1001]
-à- d . "0201 0121 1001"
, ("1001","121","201")
Sont des résultats valides lorsqu'ils reçoivent une entrée 9
)
Exemples
2
=>10, 2
9
=>1001, 201, 121
10
=>1010, 210, 202, 1002, 122
23
=>2111, 10111
37
=>100101, 20101, 100021, 20021, 12101, 12021, 11221
la source
Réponses:
GolfScript (25 octets) / CJam (
1917 octets)GolfScript:
Cela crée une fonction anonyme (voir la méta-discussion sur la licéité des fonctions anonymes ).
Démo en ligne
Une traduction directe dans CJam est (avec merci à Martin Büttner pour avoir rasé quelques caractères)
Dissection
La raison de l'opération de quadrature est que nous devons itérer jusqu'à la plus grande valeur possible dont la représentation ternaire, interprétée en binaire, est égale à
^
. Depuis2 = 10
, la représentation binaire "normale" de^
est celle qui compte. Si nous convertissons cela en ternaire, nous constatons que les "pires" cas sont des puissances de 2. Une approche optimale serait de prendre l'argument à la puissance deln 3/ln 2 ~= 1.585
, mais la quadrature est beaucoup plus courte.la source
Python 2 (59 octets)
(Un grand merci à @grc, @xnor et @PeterTaylor pour leur aide dans le chat)
Récursivité simple, appel avec
S(23)
ou similaire.Explication
L'idée générale est que si
n
l'expansion binaire de se termine par a1
, alors toute expansion pseudo-binaire ("binaire, mais avec deux") doit également se terminer par a1
. Sinon, cela pourrait se terminer par0
ou2
.Par conséquent, nous regardons le dernier bit de
n
, diviser et se ramifier en conséquence.Dissection
Variables:
n
: Le nombre dont nous voulons trouver les extensions pseudo-binaires deB
: Une chaîne pseudo-binaire en cours de construction de droite à gauchela source
Bash + coreutils, 77
(C'est un TABcaractère dans l'expression grep.)
Cela plie un peu cette règle:
"Dans le cas peu probable où une langue contiendrait une fonction intégrée pour obtenir le résultat, elle est interdite"
Il s'avère que cela
dc
a l'inverse de ce dont nous avons besoin. Par exemple, si nous définissons la base d'entrée sur 2 et entrons un nombre binaire avec deux, il l'analysera correctement. (De même, si le mode d'entrée est en base 10, les AF sont analysés sous forme de "chiffres" décimaux 10-15).seq
crée une liste de tous les nombres décimaux jusqu'à la représentation binaire standard de n, analysée comme une décimale. Ensuite, tous les nombres qui contiennent autre chose que {0,1,2} sont filtrés. Ensuite,dc
analyse les nombres restants comme binaires pour voir ceux qui reviennent à n.Les fonctions Bash ne peuvent que "renvoyer" des entiers scalaires 0-255. Je prends donc la liberté d'imprimer la liste sur STDOUT comme ma façon de "revenir". C'est idiomatique pour les scripts shell.
Production:
la source
Haskell, 82
ce n'est qu'une solution de force brute. il est très inefficace, car il devrait traverser 3 ^ n possibilités.
la source
Gelée , 10 octets, défi de postdates de langue
Essayez-le en ligne!
Une solution bruteforce jusqu'à un nombre d'hyperbits égal à l'entrée (ce format est appelé "hyperbinaire"). En tant que tel, il est incroyablement inefficace, fonctionnant en O (3 n ).
Explication
la source
PHP, 138 octets
Panne
la source
C ++, 159 octets
Testez-le ici
la source
k, 21 octets
Utilise la même méthode que la réponse Golfscript de Peter Taylor
Exemples:
la source