Mutually Exclusive Quines

><>, Score: 41+41 = 82

Edit: both contained a 3. Fixed

'd3*}>a!o-!<<8:5@lI55>@z:5ll55>>q:>|q::|,

and

"r00gr40g44++bb+0p64++?b6+0.22#eW4s )Z

Try it online! (swap the lines to get the other output) With verification this time!

><> is an especially hard language to use here, as there is only one way to output characters, the command o. Fortunately, we can use the put command to place an o in the source code during execution, like in my Programming in a Pristine World answer.

This one took a lot of trial and error. I started off with the two mutually exclusive programs:

'd3*}>N!o-!<<data

and

"r00gr40g8+X0pN+?Y0.data

Each one transforms itself and its data by N, the first one subtracting and the second adding. It then outputs this in reverse. The point is that the data after each program is the other program in reverse, shifted by N. (X is the cell number where the program needs to put the o and Y is the cell where the pointer loops back to. ? is where the o is put).

Both follow the same structure, represented in different ways. They run a string literal over the entire code, adding it to the stack. They recreate the string literal command they used and put it at the bottom of the stack. They loop over the stack, adding/subtracting N to each character and printing them.

The first program uses ' as the string literal, and the simple d3*} to create the value 39 and push it to the bottom of the stack. The second uses " as the string literal with the same function. It reverses the stack, gets the character at cell 0,0 and reverses the stack again. It then gets the value at cell 4,0 (g) and adds 8 to it to get o and puts that at X.

Both programs use a different method of looping. The first program uses the skip command (!) to run only half the instructions while going left, reverses direction and runs the other half. The second uses the jump command (.) to skip backwards to the start of the loop at cell Y. Both of these run until there are no more items on the stack and the program errors.

