Zwiększanie szarych kodów

36

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 0lub 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 0s 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 1s i 0s
  • 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 1i0

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 , 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.

Patrick Roberts
źródło
Czy możemy przyjmować dane wejściowe jako liczbę?
xnor
1
Mniej oczywiste, również powiązane .
Martin Ender
1
Czy mogę wziąć odwrócone wejście i wyjście, np. 0011Dla 8
Ton Hospel
1
@TonHospel przepraszam, nie widziałem twojego pytania o odwrócone operacje we / wy. Jak powiedziałem 1000000000 moja odpowiedź brzmi „nie”.
Patrick Roberts,

Odpowiedzi:

13

Galaretka , 10 8 bajtów

Dzięki Dennis za oszczędność 2 bajtów.

^\Ḅ‘^H$B

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:

a(n) = n XOR [n/2] XOR [n/4] XOR [n/8] ...

Gdzie []są wsporniki podłogowe. Rozważ przykład, 44którego reprezentacją binarną jest 101100. 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 liczby

1 0 1 1 0 0
  1 0 1 1 0
    1 0 1 1
      1 0 1
        1 0
          1

Zauważ, że n kolumna th zawiera pierwsze nbity. 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:

a(n) = n XOR floor(n/2)

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:

^\          Cumulative reduce of XOR over the input.
  Ḅ         Convert binary list to integer.
   ‘        Increment.
    ^H$     XOR with half of itself.
       B    Convert integer to binary list.
Martin Ender
źródło
Nie potrzebujesz Ḟ$; operatory bitowe rzutowane na int .
Dennis
@Dennis Dzięki, odkryłem to podczas pisania. :)
Martin Ender
@MartinEnder Czy liczba całkowita, którą konwertuje na wewnętrznie dużą liczbę całkowitą?
Patrick Roberts,
@PatrickRoberts tak, jeśli to konieczne - to Python pod maską.
Jonathan Allan
Niezła analiza i wyjaśnienie.
Wayne Conrad
8

JavaScript (ES6), 58 bajtów

s=>s.replace(s.split`1`.length%2?/.$/:/.?(?=10*$)/,c=>1-c)

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.

Neil
źródło
Bardzo fajna metoda. Jest pierwszym ?w /.?(?=10*$)/naprawdę konieczne? Och nieważne. Tak to jest. :-)
Arnauld
8

Perl, 27 25 bajtów

Obejmuje +1 dla -p

Podaj ciąg wejściowy na STDIN, np

gray.pl <<< 1010

gray.pl:

#!/usr/bin/perl -p
s%(10*\K1(\K0)*)*%1-$&%e

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.

Ton Hospel
źródło
1
Wow, \Gnaprawdę ułatwia ci to zadanie!
Neil,
1
Z drugiej strony \Ksprawia , że wszystko jest jeszcze łatwiejsze.
Neil,
Haaaaa ... Teraz chcę też zobaczyć \Gwdrożenie.
Magic Octopus Urn
2
@carusocomputing Możesz zobaczyć starsze wersje zgłoszenia, klikając edytowany link
Ton Hospel,
6

Haskell, 118 115 108 bajtów

g 0=[""]
g n|a<-g$n-1=map('0':)a++map('1':)(reverse a)
d=dropWhile
f s=d(=='0')$(d(/='0':s)$g$1+length s)!!1

Wypróbuj na Ideone.
Naiwne podejście: ggeneruje zestaw wszystkich szarych kodów o długości n(z dopełnieniem 0), fwywołuje za gpomocą length(input)+1, usuwa wszystkie elementy, dopóki nie 0<inputstring>zostanie znaleziony, i zwraca następny element (obcinając potencjalnie wiodący 0).

Laikoni
źródło
1
Dobra pierwsza odpowiedź! Mam nadzieję, że wkrótce uda nam się uzyskać bardziej wydajne.
Patrick Roberts,
5

MATL , 18 bajtów

ZBtE:t2/kZ~tb=fQ)B

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.

ZB      % Input string implicitly. Convert from binary string to integer
        %   STACK: 5
t       % Duplicate
        %   STACK: 5, 5
E       % Multiply by 2. This is the number of terms we'll generate from the sequence
        %   STACK: 5, 10
:       % Range
        %   STACK: 5, [1 2 3 4 5 6 7 8 9 10]
t       % Duplicate
        %   STACK: 5, [1 2 3 4 5 6 7 8 9 10], [1 2 3 4 5 6 7 8 9 10]
2/k     % Divide by 2 and round down, element-wise
        %   STACK: 5, [1 2 3 4 5 6 7 8 9 10], [0 1 1 2 2 3 3 4 4 5]
Z~      % Bit-wise XOR, element-wise
        %   STACK: 5, [1 3 2 6 7 5 4 12 13 15]
