Самая короткая программа по количеству символов, которая выводит n-бит Grey Code. n будет произвольным числом меньше 1000100000 (из-за предложений пользователя), которое берется из стандартного ввода. Серийный код будет напечатан в стандартном выводе, как в примере.
Примечание. Я не ожидаю, что программа напечатает серый код за разумное время (n=100000 overkill); Я действительно ожидаю, что он начнет печатать.
Ввод
4
Ожидаемый результат:
0000
0001
0011
0010
0110
0111
0101
0100
1100
1101
1111
1110
1010
1011
1001
1000
n=1<<input()
for x in range(n):print bin(n+x^x/2)[3:]
Эта версия 54 char преодолевает ограничение диапазона в Python2, так что n = 100000 работает!
x,n=0,1<<input()
while n>x:print bin(n+x^x/2)[3:];x+=1
69 символов
G=lambda n:n and[x+y for x in'01'for y in G(n-1)[::1-2*int(x)]]or['']
75 символов
G=lambda n:n and['0'+x for x in G(n-1)]+['1'+x for x in G(n-1)[::-1]]or['']
APL (29 символов)
С функцией F как (⌽ является "поворот" char)
z←x F y
z←(0,¨y),1,¨⌽y
Выдает серый код с 5 цифрами (⍴ теперь является "rho" char)
F/5⍴⊂0,1
Число "5" можно изменить или быть переменной.
(Извините за непечатаемые символы APL. SO не позволит мне отправлять изображения в качестве нового пользователя)
#l{'0,'1}1[;@l<][%;~['1%+].>.%['0%+].>.+//%1+]<>%[^].>
Тестирование:
./impossible gray.i! 5
Impossible v0.1.28
00000
00001
00011
00010
00110
00111
00101
00100
01100
01101
01111
01110
01010
01011
01001
01000
11000
11001
11011
11010
11110
11111
11101
11100
10100
10101
10111
10110
10010
10011
10001
10000
(на самом деле я не знаю, разрешены ли личные языки, так как Невозможно! все еще находится в разработке, но я все равно хотел его опубликовать..)
Чтение из stdin, запись в stdout
~2\?:),{.2/^)+2base''*1>n}%
Пример прогона
$ echo 4 | ruby golfscript.rb gray.gs
0000
0001
0011
0010
0110
0111
0101
0100
1100
1101
1111
1110
1010
1011
1001
1000
(1<<n=gets.to_i).times{|x|puts"%.#{n}b"%(x^x/2)}
Это работает для n = 100000 без проблем
С++, 168 символов, не считая пробелов:
#include <iostream>
#include <string>
int r;
void x(std::string p, char f=48)
{
if(!r--)std::cout<<p<<'\n';else
{x(p+f);x(p+char(f^1),49);}
r++;
}
int main() {
std::cin>>r;
x("");
return 0;
}
Haskell, 82 символа:
f a=map('0':)a++map('1':)(reverse a)
main=interact$unlines.(iterate f[""]!!).read
Бесподобный стиль для победы! (или, по крайней мере, на 4 меньше ударов). Престижность к FUZxxl.
previous: 86 символов:
f a=map('0':)a++map('1':)(reverse a)
main=interact$ \s->unlines$iterate f[""]!!read s
Вырезать два удара с помощью взаимодействия, один с unline.
старше: 89 символов:
f a=map('0':)a++map('1':)(reverse a)
main=readLn>>= \s->putStr$concat$iterate f["\n"]!!s
Обратите внимание, что лента дает вам немедленный выход бесплатно.
Mathematica 50 Chars
Nest[Join["0"<>#&/@#,"1"<>#&/@[email protected]#]&,{""},#]&
Спасибо А. Рексу за предложения!
Предыдущие попытки
Вот моя попытка в Mathematica (140 символов). Я знаю, что это не кратчайший, но я думаю, что это проще всего, если вы знакомы с функциональным программированием (хотя это может быть мой язык). Функция addbit принимает n-разрядный серый код и возвращает сериальный код n + 1 бит с использованием логики со страницы wikipedia. Функция make grey code применяет функцию добавления вложенной формы к 1-битовому серому коду, {{ 0}, {1}}, пока не будет создана n-разрядная версия. Функция charactercode печатает только числа без фигурных скобок и запятых, которые находятся на выходе функции добавления.
addbit[set_] :=
Join[Map[Prepend[#, 0] &, set], Map[Prepend[#, 1] &, Reverse[set]]]
MakeGray[n_] :=
Map[FromCharacterCode, Nest[addbit, {{0}, {1}}, n - 1] + 48]
Простая реализация Python, описанная в Построение n-разрядного кода Grey в Википедии:
import sys
def _gray(n):
if n == 1:
return [0, 1]
else:
p = _gray(n-1)
pr = [x + (1<<(n-1)) for x in p[::-1]]
return p + pr
n = int(sys.argv[1])
for i in [("0"*n + bin(a)[2:])[-n:] for a in _gray(n)]:
print i
(233 символа)
Тест:
$ python gray.py 4
0000
0001
0011
0010
0110
0111
0101
0100
1100
1101
1111
1110
1010
1011
1001
1000
Здесь жертвоприношение, в C:
#include <stdio.h>
#include <stdlib.h>
int main(void)
{
char s[256];
int b, i, j, m, g;
gets(s);
b = atoi(s);
for (i = 0; i < 1 << b; ++i)
{
g = i ^ (i / 2);
m = 1 << (b - 1);
for (j = 0; j < b; ++j)
{
s[j] = (g & m) ? '1' : '0';
m >>= 1;
}
s[j] = '\0';
puts(s);
}
return 0;
}
С# - не лучший язык для кодового гольфа, но я думал, что все равно пойду.
static void Main(){var s=1L<<int.Parse(Console.ReadLine());for(long i=0;i<s;i++){Console.WriteLine(Convert.ToString(s+i^i/2,2).Substring(1));}}
Считываемая версия:
static void Main()
{
var s = 1L << int.Parse(Console.ReadLine());
for (long i = 0; i < s; i++)
{
Console.WriteLine(Convert.ToString(s + i ^ i / 2, 2).Substring(1));
}
}
И вот мое жертвоприношение Фантом
public static Str[]grayCode(Int i){if(i==1)return["0","1"];else{p:=grayCode(i-1);p.addAll(p.dup.reverse);p.each|s,c|{if(c<(p.size/2))p[c]="0"+s;else p[c]="1"+s;};return p}}
(177 char)
Или расширенная версия:
public static Str[] grayCode(Int i)
{
if (i==1) return ["0","1"]
else{
p := grayCode(i-1);
p.addAll(p.dup.reverse);
p.each |s,c|
{
if(c<(p.size/2))
{
p[c] = "0" + s
}
else
{
p[c] = "1" + s
}
}
return p
}
}
let m=List.map;;let rec g l=function|1->l|x->g((m((+)"0")l)@(l|>List.rev|>m((+)"1")))(x - 1);;stdin.ReadLine()|>int|>g["0";"1"]|>List.iter(printfn "%s")
F # 180 175 слишком много символов
Сегодня утром я сделал еще одну версию, упростив рекурсивную версию, но, к сожалению, из-за рекурсии она не будет делать 100000.
Рекурсивное решение:
let rec g m n l =
if(m = n) then l
else List.map ((+)"0") l @ List.map ((+)"1") (List.rev(l)) |> g (m+1) n
List.iter (fun x -> printfn "%s" x) (g 1 (int(stdin.ReadLine())) ["0";"1"]);;
После этого я создал рабочую версию для требования "100000" - она слишком долго, чтобы конкурировать с другими показанными здесь решениями, и я, вероятно, повторно изобрел колесо несколько раз, но в отличие от многих решений, которые я имею здесь он будет работать с очень-очень большим количеством бит, и он был хорошим опытом обучения для F # noob - я не стал его укорачивать, так как он слишком длинный в любом случае; -)
Итеративное решение: (работает с 100000 +)
let bits = stdin.ReadLine() |>int
let n = 1I <<< bits
let bitcount (n : bigint) =
let mutable m = n
let mutable c = 1
while m > 1I do
m <- m >>>1
c<-c+1
c
let rec traverseBits m (number: bigint) =
let highbit = bigint(1 <<< m)
if m > bitcount number
then number
else
let lowbit = 1 <<< m-1
if (highbit&&& number) > 0I
then
let newnum = number ^^^ bigint(lowbit)
traverseBits (m+1) newnum
else traverseBits (m+1) number
let res = seq
{
for i in 0I..n do
yield traverseBits 1 i
}
let binary n m = seq
{
for i = m-1 downto 0 do
let bit = bigint(1 <<< i)
if bit &&&n > 0I
then yield "1"
else yield "0"
}
Seq.iter (fun x -> printfn "%s" (Seq.reduce (+) (binary x bits))) res
Это мой бросок на него в Луа, как можно ближе к нему.
LuaJIT (или lua с lua-bitop): 156 байт
a=io.read()n,w,b=2^a,io.write,bit;for x=0,n-1 do t=b.bxor(n+x,b.rshift(x,1))for k=a-1,0,-1 do w(t%2^k==t%n and 0 or 1)t=t%2^k==t and t or t%2^k end w'\n'end
Lua 5.2: 154 байт
a=io.read()n,w,b=2^a,io.write,bit32;for x=0,n-1 do t=b.XOR(n+x,b.SHR(x,1))for k=a-1,0,-1 do w(t%2^k==t%n and 0 or 1)t=t%2^k==t and t or t%2^k end w'\n'end
В безрежимном прологе (138 байтов, если вы удалите пробел после '< <'; редактор представления усекает последнюю строку без него):
b(N,D):-D=0->nl;Q is D-1,H is N>>Q/\1,write(H),b(N,Q).
c(N,D):-N=0;P is N xor(N//2),b(P,D),M is N-1,c(M,D).
:-read(N),X is 1<< N-1,c(X,N).
Ruby, 50 Chars
(2**n=gets.to_i).times{|i|puts"%0#{n}d"%i.to_s(2)}