Numeracja stron w stylu xkcd

65

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>

Martin Ender
źródło
32
Mam tę książkę od pierwszego wydania i nigdy nie zauważyłem numeracji stron.
Alex A.
2
@AlexA. Mam to na moim Kindle, gdzie nie możesz zrobić żadnej interesującej numeracji stron.
LegionMammal978
21
@ LegionMammal978: Tragiczny.
Alex A.,
1
@ SuperJedi224 Konsensus wydaje się być nie , więc przepraszam (zrobiłbym wyjątek od konsensusu, jeśli byłby to jedyny rodzaj danych wejściowych, jaki może obsłużyć Twój język, ale tak nie jest).
Martin Ender
4
Przypomina mi to, jak liczyłem, kiedy miałem 3 lata. Rozumowałem: „nie ma pięćdziesięciu dziesięciu, więc po stu dziewięciu musi być dwieście”. Ja tylko sobie sprawę, mój błąd, widząc różnicę między 59->60i 109->110, z dodatkowym 0.
Cyoce

Odpowiedzi:

12

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ń”.

isaacg
źródło
32

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 0 odpowiada liczbie całkowitej n = (2 k + 1 -1) a k + ... + (2 1 -1) a 0 .

Ponieważ zarówno (2 k -1) + ... + (2 1 -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 0 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 2 (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.

Dennis
źródło
28

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.

Sp3000
źródło
nie 2andskompilować w 3? Mam 2 lata i 2and2zgłasza błąd składniowy
TankorSmash
3
@TankorSmash 2and2nie działałby, ponieważ zostałby przeanalizowany jako 2 and2- spróbuj 2and 2, co powinno działać, jeśli Twoja wersja Pythona jest wystarczająco nowa (przetestowana w Pythonie 2.7.10)
Sp3000
Och, dobrze, masz rację. Nawet w wersji 2.7.3 działa.
TankorSmash
12

CJam, 22 21 20 bajtów

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

Jest to podejście O (e n n) , gdzie n jest wejściem. Zawiera ona pierwszych ⌊e n 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.
Dennis
źródło
9

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.

isaacg
źródło
8

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
Kompas
źródło
5
Btw, nienazwane funkcje są całkowicie akceptowalne, więc nie potrzebujesz f=.
Martin Ender
2
-16 bajtów: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
@nderscore Całkiem fajne: D
Kompas
1
-7 bajtów jeśli używasz ES7 zamienić Math.pow(3,s.length+c)z 3**(s.length+c).
Gustavo Rodrigues,
3
@GustavoRodrigues Nie skończyłem nawet nauki ES6! @ _ @
Compass
7

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.

randomra
źródło
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;}

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)));
        }
    }
}
ankh-morpork
źródło
5

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
$ 
Cyfrowa trauma
źródło
5

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;}
SuperJedi224
źródło
4
Można to trochę skrócić, ustawiając funkcję zamiast pełnego programu (i biorąc dane wejściowe jako argument zamiast ze skanera).
Geobits,
2
Nie potrzebujesz nawiasów klamrowych w if(j == 0) instrukcji (cztery bajty). Nie musisz deklarować k; możesz po prostu użyć jponownie (jeszcze cztery). Można użyć wnioskowania typu ogólnego (w Javie 7) w deklaracji listy ( new ArrayList<>();) (kolejne 4)
durron597
4

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.

ankh-morpork
źródło
4

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.
Dennis
źródło
4

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

JimmyJazzx
źródło
1
Możesz usunąć nawiasy z Debug.Print (q). Możesz także usunąć większość białych znaków (edytor odłoży je z powrotem, ale nie są konieczne). Nie musisz deklarować k as Long, po prostu napisz k. Będzie to zmienna typu Variant i kod będzie nadal działał. Z tymi wskazówkami powinieneś zmniejszyć do ~ 165 bajtów.
CommonGuy
Jeszcze kilka myśli: Możesz pominąć pierwszy i ostatni argument InStr, są one opcjonalne. Trim()nie jest konieczne, ponieważ nie masz spacji. Przy prawidłowym zastosowaniu uzyskuję 147 bajtów .
CommonGuy
1
Dzięki za pomoc, jedno szybkie pytanie, wyjście powinno być wyjściem standardowym. Nie jestem pewien, co by to było w VBA. debug.print qbyłoby standardowe wyjście? msgbox qjest krótszy, ale znowu wydaje się, że nie jest to całkiem standardowe wyjście. Sheet1.cells(1,1)wygląda na typowe wyjście, ale zakłada, że ​​działa w programie Excel. Po prostu nie jestem całkiem pewien, jak ścisły jest golf-code w tego typu sprawach.
JimmyJazzx
Gratulacje, pokonałeś odpowiedź java;) Ja też nie wiem ... Po prostu użyj MsgBox, jeśli ktoś narzeka, nadal możesz go zmienić.
CommonGuy
4

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 :)