I ran into a number of problems with most of the lower values of N, because shifting one character would turn it into another character essential for that program (and therefore couldn't be used as data for the other program) or two characters from the two programs would shift into the same character. For example:

  1. ++1 = , = --1
  2. .+2 = 0
  3. * = --3
  4. g+4 = k = o-4

etc.

Eventually I got to 10 (a), where I was able to avoid these issues. There might be a shorter version where the shifts are reversed, and the first program is adding N while the second subtracts it. This might be worse off though, as the first program is generally on the lower end of the ASCII scale, so subtracting is better to avoid conflicts.


Forth (64-bit little-endian gforth), 428 + 637 = 1065 bytes

s"	:	l	bl	-	;	:	m	l	emit	;	:	s	space	;	:	z	m	m	m	m	s	;	:	p	.	't	'i	'm	'e	z	;	'e	'r	'e	'h	z	:	q	>r	char	l	bl	l	do	dup	@	.	'L	m	s	cell+	loop	r>	.	;	:	n	'e	'p	'y	't	z	;	q	;	's	p	'B	l	p	#tab	p	'p	'u	'd	'Q	char+	z	n	'B	l	p	n":	l	bl	-	;	:	m	l	emit	;	:	s	space	;	:	z	m	m	m	m	s	;	:	p	.	't	'i	'm	'e	z	;	'e	'r	'e	'h	z	:	q	>r	char	l	bl	l	do	dup	@	.	'L	m	s	cell+	loop	r>	.	;	:	n	'e	'p	'y	't	z	;	q	;	's	p	'B	l	p	#tab	p	'p	'u	'd	'Q	char+	z	n	'B	l	p	n

HERE 3245244174817823034 , 7784873317282429705 , 665135765556913417 , 7161128521877883194 , 682868438367668581 , 679209482717038957 , 680053688600562035 , 678116140452874542 , 682868623551327527 , 680649414991612219 , 682868636436227367 , 7136360695317203258 , 7809815063433470312 , 8458896374132993033 , 5487364764302575984 , 7810758020979846409 , 680166068077538156 , 4181938639603318386 , 8081438386390920713 , 8793687458429085449 , 2812844354006760201 , 7784826166316108147 , 676210045490917385 , 681493840106293616 , 7521866046790788135 , 679491013524025953 , 7928991804732031527 , 216 115 EMIT 34 EMIT 9 EMIT 2DUP TYPE 34 EMIT TYPE

Try it online!

Verification script

Thanks to @Nathaniel for the idea of using Forth - he reminded me in the comments that Forth is not case-sensitive. Then came the mood swings - I've been finding reasons why this will not work, followed by solutions to these problems, again and again. All while spinning my indoor training bike like an oversided and misshaped fidget spinner (you just have to grab one end of the handle bar and tilt it a bit).

Before writing these programs, I drafted what characters can be used by which program. Specifically, the second program can only use uppercase letters, decimal digits, tabs, and commas. This would mean that the first program is all lowercase, but I used some uppercase letters for their ASCII values.

Because tabs are unwieldy, I'll use spaces in the explanation instead.

The first program is of the form s" code"code - the s" starts a string literal, which is then processed by the second copy of the code - a standard quine framework. However, instead of outputting its own source code, it will create the other program, which looks like this:

  • HERE
  • For each 8 bytes in the original string, 64-bit-number-literal ,
  • length-of-the-string
  • 115 EMIT 34 EMIT 9 EMIT 2DUP TYPE 34 EMIT TYPE

This uses Forth's data space. HERE returns the pointer to the end of the currently allocated data space area, and , appends a cell filled with a number to it. Therefore, the first three bullet points can be seen like a string literal created using s". To finish the second program off:

  • EMIT outputs a character given its ASCII value, so:
    • 115 EMIT prints a lowercase s
    • 34 EMIT prints the quote character "
    • 9 EMIT prints a tab
  • 2DUP duplicates the top two elements on the stack ( a b -- a b a b ), here it's the pointer to and the length of the string
  • TYPE prints a string to output the first copy of the code
  • 34 EMIT prints the closing quote ", and finally
  • TYPE outputs the second copy of the code

Let's see how the first program works. In many cases numbers have to be avoided, which is done using the 'x gforth syntax extension for character literals, and sometimes subtracting the ASCII value of space, which can be obtained using bl:

s" ..."      \ the data
: l bl - ;   \ define a word, `l`, that subtracts 32
: m l emit ; \ define a word, `m`, that outputs a character. Because 32 is
             \ subtracted using `l`, lowercase characters are converted to
             \ uppercase, and uppercase characters are converted to some
             \ symbols, which will become useful later
: z m m m m space ; \ `z` outputs four characters using `m`, followed by a
                    \ space. This is very useful because all words used in the
                    \ second program are four characters long
: p . 't 'i 'm 'e z ; \ define a word, `p`, that, given a number, outputs that
                      \ number, followed by a space, `EMIT`, and another space
'e 'r 'e 'h z \ here is where outputting the second program starts - `HERE `
: q \ define a helper word, `q`, that will be called only once. This is done
    \ because loop constructs like do...loop can't be used outside of a word.
  >r \ q is called with the address and the length of the data string. >r saves
     \ the length on the return stack, because we don't need it right now. While
     \ it might seem like this is too complicated to be the best way of doing
     \ this for codegolf, just discaring the length would be done using four
     \ characters - `drop`, which would give you the same bytecount if you could
     \ get the length again in... 0 characters.
  char l \ get a character from after the call to q, which is `;`, with the
         \ ASCII value of $3B, subtract $20 to get $1B, the number of 64-bit
         \ literals necessary to encode the string in the second program.
  bl l \ a roundabout way to get 0
  do   \ iterate from 0 (inclusive) to $1B (exclusive)
    \ on the start of each iteration, the address of the cell we are currently
    \ processing is on the top of the stack.
    dup @ . \ print the value. The address is still on the stack.
    'L m space \ the ASCII value of L is exactly $20 larger than the one of ,
    cell+ \ go to the next cell
  loop
  r> . \ print the length of the string
;
: n 'e 'p 'y 't z ; \ define a word, `n`, that outputs `TYPE`
q ; \ call q, and provide the semicolon for `char` (used to encode the length
    \ of the string in 64-bit words). Changing this to an uppercase U should
    \ make this work on 32-bit systems, but I don't have one handy to check that
's p \ print the code that outputs the lowercase s
'B l p \ likewise, 'B l <=> $42 - $20 <=> $22 <=> the ASCII value of a comma
#tab p \ print the code that outputs a tab
'p 'u 'd 'Q char+ z \ char+ is the best way to add 1 without using any digits.
                    \ it is used here to change the Q to an R, which can't be
                    \ used because of `HERE` in the second program. R has an
                    \ ASCII value exactly $20 larger than the ASCII value of 2,
                    \ so this line outputs the `2DUP`.
n 'B l p n \ output TYPE 34 EMIT TYPE to finish the second program. Note the
           \ that the final `n` introduces a trailing space. Trying to remove
           \ it adds bytes.

To finish this off, I'd like to say that I tried using EVALUATE, but the second program becomes larger than both of the ones presented above. Anyway, here it is:

: s s" ; s evaluate"s" : l bl - ; : m l emit ; : d here $b $a - allot c! ; : c here swap dup allot move ; : q bl l do #tab emit dup @ bl l u.r cell+ #tab emit 'L m loop ; here bl 'B l 's bl 's bl 'Z l d d d d d d d -rot c bl 'B l 's 'B l d d d d s c 'B l d c 'e 'r 'e 'h m m m m 'A q #tab emit 'e 'p 'y 't m m m m"; s evaluate

If you manage to golf this down enough to outgolf my s" ..."... approach, go ahead and post it as your own answer.


Perl, (311+630 = 941 bytes) 190+198 = 388 bytes

Both programs print to standard output.

The first perl program contains mostly printable ASCII characters and newlines, and it ends in exactly one newline, but the two letter ÿ represents the non-ASCII byte \xFF:

@f='^"ÿ"x92;@f=(@f,chr)for 115,97,121,36,126,191,153,194,216,113;print@f[1..5,5,10,5..9,0,9,0,5]'^"ÿ"x92;@f=(@f,chr)for 115,97,121,36,126,191,153,194,216,113;print@f[1..5,5,10,5..9,0,9,0,5]

The second one contains mostly non-ASCII bytes, including several high control characters that are replaced by stars in this post, and no newlines at all:

say$~~q~¿*ÂØ¡Ý*Ý*ÆÍÄ¿*Â׿*Ó***Ö***ßÎÎÊÓÆÈÓÎÍÎÓÌÉÓÎÍÉÓÎÆÎÓÎÊÌÓÎÆËÓÍÎÉÓÎÎÌÄ*****¿*¤ÎÑÑÊÓÊÓÎÏÓÊÑÑÆÓÏÓÆÓÏÓʢءÝ*Ý*ÆÍÄ¿*Â׿*Ó***Ö***ßÎÎÊÓÆÈÓÎÍÎÓÌÉÓÎÍÉÓÎÆÎÓÎÊÌÓÎÆËÓÍÎÉÓÎÎÌÄ*****¿*¤ÎÑÑÊÓÊÓÎÏÓÊÑÑÆÓÏÓÆÓÏÓÊ¢~

A hexdump of the first program with xxd is:

00000000: 4066 3d27 5e22 ff22 7839 323b 4066 3d28  @f='^"."x92;@f=(
00000010: 4066 2c63 6872 2966 6f72 2031 3135 2c39  @f,chr)for 115,9
00000020: 372c 3132 312c 3336 2c31 3236 2c31 3931  7,121,36,126,191
00000030: 2c31 3533 2c31 3934 2c32 3136 2c31 3133  ,153,194,216,113
00000040: 3b70 7269 6e74 4066 5b31 2e2e 352c 352c  ;print@f[1..5,5,
00000050: 3130 2c35 2e2e 392c 302c 392c 302c 355d  10,5..9,0,9,0,5]
00000060: 275e 22ff 2278 3932 3b40 663d 2840 662c  '^"."x92;@f=(@f,
00000070: 6368 7229 666f 7220 3131 352c 3937 2c31  chr)for 115,97,1
00000080: 3231 2c33 362c 3132 362c 3139 312c 3135  21,36,126,191,15
00000090: 332c 3139 342c 3231 362c 3131 333b 7072  3,194,216,113;pr
000000a0: 696e 7440 665b 312e 2e35 2c35 2c31 302c  int@f[1..5,5,10,
000000b0: 352e 2e39 2c30 2c39 2c30 2c35 5d0a       5..9,0,9,0,5].