t       % Duplicate
        %   STACK: 5, [1 3 2 6 7 5 4 12 13 15], [1 3 2 6 7 5 4 12 13 15]
b       % Bubble up
        %   STACK: [1 3 2 6 7 5 4 12 13 15], [1 3 2 6 7 5 4 12 13 15], 5
=       % Equality test, element-wise
        %   STACK: [1 3 2 6 7 5 4 12 13 15], [0 0 0 0 0 1 0 0 0 0]
f       % Find: yield (1-based) index of nonzero values (here there's only one)
        %   STACK: [1 3 2 6 7 5 4 12 13 15], 6
Q       % Increase by 1
        %   STACK: [1 3 2 6 7 5 4 12 13 15], 7
)       % Apply as index
        %   STACK: 4
B       % Convert to binary array
        %   STACK: [1 0 0]
        % Implicitly display
Luis Mendo
źródło
Zauważyłem, że dane wyjściowe są znakami rozdzielanymi spacjami ... czy wypisuje jakąś tablicę?
Patrick Roberts
@PatrickRoberts Tak, dokładnie. Zakładam, że to do przyjęcia, prawda?
Luis Mendo,
Przyjmę to tak, jak jest. Rozluźniłem już swoje wymagania dotyczące formatu I / O, więc nie ma sensu ponownie zwiększać jego dokładności. Dobra robota.
Patrick Roberts
5

CJam (19 bajtów)

{_2b__(^@1b1&*)^2b}

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

{         e# Declare a block:
  _2b     e#   Convert the bit array to a binary number
  __(^    e#   x ^ (x-1) gives 1s from the least significant set bit down
  @1b1&   e#   Get the parity of the number of set bits from the original array
  *       e#   Multiply: if we have an even number of set bits, we get 0;
          e#   otherwise we have 2**(lssb + 1) - 1
  )^      e#   Increment and xor by 1 or 2**(lssb + 1)
  2b      e#   Base convert back to a bit array
}

Pracując wyłącznie z tablicą bitów, myślę, że trzeba ją odwrócić: praca z lewą stroną 1jest znacznie łatwiejsza niż z prawej. Najlepsze, jakie do tej pory znalazłem, to (24 bajty):

{W%_1b)1&1$+1#0a*1+.^W%}

Alternatywne podejście (19 bajtów)

{[{1$^}*]2b)_2/^2b}

To konwertuje z kodu Graya na indeks, inkrementuje i konwertuje z powrotem na kod Graya.

Peter Taylor
źródło
5

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

f=(s,n=1)=>(b=(n^n/2).toString(2),s)?f(b!=s&&s,n+1):b

console.log(f("1"));      // -> 11
console.log(f("11"));     // -> 10
console.log(f("111"));    // -> 101
console.log(f("1011"));   // -> 1001
console.log(f("1111"));   // -> 1110
console.log(f("10111"));  // -> 10110
console.log(f("101100")); // -> 100100
console.log(f("100000")); // -> 1100000

Arnauld
źródło
Obawiam się, że to przesłanie się nie kwalifikuje, ponieważ metoda nie działa dla nieograniczonej długości łańcucha. Zmień na niekonkurencyjny, jeśli chcesz zachować tę odpowiedź tutaj.
Patrick Roberts
@PatrickRoberts - Jasne. To ma sens.
Arnauld
@PatrickRoberts Naprawdę? W jaki sposób limit rekurencji nie mieści się w „ograniczeniach pamięci narzuconych przez środowisko”?
Sanchises
@sanchises Miałem na myśli pamięć sterty, ale co więcej, ten program powtarza się dla każdego możliwego szarego kodu, aż do testowanego, co jest niezwykle nieefektywne. Technicznie można to przesłać jako „Node.js 6.5” i --harmonydodać bajty karne, aby uzyskać dostęp do optymalizacji rekurencji wywołania ogonowego, co wydaje się tutaj możliwe.
Patrick Roberts,
@sanchises Patrząc na moją odpowiedź, był to kiepski argument. Głównym problemem jest to, że ograniczenie nie jest narzucane przez środowisko, jest narzucane przez algorytm. Istnieją inne odpowiedzi, które powtarzają się dla każdego bitu, a nie dla każdej wartości przyrostowej, i uważam, że są one bardziej akceptowalne, ponieważ działają na znacznie szerszy zakres wartości.
Patrick Roberts,
2

Siatkówka, 25 bajtów

^(10*10*)*
$1:
1:
0
.?:
1

Jestem pewien, że powinien istnieć lepszy sposób na zrobienie tego ...

Neil
źródło
Czy naprawdę potrzebujesz ^?
Ton Hospel
@TonHospel Wyrażenie regularne próbowało dopasować wszędzie bez niego. (Domyślnie tryb zastępowania jest zamiennikiem globalnym).
Neil,
2

05AB1E , 12 bajtów