Qwertiy
źródło
Jak mogę zostawić niepotrzebne nawiasy klamrowe w wyrażeniu regularnym? o_O
Qwertiy
3

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.
dcsohl
źródło
3

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
PenutReaper
źródło
Pamiętaj, że @jest poprawnym identyfikatorem w sql i najprawdopodobniej możesz uciec, Char(8000) który jest jeszcze tańszy niż nvarchar (max). Można również konwertować do charzamiast varcharlub użyj strfunkcji.
Michael B
@MichaelB Oh, myślałem, że użyłem @, głupie mnie. Rada CHAR(8000)jest całkiem dobra, spróbuję tego. Zawsze wydaje mi się, że zapominam o istnieniu STR()podziękowań dla heads up.
PenutReaper,
tak naprawdę nie pomaga. Można jednak przepisać część po CTE na ::, select @t=concat(@t,@/i)która powinna być mniejsza. Wymaga jednak sql2012.
Michael B
@MichaelB ah. CONCAT, Jestem w 2008 roku. Więc nie mogę go teraz przetestować bez użycia skrzypce SQL. Dobry telefon.
PenutReaper
3

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.

SuperJedi224
źródło
2

Perl, 66 bajtów

Numer należy wprowadzić przez STDIN.

$_=1;$c=<>;s/(.*)(.?)2(.*)/$1.$2+1 .$3.0/e||$_++while(--$c);print;
Frederick
źródło
Czy możesz wyjaśnić, jak działa Twoje rozwiązanie? Nie widzę w jaki sposób trzeba (.?)się $2ponieważ (.*)w $1powinno być chciwym i uzyskać ten znak jako pierwszy. Ale jeśli zostanie usunięty, kod nie daje już poprawnych wyników! Nawiasem mówiąc, nie potrzebujesz finału ;.
CJ Dennis
@CJDennis Dzięki za zapisany bajt. W każdym razie. dostanie cyfrę nadchodzącą tuż przed dwiema, chyba że nie będzie tam żadnej cyfry (np. 20). W przypadkach takich jak 120 lub 10020 grupy wyrażeń regularnych takie jak to: () (1) 2 (0) i (10) (0) 2 (0). Następnie pierwsza grupa jest po prostu ignorowana, druga grupa (która jest zawsze albo jedną cyfrą, jeśli to możliwe, albo pusta) jest zwiększana, a trzecia grupa (zawsze składająca się z zer) jest ignorowana i dodawane jest zero. Po prostu użyłem wpisu OEIS jako mojego przewodnika po tym wyrażeniu regularnym.
Frederick
Mam swój kod w dół do 53 bajtów: $c=<>;s/(.*)2(.*)/$1+1 .$2.0/e||$_++while($c--);print. Miałem rację, (.?)nigdy niczego nie uchwyciłem.
CJ Dennis,
Można zoptymalizować do $_=1;$c=<>;s/(.?)2/1+$1.0/e||$_++while(--$c);print, czyli 50 bajtów. .*na początku lub na końcu można zoptymalizować, jeśli po prostu zastąpisz go oryginalnym tekstem. Ponadto nie ma powodu, aby dodawać 0 na końcu, ponieważ w oryginale zawsze są tylko zera $3.
Thraidh
2

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 .

isaacg
źródło
2

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.

CJ Dennis
źródło
@ Frederick jesteśmy na skraju naszych miejsc i czekamy na 2.
Robert Grant,
@RobertGrant Grał swój komentarz w golfa od dwóch rzeczy do jednej!
CJ Dennis,
Dwie rzeczy: 1. Zamiast używać $ ARGV [0], użyj <> jako danych wejściowych. Będzie pobierał dane wejściowe ze standardowego wejścia, chyba że istnieją argumenty jako pliki. 2. W przypadku takich schematów zliczania nieparzystych użyj wyrażeń regularnych. Zamiast wykonywać nieparzyste operacje matematyczne, możesz zastąpić cyfry cyframi, tak jakby to był ciąg znaków. Najlepsze jest to, że możesz jednocześnie korzystać z operacji matematycznych (takich jak przyrost), pod warunkiem, że jest to ciąg składający się wyłącznie z cyfr. Sprawdź dokumentację operatorów wyrażeń regularnych, ponieważ mogą one być bardzo przydatne w tak wielu przypadkach.
Frederick
Przepraszam, nacisnąłem Enter i zapisałem to zanim skończyłem komentarz.
Frederick
@ Frederick nie bądź taki skromny. Wiemy, co się stało!
Robert Grant,
1

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}
Zestawienie
źródło
1

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
Toby Speight
źródło
Wydaje mi się, że wersja C ++ jest podobna, ale można ją wykorzystać auto a=~0ullz niewielką przewagą ...
Toby Speight
0

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
lodowisko. dozorca 6
źródło
2
Konwersja na inny język bez nawet prostej optymalizacji poprzez usunięcie niepotrzebnych nawiasów klamrowych w wyrażeniu regularnym nie wydaje mi się fajna ...
Qwertiy
@ Qwertiy Podałem odpowiedź na twoją odpowiedź i przy obu tych odpowiedziach nie mogę uzyskać takich samych wyników bez nawiasów w wyrażeniu regularnym
rink.attendant.6
Całe wystąpienie zostaje zastąpione. Dlaczego potrzebujesz go w grupie? Wersja JS działa w przeglądarce Firefox bez nawiasów.
Qwertiy
0

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
Bubbler
źródło
0

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

rekurencyjny
źródło