Uniwersalny (oparty na regułach) solver Code Golf

14

Code golf zawsze zawiera odpowiedzi, które mniej lub bardziej naginają reguły, przełamując ograniczenia, które pretendenci wzięli za pewnik lub po prostu o tym nie pomyśleli i nie wymienili ich w przepisach. Jedną z tych interesujących luk jest możliwość wyjścia więcej niż wymaga wyzwanie, aby uzyskać lepszy wynik.

Biorąc to do końca, możemy napisać uniwersalny koder solvera do golfa, który drukuje pożądane dane wyjściowe - jeśli nie przejmujesz się, że może to potrwać wieki i wyświetla wiele innych rzeczy przed i po nim.

Wszystko, co musimy wygenerować, to sekwencja, która z pewnością zawiera wszystkie możliwe podsekwencje. Dla tego kodu golfowego będzie to sekwencja Ehrenfeucht-Mycielski :

Sekwencja zaczyna się od trzech bitów 010; każda kolejna cyfra jest tworzona przez znalezienie najdłuższego sufiksu sekwencji, który również pojawia się wcześniej w sekwencji, i uzupełnienie bitu po ostatnim wcześniejszym pojawieniu się tego sufiksu.

Każda skończona podsekwencja bitów zachodzi w sposób ciągły, nieskończenie często w obrębie sekwencji

Pierwsze kilka cyfr sekwencji to:

010011010111000100001111 ... (sekwencja A038219 w OEIS ).

Łącząc 8 bitów sekwencji w bajt, otrzymamy wyjście ASCII, które możemy wyprowadzić na ekran lub do pliku i które zawiera każde możliwe skończone wyjście . Program wyświetli fragmenty pi, teksty „Never will give you you” , jakąś fajną grafikę ASCII, własny kod źródłowy i wszystko inne, co chcesz, aby powstało.

Do testowania poprawności, oto skróty dla pierwszych 256 bajtów sekwencji:

MD5: 5dc589a06e5ca0cd9280a364a456d7a4
SHA-1: 657722ceef206ad22881ceba370d32c0960e267f

Pierwsze 8 bajtów sekwencji w zapisie szesnastkowym to:

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

Zasady:

schnaader
źródło
Najdłuższy przyrostek w 010, który pojawił się wcześniej w tej sekwencji, to 0, prawda? A najnowszy wcześniejszy występ to tylko drugie 0. I do tej pory nic nie następuje po drugim 0, więc nie ma nic, na czym moglibyśmy zbudować uzupełnienie. Nie jestem native speakerem angielskiego - może po prostu źle to zrozumiałem. Artykuł w Wikipedii używa tych samych słów, ale ma dłuższą sekwencję, więc nazwałbym ją „najnowszą… która ma obserwującego”.
użytkownik nieznany
8
Pedantyczny quibble: pi nigdy się nie pojawi - tylko każdy skończony ciąg znaków będzie zawarty w wyjściu.
Keith Randall
Mam inne pytanie: czy powtórzenie może się pokrywać? Na przykład w 111, (1 [1) 1]?
użytkownik nieznany
@KeithRandall: Wolałbym sekwencję, która z pewnością nie zawiera „Nigdy się nie poddam” i podobnych produkcji.
użytkownik nieznany
2
Warto wspomnieć, że sama obecność „odpowiedzi” osadzonej w nieokreślonym miejscu w nieskończonym ciągu nie może być oczywiście uważana za „wysyłanie” tej odpowiedzi. Ponadto ta konkretna sekwencja jest tylko jednym przykładem sekwencji rozłącznej - istnieje nieskończenie wiele takich sekwencji.
res

Odpowiedzi:

7

C, –110 znaków

Ta wersja programu wykorzystuje algorytm liniowego środowiska wykonawczego do wygenerowania sekwencji. Odejmowanie 512 z 402 znaków w programie daje w sumie ujemną 110.

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

Zgodnie z problemem program działa w nieskończonej pętli, co wymaga dużej alokacji pamięci, a użycie realloc()do zachowania ciągłości sekwencji może przyczynić się do fragmentacji sterty. Możesz poprawić wykorzystanie pamięci programu, zastępując calloc(7,8)w pierwszym wierszu znakiem calloc(1,sizeof*v). Pomoże to zwłaszcza na 32-bitowej maszynie, gdzie 56 jest prawdopodobnie zbyt duże dwa razy.

