Numérotation des pages de style xkcd

65

Le livre de Randall Munroe "xkcd, volume 0" utilise un système de nombres plutôt impairs pour les numéros de page. Les premiers numéros de page sont

1, 2, 10, 11, 12, 20, 100, 101, 102, 110, 111, 112, 120, 200, 1000, 1001, ...

Cela ressemble un peu à ternaire, mais il faut noter qu'il saute de 20tout droit à 100, à partir 120de 200et à partir 200de 1000. Une façon de définir cette séquence est de dire qu'elle énumère tous les nombres ternaires qui contiennent au plus un 2et aucun 1après 2. Vous pouvez trouver cela sur OEIS dans l'entrée A169683 . Ce système de numération est appelé binaire de biais .

Votre tâche consiste à trouver la représentation d'un entier positif donné Ndans ce système de numération.

Vous pouvez écrire un programme ou une fonction en prenant l’entrée via STDIN (ou l’alternative la plus proche), un argument de ligne de commande ou une argumentation de fonction et en générant le résultat via STDOUT (ou l’alternative la plus proche), une valeur de retour de fonction ou un paramètre de fonction (out).

La sortie peut être une chaîne, un nombre avec une représentation décimale égale à la représentation binaire asymétrique ou une liste de chiffres (sous forme d'entiers ou de caractères / chaînes). Vous ne devez pas retourner les zéros non significatifs.

C'est le code de golf, donc la réponse la plus courte (en octets) gagne.

Anecdote: Ce système de numérotation présente certains avantages. Lorsque vous incrémentez un nombre, vous modifiez toujours au maximum deux chiffres adjacents. Vous ne devez jamais effectuer la modification sur l'intégralité du nombre. Avec la bonne représentation qui permet d’incrémenter en O (1).

Cas de test

1 => 1
2 => 2
3 => 10
6 => 20
7 => 100
50 => 11011
100 => 110020
200 => 1100110
1000 => 111110120
10000 => 1001110001012
100000 => 1100001101010020
1000000 => 1111010000100100100
1048576 => 10000000000000000001

1000000000000000000 => 11011110000010110110101100111010011101100100000000000001102

Je donnerai une prime à la réponse la plus courte qui peut résoudre le dernier cas de test (et toute autre entrée de même ampleur, alors ne pensez pas à le coder en dur) en moins d'une seconde.

Classements

Voici un extrait de pile permettant de générer à la fois un classement régulier et un aperçu des gagnants par langue.

Pour vous assurer que votre réponse apparaît, commencez votre réponse par un titre, en utilisant le modèle Markdown suivant:

# Language Name, N bytes

Nest la taille de votre soumission. Si vous améliorez votre score, vous pouvez conserver les anciens scores en les effaçant. Par exemple:

# Ruby, <s>104</s> <s>101</s> 96 bytes

<script>site = 'meta.codegolf'; postID = 5314; isAnswer = true; QUESTION_ID = 51517</script><script src='https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js'></script><script>jQuery(function(){var u='https://api.stackexchange.com/2.2/';if(isAnswer)u+='answers/'+postID+'?order=asc&sort=creation&site='+site+'&filter=!GeEyUcJFJeRCD';else u+='questions/'+postID+'?order=asc&sort=creation&site='+site+'&filter=!GeEyUcJFJO6t)';jQuery.get(u,function(b){function d(s){return jQuery('<textarea>').html(s).text()};function r(l){return new RegExp('<pre class="snippet-code-'+l+'\\b[^>]*><code>([\\s\\S]*?)</code></pre>')};b=b.items[0].body;var j=r('js').exec(b),c=r('css').exec(b),h=r('html').exec(b);if(c!==null)jQuery('head').append(jQuery('<style>').text(d(c[1])));if (h!==null)jQuery('body').append(d(h[1]));if(j!==null)jQuery('body').append(jQuery('<script>').text(d(j[1])))})})</script>

Martin Ender
la source
32
J'ai ce livre depuis sa parution et je n'ai jamais remarqué la numérotation des pages.
Alex A.
2
@Alexa. Je l’ai sur mon Kindle où vous ne pouvez effectuer aucune numérotation de page intéressante.
LegionMammal978
21
@ LegionMammal978: Tragic.
Alex A.
1
@ SuperJedi224 Le consensus semble être non , alors désolé (je ferais une exception du consensus si c'était le seul type de saisie que votre langage puisse gérer, mais cela ne semble pas être le cas).
Martin Ender
4
Cela me rappelle comment j'avais l'habitude de compter quand j'avais 3 ans. Je raisonnais: "il n'y a pas cinquante-dix ans, donc après cent-neuf ans, il doit y en avoir deux cent." Je me suis rendu compte de mon erreur en voyant la différence entre 59->60et 109->110, avec le 0 supplémentaire.
Cyoce

Réponses:

12

Pyth, 17 octets

Ljb3ye.f!-P-yZ01Q

C'est un peu ridiculement lent - O(output^log_2(3)). C'est exponentiel dans la longueur de l'entrée, mais pas doublement exponentiel, comme certaines des réponses sur la page. Quelques idées tirées de la réponse de @ Dennis, ici .

Manifestation.

Il utilise .fla fonction "boucle jusqu'à ce que n correspondances" de Pyth.

isaacg
la source
32

CJam, 24 23 22 21 19 octets

ri_)2b,,W%{2\#(md}/

Il s'agit d'une approche O (log n) , où n est l'entrée, qui complète le dernier cas de test instantanément. Il convertit n directement en biais binaire, en utilisant une division modulaire par les valeurs du chiffre 1 .

Ce code se termine par une erreur renvoyée à STDERR avec l'interpréteur Java, qui est autorisée conformément au consensus sur Meta .

Si vous essayez ce code dans l' interpréteur CJam , ignorez tout, sauf la dernière ligne de sortie.

L’erreur peut être éliminée, au prix de 2 octets, en ajoutant 2>au début à W%.

Merci à @ MartinBüttner pour le golf d'un octet.

Contexte

La représentation binaire de biais a k ... a 0 correspond à l'entier n = (2 k + 1 -1) a k + ... + (2 1 -1) a 0 .

Puisque les deux (2 k -1) + ... + (2 1 -1) = 2 k + 1 - (k + 2) et (2 k -1) + ... + 2 (2 j -1) = 2 k + 1 - (2 j + 1 - 2 j + k + 1) sont inférieurs à 2 k + 1 -1 , les valeurs de a k à a 0 peuvent être récupérées par division modulaire successive de 2 k + 1 -1 , 2 k -1 , etc.

Pour commencer, nous devons d’abord trouver la valeur de 2 k + 1 -1 . Puisque n est au plus 2 (2 k + 1 -1) , l'entier n + 1 doit être strictement inférieur à 2 k + 2 .

Ainsi, en prenant la partie entière du logarithme binaire de n + 1, on obtient k + 1 .

Enfin, nous observons que l'entier n + 1 a ⌊log 2 (n + 1) ⌋ chiffres en base 2.

Comment ça fonctionne

ri    e# Read an integer N from STDIN.
2b,   e# Push the number of binary digits of N + 1, i.e, K + 2 = log(N + 1) + 1.
,W%   e# Push the range [K+1 ... 0].
{     e# For each J in the range:
  2\# e#   J -> 2**J
  (   e#     -> 2**J - 1
  md  e#   Perform modular division of the integer on the stack (initially N)
      e#   by 2**J - 1: N, 2**J - 1 -> N/(2**J - 1), N%(2**J - 1)
}/    e#

Dans les deux dernières itérations, nous effectuons une division modulaire par 1 et 0 . Le premier pousse un 0 non désiré sur la pile. Les dernières tentatives d’exécution 0 0 md, qui suppriment les 0 non désirés de la pile, se terminent immédiatement au lieu d’appuyer sur quoi que ce soit et dumpent la pile dans STDOUT.

Dennis
la source
28

Python 2, 67 octets

def f(n):x=len(bin(n+1))-3;y=2**x-1;return n and n/y*10**~-x+f(n%y)

Semble fonctionner pour les cas de test donnés. Si j'ai bien compris, cela devrait être le cas O(place values set in output), alors le dernier cas est traité avec facilité.

Appelle comme f(100). Retourne une représentation décimale égale au binaire de biais.

Python 3, 65 octets

def g(n,x=1):*a,b=n>x*2and g(n,x-~x)or[n];return a+[b//x,b%x][:x]

Un peu moins efficace mais toujours logarithmique, le dernier cas est donc quasi instantané.

Appelle comme g(100). Retourne une liste de chiffres.

Sp3000
la source
ne 2andcompile en 3? Je suis dans 2 et 2and2jette une erreur de syntaxe
TankorSmash
3
@TankorSmash 2and2ne fonctionnerait pas car il serait analysé comme 2 and2- try 2and 2, qui devrait fonctionner si votre version de Python est suffisamment nouvelle (testé dans Python 2.7.10)
Sp3000 le
Oh bien, tu as raison. Même sur 2.7.3 cela fonctionne.
TankorSmash
12

CJam, 22 21 20 octets

ri_me,3fb{0-W<1-!},=

Ceci est un O (e n n) approche, où n est l'entrée. Il répertorie les premiers ⌊e n entiers non négatifs en base 3, élimine ceux qui ont 2 s ou 1 s après les 2 premiers (le cas échéant) et sélectionne le n + 1 e .

Essayez-le en ligne dans l' interprète CJam .

Comment ça fonctionne

ri    e# Read an integer N from STDIN.
_me,  e# Push [0 ... floor(exp(N))-1].
3fb   e# Replace each integer in the range by the array of its digits in base 3.
{     e# Filter; for each array A:
  0-  e#   Remove all 0's.
  W<  e#   Remove the last element.
  1-  e#   Remove all 1's.
  !   e#   Logical NOT. Pushes 1 iff the array is empty.
},    e#   If ! pushed 1, keep the array.
=     e# Select the (N+1)th element of the filtered array.
Dennis
la source
9

Pyth, 20 octets

Jt^2hslhQ#p/=%QJ=/J2

S'exécute en O (journal (entrée ())), bien en dessous d'une seconde pour le cas de test final. Basé autour d'une course jusqu'à la boucle d'erreur. Pas de retour à la ligne.

Manifestation.

Explication:

Jt^2hslhQ#p/=%QJ=/J2
                        Implicit: Q is the input.
      lhQ                          log(Q+1,2)
     slhQ                    floor(log(Q+1,2))
    hslhQ                    floor(log(Q+1,2))+1
  ^2hslhQ                 2^(floor(log(Q+1,2))+1)
 t^2hslhQ                 2^(floor(log(Q+1,2))+1)-1
Jt^2hslhQ               J=2^(floor(log(Q+1,2))+1)-1
         #              until an error is thrown:
            =%QJ        Q=Q%J
                =/J2    J=J/2
           /            The value Q/J, with the new values of Q and J.
          p             print that charcter, with no trailing newline.

J est initialisé à la valeur de la plus petite position de chiffre binaire asymétrique supérieure à l'entrée. Ensuite, chaque fois dans la boucle, nous procédons comme suit:

  • Supprimer chaque chiffre de valeur Jde Qavec =%QJ. Par exemple, si Q=10et J=7, Qdevient 3, ce qui correspond au changement binaire d' inclinaison de 110la 10. Cela n'a aucun effet lors de la première itération.
  • Passez Jà la valeur de base binaire asymétrique suivante plus petite avec =/J2. Il s’agit d’une division par 2, passant J=7à J=3, par exemple. Comme cela se produit avant la sortie du premier chiffre, la Jposition initiale d’un chiffre est plus élevée que nécessaire.
  • Trouvez la valeur numérique actuelle avec /QJ(efficacement).
  • Imprimez cette valeur avec p, au lieu de l’impression par défaut de Pyth, pour éviter la fin de ligne.

Cette boucle se répète jusqu'à ce que Jzéro soit atteint, point auquel une erreur de division par zéro est générée et la boucle se termine.

isaacg
la source
8

ES6, 105 octets

f=n=>{for(o=0;n--;c?o+=Math.pow(3,s.length-c):o++)s=t(o),c=s.search(2)+1;return t(o);},t=a=>a.toString(3)

L'utilisation est: f(1048576)=> `" 10000000000000000001 "

Testez le dernier argument à vos risques et périls. J'ai abandonné après 5 secondes.

Et jolie impression avec des commentaires!

f=n=>{ //define function f with input of n (iteration)
    for(o=0; //define o (output value in decimal)
        n--; //decrement n (goes towards falsy 0) each loop until 0
        c?o+=Math.pow(3,s.length-c):o++) //if search finds a 2, increment output by 3^place (basically moves the 2 to the left and sets the place to 0), else ++
        s=t(o), //convert output to base 3      
        c=s.search(2)+1; //find the location of 2, +1, so a not-found becomes falsy 0.
    return t(o); //return the output in base 3
},

t=a=>a.toString(3);  //convert input a to base 3
Boussole
la source
5
Btw, les fonctions non nommées sont parfaitement acceptables, vous n’avez donc pas besoin f=.
Martin Ender
2
-16 octets:f=n=>{for(o=0;~n--;o+=c?Math.pow(3,s.length+c):1)s=o.toString(3),c=~s.search(2);return s}
nderscore le
@nderscore Plutôt cool: D
Compass
1
-7 octets si vous utilisez ES7: remplacez Math.pow(3,s.length+c)par 3**(s.length+c).
Gustavo Rodrigues
3
@ GustavoRodrigues Je n'ai même pas fini d'apprendre l'ES6! @ _ @
Compass
7

Retina, 55 octets

^
0a
(+`12(.*a)1
20$1
0?2(.*a)1
10$1
0a1
1a
)`1a1
2a
a
<empty line>

Prend une entrée unaire.

Chaque ligne doit aller dans son propre fichier, mais vous pouvez exécuter le code sous la forme d'un fichier avec l' -sindicateur. Par exemple:

> echo 11111|retina -s skew
12

Méthode: Exécute l'incrémentation d'un nombre d'entrée de chaîne à partir de la chaîne 0.

Nous utilisons les règles d'incrémentation suivantes:

  • si contient 2: ^2 -> ^12; 02 -> 12;12 -> 20
  • si ne contient pas 2: 0$ -> 1$;1$ -> 2$

(Il peut y avoir au plus un 2dans la chaîne; ^et $marque le début et la fin de la chaîne dans les règles.)

Plus d'informations sur Retina.

randomra
la source
7

Java, 154 148

n->{String s="0";for(;n-->0;)s=s.contains("2")?s.replaceAll("(^|0)2","10").replace("12","20"):s.replaceAll("1$","2").replaceAll("0$","1");return s;}

Cette réponse se présente sous la forme d'une fonction anonyme unique prenant un argument entier et renvoyant la réponse sous forme de chaîne. Vous trouverez ci-dessous une classe complète pour tester cette solution.

import java.util.function.Function;
public class Skew {
    public static void main(String[] args){
        Function<Integer,String> skew = n->{String s="0";for(;n-->0;)s=s.contains("2")?s.replaceAll("(^|0)2","10").replace("12","20"):s.replaceAll("1$","2").replaceAll("0$","1");return s;};

        for(String s:args){
            System.out.println(skew.apply(Integer.parseInt(s)));
        }
    }
}
Ankh-Morpork
la source
5

Bash + coreutils, 52

dc -e3o0[r1+prdx]dx|grep -v 2.\*[12]|sed -n $1{p\;q}

Ceci est un brutal, donc c'est plutôt lent pour les grands nombres.

Sortie:

$ ./xkcdnum.sh 1000
111110120
$ 
Trauma numérique
la source
5

Java, 337 335 253 246 244 octets

Une méthode qui prend l'index en tant que longet renvoie le résultat sous forme de chaîne

Utilise a longpour l'index, donc peut théoriquement gérer le dernier cas de test, mais je ne le suggérerais vraiment pas.

String f(long i){List<Long>l=new ArrayList<>();l.add(0L);for(;i-->0;){int j=l.indexOf(2);if(j!=-1){l.set(j,0L);if(j==0){l.add(0,1L);}else{l.set(j-1,l.get(j-1)+1);}}else{j=l.size()-1;l.set(j,l.get(j)+1);}}String s="";for(long q:l)s+=q;return s;}
SuperJedi224
la source
4
Vous pouvez raccourcir un peu cette tâche en en faisant une fonction plutôt qu'un programme complet (et en prenant l'entrée comme argument plutôt que depuis un scanner).
Geobits
2
Vous n'avez pas besoin d'accolades dans la if(j == 0) déclaration (quatre octets). Vous n'avez pas besoin de déclarer k; vous pouvez simplement utiliser à jnouveau (quatre autres). Vous pouvez utiliser l'inférence de type générique (en Java 7) dans votre déclaration de liste ( new ArrayList<>();) (4 autres)
durron597
4

Haskell, 73 72

Merci à @nimi pour 1 octet!

Cette solution ne rapportera aucune prime, les deux derniers tests ont pris un temps démesuré, mais je pense que j'ai assez bien réussi.

i(2:b)=1:0:b
i[b]=[b+1]
i(b:2:c)=b+1:0:c
i(b:c)=b:i c
s=(iterate i[0]!!)

Cette solution est une approche plutôt naïve qui calcule le nombre binaire asymétrique nen incrémentant 0 nfois.

Ankh-Morpork
la source
4

CJam, 24 octets

Q{0\+2a/())+a\+0a*}ri*si

C'est une approche O (n log n) , où n est l'entrée. Il commence par la représentation binaire asymétrique de 0 et incrémente le nombre entier correspondant n fois.

Essayez-le en ligne dans l' interprète CJam .

Contexte

L'incrémentation d'un nombre en binaire oblique peut être effectuée en suivant deux étapes simples:

  1. Remplace un éventuel 2 par un 0 .

  2. Si un 2 a été remplacé, incrémentez le chiffre à sa gauche.

    Sinon, incrémentez le dernier chiffre.

Comment ça fonctionne

Q     e# Push an empty array.
{     e# Define an anonymous function:
  0\+ e#   Prepend a 0 to the array.
  2a/ e#   Split the array at 2's.
  (   e#   Shift out the first chunk of this array.
  )   e#   Pop the last digit.
  )+  e#   Increment it and append it to the array.
  a\+ e#   Prepend the chunk to the array of chunks.
  0a* e#   Join the chunks, using [0] as separator.
      e#   If there was a 2, it will get replaced with a 0. Otherewise, there's
      e#   only one chunk and joining the array dumps the chunk on the stack.
}     e#
ri*   e# Call the function int(input()) times.
si    e# Cast to string, then to integer. This eliminates leading 0's.
Dennis
la source
4

VBA, 209 147 142 octets

Sub p(k)
For i=1To k
a=StrReverse(q)
If Left(Replace(a,"0",""),1)=2Then:q=q-2*10^(InStr(a,2)-1)+10^InStr(a,2):Else:q=q+1
Next
msgbox q
End Sub

Mon calcul est inefficace et mon golf pourrait utiliser le travail. Mais c’est ma première tentative de PoG et je me suis dit que j’essaierais celui-ci. Une sorte de moyen de force brute cependant.

Il ne fait que compter par 1 sauf si le dernier chiffre est un 2 puis recule de 2 et avance de 10. Plus les 0 finaux.

Cela cesse de fonctionner à 65534 car VBA insiste pour donner une sortie en notation scientifique, mais la logique devrait fonctionner correctement pour des nombres encore plus élevés.

Dans l’attente des suggestions de golf, VBA n’est pas très adapté au golf, mais il n’est pas souvent représenté et je pense qu’il peut battre Java pour la longueur.

Edit1: Merci Manu d' avoir aidé à réduire de 62 octets

Edit2: Swapped debug.printpour msgboxen sortie. 5 octets enregistrés

JimmyJazzx
la source
1
Vous pouvez supprimer les crochets de Debug.Print (q). En outre, vous pouvez supprimer la plupart des espaces (l'éditeur les redéfinira, mais ils ne sont pas nécessaires). Vous n'avez pas besoin de déclarer k as Long, écrivez simplement k. Ce sera une variable du type Variant et le code fonctionnera toujours. Avec ces conseils, vous devriez descendre à ~ 165 octets.
CommonGuy
Quelques réflexions supplémentaires: Vous pouvez omettre le premier et le dernier argument de InStr, ils sont facultatifs. Trim()n'est pas nécessaire, car vous n'avez pas d'espace. Appliqué correctement, j'arrive à 147 octets .
CommonGuy
1
Merci pour l'aide Manu, Une question rapide, la sortie devrait être la sortie standard. Je ne suis pas sûr de ce que ce serait dans VBA. debug.print qserait la sortie standard? msgbox qest plus court mais semble encore une fois que ce n'est pas tout à fait la sortie standard. Sheet1.cells(1,1)semble être la sortie typique, mais suppose son exécution dans Excel. Je ne suis tout simplement pas tout à fait sûr de la sévérité du code-golf dans ce genre de choses.
JimmyJazzx
Félicitations, vous battez la réponse java;) Je ne sais pas non plus ... Utilisez-le MsgBox, si quelqu'un se plaint, vous pouvez toujours le modifier.
CommonGuy
4

Javascript ES6, 99 86 78 76 72 caractères

f=n=>{for(s="1";--n;s=s.replace(/.?2|.$/,m=>[1,2,10][+m]||20));return s}

// Old version, 76 chars:
f=n=>{for(s="1";--n;s=s.replace(/02|12|2|.$/,m=>[1,2,10][+m]||20));return s}

// Old version, 86 chars:
f=n=>{for(s="1";--n;s=s.replace(/(02|12|2|.$)/,m=>[1,2,10,,,,,,,,,,20][+m]));return s}

// Old version, 99 chars:
f=n=>{for(s="1";--n;s=s.replace(/(^2|02|12|20|.$)/,m=>({0:1,1:2,2:10,12:20,20:100}[+m])));return s}

Tester:

;[1,2,3,6,7,50,100,200,1000,10000,100000,1000000,1048576].map(f) == "1,2,10,20,100,11011,110020,1100110,111110120,1001110001012,1100001101010020,1111010000100100100,10000000000000000001"

Anecdote: Ce système de numérotation présente certains avantages. Lorsque vous incrémentez un nombre, vous modifiez toujours au maximum deux chiffres adjacents. Vous ne devez jamais effectuer la modification sur l'intégralité du nombre. Avec la bonne représentation qui permet d’incrémenter en O (1).

Merci pour le fait - c'est la base de ma solution :)

Qwertiy
la source
Comment pourrais-je laisser des accolades inutiles dans la regex? o_O
Qwertiy
3

Octave, 107 101 octets

Devrait être O (log n) si je pense que ce droit ...

function r=s(n)r="";for(a=2.^(uint64(fix(log2(n+1))):-1:1)-1)x=idivide(n,a);r=[r x+48];n-=x*a;end;end

Joli-imprimé:

function r=s(n)
  r="";
  for(a=2.^(uint64(fix(log2(n+1))):-1:1)-1)
    x=idivide(n,a);
    r=[r x+48];
    n-=x*a;
  end
end

J'étais un peu bloqué face au dernier défi, étant donné qu'Octave considère par défaut tout comme des nombres à virgule flottante et que je n'avais pas la précision nécessaire pour calculer le dernier. J'ai contourné cela en dépensant de précieux octets pour que tout soit forcément un entier non signé. Le résultat du dernier résultat était trop grand pour être traité comme un nombre. Le résultat est donc une chaîne.

Sortie (j'inclus 1e18 - 1pour montrer que je peux le faire avec précision, et le dernier ensemble de sorties indique le temps nécessaire pour calculer cette valeur):

octave:83> s(uint64(1e18))
ans = 11011110000010110110101100111010011101100100000000000001102

octave:84> s(uint64(1e18)-1)
ans = 11011110000010110110101100111010011101100100000000000001101

octave:85> tic();s(uint64(1e18)-1);toc()
Elapsed time is 0.0270021 seconds.
dcsohl
la source
3

T-SQL, 221 189 177 octets

EDIT: Les versions originales de ce code produiraient une sortie incorrecte pour certains nombres, cela a été corrigé.

Avec chaque requête ici, ajoutez simplement le nombre à calculer avant la première virgule.

Tout le monde sait que T-SQL est la meilleure langue de golf. Voici une version qui va calculer même le dernier cas de test. Sur la machine sur laquelle j'ai testé, elle a fonctionné en moins d'une seconde, je serais intéressé de voir comment elle fonctionnera pour tous les autres.

DECLARE @ BIGINT=,@T VARCHAR(MAX)='';WITH M AS(SELECT CAST(2AS BIGINT)I UNION ALL SELECT I*2FROM M WHERE I<@)SELECT @T += STR(@/(I-1),1),@%=(I-1)FROM M ORDER BY I DESC SELECT @T

Et le voici à nouveau, mais lisible:

DECLARE 
    @ BIGINT=,
    @T VARCHAR(MAX)='';

WITH M AS
(
    SELECT
        CAST(2 AS BIGINT) I

    UNION ALL

    SELECT I * 2
    FROM M
    WHERE I < @
)

SELECT 
    @T+=STR(@/(I-1),1),
    @%=(I-1)
FROM M 
ORDER BY I DESC

SELECT @T

Si je n'utilise que ints, cela peut être un peu plus court, avec 157 octets:

DECLARE @ INT=,@T VARCHAR(MAX)='';WITH M AS(SELECT 2I UNION ALL SELECT I*2FROM M WHERE I<@)SELECT @T+=STR(@/(I-1),1),@%=(I-1)FROM M ORDER BY I DESC SELECT @T

Et encore une fois, plus lisible:

DECLARE 
    @ INT=,
    @T VARCHAR(MAX)='';

WITH M AS
(
    SELECT
        2I

    UNION ALL

    SELECT 
        I * 2
    FROM M
    WHERE I < @
)

SELECT 
    @T+=STR(@/(I-1),1),
    @%=(I-1)
FROM M 
ORDER BY I DESC

SELECT @T
PenutReaper
la source
Remember @est un identifiant valide en SQL et vous permettra probablement de vous en tirer, Char(8000) ce qui est encore meilleur marché que nvarchar (max). Vous pouvez également convertir au charlieu de varchar, ou utiliser la strfonction.
Michael B
@MichaelB Oh, je pensais que j'avais utilisé @, bête moi. Le CHAR(8000)conseil est plutôt bon, je vais essayer. Je semble toujours oublier l'existence de STR()remerciements pour le heads up.
PenutReaper
n'aide pas réellement. Cependant, vous pouvez réécrire la partie après le CTE dans :: select @t=concat(@t,@/i)cela devrait être plus petit. Nécessite sql2012 cependant.
Michael B
@MichaelB ah. CONCATJe suis en 2008. Je ne peux donc pas le tester sans utiliser un violon SQL pour le moment. Bon appel cependant.
PenutReaper
3

Code de la machine de Turing, 333 293 octets

J'utilise un encodage tel qu'utilisé ici .

Cette machine utilise 9 états et 11 couleurs.

Si une entrée binaire est autorisée, elle peut être réduite à 4 couleurs seulement, en économisant quelques dizaines d'octets.

0 _ _ l 1
0 * * r 0
1 9 8 l 2 
1 8 7 l 2
1 7 6 l 2
1 6 5 l 2
1 5 4 l 2
1 4 3 l 2
1 3 2 l 2
1 2 1 l 2
1 1 0 l 2
1 0 9 l 1
1 _ _ r 8
2 _ _ l 3
2 * * l 2
3 _ 1 r 4
3 * * l 5
4 _ _ r 0
4 * * r 4
5 * * l 5
5 _ _ r 6
6 _ _ l 7
6 2 0 l 7
6 * * r 6
7 _ 1 r 4
7 0 1 r 4
7 1 2 r 4
8 _ _ * halt
8 * _ r 8

Si le lien ci-dessus ne fonctionne pas (parfois cela fonctionne pour moi, parfois la page refuse de charger), vous pouvez également le tester en utilisant cette implémentation Java.

SuperJedi224
la source
2

Perl, 66 octets

Le numéro doit être entré via STDIN.

$_=1;$c=<>;s/(.*)(.?)2(.*)/$1.$2+1 .$3.0/e||$_++while(--$c);print;
Frédéric
la source
Pouvez-vous expliquer comment votre solution fonctionne? Je ne vois pas comment vous avez besoin (.?)en $2car (.*)en $1devrait être gourmand et obtenir ce premier caractère. Mais s'il est supprimé, le code ne produit plus les bons résultats! Au fait, vous n'avez pas besoin de la finale ;.
CJ Dennis
@CJDennis Merci pour cet octet enregistré. Quoi qu'il en soit, le. le chiffre vient juste avant les deux sauf s'il n'y a pas de chiffre (par exemple 20). Dans des cas tels que 120 ou 10020, les groupes de regex sont comme ceci: () (1) 2 (0) et (10) (0) 2 (0). Ensuite, le premier groupe est simplement ignoré, le deuxième groupe (qui est toujours un chiffre ou vide) est incrémenté et le troisième groupe (toujours composé de zéros) est ignoré et un zéro est ajouté. J'ai simplement utilisé l'entrée OEIS comme guide pour cette expression rationnelle.
Frédéric
Je suis votre code jusqu'à 53 octets: $c=<>;s/(.*)2(.*)/$1+1 .$2.0/e||$_++while($c--);print. J'avais raison, (.?)rien jamais capturé.
CJ Dennis
Peut être optimisé pour $_=1;$c=<>;s/(.?)2/1+$1.0/e||$_++while(--$c);print, ce qui est 50 octets. .*au début ou à la fin peuvent être optimisés, si vous le remplacez par le texte original. De plus, il n'y a aucune raison d'ajouter le 0 à la fin, car il n'y a toujours que des zéros dans l'original $3.
Thraidh
2

Pyth, 19 octets

m/=%Qtydtd^L2_SslhQ

Complexité logarithmique. Finit facilement dans le temps nécessaire. Sortie sous la forme d'une liste de chiffres.

Démonstration .

isaacg
la source
2

Perl, 84 70 67 octets

$n=<>;$d*=2while($d++<$n);$_.=int($n/$d)while($n%=$d--,$d/=2);print

Pas très gaie, ça va mieux mais ça marche très vite!

La suggestion de Dennis le réduit à 51 (commutateur de 50 octets + -p)

$d*=2while$d++<$_;$\.=$_/$d|0while$_%=$d--,$d/=2}{

Il doit être appelé comme perl -p skew_binary.pl num_list.txtnum_list.txtcontient une seule ligne avec le numéro à encoder.

CJ Dennis
la source
@frederick nous sommes sur le point d'attendre deux sièges.
Robert Grant
@RobertGrant Il a joué son commentaire de deux choses à une chose!
CJ Dennis
Deux choses: 1. Au lieu d’utiliser $ ARGV [0], utilisez <> comme entrée. Cela prendra l’entrée de stdin sauf s’il ya des fichiers comme arguments. 2. Pour les schémas de comptage impair comme celui-ci, utilisez des expressions régulières. Au lieu d'effectuer des opérations mathématiques bizarres, vous pouvez remplacer les chiffres d'un nombre comme s'il s'agissait d'une chaîne. La meilleure partie est que vous pouvez utiliser des opérations mathématiques (comme incrémenter) en même temps, à condition qu'il s'agisse d'une chaîne composée entièrement de chiffres. Consultez la documentation des opérateurs d'expression régulière, car ils peuvent être très utiles à maintes reprises.
Frédéric
Désolé, j'ai appuyé sur Entrée et il a été enregistré avant de terminer le commentaire.
Frédéric
@frederick ne soyez pas si modeste. Nous savons ce qui s'est passé!
Robert Grant
1

Mathematica, 65

Devrait être assez rapide, bien que je dois admettre que j’ai jeté un coup d’œil aux autres soumissions avant de le présenter.

f = (n = #;
     l = 0; 
     While[n > 0,
      m = Floor[Log2[1 + n]];
      l += 10^(m - 1);
      n -= 2^m - 1
     ]; l)&

Usage:

f[1000000000000000000]

Sortie:

11011110000010110110101100111010011101100100000000000001102

Commence à envoyer des messages d'erreur MaxExtraPrecision quelque part après 10 ^ 228 (pour lequel le résultat est calculé en 0,03 seconde sur ma machine)

Une fois la limite MaxExtraPrecision supprimée, il gérera les nombres jusqu’à environ 10 ^ 8000 en une seconde.

Contribution:

Timing[Block[{$MaxExtraPrecision = Infinity}, f[10^8000]];]

Sortie:

{1.060807, Null}
Pointage
la source
1

C, 95 octets

void f(unsigned long i,int*b){for(unsigned long a=~0,m=0;a;a/=2,b+=!!m)m|=*b=i/a,i-=a**b;*b=3;}

Ceci accepte un entier et un tampon dans lequel renvoyer les chiffres. Les résultats sont stockés dans b, terminés par une valeur 3(qui ne peut pas apparaître dans la sortie). Nous n'avons pas à gérer l'entrée de 0(comme la question ne spécifie que les entiers positifs), il n'y a donc pas de casse spéciale pour éviter une sortie vide.

Code étendu

void f(unsigned long i,int*b)
{
    for (unsigned long a=~0, m=0;  a;  a/=2, b+=(m!=0)) {
        *b = i/a;               /* rounds down */
        i -= *b * a;
        m = m | *b;             /* m != 0 after leading zeros */
    }
    *b=3;                       /* add terminator */
}

Nous opérons par soustraction successive, en commençant par le chiffre le plus significatif. La seule complication est que nous utilisons la variable mpour éviter d’imprimer des zéros en tête. Une extension naturelle unsigned long longpeut être faite si vous le souhaitez, au prix de 10 octets.

Programme de test

Transmettez les numéros à convertir en arguments de commande. Il convertit le inttampon de tableau en une chaîne de chiffres imprimable. Le temps d’exécution est inférieur à une milliseconde 1000000000000000000.

#include <stdio.h>
#include <stdlib.h>
int main(int argc, char**argv)
{
    while (*++argv) {
        unsigned long i = strtoul(*argv, NULL, 10);
        int result[1024];
        f(i,result);

        /* convert to string */
        char s[1024];
        {char*d=s;int*p=result;while(*p!=3)*d++=*p+++'0';*d=0;}
        printf("%lu = %s\n", i, s);
    }

    return EXIT_SUCCESS;
}

Résultats de test

$ ./51517 $(seq 20)
1 = 1
2 = 2
3 = 10
4 = 11
5 = 12
6 = 20
7 = 100
8 = 101
9 = 102
10 = 110
11 = 111
12 = 112
13 = 120
14 = 200
15 = 1000
16 = 1001
17 = 1002
18 = 1010
19 = 1011
20 = 1012
Toby Speight
la source
J'imagine qu'une version C ++ est similaire, mais peut utiliser auto a=~0ullpour un léger avantage ...
Toby Speight
0

CoffeeScript, 92 69 octets

Basé sur la réponse et les mises à jour de Qwertiy :

f=(n)->s='1';(s=s.replace /(.?2|.$)/,(m)->[1,2,10][+m]||20)while--n;s

# older version, 92 bytes
f=(n)->s='1';(s=s.replace /(^2|02|12|20|.$)/,(m)->{0:1,1:2,2:10,12:20,20:100}[+m])while--n;s
rink.attendant.6
la source
2
Convertir dans une autre langue sans même une simple optimisation en supprimant les accolades inutiles dans la regex ne semble pas cool pour moi ...
Qwertiy
@ Qwertiy J'ai fourni une attribution à votre réponse, et avec les deux réponses, je ne peux pas produire les mêmes résultats sans les crochets dans la regex
rink.attendant.6
Toute l'occurrence est remplacée. Pourquoi en avez-vous besoin pour faire partie du groupe? La version JS fonctionne dans Firefox sans crochets.
Qwertiy
0

Japt , 31 octets

_r/?2|.$/g_÷C ç20 ª°Zs3}}gU['0]

Essayez-le en ligne!

Port presque direct de cette solution JS . Aucune idée s'il y a un meilleur moyen.

Déballé et comment ça marche

X{Xr/?2|.$/gZ{Z÷C ç20 ||++Zs3}}gU['0]

X{     Declare a function...
Xr       Accept a string, replace the regex...
/?2|.$/g   /.?2|.$/   (g is needed to match *only once*, opposite of JS)
Z{       ...with the function... (matched string will be 0,1,2,02 or 12)
Z÷C        Implicitly cast the matched string into number, divide by 12
ç20        Repeat "20" that many times (discard fractions)
||         If the above results in "", use the next one instead
++Z        Increment the value
s3         Convert to base-3 string (so 0,1,2 becomes 1,2,10)
}}
gU['0] Repeatedly apply the function on "0", U (input) times
Barboteur
la source
0

Stax , 16 octets

üxëàè£öΦGΩ│Je5█ò

Exécuter et déboguer

Je ne sais pas exactement quelle est la classe de complexité formelle, mais c'est assez rapide pour effectuer tous les tests en un dixième de seconde sur cette machine.

Déballé, non golfé et commenté, cela ressemble à ceci. Dans ce programme, le registre x contient à l'origine l'entrée.

z       push []
{       start block for while loop
 |X:2N  -log2(++x)
 {^}&   increment array at index (pad with 0s if necessary)
 xc:G-X unset high bit of x; write back to x register
w       while; loop until x is falsy (0)
$       convert to string

Exécuter celui-ci

récursif
la source