Solveur de golf universel (pliant les règles)

Le golf de code implique toujours des réponses qui détournent les règles plus ou moins en brisant les contraintes que les challengers tenaient pour acquises ou tout simplement n'ont pas pensé et n'ont pas énuméré dans les règles. L'une de ces lacunes intéressantes est la possibilité de produire plus que ce que le défi demande pour obtenir un meilleur résultat.

En poussant cela à l'extrême, nous pouvons écrire un solveur de golf à code universel qui imprime la sortie souhaitée - si vous ne vous souciez pas que cela puisse prendre des années et génère beaucoup d'autres choses avant et après.

Tout ce dont nous avons besoin pour produire est une séquence qui est garantie de contenir toutes les sous-séquences possibles. Pour ce code golf, ce sera la séquence Ehrenfeucht-Mycielski :

La séquence commence par les trois bits 010; chaque chiffre successif est formé en trouvant le suffixe le plus long de la séquence qui apparaît également plus tôt dans la séquence, et en complétant le bit suivant l'apparence antérieure la plus récente de ce suffixe.

Chaque sous-séquence finie de bits se produit de manière contiguë, infiniment souvent dans la séquence

Les premiers chiffres de la séquence sont:

010011010111000100001111 ... (séquence A038219 dans OEIS ).

En combinant 8 bits de la séquence à un octet, nous obtiendrons une sortie ASCII que nous pourrons sortir à l'écran ou dans un fichier et qui contient toutes les sorties finies possibles . Le programme affichera des parties de pi, les paroles de «Never gonna give you up» , de l'art ASCII sympa, son propre code source et tout le reste que vous voudriez qu'il sorte.

Pour tester l'exactitude, voici les hachages pour les 256 premiers octets de la séquence:

MD5: 5dc589a06e5ca0cd9280a364a456d7a4
SHA-1: 657722ceef206ad22881ceba370d32c0960e267f

Les 8 premiers octets de la séquence en notation hexadécimale sont:

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

Règles:

• Votre programme doit produire la séquence Ehrenfeucht-Mycielski (rien d'autre), combinant 8 bits à un caractère octet / ASCII.

• Le programme le plus court (nombre de caractères) gagne. Soustrayez 512 de votre nombre de caractères si vous parvenez à générer la séquence en temps linéaire par octet généré .

C, –110 caractères

Cette version du programme utilise l'algorithme d'exécution linéaire pour générer la séquence. La soustraction de 512 des 402 caractères du programme donne un total de 110 négatifs.

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

Selon le problème, le programme s'exécute dans une boucle infinie, ce qui nécessite beaucoup d'allocation de mémoire, et l'utilisation realloc()pour conserver la séquence contiguë peut contribuer à la fragmentation du tas. Vous pouvez améliorer l'utilisation de la mémoire du programme en remplaçant calloc(7,8)sur la première ligne par calloc(1,sizeof*v). Cela aidera particulièrement sur une machine 32 bits, où 56 est probablement trop grand par un facteur de deux.

Le code est un peu illisible, et pas d'une manière intéressante; je m'en excuse. Franchement, même la version non golfée n'est pas très claire:

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

(Le code non golfé ci-dessus est basé sur le code écrit par Grzegorz Herman et Michael Soltys, tel que référencé dans la description du problème, et à partir de la page d'accueil de Soltys .)

Merci à @schnaader et @res pour avoir signalé un bug dans la version initiale.

Ruby, 109 104 101 94 caractères

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

Implémentation dans Ruby à l'aide d'expressions régulières pour la recherche de suffixes. Puisqu'il faut un temps assez long jusqu'à ce que la mémoire soit insuffisante, le programme doit être interrompu par l'utilisateur.

Edit: je viens de remarquer qu'il suffit de commencer par la séquence0 .

Edit 2: La proposition de res enregistre 2 caractères, certains autres car nous n'avons pas besoin de couper un seul octet avant pack.

Perl, 95 caractères

J'avais en fait une version à moitié décente au début. Alors que je jouais au golf, chaque version devenait plus lente. De plus en plus lent.

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

Les trois premiers caractères ( $|=) ne sont pas nécessaires à proprement parler ... mais sans cela, vous devez généralement attendre que le script ait fini de générer 4096 octets complets avant de voir la sortie. Et cela prendrait des heures. Peut-être des siècles; Je ne suis pas sûr. Ai-je mentionné que les performances de ce programme se détériorent au fil du temps? Donc, à cause de cela, je me suis senti obligé de les inclure dans le décompte.

D'un autre côté, ce script possède l'un des regex les plus laids que j'ai jamais créés, donc je pense que j'en suis fier.