Código universal (flexão de regras)

14

O código golf sempre envolve algumas respostas que distorcem as regras mais ou menos quebrando as restrições que os desafiadores deram como certa ou simplesmente não pensaram e não listaram nas regras. Uma dessas brechas interessantes é a possibilidade de gerar mais do que o desafio exige para obter um resultado melhor.

Levando isso a extremos, podemos escrever um solucionador de golfe com código universal que imprima a saída desejada - se você não se importa que isso pode levar séculos e gera muitas outras coisas antes e depois dela.

Tudo o que precisamos produzir é uma sequência que é garantida para conter todas as subsequências possíveis. Para este código de golfe, esta será a sequência de Ehrenfeucht-Mycielski :

A sequência começa com os três bits 010; cada dígito sucessivo é formado pela localização do sufixo mais longo da sequência que também aparece mais cedo na sequência e complementando o bit após a aparência anterior mais recente desse sufixo.

Toda subsequência finita de bits ocorre contígua, infinitamente, freqüentemente na sequência

Os primeiros dígitos da sequência são:

010011010111000100001111 ... (sequência A038219 em OEIS ).

Combinando 8 bits da sequência em um byte, obteremos uma saída ASCII que podemos gerar na tela ou em um arquivo e que contém todas as saídas finitas possíveis . O programa produzirá partes de pi, as letras de "Never never desist you" , algumas belas obras de arte ASCII, seu próprio código-fonte e tudo o mais que você desejar.

Para testar a exatidão, aqui estão os hashes dos primeiros 256 bytes da sequência:

MD5: 5dc589a06e5ca0cd9280a364a456d7a4
SHA-1: 657722ceef206ad22881ceba370d32c0960e267f

Os primeiros 8 bytes da sequência em notação hexadecimal são:

4D 71 0F 65 27 46 0B 7C

Regras:

  • Seu programa deve gerar a sequência Ehrenfeucht-Mycielski (nada mais), combinando 8 bits em um byte / caractere ASCII.

  • O programa mais curto (contagem de caracteres) vence. Subtraia 512 da sua contagem de caracteres se você conseguir gerar a sequência em tempo linear por byte gerado .

schnaader
fonte
O sufixo mais longo em 010, que apareceu anteriormente nessa sequência, é 0, não é? E a aparência anterior mais recente é apenas o segundo 0. E até agora, nada segue o segundo 0, então não há nada em que possamos construir um complemento. Eu não sou um falante nativo de inglês - talvez eu tenha entendido errado. O artigo da wikipedia usa as mesmas palavras, mas possui uma sequência mais longa, então eu o chamaria de "o mais recente ... que tem um seguidor".
usuário desconhecido
8
Esquiva pedante: pi nunca aparecerá - apenas todas as cordas finitas estarão contidas na saída.
Keith Randall
Tenho outra pergunta: uma repetição pode se sobrepor? Por exemplo, em 111, (1 [1) 1]?
usuário desconhecido
@KeithRandall: Eu preferiria uma sequência que é garantida para não conter 'Never never desist you you' e produções do mesmo tipo.
usuário desconhecido
2
Vale a pena mencionar que a mera presença de uma "resposta" incorporada em um local não especificado em uma seqüência infinita não pode ser considerada como "saída" dessa resposta, é claro. Além disso, essa sequência específica é apenas um exemplo de uma sequência disjuntiva - existem infinitas sequências como essa.
res

Respostas:

7

C, -110 caracteres

Esta versão do programa usa o algoritmo de tempo de execução linear para gerar a sequência. Subtrair 512 dos 402 caracteres do programa fornece um total de 110 negativo.

#define C v=calloc(7,8),v->p=p
#define G(F,K)u->F[d[K]]
#define S(F,T)G(f,T)=F,G(t,T)=T,G(n,T)=
struct{int p,f[2],t[2];void*n[2];}r,*u,*v,*w;char*d,c;p,b,h,i,j,k;
main(s){for(;d=++p-s?d:realloc(d,s*=2);){d[i=p]=b;c+=c+b;p%8||putchar(c);
for(u=&r;b=u->p,u->p=p,w=G(n,k=i);S(i,k)v=G(n,k),u=v)for(h=G(f,k),j=G(t,k);j>h;--i,--j)
if(d[i]-d[j]){S(i,k)C;u=v;S(h,j)w;S(0,i)C;b=w->p;goto x;}S(0,i)C;x:b=1-d[b+1];}}

Conforme o problema, o programa é executado em um loop infinito, o que exige muita alocação de memória, e o uso realloc()para manter a sequência contígua pode contribuir para a fragmentação da pilha. Você pode melhorar o uso da memória do programa substituindo calloc(7,8)na primeira linha por calloc(1,sizeof*v). Isso ajudará especialmente em uma máquina de 32 bits, onde 56 é provavelmente muito grande por um fator de dois.

O código é meio ilegível, e não de uma maneira interessante; por isso peço desculpas. Francamente, mesmo a versão não-gasta não é muito clara:

#include <stdio.h>
#include <stdlib.h>

typedef struct branch branch;
typedef struct node node;

struct branch {
    int from, to;
    node *next;
};

struct node {
    int pos;
    branch br[2];
};

static node root = { 0 };

static unsigned char *data = NULL;
static int endpos = 0;
static int size = 1;

static node *mknode(void)
{
    node *n;

    n = calloc(1, sizeof *n);
    n->pos = endpos;
    return n;
}

