28
\$\begingroup\$

Similar to other quine puzzles (more specifically, this one), write a program that produces the source for itself.

Here's the new twist: The code produced should NOT be identical to the source. Rather, it should output a different program that will create the first.

The challenge linked to above achieved that by jumping between two languages. I'm thinking this one would be done in just one language, but the two (or more) versions of the source should be significantly different (see rules below). With this constraint, single character answers would be disallowed, thus requiring a little more thought be put into a final submission.


RULES

  1. Your code must be produced in just one language. (Multiple submissions, one for each language is perfectly acceptable.)
  2. Your different code versions must be syntactically distinct. In other words, if you were to draw out an abstract syntax tree for your code, there should be at least one node different.
    • Supplying an AST will not be necessary, but if you feel inclined to provide one for each of your programs, it would help in judging.
  3. You may produce as many iterations as you wish, as long as they all remain syntactically distinct. (More will help your score, see below.)

SCORING

Your final score will be the mean length of all your programs, divided by the number of programs.

Example 1:

A (source for B) = 50 characters
B (source for A) = 75 characters
Final Score = 31.25

Example 2:

A (source for B) = 50 characters
B (source for C) = 75 characters
C (source for A) = 100 characters
Final Score = 25

\$\endgroup\$
6
  • 20
    \$\begingroup\$ I meta quine once. \$\endgroup\$
    – mellamokb
    Apr 13, 2012 at 13:32
  • 1
    \$\begingroup\$ @mellamokb har har ;-) \$\endgroup\$
    – Gaffi
    Apr 13, 2012 at 13:33
  • \$\begingroup\$ This is actually just a more general version of this quine challenge, and the answers given there will win here, too. \$\endgroup\$ Apr 13, 2012 at 17:02
  • \$\begingroup\$ @leftaroundabout, the requirement for syntactic differences invalidates a 'rotating quine', so this is not more general. \$\endgroup\$
    – boothby
    Apr 13, 2012 at 18:02
  • 2
    \$\begingroup\$ Never meta quine I didn't like. \$\endgroup\$ Aug 14, 2014 at 19:51

6 Answers 6

38
\$\begingroup\$

Python, 0 (limit of (68+3 n )/(16n))

If two abstract syntax trees are different if they have different constants,

r='r=%r;n=(0x%XL+1)%%0x10...0L;print r%%(r,n)';n=(0xF...FL+1)%0x10...0L;print r%(r,n)

there are 16n programs of length at most 68+3n, giving asymptotic score of 0.

If you want programs with variable structure, we can implement a binary adder on n bits. Here, there are 2n programs of length O( n2). Goes in a cycle due to dropped carry bit.

s="""
print 's='+'"'+'"'+'"'+s+'"'+'"'+'"'
n=lambda m:reduce(lambda (s,c),y:(s+(c^y,),c&y),m,((),1))[0]
print s[:112]
t=n(t)
print "t=(%s,)+(0,)*%s"%(t[0],len(t)-1)
for i in range(len(t)-1):
    print i*' '+'for i in range(2):'
    print ' '+i*' '+['pass','t=n(t)'][t[i+1]]
print s[113:-1]
"""

print 's='+'"'+'"'+'"'+s+'"'+'"'+'"'
n=lambda m:reduce(lambda (s,c),y:(s+(c^y,),c&y),m,((),1))[0]
print s[:112]
t=(0,)+(0,)*10
for i in range(2):
 t=n(t)
 for i in range(2):
  t=n(t)
  for i in range(2):
   t=n(t)
   for i in range(2):
    t=n(t)
    for i in range(2):
     pass
     for i in range(2):
      t=n(t)
      for i in range(2):
       pass
       for i in range(2):
        pass
        for i in range(2):
         pass
         for i in range(2):
          t=n(t)
t=n(t)
print "t=(%s,)+(0,)*%s"%(t[0],len(t)-1)
for i in range(len(t)-1):
    print i*' '+'for i in range(2):'
    print ' '+i*' '+['pass','t=n(t)'][t[i+1]]
