Увеличение серых кодов

36

Введение

Серый код является альтернативой двоичного представления , в котором число увеличиваются на переключая только один бит, а не количество переменных бит. Вот некоторые серые коды вместе с их десятичным и двоичным эквивалентами:

 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

Циклический битовый код серого кода

Иногда называемый «отраженный двоичный файл», свойство изменения только одного бита за раз легко достигается с помощью циклических битовых комбинаций для каждого столбца, начиная с младшего значащего бита:

bit 0: 0110011001100110011001100110011001100110011001100110011001100110
bit 1: 0011110000111100001111000011110000111100001111000011110000111100
bit 2: 0000111111110000000011111111000000001111111100000000111111110000
bit 3: 0000000011111111111111110000000000000000111111111111111100000000
bit 4: 0000000000000000111111111111111111111111111111110000000000000000
bit 5: 0000000000000000000000000000000011111111111111111111111111111111

...и так далее.

Задача

Если задана не дополняемая входная строка серого кода, увеличьте серый код, чередуя один символ в последовательности или добавив перед ним 1(при увеличении до следующей степени 2), затем выведите результат в виде не дополненного серого кода.

Предостережения

  • Не беспокойтесь о принятии 0или пустой строке в качестве входных данных.
  • Наименьший ввод будет 1, и нет никакой верхней границы для длины строки, кроме ограничений памяти, наложенных средой.
  • Под незаполненной строкой я подразумеваю, что не будет ни начальных, ни конечных пробелов (кроме необязательного конечного перевода строки), ни начальных 0s на входе или выходе.

Форматы ввода / вывода

Следующие форматы принимаются для ввода и вывода, но строки приветствуются по сравнению с другими форматами:

  • самый значительный «бит» первый
  • не дополненный массив символов или строка ASCII '1's и '0's
  • не дополненный массив целых чисел 1s и 0s
  • ненасыщенный логический массив

Что не разрешено:

  • наименее значимый "бит" первый
  • десятичное, двоичное или унарное целое
  • структура данных фиксированной длины
  • массив символов или строка непечатаемых индексов ASCII 1и0

тесты

input -> output
1 -> 11
11 -> 10
111 -> 101
1011 -> 1001
1111 -> 1110
10111 -> 10110
101100 -> 100100
100000 -> 1100000

Дополнительные тесты могут быть добавлены по запросу.

критерии

Это , поэтому выигрывает самая короткая программа в байтах! Все связи будут разорваны в пользу более ранних представлений; применяются стандартные лазейки. Лучший ответ будет принят 9 октября 2016 года и будет обновляться всякий раз, когда будут предоставлены лучшие ответы.

Патрик Робертс
источник
1
Связанный. Связанный.
Мартин Эндер
Можем ли мы принять ввод как число?
xnor
1
Менее очевидно, также связано .
Мартин Эндер
1
Могу ли я взять и вход и выход в обратном порядке, например, 0011для 8
Тонн Хоспел
1
@TonHospel извините, я не видел ваш вопрос о реверсивных ввода / вывода. Как я уже сказал 1000000000, мой ответ - нет.
Патрик Робертс

Ответы:

13

Желе , 10 8 байт

Спасибо Деннису за сохранение 2 байта.

^\Ḅ‘^H$B

Вход и выход представляют собой списки 0 и 1.

Попробуйте онлайн!

объяснение

Обратный код Грея дается A006068 . Используя это, нам не нужно генерировать большое количество кодов Грея для поиска входных данных. Одна классификация этой последовательности, приведенная в OEIS, такова:

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

Где []находятся напольные кронштейны. Рассмотрим пример с 44двоичным представлением 101100. Деление на 2 и пол - это просто сдвиг вправо, отсекая наименее значимый бит. Итак, мы пытаемся XOR следующие цифры

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

Обратите внимание, что nстолбец th содержит первые nбиты. Следовательно, эта формула может быть вычислена тривиально на двоичном входе как совокупное уменьшение XOR по списку (который в основном применяет XOR к каждому префиксу списка и дает нам список результатов).

Это дает нам простой способ инвертировать код Грея. После этого мы просто увеличиваем результат и преобразуем его обратно в код Грея. Для последнего шага мы используем следующее определение:

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

К счастью, Jelly, кажется, автоматически вводит входные данные при попытке XOR их. Во всяком случае, вот код:

^\          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.
Мартин Эндер
источник
Вам не нужно Ḟ$; побитовые операторы приводятся к int .
Деннис
@ Деннис Спасибо, я обнаружил это во время записи. :)
Мартин Эндер
@MartinEnder Является ли целое число, которое оно конвертирует, внутренне большим целым числом?
Патрик Робертс
@PatrickRoberts да, если нужно - это Python под капотом.
Джонатан Аллан
Хороший анализ и объяснение.
Уэйн Конрад
8