And a hexdump of the second program is:

00000000: 7361 7924 7e7e 717e bf99 c2d8 a1dd 00dd  say$~~q~........
00000010: 87c6 cdc4 bf99 c2d7 bf99 d39c 978d d699  ................
00000020: 908d dfce ceca d3c6 c8d3 cecd ced3 ccc9  ................
00000030: d3ce cdc9 d3ce c6ce d3ce cacc d3ce c6cb  ................
00000040: d3cd cec9 d3ce cecc c48f 8d96 918b bf99  ................
00000050: a4ce d1d1 cad3 cad3 cecf d3ca d1d1 c6d3  ................
00000060: cfd3 c6d3 cfd3 caa2 d8a1 dd00 dd87 c6cd  ................
00000070: c4bf 99c2 d7bf 99d3 9c97 8dd6 9990 8ddf  ................
00000080: cece cad3 c6c8 d3ce cdce d3cc c9d3 cecd  ................
00000090: c9d3 cec6 ced3 ceca ccd3 cec6 cbd3 cdce  ................
000000a0: c9d3 cece ccc4 8f8d 9691 8bbf 99a4 ced1  ................
000000b0: d1ca d3ca d3ce cfd3 cad1 d1c6 d3cf d3c6  ................
000000c0: d3cf d3ca a27e                           .....~

In the second program, the quoted string (189 bytes long, delimited by tildes) is the entire first program except the final newline, only encoded by bitwise complementing each byte. The second program simply decodes the string by complementing each of the bytes, which the ~ operator does in perl. The program prints the decoded string followed by a newline (the say method adds a newline).

In this construction, the decoder of the second program uses only six different ASCII characters, so the first program can be practically arbitrary, as long as it only contains ASCII characters and excludes those six characters. It's not hard to write any perl program without using those five characters. The actual quine logic is thus in the first program.

In the first program, the quine logic uses a 11 word long dictionary @f, and assembles the output from those words. The first words repeats most of the source code of the first program. The rest of the words are specific single characters. For example, word 5 is a tilde, which is the delimiter for the two string literal in the second program. The list of numbers between the brackets is the recipe for which words to print in what order. This is a pretty ordinary general construction method for quines, the only twist in this case is that the first dictionary words is printed with its bytes bitwise complemented.

Tags:

Quine

Code Challenge

Recent Posts