Mutually Exclusive Quines

29

4

Your challenge is simple. Write two programs that share no characters which output each other.

Example

Two programs P and Q are mutually exclusive quines if:

  1. P outputs Q
  2. Q outputs P
  3. There is no character c which belongs to both P and Q
  4. Each program P and Q are proper quines
    1. This counts empty quines and quines that read their own (or the other's) source code as invalid.

More rules

  • The shortest combined length of these programs wins. That is, size(P) + size(Q) is your score, and the lowest score wins.
  • Both programs are in the same language
  • Each program may be a full program or function, and they need not be the same.
    • For example, P may be a full program and Q may be a function.

Verification

This Try it online! snippet here can verify whether or not two programs are mutually exclusive. The inputs are put in the first two arguments.

Conor O'Brien

Posted 2018-01-23T17:14:08.727

Reputation: 36 228

2Related. – Martin Ender – 2018-01-23T17:22:24.297

1Related, Related. – Post Rock Garf Hunter – 2018-01-23T18:07:06.957

3I would presume that two programs that read one another's source are banned as well. – Giuseppe – 2018-01-23T23:41:34.843

@Giuseppe Ye​s. – Conor O'Brien – 2018-01-24T00:13:51.660

2I'd love to see a non-esolang answer to this challenge. (I had a bit of a thought about how to do that, but so far I haven't seen a way. It might be possible in Forth though, since it's not case sensitive and doesn't rely much on non-alphabetic characters.) – Nathaniel – 2018-01-24T11:39:49.283

Can I pass the same flag to the interpreter/compiler of both programs? – BlackCap – 2018-01-28T07:31:05.587

@BlackCap please elaborate? – Conor O'Brien – 2018-01-28T07:32:15.847

I don't actually have an answer that uses this, but would something like bc -not and the programs 0 and 1 be an acceptable answer if I pay for the flag? – BlackCap – 2018-01-28T07:37:24.340

@BlackCap I still don't quite get your question. Are you asking if you can add different arguments to the two programs? Or are you asking if arguments are allowed? – Conor O'Brien – 2018-01-28T07:39:51.597

1If I can pass the same argument, not to the programs themselves, but to the compiler of both programs. Typically compiler flags are allowed if you pay for them, but for this challenge you might argue it goes against the mutually exclusive rule. – BlackCap – 2018-01-28T07:43:28.260

There is an obvious problem with applying the part of the proper quine definition that says there must be a part of the program that encodes something other than itself. That only makes sense for this kind of variant if you interpret it as "after going a full cycle". But if you do that, then I think @BlackCap's suggestion is disallowed. – Ørjan Johansen – 2018-01-28T10:08:21.750