JavaScript (ES6), 58 байт

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

Непосредственно переключает соответствующий бит. Объяснение: Как показано в ответе MartinEnder, каждый бит в декодированном коде Грея представляет собой совокупный XOR, или четность, самого себя и биты слева от него. Затем нам нужно увеличить число, которое вызывает пульсацию переноса, которая переключает все самые правые 1 бит на 0, а затем следующие 0 бит на 1. Повторное кодирование приводит к коду с переключением только этой одной позиции 0 бит. Если четность всех 1 битов четна, то самый правый бит равен 0, и поэтому мы просто переключаем последний бит. Если четность всех 1 битов нечетна, то самые правые биты равны 1, и нам нужно найти последний 1 бит. Теперь это последний из переносимых битов, поэтому бит, который нам нужно переключить, является следующим битом справа.

Нил
источник
Очень хороший метод. Является первым ?в /.?(?=10*$)/действительно необходимо? О, неважно. Да, это. :-)
Арно
8

Perl, 27 25 байт

Включает +1 для -p

Введите строку ввода в STDIN, например

gray.pl <<< 1010

gray.pl:

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

В Perl нет дешевых целых чисел с бесконечной точностью. Так что непосредственно переключайте правый бит, который находится непосредственно перед тем, где будет последний нечетный 1.

Тон Хоспел
источник
1
Вау, \Gдействительно облегчает вам жизнь!
Нил
1
С другой стороны, \Kделает вещи еще проще для вас.
Нил
Хааааа ... Теперь я тоже хочу увидеть \Gреализацию.
Волшебная Урна Осьминога
2
@carusocomputing Вы можете увидеть более старые версии представления, нажав на отредактированную ссылку
Ton Hospel
6

Haskell, 118 115 108 байт

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

Попробуйте это на Ideone.
Наивный подход: gгенерирует набор всех серых кодов с длиной n(с 0-отступом), fвызывает gс length(input)+1, удаляет все элементы до тех пор, пока не 0<inputstring>будет найден, и возвращает следующий элемент (обрезая возможный ведущий 0).

Laikoni
источник
1
Хороший первый ответ! Я надеюсь, что мы скоро сможем получить более эффективные.
Патрик Робертс
5

MATL , 18 байт

ZBtE:t2/kZ~tb=fQ)B

Попробуйте онлайн! Или проверьте все тестовые случаи .

объяснение

Пусть a ( n ) обозначает последовательность целых чисел, соответствующую кодам Грея ( OEIS A003188 ). Программа использует характеристику a ( n ) = n XOR floor ( n / 2), где XOR является побитовым.

По сути, код преобразует входные данные в целое число a 0 , находит это целое число в последовательности и затем выбирает следующий член. Это требует генерации достаточно большого числа членов последовательности a ( n ). Оказывается, 2 · a 0 достаточно велико. Это связано с тем, что код Грея a ( n ) никогда не имеет больше двоичных цифр, чем n .

Давайте возьмем входные данные '101'в качестве примера.

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
Луис Мендо
источник
Я заметил, что вывод - это символы, разделенные пробелами ... это печать какого-то массива?
Патрик Робертс
@PatrickRoberts Да, именно так. Я предположил, что это приемлемо, не так ли?
Луис Мендо
Я приму это как есть. Я уже ослабил свои требования к формату ввода / вывода, поэтому нет смысла делать его более строгим. Хорошая работа.
Патрик Робертс
5

CJam (19 байт)

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

Демо онлайн . Это анонимный блок (функция) из битового массива в битовый массив, который демонстрационная программа выполняет в цикле.

Он работает по простому принципу: если число установленных битов четное, мы должны переключать младший значащий бит, в противном случае мы должны переключать бит слева от младшего значащего установленного бита. На самом деле выявить этот бит оказалось намного проще, если использовать битовые хаки для целого числа, чем использовать список битов.

рассечение

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

Работая исключительно с битовым массивом, я думаю, что необходимо обратить его вспять: работать с самым левым 1намного легче, чем с самым правым. Лучшее, что я нашел до сих пор (24 байта):

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

Альтернативный подход (19 байт)

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

Это преобразует код Грея в индекс, увеличивает и преобразует обратно в код Грея.

Питер Тейлор
источник
5

JavaScript (ES6), 53 байта (не конкурирующий)

Рекурсивная функция, которая строит все серые коды до тех пор, пока не будет найден ввод, затем останавливается на следующей итерации.