Wykorzystuje kodowanie CP-1252 .

CÐ<^¹SOÉ*>^b

Wypróbuj online!

Wyjaśnienie

Przykład dla wejścia 1011 .

C              # convert to int (bigint if necessary)
               # STACK: 11
 Ð             # triplicate
               # STACK: 11, 11, 11
  <            # decrease by 1
               # STACK: 11, 11, 10
   ^           # XOR
               # STACK: 11, 1
    ¹          # push first input
               # STACK: 11, 1, 1011
     S         # split to list
               # STACK: 11, 1, [1,0,1,1]
      O        # sum
               # STACK: 11, 1, 3
       É       # mod 2
               # STACK: 11, 1, 1
        *      # multiply
               # STACK: 11, 1
         >     # increase by 1
               # STACK: 11, 2
          ^    # XOR
               # STACK: 9
           b   # convert to binary
               # STACK: 1001
               # implicitly print top of stack
Emigna
źródło
2

Python 2.7, 68 znaków

def f(s):i=long(s,2);print bin(i^(1,(i&-i)<<1)[s.count('1')&1])[2:]

Python 3, 68 znaków

def f(s):i=int(s,2);print(bin(i^(1,(i&-i)<<1)[s.count('1')&1])[2:])

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 0bprzedrostek boolowski.

Morwenn
źródło
1
Możesz zapisać 1 bajt, usuwając spację po def f(s):i (zakładając, że Python 2) inny, używając printzamiast return.
ElPedro
@ElPedro Dzięki, zastosowałem także sztuczkę warunkową i rozważyłem rozmiar xora po lewej stronie, aby zapisać kilka dodatkowych znaków :)
Morwenn
Właśnie to widziałem. Ładna odpowiedź :-)
ElPedro
Um ... sprawdzanie dokumentacji Pythona, wygląda na to, że 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łoszenie
Patrick Roberts,
1
@PatrickRoberts Sprawdzę później. longzamiast intmoże rozwiązać problem.
Morwenn
2

C ++, 205 bajtów

#include <string>
std::string g(std::string s){int i,z;if(s=="1")return"11";for(i=z=0;i<s.length();i++)if(s[i]=='1')z++;i--;if(z%2){char c=s[i];s.erase(i);s=g(s);s+=c;}else{s[i]=s[i]==49?48:49;}return s;}

Opis: Parzyste liczby mają parzystą liczbę jedynek. Zmienne się zliczą; jeśli zjest 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.

AlexRacer
źródło
Dziękujemy za przesłanie. Jeśli mógłbyś podać krótki opis swojego podejścia i link do internetowej kompilacji tego jako wersji demonstracyjnej, naprawdę byłbym wdzięczny.
Patrick Roberts,
1
@PatrickRoberts Dodano link i opis zgodnie z prośbą.
AlexRacer,
2

Partia, 199 197 bajtów

@echo off
set/ps=
set r=
set t=%s:0=%
if 1%t:11=%==1 goto g
:l
set b=%s:~-1%
set s=%s:~,-1%
set r=%b%%r%
if %b%==0 goto l
if 0%s%==0 set s=0
:g
set/ab=1-%s:~-1%
echo %s:~,-1%%b%%r%

Odczytuje 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. sdlatego zawiera prefiks parzystości i rresztę ciągu.sjest ustawiony na zero, jeśli był pusty, aby można było przełączać jego ostatnią cyfrę, a następnie wszystko jest konkatenowane.

Neil
źródło
1

Właściwie 20 19 13 bajtów

Na 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!

σ1♀&2@¿u;½≈^├

Ungolfing

      Implicit input a as a list, such as [1,0,1,1,0,0].
σ     Get the cumulative sums of a.
1♀&   Map x&1 (equivalent to x%2) over every member of the cumulative sum.
2@¿   Convert from binary to decimal.
u     Increment x.
;½≈   Duplicate and integer divide by 2.
^     XOR x and x//2.
├     Convert to binary to obtain our incremented Gray code.
      Implicit return as a string, such as "100100".
Sherlock9
źródło
1

J, 38 bajtów

[:#:@(22 b.<.@-:)@>:@#.[:22 b./[:#:#.\

Wypróbuj online!

Jest to zasadniczo algorytm Martina w J.

Zauważ, że 22 b.to XOR.

                                    [: #: #.\   Creates the prefixes of the input
                                                converts to a number, then converts
                                                back to binary.  Needed to get the
                                                padding on the left.

                          [: 22 b./             Reduce the rows of the resulting 
                                                matrix with XOR, giving us the 
                                                normal binary
                      @#.                       Convert to int and...
                   @>:                          Increment and...
      (22 b. <.@-:)                             XOR that with its own floored half
[: #:@                                          And turn the result back to binary
Jonasz
źródło
Dobra robota, stary!
Patrick Roberts,