Książka Randall Munroe „xkcd, tom 0” używa raczej nieparzystego systemu liczbowego dla numerów stron. Pierwsze kilka numerów stron to

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

To wygląda trochę jak trójka, ale zauważ, że przeskakuje od 20prostej do 100, od 120do 200i od 200do 1000. Jednym ze sposobów zdefiniowania tej sekwencji jest powiedzenie, że wylicza ona wszystkie liczby trójskładnikowe, które zawierają co najwyżej jeden, 2a 1potem nie 2. Można go znaleźć w OEIS w pozycji A169683 . Ten system liczb jest znany jako skośny binarny .

Twoim zadaniem jest znalezienie reprezentacji danej dodatniej liczby całkowitej Nw tym systemie liczbowym.

Możesz napisać program lub funkcję, pobierając dane wejściowe przez STDIN (lub najbliższą alternatywę), argument wiersza poleceń lub argument funkcji i wypisując wynik przez STDOUT (lub najbliższą alternatywę), wartość zwracaną funkcji lub parametr funkcji (wyjściowej).

Dane wyjściowe mogą być ciągiem, liczbą z reprezentacją dziesiętną równą skośnej reprezentacji binarnej lub listą cyfr (jako liczby całkowite lub znaki / ciągi). Nie wolno zwracać wiodących zer.

To jest kod golfowy, więc wygrywa najkrótsza odpowiedź (w bajtach).

Ciekawostka: ten system liczb ma pewne zalety. Zwiększając liczbę, zawsze zmienisz maksymalnie dwie sąsiednie cyfry - nigdy nie będziesz musiał przenosić zmiany przez cały numer. Z odpowiednią reprezentacją, która pozwala na zwiększenie O (1).

Przypadki testowe

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

Dam nagrodę za najkrótszą odpowiedź, która może rozwiązać ostatni przypadek testowy (i każdy inny wkład o podobnej wielkości, więc nie myśl o jego zakodowaniu na stałe) w mniej niż sekundę.

Liderów

Oto fragment kodu, który pozwala wygenerować zarówno zwykłą tabelę wyników, jak i przegląd zwycięzców według języka.

Aby upewnić się, że twoja odpowiedź się pojawi, zacznij od nagłówka, korzystając z następującego szablonu Markdown:

# Language Name, N bytes

gdzie Njest rozmiar twojego zgłoszenia. Jeśli poprawisz swój wynik, możesz zachować stare wyniki w nagłówku, przekreślając je. Na przykład:

# 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>

Pyth, 17 bajtów

Ljb3ye.f!-P-yZ01Q

Jest to nieco absurdalnie wolne O(output^log_2(3)). Jest wykładniczy pod względem długości danych wejściowych, ale nie podwójnie wykładniczy, jak niektóre odpowiedzi na stronie. Kilka pomysłów zaczerpniętych z odpowiedzi @ Dennisa tutaj .

Demonstracja.

Wykorzystuje .ffunkcję „pętli Pytha, dopóki nie znaleziono n dopasowań”.

CJam, 24 23 22 21 19 bajtów

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

Jest to podejście O (log n) , gdzie n oznacza dane wejściowe, które natychmiast kończą ostatni przypadek testowy. Konwertuje n bezpośrednio na pochylenie binarne, używając podziału modułowego przez wartości cyfry 1 .

Kod kończy się błędem, który przechodzi do STDERR z interpreterem Java, co jest dozwolone zgodnie z konsensusem w sprawie Meta .

Jeśli wypróbujesz ten kod w interpretatorze CJam , po prostu zignoruj ​​wszystko oprócz ostatniego wiersza wyniku.

Błąd można wyeliminować kosztem 2 bajtów, przygotowując 2>do W%.

Dzięki @ MartinBüttner za grę w golfa o jeden bajt.

tło

Skośna reprezentacja binarna a _k ... a ₀ odpowiada liczbie całkowitej n = (2 ^{k + 1} -1) a _k + ... + (2 ¹ -1) a ₀ .

Ponieważ zarówno (2 ^k -1) + ... + (2 ¹ -1) = 2 ^{k + 1} - (k + 2) i (2 ^k -1) + ... + 2 (2 ^j -1) = 2 ^{k + 1} - (2 ^{J + 1} - 2 ^j + k + 1) jest mniejsza niż 2 ^{k + 1} -1 , wartości a _k w a ₀ mogą być odzyskane przez kolejne modułowej dzielenie przez 2 ^{k + 1} -1 , 2 ^k -1 itd.