static branch *getbranch(node *n, int p)
{
    return &n->br[data[p]];
}

static void setbranch(node *n, int from, int to, node *next)
{
    n->br[data[to]].next = next;
    n->br[data[to]].from = from;
    n->br[data[to]].to = to;
}

int main(void)
{
    node *u, *v, *w;
    int follower, from, i, i0, j;
    int out, b;

    out = b = 0;
    for (;;) {
        ++endpos;
        if (endpos == size) {
            size *= 2;
            data = realloc(data, size);
        }
        data[endpos] = b;
        out = (out << 1) | b;
        if (endpos % 8 == 0) {
            putchar(out);
            out = 0;
        }

        i = endpos;
        u = &root;
        for (;;) {
            follower = u->pos + 1;
            u->pos = endpos;
            w = getbranch(u, i)->next;
            if (!w)
                break;
            i0 = i;
            from = getbranch(u, i0)->from;
            for (j = getbranch(u, i0)->to ; j > from ; --j) {
                if (data[i] != data[j]) {
                    /* divide branch */
                    v = mknode();
                    setbranch(u, i, i0, v);
                    u = v;
                    setbranch(u, from, j, w);
                    setbranch(u, 0, i, mknode());
                    follower = w->pos + 1;
                    goto bitfound;
                }
                --i;
            }
            v = getbranch(u, i0)->next;
            setbranch(u, i, i0, v);
            u = v;
        }
        /* extend branch */
        setbranch(u, 0, i, mknode());

      bitfound:
        b = 1 - data[follower];
    }
}

(O código não destruído acima é baseado no código escrito por Grzegorz Herman e Michael Soltys, conforme referenciado na descrição do problema e na página inicial de Soltys .)

Agradecemos a @schnaader e @res por reportar um erro na versão inicial.

caixa de pão
fonte
Agradável! Era isso que eu esperava com o bônus -512.
schnaader
Alguma idéia de por que isso causa falhas no sistema? Todas as mallocversões modificadas , não golfadas e modificadas param a saída após cerca de 10.000 bytes e continuam alocando memória , causando prog > out.datuma falha instantânea com apenas ~ 700 KB de uso de memória. Se eu inserir printf("\n%i\n", size);depois realloc, a maior saída é 4. Sistema: Windows 7 Prof. 64 bits, 4 GB de RAM, GCC 4.6.1
schnaader
(+1) Acho que, com o Ubuntu12.04 / gcc, os dois programas compilam e produzem a saída correta ... Com o Win7 / mingw / gcc, os dois programas compilam, mas produzem falhas de segmentação ... Com o Win7 / lcc, o A versão sem golf funciona, mas a versão com golf produz falhas de segmentação.
res
1
Isso soa como o uso de dados não inicializados para mim. Com certeza - não tenho acesso a uma máquina Windows, mas o valgrind mostra o problema. Parece que também reproduzi esse bug da implementação de referência original. Felizmente, é uma solução fácil; obrigado por denunciá-lo!
breadbox
Ótimo, funciona como um encanto agora.
amigos estão dizendo sobre schnaader
6

Ruby, 109 104 101 94 caracteres

s=?0
loop{s=(s[/(.*).*\1/][/.#{$1}/]<?1??1:?0)+s
s.size&7<1&&$><<[s.reverse.to_i(2)].pack(?C)}

Implementação em Ruby usando expressões regulares para pesquisa de sufixos. Como leva muito tempo até ficar sem memória, o programa deve ser encerrado pelo usuário.

Edit: Acabei de notar que é o suficiente para começar com a sequência 0.

Edit 2: A proposta de res salva 2 caracteres, alguns outros porque não precisamos cortar um único byte antes pack.

Howard
fonte
Usar s=(s[/(.*).*\1/][/.#{$1}/]<?1??1:?0)+ssalvará outros dois caracteres.
res
@res Isso funciona mesmo. Obrigado.
Howard
Você pode se livrar dos parênteses ?C?
Fund Monica's Lawsuit
4

Perl, 95 caracteres

Na verdade, eu tinha uma versão meio decente disso no começo. Então, enquanto jogava golfe, cada versão ficava mais lenta. Cada vez mais lento.

$|=$_="010";
y///c%8||print pack"B*",/(.{8})$/while/(.+)$(?(?{m|.*$^N(.)|})(?{$_.=1-$^N})|(?!))/

Os três primeiros caracteres ( $|=) não são necessários, falando estritamente ... mas sem isso, você normalmente teria que esperar o script terminar de gerar 4096 bytes completos antes de ver qualquer saída. E isso levaria horas. Talvez séculos; Não tenho certeza. Eu mencionei que o desempenho deste programa se deteriora com o tempo? Então, por causa disso, eu me senti compelido a incluí-los na contagem.

Por outro lado, esse script tem uma das expressões mais feias que eu já criei, então acho que tenho orgulho disso.

caixa de pão
fonte
1
Não se preocupe com o desempenho, o algoritmo é O (N ^ 3) sem otimizações. Meu simples programa Delphi que escrevi levou cerca de 30 segundos para 256 bytes, mas cerca de uma hora para 1024 bytes; portanto, assumi que 4096 bytes demorariam um ou vários dias. Claro, RegEx e otimizações espaciais têm o potencial para torná-lo pior :)
schnaader
Meu script Perl inicial levou 10 segundos para 256 bytes. Esta versão leva 90 segundos. (Nem parece ser uma desaceleração linear.) #
breadbox