print s[113:-1]
\$\endgroup\$
5
  • \$\begingroup\$ Might I be confused? It looks like the output is identical to the source (not the objective of this challenge)? \$\endgroup\$
    – Gaffi
    Apr 15, 2012 at 18:10
  • \$\begingroup\$ Look in the nested block. pass will change to t=n(t) and back, in all 2^n combinations. \$\endgroup\$
    – boothby
    Apr 16, 2012 at 0:04
  • \$\begingroup\$ I do see that now. You confused me with all the repetition! \$\endgroup\$
    – Gaffi
    Apr 16, 2012 at 2:07
  • 24
    \$\begingroup\$ for some reason, I like very long golf solutions with tiny scores. \$\endgroup\$
    – boothby
    Apr 20, 2012 at 4:01
  • \$\begingroup\$ Wow, you completely owned that! Very nice. \$\endgroup\$
    – Claudiu
    Mar 8, 2014 at 5:08
6
\$\begingroup\$

C++, score of 0.734194

The following source code prints a meta quine of order 999 to the console (explanation below):

#define X 1*(1+1)
#include<iostream>
#include<vector>
#define Q(S)auto q=#S;S
Q( \
  main() \
  { \
      using namespace std; \
      cout<<"#define X 1"; \
      int x=X==2?1000:X-1; \
      vector<int> factors; \
      for ( int p = 2; p <= x; ++p) \
      { \
        while ( x % p == 0 ) \
        { \
          factors.push_back( p ); \
          x /= p; \
        } \
      } \
      for ( int factor : factors ) \
      { \
        cout<<"*(1"; \
        for ( int i=1;i<factor;++i) \
          cout<<"+1"; \
        cout<<")"; \
      } \
      cout<<"\n#include<iostream>\n#include<vector>\n#define Q(S)auto q=#S;S\nQ("<<q<<")"; \
  })

The only line that changes is the first line. The value of X will be 1000, 999, 998, ..., 3, 2 and then it will start again. However, in order to get different syntax trees every time, X is represented in terms of its prime factorization, where every prime is written as a sum of 1s. The ASTs are different, because the prime factorization of integers is different for every value.

The program will print itself, except that the first line is changed and the backslashes, line breaks and indentations that are within Q(...) will be removed.

The following program calculates the score of my answer:

#include <iostream>

const int n = 1000;

int getProgramLength( int n )
{
  int sum = 442;
  for ( int p = 2; p*p <= n; ++p )
  {
    while ( n % p == 0 )
    {
      sum += 2 * ( 1 + p );
      n /= p;
    }
  }
  if ( n > 1 )
    sum += 2 * ( 1 + n );
  return sum;
}

int main()
{
  int sum = 0;
  for ( int i = 2; i <= n; ++i )
    sum += getProgramLength( i );
  std::cout << (double)sum/(n-1)/(n-1) << '\n';
}

It printed 0.734194 to the console. Obviously, 1000 can be replaced by larger integers and the score will approach 0 as its limit. The mathematical proof involves Riemann's Zeta function is somewhat convoluted. I leave it as an exercise to the reader. ;)

\$\endgroup\$
4
\$\begingroup\$

Perl, score of 110.25

I have to admit, I'm not very good with quines. I'm 100% certain that there is room for improvement. The solution is based off of the same principle of the Element solution below.

The first program is 264 characters.

$s='$a=chr(39);print"\$s=$a$s$a;";$s=reverse$s;for(1..87){chop$s}$s=reverse$s;print$s;$f++;if($f==0){$a=chr(39);print"\$s=$a$s$a;$s"}';$a=chr(39);print"\$s=$a$s$a;";$s=reverse$s;for(1..87){chop$s}$s=reverse$s;print$s;$f++;if($f==0){$a=chr(39);print"\$s=$a$s$a;$s"}

The second program is 177 characters.

$s='$a=chr(39);print"\$s=$a$s$a;";$s=reverse$s;for(1..87){chop$s}$s=reverse$s;print$s;$f++;if($f==0){$a=chr(39);print"\$s=$a$s$a;$s"}';if($f==0){$a=chr(39);print"\$s=$a$s$a;$s"}

I'm working on the AST for this entry (and the Element entry).


Element, score of 47.25

The first program is 105 characters.

\ \3\:\$\'\[\\\\\`\(\`\]\#\2\1\'\[\(\#\]\`\ \3\:\$\'\[\\\\\`\(\`\]\#\` 3:$'[\\`(`]#21'[(#]` 3:$'[\\`(`]#`

The second program is 84 characters.