Na początek musimy najpierw znaleźć wartość 2 ^{k + 1} -1 . Ponieważ n wynosi co najwyżej 2 (2 ^{k + 1} -1) , liczba całkowita n + 1 musi być ściśle mniejsza niż 2 ^{k + 2} .

Tak więc, biorąc całkowitą część logarytmu binarnego n + 1, daje k + 1 .

Na koniec obserwujemy, że liczba całkowita n + 1 ma ⌊log ₂ (n + 1) ⌋ cyfr w bazie 2.

Jak to działa

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#

W dwóch ostatnich iteracjach dokonujemy podziału modułowego przez 1 i 0 . Pierwszy wypycha niechciane 0 na stosie. Ostatnie próby wykonania 0 0 md, które usuwają niechciane 0 s ze stosu, wychodzą natychmiast zamiast wypychania czegokolwiek i zrzucają stos do STDOUT.

Python 2, 67 bajtów

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

Wydaje się działać dla podanych przypadków testowych. Jeśli mam rację, powinno to być O(place values set in output), więc z łatwością zrobi to ostatni przypadek.

Zadzwoń jak f(100). Zwraca dziesiętną reprezentację równą binarnemu skośnemu.

Python 3, 65 bajtów

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

Nieco mniej wydajny, ale wciąż logarytmiczny, więc ostatni przypadek jest prawie natychmiastowy.

Zadzwoń jak g(100). Zwraca listę cyfr.

CJam, 22 21 20 bajtów

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

Jest to podejście O (e ⁿ n) , gdzie n jest wejściem. Zawiera ona pierwszych ⌊e ⁿ ⌋ nieujemne liczby całkowite w podstawy 3, eliminuje te, które mają 2 s i 1 s po pierwszym 2 (jeżeli występuje) i wybiera się n + 1 ^y .

Wypróbuj online w interpretatorze CJam .

Jak to działa

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.

Pyth, 20 bajtów

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

Działa w O (log (input ())), znacznie poniżej sekundy dla końcowego przypadku testowego. Oparty na przebiegu do pętli błędów. Brak końca nowej linii.

Demonstracja.

Wyjaśnienie:

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 jest inicjalizowany do wartości najmniejszej pozycji pochylonej cyfry binarnej, która jest większa niż wartość wejściowa. Następnie za każdym razem przez pętlę wykonujemy następujące czynności:

• Usuń każdą cyfrę wartości Jz Qprzy pomocy =%QJ. Na przykład, jeśli Q=10a J=7, Qstaje 3, co odpowiada skośnej zmiany binarnym od 110celu 10. Nie ma to wpływu na pierwszą iterację.
• Przejdź Jdo następnej mniejszej podstawowej wartości binarnej skośnej za pomocą =/J2. Jest to dzielony podział przez 2, zmieniający J=7się J=3na przykład na. Ponieważ dzieje się to przed Jwypuszczeniem pierwszej cyfry, jest ona zinicjalizowana o jedną cyfrę wyżej niż to konieczne.
• Znajdź rzeczywistą wartość cyfry za pomocą /QJ(skutecznie).
• Wydrukuj tę wartość p, zamiast domyślnego drukowania Pytha, aby uniknąć końcowego znaku nowej linii.

Ta pętla będzie się powtarzać, aż Josiągnie zero, w którym to momencie zostanie wyrzucony błąd dzielenia przez zero i pętla się zakończy.

ES6, 105 bajtów

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)