Kod jest w pewnym sensie nieczytelny i nie w interesujący sposób; za to przepraszam. Szczerze mówiąc, nawet wersja bez golfa nie jest strasznie jasna:

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

(Niegolfowany kod powyżej opiera się na kodzie napisanym przez Grzegorza Hermana i Michaela Soltysa, o których mowa w opisie problemu oraz ze strony głównej Soltysa ).

Dzięki @schnaader i @res za zgłoszenie błędu w początkowej wersji.

chlebak
źródło
Ładny! Właśnie tego oczekiwałem dzięki premii -512.
schnaader
Masz pojęcie, dlaczego powoduje to awarie systemu? Wszystkie mallocwersje z golfem, bez golfa i zmodyfikowane zatrzymują wyjście po około 10000 bajtach i kontynuują przydzielanie pamięci, prog > out.datnatychmiast powodują awarię przy zużyciu pamięci tylko ~ 700 KB. Jeśli wstawię printf("\n%i\n", size);po realloc, największą wartością wyjściową jest 4. System: Windows 7 Prof. 64-bit, 4 GB pamięci RAM, GCC 4.6.1
schnaader
(+1) Uważam, że w Ubuntu12.04 / gcc oba programy kompilują się i generują prawidłowe dane wyjściowe ... W Win7 / mingw / gcc oba programy kompilują się, ale generują błędy segmentacji ... W Win7 / lcc wersja bez golfa działa, ale wersja z golfem powoduje błędy segmentacji.
res
1
Dla mnie to brzmi jak wykorzystanie niezainicjowanych danych. Rzeczywiście - nie mam dostępu do komputera z systemem Windows, ale valgrind pokazuje problem. Wygląda na to, że odtworzyłem ten błąd również z oryginalnej implementacji referencyjnej. Na szczęście jest to łatwa poprawka; dzięki za zgłoszenie!
breadbox
Świetnie, działa teraz jak urok.
schnaader
6

Ruby, 109 104 101 94 znaków

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

Implementacja w Ruby przy użyciu wyrażeń regularnych do wyszukiwania sufiksów. Ponieważ zabranie pamięci zajmuje dużo czasu, program musi zostać zakończony przez użytkownika.

Edytować: Właśnie zauważyłem, że wystarczy zacząć od sekwencji 0.

Edycja 2: Propozycja res zapisuje 2 znaki, niektóre inne, ponieważ nie musimy wcześniej wycinać ani jednego bajtu pack.

Howard
źródło
Użycie s=(s[/(.*).*\1/][/.#{$1}/]<?1??1:?0)+sspowoduje zapisanie kolejnych dwóch znaków.
res
@res To naprawdę działa. Dziękuję Ci.
Howard
Czy możesz pozbyć się nawiasów ?C?
Pozew Fund Moniki z
4

Perl, 95 znaków

Na początku miałem w połowie przyzwoitą wersję tego. Potem, gdy grałem w golfa, każda wersja stała się wolniejsza. Coraz wolniej.

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

Pierwsze trzy znaki ( $|=) nie są konieczne, ściśle mówiąc ... ale bez tego zwykle trzeba by czekać, aż skrypt zakończy generowanie pełnych 4096 bajtów, zanim zobaczysz wynik. A to zajmie godziny. Może stulecia; Nie jestem pewny. Czy wspomniałem, że wydajność tego programu pogarsza się z czasem? Z tego powodu poczułem się zmuszony do włączenia ich do hrabstwa.

Z drugiej strony, ten skrypt ma jeden z najbrzydszych wyrażeń regularnych, jakie kiedykolwiek stworzyłem, więc myślę, że jestem z niego dumny.

chlebak
źródło
1
Nie martw się o wydajność, algorytm to O (N ^ 3) bez optymalizacji. Mój prosty program Delphi, który napisałem, zajął około 30 sekund na 256 bajtów, ale około godziny na 1024 bajty, więc zakładam, że 4096 bajtów zajmie jeden lub kilka dni. Oczywiście, RegEx i optymalizacje przestrzeni mogą go pogorszyć :)
schnaader
Mój początkowy skrypt Perla zajął 10 sekund na 256 bajtów. Ta wersja zajmuje 90 sekund. (Nie wydaje się też, by było to spowolnienie liniowe.)
breadbox