Wprowadzenie
Grey kod jest alternatywą dla reprezentacji binarnej, w których liczba jest zwiększana przez przełączenie tylko jednego bitu, a nie do ilości zmienny bitów. Oto niektóre szare kody wraz z ich dziesiętnymi i binarnymi odpowiednikami:
decimal | binary | gray
-------------------------
0 | 0 | 0
-------------------------
1 | 1 | 1
-------------------------
2 | 10 | 11
-------------------------
3 | 11 | 10
-------------------------
4 | 100 | 110
-------------------------
5 | 101 | 111
-------------------------
6 | 110 | 101
-------------------------
7 | 111 | 100
-------------------------
8 | 1000 | 1100
-------------------------
9 | 1001 | 1101
-------------------------
10 | 1010 | 1111
-------------------------
11 | 1011 | 1110
-------------------------
12 | 1100 | 1010
-------------------------
13 | 1101 | 1011
-------------------------
14 | 1110 | 1001
-------------------------
15 | 1111 | 1000
Cykliczny wzór bitowy szarego kodu
Czasami nazywany „odzwierciedleniem binarnym”, właściwość zmiany tylko jednego bitu na raz jest łatwo osiągana dzięki cyklicznym wzorom bitów dla każdej kolumny, zaczynając od najmniej znaczącego bitu:
bit 0: 0110011001100110011001100110011001100110011001100110011001100110
bit 1: 0011110000111100001111000011110000111100001111000011110000111100
bit 2: 0000111111110000000011111111000000001111111100000000111111110000
bit 3: 0000000011111111111111110000000000000000111111111111111100000000
bit 4: 0000000000000000111111111111111111111111111111110000000000000000
bit 5: 0000000000000000000000000000000011111111111111111111111111111111
...i tak dalej.
Cel
Biorąc pod uwagę niepochodzący ciąg wejściowy szarego kodu, zwiększaj szary kod, zmieniając pojedynczy znak w sekwencji lub przygotowując 1
(przy zwiększaniu do następnej potęgi 2), a następnie wyślij wynik jako niepodszarpany szary kod.
Ostrzeżenia
- Nie martw się o pobranie
0
lub pusty ciąg znaków jako dane wejściowe. - Najniższe wejście będzie
1
, i nie ma górnego ograniczenia długości łańcucha innego niż ograniczenia pamięci narzucone przez środowisko. - Przez łańcuch bez dopełnienia mam na myśli, że nie będzie żadnych początkowych ani końcowych białych znaków (poza opcjonalnym końcowym znakiem nowej linii) i żadnych wiodących liter
0
s na wejściu lub wyjściu.
Formaty we / wy
Następujące formaty są akceptowane jako dane wejściowe i wyjściowe, ale zachęca się ciągi znaków w stosunku do innych formatów:
- najważniejszy „bit” jako pierwszy
- non-wyściełane tablica znak lub ciąg ASCII
'1'
s i'0'
s - niepaścieniana tablica liczb całkowitych
1
s i0
s - niemodyfikowana tablica boolowska
Co nie jest dozwolone:
- najpierw najmniej znaczący „bit”
- dziesiętna, binarna lub jednoargumentowa liczba całkowita
- struktura danych o stałej długości
- tablica znaków lub ciąg niedrukowalnych indeksów ASCII
1
i0
Testy
input -> output
1 -> 11
11 -> 10
111 -> 101
1011 -> 1001
1111 -> 1110
10111 -> 10110
101100 -> 100100
100000 -> 1100000
Więcej testów można dodać na żądanie.
Kryteria
To jest golf golfowy , więc wygrywa najkrótszy program w bajtach! Wszystkie więzi zostaną zerwane przez faworyzowanie wcześniejszych zgłoszeń; obowiązują standardowe luki. Najlepsza przesłana odpowiedź zostanie zaakceptowana 9 października 2016 r. I będzie aktualizowana za każdym razem, gdy zostaną podane lepsze odpowiedzi.
źródło
0011
Dla 8Odpowiedzi:
Galaretka ,
108 bajtówDzięki Dennis za oszczędność 2 bajtów.
Wejścia i wyjścia to listy zer i jedynek.
Wypróbuj online!
Wyjaśnienie
Odwrotność kodu Graya podana jest przez A006068 . Korzystając z tego, nie musimy generować dużej liczby kodów Graya, aby sprawdzić dane wejściowe. Jedna klasyfikacja tej sekwencji podana w OEIS jest następująca:
Gdzie
[]
są wsporniki podłogowe. Rozważ przykład,44
którego reprezentacją binarną jest101100
. Dzielenie przez 2 i podłogę jest tylko przesunięciem w prawo, odcinając najmniej znaczący kawałek. Więc próbujemy XOR następujące liczbyZauważ, że
n
kolumna th zawiera pierwszen
bity. Stąd ta formuła może być obliczona w sposób trywialny na wejściu binarnym jako skumulowana redukcja XOR na liście (która zasadniczo stosuje XOR do każdego prefiksu listy i daje nam listę wyników).To daje nam prosty sposób na odwrócenie szarego kodu. Następnie zwiększamy wynik i przekształcamy go z powrotem w kod Graya. W ostatnim kroku używamy następującej definicji:
Na szczęście Jelly wydaje się automatycznie umieszczać dane wejściowe na podłodze przy próbie ich XOR. W każdym razie oto kod:
źródło
Ḟ$
; operatory bitowe rzutowane na int .JavaScript (ES6), 58 bajtów
Bezpośrednio przełącza odpowiedni bit. Objaśnienie: Jak pokazano w odpowiedzi MartinEnder ♦, każdy bit w zdekodowanym kodzie Graya jest skumulowanym XOR lub parzystością samego siebie i bitów po jego lewej stronie. Następnie musimy zwiększyć liczbę, która powoduje tętnienie przenoszenia, które przełącza wszystkie skrajnie prawe 1 bity na 0, a następnie następne 0 bitów na 1. Ponowne kodowanie powoduje powstanie kodu z tylko jedną pozycją 0 bitów przełączoną. Jeśli parzystość wszystkich 1 bitów jest parzysta, to bit najbardziej po prawej stronie wynosi 0, a zatem przełączamy tylko ostatni bit. Jeśli parzystość wszystkich 1 bitów jest nieparzysta, to najbardziej prawostronne bity wynoszą 1 i musimy znaleźć ostatni 1 bit. To jest teraz ostatni z przenoszonych bitów, więc bit, który musimy przełączyć, to następny bit od prawej.
źródło
?
w/.?(?=10*$)/
naprawdę konieczne? Och nieważne. Tak to jest. :-)Perl,
2725 bajtówObejmuje +1 dla
-p
Podaj ciąg wejściowy na STDIN, np
gray.pl
:Perl nie ma tanich liczb całkowitych o nieskończonej precyzji. Więc bezpośrednio przełącz odpowiedni bit, który jest tuż przed tym, gdzie będzie ostatnia nieparzysta 1.
źródło
\G
naprawdę ułatwia ci to zadanie!\K
sprawia , że wszystko jest jeszcze łatwiejsze.\G
wdrożenie.Haskell,
118 115108 bajtówWypróbuj na Ideone.
Naiwne podejście:
g
generuje zestaw wszystkich szarych kodów o długościn
(z dopełnieniem 0),f
wywołuje zag
pomocąlength(input)+1
, usuwa wszystkie elementy, dopóki nie0<inputstring>
zostanie znaleziony, i zwraca następny element (obcinając potencjalnie wiodący0
).źródło
MATL , 18 bajtów
Wypróbuj online! Lub sprawdź wszystkie przypadki testowe .
Wyjaśnienie
Niech a ( n ) oznacza sekwencję liczb całkowitych odpowiadających kodom Graya ( OEIS A003188 ). Program wykorzystuje charakterystykę a ( n ) = n XOR floor ( n / 2), gdzie XOR jest bitowy.
Zasadniczo, kod przetwarza sygnał wejściowy na całkowitą w 0 stwierdza, że całkowitą w kolejności, a następnie wybiera następny określenia. Wymaga to wygenerowania wystarczająco dużej liczby elementów sekwencji a ( n ). Okazuje się, że 2 · 0 jest dostatecznie duża. Wynika to z faktu, że szary kod a ( n ) nigdy nie ma więcej cyfr binarnych niż n .
Weźmy
'101'
za przykład przykład.źródło
CJam (19 bajtów)
Demo online . Jest to anonimowy blok (funkcja) z tablicy bitów do tablicy bitów, który demo wykonuje w pętli.
Działa na prostej zasadzie, że jeśli liczba ustawionych bitów jest równa, powinniśmy przełączyć najmniej znaczący bit, a w przeciwnym razie powinniśmy przełączyć bit na lewo od najmniej znaczącego zestawu bitów. Właściwie identyfikacja tego bitu okazuje się znacznie łatwiejsza przy użyciu hacków bitowych na liczbach całkowitych niż przy użyciu listy bitów.
Sekcja
Pracując wyłącznie z tablicą bitów, myślę, że trzeba ją odwrócić: praca z lewą stroną
1
jest znacznie łatwiejsza niż z prawej. Najlepsze, jakie do tej pory znalazłem, to (24 bajty):Alternatywne podejście (19 bajtów)
To konwertuje z kodu Graya na indeks, inkrementuje i konwertuje z powrotem na kod Graya.
źródło
JavaScript (ES6), 53 bajty (niekonkurujące)
Funkcja rekurencyjna, która buduje wszystkie szare kody aż do znalezienia danych wejściowych, a następnie zatrzymuje się przy następnej iteracji.
Najwyższe możliwe wejście zależy od limitu rekurencji przeglądarki (około 13 bitów w Firefoksie i 15 bitów w Chrome).
źródło
--harmony
dodać bajty karne, aby uzyskać dostęp do optymalizacji rekurencji wywołania ogonowego, co wydaje się tutaj możliwe.Siatkówka, 25 bajtów
Jestem pewien, że powinien istnieć lepszy sposób na zrobienie tego ...
źródło
^
?05AB1E , 12 bajtów
Wykorzystuje kodowanie CP-1252 .
Wypróbuj online!
Wyjaśnienie
Przykład dla wejścia 1011 .
źródło
Python 2.7, 68 znaków
Python 3, 68 znaków
Ta funkcja konwertuje podany ciąg binarny na liczbę całkowitą, a następnie x lub ostatni bit, jeśli liczba ustawionych bitów w oryginalnym ciągu jest parzysta, lub zamienia bit na lewo od skrajnie prawego zestawu bitów, jeśli liczba ustawionych bitów w oryginale ciąg jest nieparzysty. Następnie konwertuje wynik na ciąg binarny i usuwa
0b
przedrostek boolowski.źródło
def f(s):
i (zakładając, że Python 2) inny, używającprint
zamiastreturn
.int()
generuje 32-bitową liczbę całkowitą, chociaż moim wymaganiem jest zwiększenie dowolnej długości łańcucha. Nie jestem pewien, czy kwalifikuje się to jako prawidłowe zgłoszenielong
zamiastint
może rozwiązać problem.C ++, 205 bajtów
Opis: Parzyste liczby mają parzystą liczbę jedynek. Zmienne się
z
liczą; jeśliz
jest parzysty (z mod 2 = z%2 = 0
- gałąź else), zmień ostatni bit; Jeśliz
jest nieparzysty, wywołaj tę funkcję ponownie bez ostatniego znaku i oblicz nową wartość, a następnie dołącz ostatni znak.Kliknij tutaj, aby wypróbować go dla przypadków testowych.
źródło
Partia,
199197 bajtówOdczytuje dane wejściowe ze STDIN do zmiennej
s
. Usuwa zera i wykonuje kontrolę parzystości na jedynkach, a jeśli liczba nieparzysta jest usuwana z pętli z prawej strony zer, zatrzymując się, gdy usuwa zera 1.s
dlatego zawiera prefiks parzystości ir
resztę ciągu.s
jest ustawiony na zero, jeśli był pusty, aby można było przełączać jego ostatnią cyfrę, a następnie wszystko jest konkatenowane.źródło
Właściwie
201913 bajtówNa podstawie odpowiedzi Jelly Martina Endera z moją własną wersją „skumulowanego zmniejszenia XOR ponad dane wejściowe”. Sugestie dotyczące gry w golfa mile widziane. Wypróbuj online!
Ungolfing
źródło
J, 38 bajtów
Wypróbuj online!
Jest to zasadniczo algorytm Martina w J.
Zauważ, że
22 b.
to XOR.źródło