@BlackCap The rules about flags had been changed last I heard. They now cost nothing but which flags are used is considered part of the language choice. (So you'd need to specify something like "bc with -not flag" as the language.) – Ørjan Johansen – 2018-01-28T10:11:42.480

@ØrjanJohansen 's suggestion makes sense. I suppose then if you were to use flags, they must be consistent. – Conor O'Brien – 2018-01-28T16:09:49.827

Answers

37

><>, 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.

Jo King

Posted 2018-01-23T17:14:08.727

Reputation: 38 234

19

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.

NieDzejkob

Posted 2018-01-23T17:14:08.727

Reputation: 4 630

1Great! I'm happy that my comment sparked this solution! – Nathaniel – 2018-02-01T00:39:47.587

16

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.

b_jonas

Posted 2018-01-23T17:14:08.727

Reputation: 341

14

Haskell, 306 + 624 = 930 bytes

Program 1: An anonymous function taking a dummy argument and returning a string.

(\b c()->foldr(\a->map pred)b(show()>>c)`mappend`show(map(map fromEnum)$tail(show c):pure b))"İĴİóđđđÝöÝâÝæÝääē××êääē××İēÀħđĮâħēĕóİóòòĮááħááđéêâéêēááĮÀħ""(\b c()->foldr(\a->map pred)b(show()>>c)`mappend`show(map(map fromEnum)$tail(show c):pure b))"

Try it online!

Program 2: q[[40,...]] at the end is an anonymous function taking a dummy argument and returning a string.

z~z=[[['@','0'..]!!4..]!!z]
q[x,q]_=z=<<x++q++[34,34]++x
q[[40,92,98,32,99,40,41,45,62,102,111,108,100,114,40,92,97,45,62,109,97,112,32,112,114,101,100,41,98,40,115,104,111,119,40,41,62,62,99,41,96,109,97,112,112,101,110,100,96,115,104,111,119,40,109,97,112,40,109,97,112,32,102,114,111,109,69,110,117,109,41,36,116,97,105,108,40,115,104,111,119,32,99,41,58,112,117,114,101,32,98,41,41,34],[304,308,304,243,273,273,273,221,246,221,226,221,230,221,228,228,275,215,215,234,228,228,275,215,215,304,275,192,295,273,302,226,295,275,277,243,304,243,242,242,302,225,225,295,225,225,273,233,234,226,233,234,275,225,225,302,192,295]]

Try it online!

Character set 1 (includes space):

 "$()-:>E\`abcdefhilmnoprstuw×ÝáâäæéêñòóöđēĕħĮİĴ

Character set 2 (includes newline):

!'+,.0123456789<=@[]_qxz~

Since only set 1 contains non-ASCII characters, their UTF-8 bytes are also disjoint.

How it works

  • Program 1 is generally written with lambda expressions, spaces and parentheses, free use of builtin alphanumeric functions, and with the quine data as string literals at the end.

    • Program 1's own core code is turned into string literal data simply by surrounding it with quote marks.
      • To support this, every backslash is followed by a or b, which form valid escape sequences that roundtrip through show.
      • Another tiny benefit is that a, b and c are the only lower case letters whose ASCII codes are less than 100, saving a digit in the numerical encoding used by program 2.
    • The string literal encoding of program 2's core code is more obfuscated by using non-ASCII Unicode: Every character has 182 added to its code point to ensure there is no overlap with the original characters.
      • 182 used to be 128, until I realized I could abuse the fact that 182 is twice the length of the string literal for program 1's code to shorten the decoding. (As a bonus, program 2 can use newlines.)
  • Program 2 is generally written with top level function equations (except for the final anonymous one), character literals and decimal numbers, list/range syntax and operators, and with the quine data as a list of lists of Ints at the end.

    • Program 1's core code is encoded as a list of its code points, with a final double quote.
    • Program 2's core code is encoded as the list of code points of the string literal used in program 1, still shifted upwards by 182.

Walkthrough, program 1

  • b and c are the values of the string literals for program 2 and 1, respectively, given as final arguments to the lambda expression. () is a dummy argument solely to satisfy PPCG's rule that the program should define a function.
  • foldr(\a->map pred)b(show()>>c) decodes the string b to the core code of program 2 by applying map pred to it a number of times equal to the length of show()>>c == c++c, or 182.
  • tail(show c) converts the string c to the core code of program 1, with a final double quote appended.
  • :pure b combines this in a list with the string b.
  • map(map fromEnum)$ converts the strings to lists of code points.
  • `mappend`show(...) serializes the resulting list of lists and finally appends it to the core code of program 2.

Walkthrough, program 2

  • The toplevel z~z=[[['@','0'..]!!4..]!!z] is a function converting code points back to characters (necessary to write since not all the characters in toEnum are available.)
    • Its code point argument is also called z. The laziness marker ~ has no effect in this position but avoids a space character.
    • ['@','0'..] is a backwards stepping list range starting at ASCII code 64, then jumping 16 down each step.
    • Applying !!4 to this gives a \NUL character.
    • Wrapping that in a [ ..] range gives a list of all characters, which !!z indexes.
    • The character is finally wrapped in a singleton list. This allows mapping the function z over lists using =<< instead of the unavailable map and <$>.
  • The toplevel q[x,q]_=z=<<x++q++[34,34]++x is a function constructing program 1 from the quine data list.
    • x is the data for the core of program 1 (including a final double quote) and the inner q is the obfuscated data for the core of program 2. _ is another dummy argument solely to make the final anonymous function a function instead of just a string.
    • x++q++[34,34]++x concatenates the pieces, including two double quote marks with ASCII code 34.
    • z=<< constructs program 1 by mapping z over the concatenation to convert from code points to characters.
  • The final q[[40,...]] is an anonymous function combining q with the quine data.

Ørjan Johansen

Posted 2018-01-23T17:14:08.727

Reputation: 6 914

7

Jelly, 128 90 87 86 85 79 16 + 32 = 48 bytes

“OṾ⁾ọṙŒs”OṾ⁾ọṙŒs

Try it online!

79,7806,8318,7885,7769,338,115ỌṘ

Try it online!

The first program does the following:

“OṾ⁾ọṙŒs”OṾ⁾ọṙŒs
“OṾ⁾ọṙŒs”          String literal: 'OṾ⁾ọṙŒs'
         O         ord: [79, 7806, 8318,...]
          Ṿ        Uneval. Returns '79,7806,8318,7885,7769,338,115'
           ⁾ọṙ     Two character string literal: 'ọṙ'
              Œs   Swap case the two char literal: 'ỌṘ'.

This leaves the strings 79,7806,8318,7885,7769,338,115 and ỌṘ as the two arguments of the chain and they are implicitly concatenated and printed at the end.

The second program calculates the chr () of the list of numbers which returns OṾ⁾ọṙŒs. prints “OṾ⁾ọṙŒs” (with quotes) and returns the input, leaving “OṾ⁾ọṙŒs”OṾ⁾ọṙŒs as the full output.

dylnan

Posted 2018-01-23T17:14:08.727

Reputation: 4 993

5

Gol><>, 23 + 23 = 46 22 + 22 = 44 20 + 20 = 40 bytes

"lF{3+|3d*HqlJJJQpp2

Try it online!

'5ssTMMMotK-g6.6~Io

Try it online!

Verify it online!

How they work

"lF{3+|3d*HqlJJJQpp2

"..."        Push everything to the stack
 lF{3+|      Add 3 to everything on the stack
       3d*   Push 39 `'`
          H  Print everything on the stack (from the top) and halt

'5ssTMMMotK-g6.6~Io

'...'        Push everything to the stack
 5ss         Push 37 (34 `"` + 3)
    T    t   Loop indefinitely...
     MMMo      Decrement 3 times, pop and print
               At the end, `o` tries to print charcode -3, which is fishy (thanks Jo King)
               Program terminates

Adapted from Jo King's ><> answer. Having many more alternative commands for output and repeat, there was no need for g or p, and the two main bodies became much shorter.

Another main difference is that I generate the opponent's quote directly at the top of the stack. This way, it was slightly easier to keep the invariant of quote + my code + opponent code(reversed and shifted).

Bubbler

Posted 2018-01-23T17:14:08.727

Reputation: 16 616