nビットのグレイコードを出力する文字数で最短のプログラム。標準入力から取得される (ユーザーの提案により)nよりも小さい任意の数値になります。グレーコードは、例のように標準出力に出力されます。1000100000
注：プログラムが適切な時間でグレーコードを出力するとは思わない（n=100000やり過ぎです）。私はそれが印刷を開始することを期待しています。
入力:
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 文字のバージョンは、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['']
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
#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
( Impossible!はまだ開発中なので、個人的な言語が許可されているかどうかはわかりませんが、とにかく投稿したかったのです..)
(1<<n=gets.to_i).times{|x|puts"%.#{n}b"%(x^x/2)}
これは n=100000 で問題なく動作します
C++、空白を含まない 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 に敬意を表します。
前: 86 文字:
f a=map('0':)a++map('1':)(reverse a)
main=interact$ \s->unlines$iterate f[""]!!read s
2 つのストロークをインタラクトでカットし、1 つを unlines でカットします。
古い: 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"<>#&/@Reverse@#]&,{""},#]&
Thanks to A. Rex for suggestions!
Previous attempts
Here is my attempt in Mathematica (140 characters). I know that it isn't the shortest, but I think it is the easiest to follow if you are familiar with functional programming (though that could be my language bias showing). The addbit function takes an n-bit gray code and returns an n+1 bit gray code using the logic from the wikipedia page.. The make gray code function applies the addbit function in a nested manner to a 1 bit gray code, {{0}, {1}}, until an n-bit version is created. The charactercode function prints just the numbers without the braces and commas that are in the output of the addbit function.
addbit[set_] :=
Join[Map[Prepend[#, 0] &, set], Map[Prepend[#, 1] &, Reverse[set]]]
MakeGray[n_] :=
Map[FromCharacterCode, Nest[addbit, {{0}, {1}}, n - 1] + 48]
ウィキペディアのConstructing an n -bit Gray codeで説明されているものの簡単な Python 実装:
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;
}
C＃はコードゴルフに最適な言語ではありませんが、とにかくそれを試してみようと思いました。
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));
}
}
そして、これが私のFantomのいけにえの捧げ物です
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文字)
または拡張バージョン:
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#初心者にとっては良い学習体験でした - とにかく長すぎるので、わざわざ短くしませんでした;-)
反復ソリューション: (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
カットフリー プロローグ ('<<' の後のスペースを削除すると 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).
これは、Lua でできる限り近いものです。
LuaJIT (または lua-bitop を使用した lua): 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
ルビー、50文字
(2**n=gets.to_i).times{|i|puts"%0#{n}d"%i.to_s(2)}