Введение
Серый код является альтернативой двоичного представления , в котором число увеличиваются на переключая только один бит, а не количество переменных бит. Вот некоторые серые коды вместе с их десятичным и двоичным эквивалентами:
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
, и нет никакой верхней границы для длины строки, кроме ограничений памяти, наложенных средой. - Под незаполненной строкой я подразумеваю, что не будет ни начальных, ни конечных пробелов (кроме необязательного конечного перевода строки), ни начальных
0
s на входе или выходе.
Форматы ввода / вывода
Следующие форматы принимаются для ввода и вывода, но строки приветствуются по сравнению с другими форматами:
- самый значительный «бит» первый
- не дополненный массив символов или строка ASCII
'1'
s и'0'
s - не дополненный массив целых чисел
1
s и0
s - ненасыщенный логический массив
Что не разрешено:
- наименее значимый "бит" первый
- десятичное, двоичное или унарное целое
- структура данных фиксированной длины
- массив символов или строка непечатаемых индексов ASCII
1
и0
тесты
input -> output
1 -> 11
11 -> 10
111 -> 101
1011 -> 1001
1111 -> 1110
10111 -> 10110
101100 -> 100100
100000 -> 1100000
Дополнительные тесты могут быть добавлены по запросу.
критерии
Это код-гольф , поэтому выигрывает самая короткая программа в байтах! Все связи будут разорваны в пользу более ранних представлений; применяются стандартные лазейки. Лучший ответ будет принят 9 октября 2016 года и будет обновляться всякий раз, когда будут предоставлены лучшие ответы.
источник
0011
для 8Ответы:
Желе ,
108 байтСпасибо Деннису за сохранение 2 байта.
Вход и выход представляют собой списки 0 и 1.
Попробуйте онлайн!
объяснение
Обратный код Грея дается A006068 . Используя это, нам не нужно генерировать большое количество кодов Грея для поиска входных данных. Одна классификация этой последовательности, приведенная в OEIS, такова:
Где
[]
находятся напольные кронштейны. Рассмотрим пример с44
двоичным представлением101100
. Деление на 2 и пол - это просто сдвиг вправо, отсекая наименее значимый бит. Итак, мы пытаемся XOR следующие цифрыОбратите внимание, что
n
столбец th содержит первыеn
биты. Следовательно, эта формула может быть вычислена тривиально на двоичном входе как совокупное уменьшение XOR по списку (который в основном применяет XOR к каждому префиксу списка и дает нам список результатов).Это дает нам простой способ инвертировать код Грея. После этого мы просто увеличиваем результат и преобразуем его обратно в код Грея. Для последнего шага мы используем следующее определение:
К счастью, Jelly, кажется, автоматически вводит входные данные при попытке XOR их. Во всяком случае, вот код:
источник
Ḟ$
; побитовые операторы приводятся к int .JavaScript (ES6), 58 байт
Непосредственно переключает соответствующий бит. Объяснение: Как показано в ответе MartinEnder, каждый бит в декодированном коде Грея представляет собой совокупный XOR, или четность, самого себя и биты слева от него. Затем нам нужно увеличить число, которое вызывает пульсацию переноса, которая переключает все самые правые 1 бит на 0, а затем следующие 0 бит на 1. Повторное кодирование приводит к коду с переключением только этой одной позиции 0 бит. Если четность всех 1 битов четна, то самый правый бит равен 0, и поэтому мы просто переключаем последний бит. Если четность всех 1 битов нечетна, то самые правые биты равны 1, и нам нужно найти последний 1 бит. Теперь это последний из переносимых битов, поэтому бит, который нам нужно переключить, является следующим битом справа.
источник
?
в/.?(?=10*$)/
действительно необходимо? О, неважно. Да, это. :-)Perl,
2725 байтВключает +1 для
-p
Введите строку ввода в STDIN, например
gray.pl
:В Perl нет дешевых целых чисел с бесконечной точностью. Так что непосредственно переключайте правый бит, который находится непосредственно перед тем, где будет последний нечетный 1.
источник
\G
действительно облегчает вам жизнь!\K
делает вещи еще проще для вас.\G
реализацию.Haskell,
118 115108 байтПопробуйте это на Ideone.
Наивный подход:
g
генерирует набор всех серых кодов с длинойn
(с 0-отступом),f
вызываетg
сlength(input)+1
, удаляет все элементы до тех пор, пока не0<inputstring>
будет найден, и возвращает следующий элемент (обрезая возможный ведущий0
).источник
MATL , 18 байт
Попробуйте онлайн! Или проверьте все тестовые случаи .
объяснение
Пусть a ( n ) обозначает последовательность целых чисел, соответствующую кодам Грея ( OEIS A003188 ). Программа использует характеристику a ( n ) = n XOR floor ( n / 2), где XOR является побитовым.
По сути, код преобразует входные данные в целое число a 0 , находит это целое число в последовательности и затем выбирает следующий член. Это требует генерации достаточно большого числа членов последовательности a ( n ). Оказывается, 2 · a 0 достаточно велико. Это связано с тем, что код Грея a ( n ) никогда не имеет больше двоичных цифр, чем n .
Давайте возьмем входные данные
'101'
в качестве примера.источник
CJam (19 байт)
Демо онлайн . Это анонимный блок (функция) из битового массива в битовый массив, который демонстрационная программа выполняет в цикле.
Он работает по простому принципу: если число установленных битов четное, мы должны переключать младший значащий бит, в противном случае мы должны переключать бит слева от младшего значащего установленного бита. На самом деле выявить этот бит оказалось намного проще, если использовать битовые хаки для целого числа, чем использовать список битов.
рассечение
Работая исключительно с битовым массивом, я думаю, что необходимо обратить его вспять: работать с самым левым
1
намного легче, чем с самым правым. Лучшее, что я нашел до сих пор (24 байта):Альтернативный подход (19 байт)
Это преобразует код Грея в индекс, увеличивает и преобразует обратно в код Грея.
источник
JavaScript (ES6), 53 байта (не конкурирующий)
Рекурсивная функция, которая строит все серые коды до тех пор, пока не будет найден ввод, затем останавливается на следующей итерации.
Максимально возможный ввод зависит от предела рекурсии браузера (около 13 бит в Firefox и 15 бит в Chrome).
источник
--harmony
добавлено для штрафных байтов, чтобы иметь доступ к оптимизации рекурсии хвостового вызова, что представляется здесь возможным.Сетчатка, 25 байт
Я уверен, что должен быть лучший способ сделать это ...
источник
^
?05AB1E , 12 байтов
Использует кодировку CP-1252 .
Попробуйте онлайн!
объяснение
Пример для ввода 1011 .
источник
Python 2.7, 68 символов
Python 3, 68 символов
Эта функция преобразует данную двоичную строку в целое число, а затем xor последний бит, если число установленных битов в исходной строке является четным, или меняет местами бит слева от самого правого установленного бита, если количество установленных битов в оригинале Строка нечетная. Затем он преобразует результат в двоичную строку и удаляет
0b
логический префикс.источник
def f(s):
и (предполагая Python 2) другой, используяprint
вместоreturn
.int()
генерирует 32-битное целое число, хотя мое требование заключается в том, чтобы вы увеличивали строку любой длины. Я не уверен, что это считается действительным представлениемlong
вместо того,int
чтобы решить проблему.C ++, 205 байт
Описание: Четные числа имеют четные числа. Переменная
z
считает единицы; ifz
is even (z mod 2 = z%2 = 0
- else ветвь), измените последний бит; еслиz
нечетно, снова вызвать эту функцию без последнего символа и вычислить новое значение, а затем добавить последний символ.Нажмите здесь, чтобы попробовать его для тестовых случаев.
источник
Пакет,
199197 байтовЧитает ввод из STDIN в переменную
s
. Удаляет 0 и выполняет проверку четности на 1, и, если есть нечетное число, он удаляет самые правые 0 в цикле, останавливаясь, когда он удаляет 1,s
поэтому содержит префикс четности иr
остальную часть строки.s
устанавливается в ноль, если он был пустым, так что его последняя цифра может быть переключена, а затем все объединяется.источник
На самом деле,
201913 байтОсновано на ответе Желе Мартина Эндера с моей собственной версией "кумулятивного снижения XOR по сравнению с вводом". Предложения по игре в гольф приветствуются. Попробуйте онлайн!
Ungolfing
источник
J, 38 байт
Попробуйте онлайн!
По сути, это алгоритм Мартина в J.
Обратите внимание, что
22 b.
это XOR.источник