algorithm - significado - Código de golf: Código gris

que es codigo negro en un hospital

Question

El reto

El programa más corto por número de caracteres que genera el código gris de n bits. n será un número arbitrario menor que 1000 100000 (debido a las sugerencias del usuario) que se toma de la entrada estándar. El código gris se imprimirá en la salida estándar, como en el ejemplo.

Nota : no espero que el programa imprima el código gris en un tiempo razonable ( n=100000 es una exageración); Aunque espero que comience a imprimir.

Ejemplo

Entrada :

4

Salida esperada :

0000
0001
0011
0010
0110
0111
0101
0100
1100
1101
1111
1110
1010
1011
1001
1000

Answer 1

C, 203 personajes

Aquí hay una ofrenda de sacrificio, en 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;
}

Answer 2

C #, 149 143 caracteres

C # no es el mejor lenguaje para el código de golf, pero pensé que lo haría de todos modos.

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

Versión legible:

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

Answer 3

F #, 152 caracteres

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

Answer 4

Golfscript - 27 caracteres

Lee desde stdin, escribe a stdout

~2/?:),{.2/^)+2base''''*1>n}%

Ejecución de la muestra

$ echo 4 | ruby golfscript.rb gray.gs 
0000
0001
0011
0010
0110
0111
0101
0100
1100
1101
1111
1110
1010
1011
1001
1000

Answer 5

Lua, 156 caracteres

Este es mi lanzamiento en Lua, lo más cerca que puedo conseguirlo.

LuaJIT (o lua con lua-bitop): 156 bytes

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 bytes

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

Answer 6

Python - 53 caracteres

n=1<<input()
for x in range(n):print bin(n+x^x/2)[3:]

Esta versión de 54 caracteres supera la limitación de rango en Python2, por lo que n = 100000 funciona!

x,n=0,1<<input()
while n>x:print bin(n+x^x/2)[3:];x+=1

69 caracteres

G=lambda n:n and[x+y for x in''01''for y in G(n-1)[::1-2*int(x)]]or['''']

75 caracteres

G=lambda n:n and[''0''+x for x in G(n-1)]+[''1''+x for x in G(n-1)[::-1]]or['''']

Answer 7

Ruby - 49 caracteres

(1<<n=gets.to_i).times{|x|puts"%.#{n}b"%(x^x/2)}

Esto funciona para n = 100000 sin problema

Answer 8

Impossible! idioma (54 58 caracteres)

#l{''0,''1}1[;@l<][%;~[''1%+].>.%[''0%+].>.+//%1+]<>%[^].>

Prueba de funcionamiento:

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

(en realidad no sé si se permiten los idiomas personales, ya que Impossible! todavía está en desarrollo, pero quería publicarlo de todos modos ...)

Answer 9

C ++, 168 caracteres, sin incluir espacios en blanco:

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

Answer 10

En Prolog libre de cortes (138 bytes si elimina el espacio después de ''<<''; el editor de envíos trunca la última línea sin él):

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

Answer 11

Haskell, 82 caracteres:

f a=map(''0'':)a++map(''1'':)(reverse a)
main=interact$unlines.(iterate f[""]!!).read

¡Estilo sin puntos para la victoria! (o al menos 4 golpes menos). Felicitaciones a FUZxxl.

anterior: 86 caracteres:

f a=map(''0'':)a++map(''1'':)(reverse a)
main=interact$ /s->unlines$iterate f[""]!!read s

Cortar dos golpes con interactuar, uno con desalineados.

mayores: 89 caracteres:

f a=map(''0'':)a++map(''1'':)(reverse a)
main=readLn>>= /s->putStr$concat$iterate f["/n"]!!s

Tenga en cuenta que la pereza le da su salida inmediata de forma gratuita.

Answer 12

Implementación sencilla de Python de lo que se describe en Construir un código de Gray de n bits en Wikipedia:

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

Prueba:

$ python gray.py 4
0000
0001
0011
0010
0110
0111
0101
0100
1100
1101
1111
1110
1010
1011
1001
1000

Answer 13

Ruby, 50 caracteres

(2**n=gets.to_i).times{|i|puts"%0#{n}d"%i.to_s(2)}

Answer 14

Y aquí está mi ofrenda sacrificial fantasma

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

O la versión expandida:

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

Answer 15

Mathematica 50 caracteres

Nest[Join["0"<>#&/@#,"1"<>#&/@Reverse@#]&,{""},#]&

Gracias a A. Rex por sugerencias!

Intentos anteriores

Aquí está mi intento en Mathematica (140 caracteres). Sé que no es el más corto, pero creo que es el más fácil de seguir si está familiarizado con la programación funcional (aunque podría ser mi sesgo de lenguaje). La función addbit toma un código gris de n bits y devuelve un código gris n + 1 bit usando la lógica de la página de wikipedia. La función de código gris crea la función addbit de forma anidada a un código gris de 1 bit, {{ 0}, {1}}, hasta que se cree una versión de n bits. La función de código de caracteres imprime solo los números sin las llaves y comas que se encuentran en la salida de la función de complemento.

addbit[set_] := 
 Join[Map[Prepend[#, 0] &, set], Map[Prepend[#, 1] &, Reverse[set]]]
MakeGray[n_] := 
 Map[FromCharacterCode, Nest[addbit, {{0}, {1}}, n - 1] + 48]

Answer 16

APL (29 caracteres)

Con la función F como ( ⌽ es el carácter ''rotar'')

z←x F y
z←(0,¨y),1,¨⌽y

Esto produce el Código Gris con 5 dígitos ( ⍴ ahora es el carácter ''rho'')

F/5⍴⊂0,1

El número ''5'' puede ser cambiado o ser una variable.

(Lo siento por los caracteres APL no imprimibles. Por lo tanto, no me permitirá publicar imágenes como nuevo usuario)

Answer 17

F # 180 175 demasiados personajes

Esta mañana hice otra versión, simplificando la versión recursiva, pero lamentablemente, debido a la recursión, no haría el 100000.

Solución recursiva:

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"]);;

Una vez hecho esto, creé una versión de trabajo para el requisito "100000": es demasiado tiempo para competir con las otras soluciones que se muestran aquí y probablemente reinventé la rueda varias veces, pero a diferencia de muchas de las soluciones que he visto aquí Trabajará con una cantidad muy, muy grande de bits y, por supuesto, fue una buena experiencia de aprendizaje para un F # noob. No me molesté en acortarlo, ya que de todos modos es demasiado largo ;-)

Solución iterativa: (trabajando con 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