Максимально возможный ввод зависит от предела рекурсии браузера (около 13 бит в Firefox и 15 бит в 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
источник
Боюсь, что это представление не подходит, так как метод не работает для неограниченной длины строки. Пожалуйста, перейдите на неконкурентный, если вы хотите оставить этот ответ здесь.
Патрик Робертс
@PatrickRoberts - Конечно. В этом есть смысл.
Арно
@PatrickRoberts Действительно? Как ограничение рекурсии не попадает под «ограничения памяти, накладываемые средой»?
Санчиз
@sanchises Я имел в виду кучу памяти, но более конкретно, эта программа рекурсивно использует каждый возможный серый код, вплоть до тестируемого, что крайне неэффективно. Технически это может быть представлено как «Node.js 6.5» и --harmonyдобавлено для штрафных байтов, чтобы иметь доступ к оптимизации рекурсии хвостового вызова, что представляется здесь возможным.
Патрик Робертс
@sanchises Рассматривая мой ответ, это был плохой аргумент. Основная проблема заключается в том, что ограничение не накладывается средой, а алгоритмом. Существуют и другие ответы, которые повторяются для каждого бита, а не для каждого добавочного значения, и я считаю, что они более приемлемы, поскольку они работают для гораздо более широкого диапазона значений.
Патрик Робертс
2

Сетчатка, 25 байт

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

Я уверен, что должен быть лучший способ сделать это ...

Нил
источник
Вам на самом деле нужно ^?
Тон Хоспел
@TonHospel Регулярное выражение пыталось сопоставить везде без него. (Режим замены по умолчанию - глобальная замена.)
Нил
2

05AB1E , 12 байтов

Использует кодировку CP-1252 .

CÐ<^¹SOÉ*>^b

Попробуйте онлайн!

объяснение

Пример для ввода 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
источник
2

Python 2.7, 68 символов

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

Python 3, 68 символов

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

Эта функция преобразует данную двоичную строку в целое число, а затем xor последний бит, если число установленных битов в исходной строке является четным, или меняет местами бит слева от самого правого установленного бита, если количество установленных битов в оригинале Строка нечетная. Затем он преобразует результат в двоичную строку и удаляет 0bлогический префикс.

Morwenn
источник
1
Вы можете сэкономить 1 байт, удалив пробел после def f(s):и (предполагая Python 2) другой, используя printвместо return.
ElPedro
@ElPedro Спасибо, я также применил условный трюк и вычленил размер xor для левой руки, чтобы сохранить несколько дополнительных символов :)
Morwenn
Просто видел это. Хороший ответ :-)
ElPedro
Гм ... проверяя документацию по Python, похоже, int()генерирует 32-битное целое число, хотя мое требование заключается в том, чтобы вы увеличивали строку любой длины. Я не уверен, что это считается действительным представлением
Патрик Робертс
1
@PatrickRoberts я проверю позже. longвместо того, intчтобы решить проблему.
Морвенн
2

C ++, 205 байт

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

Описание: Четные числа имеют четные числа. Переменная zсчитает единицы; if zis even ( z mod 2 = z%2 = 0- else ветвь), измените последний бит; еслиz нечетно, снова вызвать эту функцию без последнего символа и вычислить новое значение, а затем добавить последний символ.

Нажмите здесь, чтобы попробовать его для тестовых случаев.

AlexRacer
источник
Спасибо за заявку. Если бы вы могли предоставить краткое описание вашего подхода и ссылку на онлайн-компиляцию этого в качестве демонстрации, я был бы очень признателен.
Патрик Робертс
1
@PatrickRoberts Добавил ссылку и описание, как вы просили.
AlexRacer
2

Пакет, 199 197 байтов

@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%

Читает ввод из STDIN в переменную s. Удаляет 0 и выполняет проверку четности на 1, и, если есть нечетное число, он удаляет самые правые 0 в цикле, останавливаясь, когда он удаляет 1, sпоэтому содержит префикс четности и rостальную часть строки. sустанавливается в ноль, если он был пустым, так что его последняя цифра может быть переключена, а затем все объединяется.

Нил
источник
1

На самом деле, 20 19 13 байт

Основано на ответе Желе Мартина Эндера с моей собственной версией "кумулятивного снижения XOR по сравнению с вводом". Предложения по игре в гольф приветствуются. Попробуйте онлайн!

σ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
источник
1

J, 38 байт

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

Попробуйте онлайн!

По сути, это алгоритм Мартина в J.

Обратите внимание, что 22 b.это 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
Ион
источник
Хорошая работа, чувак!
Патрик Робертс