\ \3\:\$\'\[\\\\\`\(\`\]\#\2\1\'\[\(\#\]\`\ \3\:\$\'\[\\\\\`\(\`\]\#\` 3:$'[\\`(`]#`

I'm sure that there is a lot of room for improvement.

In the first program there is one string (in which every character is escaped, despite a lot of redundancy) followed by executable parts A and B. Part A does several things: prints the string and escapes out of every character, prints the last half of the string (which is the source for part B), and then prevents the part B that follows it from doing anything.

The second program is the same string followed by part B. Part B is based off of a simple quine; it prints a string preceded by an escaped version of it. This means it prints the string, and both parts A and B.

\$\endgroup\$
2
  • \$\begingroup\$ I think this definitively, beyond any doubt, proves the validity of Element as a programming language. It is so easy to use that I, so inexperienced that I have only managed to write one complete interpreter for Element, have been able to answer this question before any other person on this entire planet of 7,000,000,000 people. Element's "one character, one function, all the time" paradigm means that all code is completely unambiguous. The language is versatile: except for []{}, any command can be placed anywhere in the entire program without causing a syntax error. It is perfect. \$\endgroup\$
    – PhiNotPi
    Apr 14, 2012 at 0:08
  • 4
    \$\begingroup\$ A bit biased, are we? ;-) \$\endgroup\$
    – Gaffi
    Apr 15, 2012 at 18:07
3
\$\begingroup\$

VBA: (251+216)/2/2 = 116.75

251

Sub a()
r=vbCrLf:c="If b.Lines(4, 4) = c Then"&r &"b.InsertLines 8, d"&r &"b.DeleteLines 4, 4"&r &"End If":d="b.InsertLines 6, c"&r &"b.DeleteLines 4, 2"
Set b=Modules("Q")
If b.Lines(4, 4) = c Then
b.InsertLines 8, d
b.DeleteLines 4, 4
End If
End Sub

216

Sub a()
r=vbCrLf:c="If b.Lines(4, 4) = c Then"&r &"b.InsertLines 8, d"&r &"b.DeleteLines 4, 4"&r &"End If":d="b.InsertLines 6, c"&r &"b.DeleteLines 4, 2"
Set b=Modules("Q")
b.InsertLines 6,c
b.DeleteLines 4,2
End Sub

This is run in MSAccess to make use of the Module object. The module is named "Q" for golfing. The difference in syntax comes from the If ... Then missing from the shorter version.

\$\endgroup\$
1
  • \$\begingroup\$ you can most likely get away with changing vbCrLF to vbCr \$\endgroup\$ May 31, 2017 at 16:34
2
\$\begingroup\$

JavaScript, 84.5 64 61

Two programs, both length 169 128 122.

(function c(){alert(/*
2/*/1/**/);return ('('+c+')()').replace(/\/([/\*])/,function(m,a){return a=='*'?'/\/':'/\*'});
})()

Before I golfed it, for your viewing pleasure:

(function c() {
    var r = /\/([/\*])/;
    var f = function(m, a) { return a === '*' ? '/\/' : '/\*' };
    var p = '(' + c + ')();';
    p = p.replace(r, f);
    /* This is just a comment!
    console.log('Quine, part two!'); /*/
    console.log('Quine, part one!'); /**/
    return p;
})();

Returns the new program and outputs the current part! I could probably make it shorter without the function regex, but... I don't want to.

\$\endgroup\$
1
  • \$\begingroup\$ No, they're syntatically distinct. Once you add the newlines, that is. \$\endgroup\$
    – Ry-
    Apr 16, 2012 at 2:44
2
\$\begingroup\$

J - (24+30)/2 / 2 = 13.5 pts

Note that strings in J are not the backslash-escaped, but quote-escaped à la Pascal: 'I can''t breathe!'.

30$(,5#{.)'''30$(,5#{.)'         NB. program 1, 24 char
'30$(,5#{.)''''''30$(,5#{.)'''   NB. program 2, 30 char

Program 1 has AST noun verb hook noun and program 2 has AST noun. Program 2 is a quoted version of program 1, which will just return program 1 when run, so this method can't be extended to three copies that easily :P

Program 1 operates by taking a copy of the code portion of the source, with a quote appended at the front, and adding five of those quotes to the end ((,5#{.)). Then, it cyclically takes 30 characters from this 16-character string, which gives exactly Program 2 as a result.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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