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 20
prostej do 100
, od 120
do 200
i od 200
do 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, 2
a 1
potem 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 N
w 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 N
jest 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>
źródło
59->60
i109->110
, z dodatkowym 0.Odpowiedzi:
Pyth, 17 bajtów
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
.f
funkcję „pętli Pytha, dopóki nie znaleziono n dopasowań”.źródło
CJam,
2423222119 bajtówJest 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>
doW%
.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
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.źródło
Python 2, 67 bajtów
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
Nieco mniej wydajny, ale wciąż logarytmiczny, więc ostatni przypadek jest prawie natychmiastowy.
Zadzwoń jak
g(100)
. Zwraca listę cyfr.źródło
2and
skompilować w 3? Mam 2 lata i2and2
zgłasza błąd składniowy2and2
nie działałby, ponieważ zostałby przeanalizowany jako2 and2
- spróbuj2and 2
, co powinno działać, jeśli Twoja wersja Pythona jest wystarczająco nowa (przetestowana w Pythonie 2.7.10)CJam,
222120 bajtówJest 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
źródło
Pyth, 20 bajtów
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:
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:
J
zQ
przy pomocy=%QJ
. Na przykład, jeśliQ=10
aJ=7
,Q
staje3
, co odpowiada skośnej zmiany binarnym od110
celu10
. Nie ma to wpływu na pierwszą iterację.J
do następnej mniejszej podstawowej wartości binarnej skośnej za pomocą=/J2
. Jest to dzielony podział przez 2, zmieniającyJ=7
sięJ=3
na przykład na. Ponieważ dzieje się to przedJ
wypuszczeniem pierwszej cyfry, jest ona zinicjalizowana o jedną cyfrę wyżej niż to konieczne./QJ
(skutecznie).p
, zamiast domyślnego drukowania Pytha, aby uniknąć końcowego znaku nowej linii.Ta pętla będzie się powtarzać, aż
J
osiągnie zero, w którym to momencie zostanie wyrzucony błąd dzielenia przez zero i pętla się zakończy.źródło
ES6, 105 bajtów
Użycie to:
f(1048576)
=> `1000000000000000000001Przetestuj ostatni argument na własne ryzyko. Poddałem się po 5 sekundach.
I ładny druk z komentarzami!
źródło
f=
.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}
Math.pow(3,s.length+c)
z3**(s.length+c)
.Siatkówka, 55 bajtów
Pobiera dane wejściowe jednoargumentowe.
Każda linia powinna przejść do własnego pliku, ale możesz uruchomić kod jako jeden plik z
-s
flagą. Na przykład:Metoda: Wykonuje inkrementację na wejściu ciągu znaków razy, zaczynając od ciągu
0
.Stosujemy następujące reguły inkrementacji:
2
:^2 -> ^12
;02 -> 12
;12 -> 20
2
:0$ -> 1$
;1$ -> 2$
(Nie może być co najwyżej jeden
2
w łańcuchu;^
i$
oznacza początek i koniec łańcucha w regulaminie).Więcej informacji o Retina.
źródło
Java,
154148Ta 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.
źródło
Bash + coreutils, 52
Jest to brutal-forcer, więc jest raczej powolny dla większych liczb.
Wynik:
źródło
Java,
337335253246244 bajtówMetoda, która pobiera indeks jako a
long
i zwraca wynik jako ciąg znakówUżywa
long
do indeksu, więc teoretycznie może obsłużyć ostatni przypadek testowy, ale tak naprawdę nie sugerowałbym tego.źródło
if(j == 0)
instrukcji (cztery bajty). Nie musisz deklarowaćk
; możesz po prostu użyćj
ponownie (jeszcze cztery). Można użyć wnioskowania typu ogólnego (w Javie 7) w deklaracji listy (new ArrayList<>();
) (kolejne 4)Haskell,
7372Dzię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.
To rozwiązanie jest dość naiwnym podejściem, które oblicza skośną liczbę binarną
n
poprzez zwiększenie 0n
razy.źródło
CJam, 24 bajty
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:
Zamień ewentualne 2 na 0 .
Jeśli 2 zostało zastąpione, zwiększ cyfrę po lewej stronie.
W przeciwnym razie zwiększ ostatnią cyfrę.
Jak to działa
źródło
VBA,
209147142 bajtówMoja 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.print
namsgbox
jako wyjście. Zapisano 5 bajtówźródło
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 napiszk
. Będzie to zmienna typu Variant i kod będzie nadal działał. Z tymi wskazówkami powinieneś zmniejszyć do ~ 165 bajtów.InStr
, są one opcjonalne.Trim()
nie jest konieczne, ponieważ nie masz spacji. Przy prawidłowym zastosowaniu uzyskuję 147 bajtów .debug.print q
byłoby standardowe wyjście?msgbox q
jest 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.MsgBox
, jeśli ktoś narzeka, nadal możesz go zmienić.JavaScript ES6,
9986787672 znakiTest:
Dziękuję za to - to podstawa mojego rozwiązania :)
źródło
Oktawa,
107101 bajtówPowinien być O (log n), jeśli mam rację ...
Ładny druk:
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 - 1
pokazać, że mogę to zrobić dokładnie, a ostatni zestaw danych wyjściowych pokazuje, ile czasu zajmuje obliczenie tej wartości):źródło
T-SQL,
221189177 bajtówEDYCJA: 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.
I oto znowu, ale czytelne:
Jeśli używam tylko ints, może to być nieco krótsze, wychodzące na 157 bajtów:
I jeszcze raz, bardziej czytelny:
źródło
@
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ć dochar
zamiastvarchar
lub użyjstr
funkcji.@
, głupie mnie. RadaCHAR(8000)
jest całkiem dobra, spróbuję tego. Zawsze wydaje mi się, że zapominam o istnieniuSTR()
podziękowań dla heads up.select @t=concat(@t,@/i)
która powinna być mniejsza. Wymaga jednak sql2012.CONCAT
, Jestem w 2008 roku. Więc nie mogę go teraz przetestować bez użycia skrzypce SQL. Dobry telefon.Kod maszynowy Turinga,
333293 bajtówUż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.
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.
źródło
Perl, 66 bajtów
Numer należy wprowadzić przez STDIN.
źródło
(.?)
się$2
ponieważ(.*)
w$1
powinno 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;
.$c=<>;s/(.*)2(.*)/$1+1 .$2.0/e||$_++while($c--);print
. Miałem rację,(.?)
nigdy niczego nie uchwyciłem.$_=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
.Pyth, 19 bajtów
Złożoność logarytmiczna. Łatwo kończy się w niezbędnym czasie. Dane wyjściowe w postaci listy cyfr.
Demonstracja .
źródło
Perl,
847067 bajtówNiezbyt golfowy,coraz lepszy, ale działa bardzo szybko!Sugestia Dennisa sprowadza go do 51 (50 bajtów + przełącznik -p)
To musi być nazywane jak
perl -p skew_binary.pl num_list.txt
gdzienum_list.txt
zawiera pojedynczą linię z numerem do zakodowania na niej.źródło
Mathematica, 65
Powinno to być dość szybkie, chociaż muszę przyznać, że zerknąłem na inne zgłoszenia, zanim to zrobiłem.
Stosowanie:
Wynik:
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:
Wynik:
źródło
C, 95 bajtów
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ściowych0
(ponieważ pytanie określa tylko dodatnie liczby całkowite), więc nie ma specjalnej obudowy, aby uniknąć pustych danych wyjściowych.Rozszerzony kod
Działamy przez kolejne odejmowanie, zaczynając od najbardziej znaczącej cyfry. Jedyną komplikacją jest to, że używamy zmiennej,
m
aby uniknąć drukowania zer wiodących. Wunsigned long long
razie potrzeby można dokonać naturalnego rozszerzenia kosztem 10 bajtów.Program testowy
Przekaż liczby do przekonwertowania jako argumenty poleceń. Konwertuje
int
bufor tablicy na drukowalny ciąg cyfr. Środowisko wykonawcze ma mniej niż jedną milisekundę dla danych wejściowych1000000000000000000
.Wyniki testu
źródło
auto a=~0ull
z niewielką przewagą ...JavaScript (Node.js) , 40 bajtów
Wypróbuj online!
To rozwiązanie nie działa na ostatniej walizce testowej. To po prostu powoduje przepełnienie stosu.
źródło
CoffeeScript,
9269 bajtówNa podstawie odpowiedzi i aktualizacji Qwertiy :
źródło
Japt , 31 bajtów
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
źródło
Stax , 16 bajtów
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.
Uruchom ten
źródło