14
\$\begingroup\$

Code golf always involves some answers that bend the rules more or less by breaking constraints that the challengers took for granted or just haven't thought about and didn't list in the rules. One of these interesting loopholes is the possibility to output more than the challenge asks for to get a better result.

Taking this to extremes, we can write an universal code golf solver that prints the desired output — if you don't care that it might take ages and outputs lots of other stuff before and after it.

All we need to output is a sequence that is guaranteed to contain every possible subsequence. For this code golf, this will be the Ehrenfeucht-Mycielski sequence:

The sequence starts with the three bits 010; each successive digit is formed by finding the longest suffix of the sequence that also appears earlier within the sequence, and complementing the bit following the most recent earlier appearance of that suffix.

Every finite subsequence of bits occurs contiguously, infinitely often within the sequence

The first few digits of the sequence are:

010011010111000100001111... (sequence A038219 in OEIS).

Combining 8 bits of the sequence to a byte, we'll get ASCII output that we can output to the screen or to a file and that contains every possible finite output. The program will output parts of pi, the lyrics of “Never gonna give you up”, some nice ASCII art, its own source code, and everything else you could want it to output.

For testing correctness, here are hashes for the first 256 bytes of the sequence:

MD5: 5dc589a06e5ca0cd9280a364a456d7a4
SHA-1: 657722ceef206ad22881ceba370d32c0960e267f

The first 8 bytes of the sequence in hexadecimal notation are:

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

Rules:

  • Your program must output the Ehrenfeucht-Mycielski sequence (nothing else), combining 8 bits to a byte/ASCII character.

  • Shortest program (character count) wins. Subtract 512 from your character count if you manage to generate the sequence in linear time per generated byte.

\$\endgroup\$
  • \$\begingroup\$ The longest suffix in 010 which appeared earlier in that sequence is 0, isn't it? And the most recent earlier appearance is just the second 0. And until now, nothing follows the second 0, so there is nothing we can build a complement on. I'm not a native english speaker - maybe I just got it wrong. The wikipedia article uses the same words, but has a longer sequence so I would name it "the most recent ... which has a follower". \$\endgroup\$ – user unknown Jun 9 '12 at 2:06
  • 8
    \$\begingroup\$ Pedantic quibble: pi will never appear - only every finite string will be contained in the output. \$\endgroup\$ – Keith Randall Jun 9 '12 at 2:55
  • \$\begingroup\$ I have another question: May a repetition overlap? For example in 111, (1[1)1]? \$\endgroup\$ – user unknown Jun 9 '12 at 3:01
  • \$\begingroup\$ @KeithRandall: I would prefer a sequence which is guaranteed not to contain 'Never gonna give you up' and productions of similar kind. \$\endgroup\$ – user unknown Jun 9 '12 at 3:04
  • 2
    \$\begingroup\$ It might be worth mentioning that the mere presence of an "answer" embedded at an unspecified location in an infinite string cannot be regarded as "outputting" that answer, of course. Also, this particular sequence is just one example of a disjunctive sequence -- there are infinitely many sequences like this. \$\endgroup\$ – r.e.s. Jun 9 '12 at 14:16
7
\$\begingroup\$

C, –110 chars

This version of the program uses the linear-runtime algorithm to generate the sequence. Subtracting 512 from the 402 chars in the program gives a total of negative 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];}}

As per the problem, the program runs in an infinite loop, which necessitates lots of memory allocation, and using realloc() to keep the sequence contiguous can contribute to heap fragmentation. You can improve the program's memory usage by replacing calloc(7,8) on the first line with calloc(1,sizeof*v). This will help especially on a 32-bit machine, where 56 is likely too large by a factor of two.

The code is kind of unreadable, and not in an interesting way; for that I apologize. Frankly, even the ungolfed version isn't terribly clear:

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

(The ungolfed code above is based on the code written by Grzegorz Herman and Michael Soltys, as referenced in the problem description, and from Soltys' home page.)

Thanks to @schnaader and @r.e.s. for reporting a bug in the initial version.

\$\endgroup\$
  • \$\begingroup\$ Nice! That's what I hoped for with the -512 bonus. \$\endgroup\$ – schnaader Jun 13 '12 at 20:59
  • \$\begingroup\$ Any idea why this causes crashes on by system? All of the golfed, ungolfed and malloc modified versions stop output after about 10000 bytes and keep on allocating memory, prog > out.dat gives an instant crash with only ~700 KB memory usage. If I insert printf("\n%i\n", size); after realloc, the biggest output is 4. System: Windows 7 Prof. 64-Bit, 4 GB RAM, GCC 4.6.1 \$\endgroup\$ – schnaader Jun 13 '12 at 21:02
  • \$\begingroup\$ (+1) I find that with Ubuntu12.04/gcc, both of your programs compile and produce the correct output ... With Win7/mingw/gcc, both programs compile but produce segmentation faults ... With Win7/lcc, the ungolfed version works, but the golfed version produces segmentation faults. \$\endgroup\$ – r.e.s. Jun 13 '12 at 23:09
  • 1
    \$\begingroup\$ That sounds like use of uninitialized data to me. Sure enough -- I don't have access to a Windows machine, but valgrind shows the problem. Looks like I reproduced this bug from the original reference implementation, too. Fortunately it's an easy fix; thanks for reporting it! \$\endgroup\$ – breadbox Jun 14 '12 at 4:47
  • \$\begingroup\$ Great, works like a charm now. \$\endgroup\$ – schnaader Jun 14 '12 at 8:59
6
\$\begingroup\$

Ruby, 109 104 101 94 characters

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

Implementation in Ruby using regular expressions for suffix search. Since it takes quite a long time until out-of-memory the program has to be terminated by the user.

Edit: I just noticed that it is enough to start with the sequence 0.

Edit 2: The proposal of r.e.s. saves 2 characters, some others because we do not have to cut out a single byte before pack.

\$\endgroup\$
  • \$\begingroup\$ Using s=(s[/(.*).*\1/][/.#{$1}/]<?1??1:?0)+s will save another two characters. \$\endgroup\$ – r.e.s. Jun 10 '12 at 23:51
  • \$\begingroup\$ @r.e.s. This works indeed. Thank you. \$\endgroup\$ – Howard Jun 11 '12 at 5:10
  • \$\begingroup\$ Can you get rid of the parentheses around ?C? \$\endgroup\$ – Nic Hartley Mar 11 '16 at 3:04
4
\$\begingroup\$

Perl, 95 chars

I actually had a halfway decent version of this at first. Then as I golfed, each version got slower. Increasingly slower.

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

The first three characters ($|=) aren't necessary, strictly speaking ... but without that there, you'd typically have to wait for the script to finish generating a full 4096 bytes before you'd see any of the output. And that would take hours. Maybe centuries; I'm not sure. Did I mention that this program's performance kind of deteriorates over time? So because of that I kind of felt compelled to include them in the count.

On the other hand, this script has one of the ugliest regexes I've ever created, so I think I'm proud of it.

\$\endgroup\$
  • 1
    \$\begingroup\$ Don't worry about the performance, the algorithm is O(N^3) without optimizations. My simple Delphi program I wrote took about 30 seconds for 256 bytes,but about an hour for 1024 bytes, so I'd assume 4096 bytes to take one or several days. Of course, RegEx and space optimizations have the potential to make it worse :) \$\endgroup\$ – schnaader Jun 9 '12 at 13:47
  • \$\begingroup\$ My initial Perl script took 10 seconds for 256 bytes. This version takes 90 seconds. (Nor does it appear to be a linear slowdown.) \$\endgroup\$ – breadbox Jun 9 '12 at 18:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.