Użycie to: f(1048576)=> `1000000000000000000001

Przetestuj ostatni argument na własne ryzyko. Poddałem się po 5 sekundach.

I ładny druk z komentarzami!

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

Siatkówka, 55 bajtów

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

Pobiera dane wejściowe jednoargumentowe.

Każda linia powinna przejść do własnego pliku, ale możesz uruchomić kod jako jeden plik z -sflagą. Na przykład:

> echo 11111|retina -s skew
12

Metoda: Wykonuje inkrementację na wejściu ciągu znaków razy, zaczynając od ciągu 0.

Stosujemy następujące reguły inkrementacji:

• jeśli zawiera 2: ^2 -> ^12; 02 -> 12;12 -> 20
• jeżeli nie zawiera 2: 0$ -> 1$;1$ -> 2$

(Nie może być co najwyżej jeden 2w łańcuchu; ^i $oznacza początek i koniec łańcucha w regulaminie).

Więcej informacji o Retina.

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;}

Ta odpowiedź ma postać pojedynczej anonimowej funkcji, która przyjmuje argument liczby całkowitej i zwraca odpowiedź jako ciąg znaków. Poniżej znajduje się pełna klasa do testowania tego rozwiązania.

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)));
        }
    }
}

Bash + coreutils, 52

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

Jest to brutal-forcer, więc jest raczej powolny dla większych liczb.

Wynik:

$ ./xkcdnum.sh 1000
111110120
$ 

Java, 337 335 253 246 244 bajtów

Metoda, która pobiera indeks jako a longi zwraca wynik jako ciąg znaków

Używa longdo indeksu, więc teoretycznie może obsłużyć ostatni przypadek testowy, ale tak naprawdę nie sugerowałbym tego.

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;}

Haskell, 73 72

^{Dzięki @nimi za 1 bajt!}

To rozwiązanie nie wygrywa żadnej nagrody, kilka ostatnich testów zajmuje zbyt dużo czasu, ale myślę, że dość dobrze grałem w golfa.

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]!!)

To rozwiązanie jest dość naiwnym podejściem, które oblicza skośną liczbę binarną npoprzez zwiększenie 0 nrazy.

CJam, 24 bajty

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

Jest to podejście O (n log n) , gdzie n jest wejściem. Zaczyna się od pochylonej reprezentacji binarnej 0 i zwiększa odpowiednią liczbę całkowitą n razy.

Wypróbuj online w interpretatorze CJam .

tło

Zwiększanie liczby w skośnym pliku binarnym można wykonać, wykonując dwa proste kroki:

1. Zamień ewentualne 2 na 0 .

2. Jeśli 2 zostało zastąpione, zwiększ cyfrę po lewej stronie.

   W przeciwnym razie zwiększ ostatnią cyfrę.

Jak to działa

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.

VBA, 209 147 142 bajtów

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

Moja matematyka jest nieefektywna, a gra w golfa przydałaby się w pracy. Ale to moja pierwsza próba PoG i pomyślałem, że dam temu szansę. Jednak rodzaj Brute Force.

Po prostu odlicza 1, chyba że ostatnia cyfra to 2, a następnie cofa się o 2 i przeskakuje do przodu o 10. Plus końcowe 0.

To przestaje działać przy 65534, ponieważ VBA nalega na podanie danych wyjściowych w notacji naukowej, ale logika powinna działać dobrze dla jeszcze wyższych liczb

Czekając na sugestie dotyczące golfa, VBA nie jest bardzo przyjazny dla golfa, ale nie jest często reprezentowany i myślę, że może pokonać Java na dłuższą metę.

Edycja1: Dzięki Manu za pomoc w goleniu 62 bajtów

Edycja2: Zamieniono debug.printna msgboxjako wyjście. Zapisano 5 bajtów

JavaScript ES6, 99 86 78 76 72 znaki

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}

Test:

;[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"

Ciekawostka: ten system liczb ma pewne zalety. Zwiększając liczbę, zawsze zmienisz maksymalnie dwie sąsiednie cyfry - nigdy nie będziesz musiał przenosić zmiany przez cały numer. Z odpowiednią reprezentacją, która pozwala na zwiększenie O (1).

Dziękuję za to - to podstawa mojego rozwiązania :)

Oktawa, 107 101 bajtów

Powinien być O (log n), jeśli mam rację ...

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

Ładny druk:

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

Trochę przeszkadzało mi podjęcie ostatecznego wyzwania, ponieważ Octave domyślnie traktuje wszystko jako liczby zmiennoprzecinkowe i nie miałem wystarczającej precyzji, aby obliczyć ostatnią. Obejrzałem to, wydając cenne bajty, aby zmusić wszystko do bycia liczbą całkowitą bez znaku. Wynik ostatniego był zbyt duży, aby traktować go jako liczbę, więc wynikiem jest ciąg znaków.

Dane wyjściowe (chcę 1e18 - 1pokazać, że mogę to zrobić dokładnie, a ostatni zestaw danych wyjściowych pokazuje, ile czasu zajmuje obliczenie tej wartości):

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.

T-SQL, 221 189 177 bajtów

EDYCJA: Oryginalne wersje tego kodu generowałyby nieprawidłowe dane wyjściowe dla niektórych liczb, zostało to poprawione.

Przy każdym zapytaniu tutaj po prostu dodaj liczbę do obliczenia przed pierwszym przecinkiem.

Wszyscy wiedzą, że T-SQL jest najlepszym językiem golfowym. Oto wersja, która obliczy nawet ostatni przypadek testowy. Na maszynie, na której testowałem, działał on w mniej niż sekundę, chciałbym zobaczyć, jak działa dla wszystkich innych.

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

I oto znowu, ale czytelne:

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

Jeśli używam tylko ints, może to być nieco krótsze, wychodzące na 157 bajtów:

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

I jeszcze raz, bardziej czytelny:

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

Kod maszynowy Turinga, 333 293 bajtów

Używam kodowania, jak tutaj użyte .

To urządzenie używa 9 stanów i 11 kolorów.

Jeśli dozwolone jest wprowadzanie danych binarnych, można je zredukować do zaledwie 4 kolorów, co pozwala zaoszczędzić kilkadziesiąt bajtów.

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

Jeśli powyższy link nie działa (czasami działa dla mnie, innym razem strona odmawia załadowania), możesz również przetestować to za pomocą tej implementacji Java.

Perl, 66 bajtów

Numer należy wprowadzić przez STDIN.

$_=1;$c=<>;s/(.*)(.?)2(.*)/$1.$2+1 .$3.0/e||$_++while(--$c);print;

Pyth, 19 bajtów

m/=%Qtydtd^L2_SslhQ

Złożoność logarytmiczna. Łatwo kończy się w niezbędnym czasie. Dane wyjściowe w postaci listy cyfr.

Demonstracja .

Perl, 84 70 67 bajtów

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

Niezbyt golfowy, coraz lepszy, ale działa bardzo szybko!

Sugestia Dennisa sprowadza go do 51 (50 bajtów + przełącznik -p)

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

To musi być nazywane jak perl -p skew_binary.pl num_list.txtgdzie num_list.txtzawiera pojedynczą linię z numerem do zakodowania na niej.

Mathematica, 65

Powinno to być dość szybkie, chociaż muszę przyznać, że zerknąłem na inne zgłoszenia, zanim to zrobiłem.

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

Stosowanie:

f[1000000000000000000]

Wynik:

11011110000010110110101100111010011101100100000000000001102

Zaczyna dawać komunikaty o błędach MaxExtraPrecision gdzieś po 10 ^ 228 (dla których oblicza wynik w 0,03 sekundy na mojej maszynie)

Po usunięciu limitu MaxExtraPrecision obsłuży liczby do około 10 ^ 8000 na sekundę.

Wejście:

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

Wynik:

{1.060807, Null}

C, 95 bajtów

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;}

Akceptuje to liczbę całkowitą i bufor, w którym zwracane są cyfry. Wyniki są przechowywane w b, zakończone wartością 3(która nie może wystąpić na wyjściu). Nie musimy obsługiwać danych wejściowych 0(ponieważ pytanie określa tylko dodatnie liczby całkowite), więc nie ma specjalnej obudowy, aby uniknąć pustych danych wyjściowych.

Rozszerzony kod

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 */
}

Działamy przez kolejne odejmowanie, zaczynając od najbardziej znaczącej cyfry. Jedyną komplikacją jest to, że używamy zmiennej, maby uniknąć drukowania zer wiodących. W unsigned long longrazie potrzeby można dokonać naturalnego rozszerzenia kosztem 10 bajtów.

Program testowy

Przekaż liczby do przekonwertowania jako argumenty poleceń. Konwertuje intbufor tablicy na drukowalny ciąg cyfr. Środowisko wykonawcze ma mniej niż jedną milisekundę dla danych wejściowych 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;
}

Wyniki testu

$ ./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

JavaScript (Node.js) , 40 bajtów

v=>(g=n=>n>v?'':g(n-~n)+(v-(v%=n))/n)(1)

Wypróbuj online!

To rozwiązanie nie działa na ostatniej walizce testowej. To po prostu powoduje przepełnienie stosu.

CoffeeScript, 92 69 bajtów

Na podstawie odpowiedzi i aktualizacji 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

Japt , 31 bajtów

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

Wypróbuj online!

Prawie bezpośredni port tego rozwiązania JS . Nie mam pojęcia, czy jest lepszy sposób.

Rozpakowane i jak to działa

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

Stax , 16 bajtów

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

Uruchom i debuguj

Nie jestem pewien, jaka jest formalna klasa złożoności, ale jest wystarczająco szybka, aby wykonać wszystkie przypadki testowe w jednej dziesiątej sekundy na tym komputerze.

Rozpakowane, niepolowane i skomentowane, wygląda to tak. W tym programie rejestr x oryginalnie zawiera dane wejściowe.

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

Uruchom ten