Biggest Irreducible Cat [duplicate]

Question

I guess you could call this the next challenge in the "Irreducible series".

• Hello World

Challenge

Create a cat subject to the constraint that it is irreducible.

A cat program C is considered irreducible if there does not exist a cat (in the same programming language as C) that can be constructed by removing characters from C.

For example

console.log(prompt.call());

can have the the bracketed characters removed

console.log(prompt[.call]())[;] ->
console.log(prompt())

And it will still be a cat. Therefore console.log(prompt.call()); is not irreducible.

The winner will be the program with the longest source code.

Extras

A big shout out to @acupoftea for showing that, for any given language, there is actually a maximum score. Otherwise you could construct an infinite set that would break Higman's lemma!.

Answer 1

C (gcc) with -trigraphs, 327 357 413 bytes

Some creative uses of the language:

• Very important typedefs for pointers to types
• Constants that are then decremented using the super-experimental tadpole operator
• Dynamic allocation of the character buffer, for reasons
• Use of fread to read in a character
• Use of fprintf to print a character as a fixed single-byte string
• The essential use of trigraphs in case you are typing on a keyboard from the 1800s
• Using iso646.h because the ISO said so :-)

??=include <stdio.h>
??=include <stdlib.h>
??=include <iso646.h>
typedef unsigned*v;struct g??<v c;??>;typedef struct g*h;h c;main()??<c=calloc(sizeof(struct g),-??-EXIT_SUCCESS);c->c=calloc(sizeof(unsigned),-??-EXIT_SUCCESS);do??<fread(c->c,-??-EXIT_SUCCESS,-??-EXIT_SUCCESS,stdin);if(feof(stdin)==EXIT_FAILURE xor EXIT_FAILURE)fprintf(stdout,"%.1s",c->c);??>while(feof(stdin)==EXIT_FAILURE xor EXIT_FAILURE);??>

Try it online!

Answer 2

Jelly u, \$4\times10^{41}\$ bytes

“...”WẈbØ%ỌV

Except instead of ... its \$133390687877217192365177139021057049493695\$ Ɱ characters

More specifically, a score of \$400172063631651577095531417063171148481103\$

How it works

The standard cat program in Jelly is

ƈȮøL¿

Try it online!

If we convert each of these characters to their Unicode code point we get

[392, 558, 248, 76, 191]

Treat this a base \$4294967296 = 2^{32}\$ number and convert it back to decimal to get \$133390687877217192365177139021057049493695\$

The above program has a string consisting of \$133390687877217192365177139021057049493695\$ Ɱ characters. We then take its length, convert it to base \$4294967296\$, convert back to characters and run as Jelly code.

By forcing Jelly to encode the source as UTF-8 rather than using the Jelly code page, multi byte characters are counted as multiple bytes rather than just 1.

This is 100% irreducible. The cat program it encodes is optimal for Jelly, so there's no way to remove any of the Ɱ characters and still create a cat program, and all of the other characters are necessary to correctly convert the string to a program and execute it. More specifically:

• Removing either “ or ” will cause syntax errors
• Removing the W will cause Ẉ to return a list of lists of \$1\$s rather than the code points in base \$4294967296\$
• Removing the Ẉ will mean the program won't ever convert the string to the code points in base \$4294967296\$
• Removing any of bØ% will prevent the base conversion happening
• Removing Ọ or V will stop the program from converting to characters and running the program

Furthermore, I believe this is the longest you can get using the method of "long string's length in a high base" in Jelly. The base being used must meet the following criteria:

• The number isn't "constructed" via commands to be larger, as these commands can be removed and the long string adjusted for the lower base
• The number doesn't have digits in it, as characters can be removed to just isolate the lowest digit and the long string can then be adjusted to match this new base

Ø% is the largest constant Jelly has which meets these criteria at \$2^{32}\$, so, as a higher base leads to a longer string, an answer in Jelly cannot beat this one.

Answer 3

JavaScript (ES7), 10346554967051525 bytes

The string -~[] is actually repeated \$2586638741762875\$ times.

Infinity=>eval((-~[]-~[]-~[]-~[]…-~[])**20+'')

You can Try this version online!, where all but the last 5 -~[] have been replaced with a hard-coded integer.

How?

The characters in the name of the input variable Infinity are not used anywhere else, so we can't simplify the code by shortening it. The only way to get its content is that the expression in eval() evaluates to the string "Infinity".

We do it by computing:

$$2586638741762875^{20}$$

where \$2586638741762875\$:

• is less than Number.MAX_SAFE_INTEGER and can therefore be generated by adding \$1\$ repeatedly
• becomes higher than Number.MAX_VALUE when raised to the power of \$20\$

We can probably make it longer by using a more convoluted expression. For instance, I think it should still be irreducible if we use -~RegExp instead of -~[].

Answer 4

Retina 0.8.2, 11 12 15 bytes

\A`[^\\](?<=\\)

Try it online! Explanation: The \ suppresses the trailing newline, without which the program fails to be a cat program. The A` is required to identify the stage as an AntiGrep rather than a Match stage (which would just output the count of something). For the output to match the input, the pattern must fail to match; this is done by matching any non-\ and then ensuring that the character was actually a \; this character was chosen because it needs to be quoted, making the pattern longer.

I also looked into the other stage types Retina has to see what the best I could do for them was.

• Deduplicate - best I could do was \D`() (5 bytes) deduplicate all empty strings
• Grep - best I could do was \G` (3 bytes) keep everything
• Match - best I could do was \!`(.|[^.])+ (12 bytes) match everything
• Sort - best I could do was \O$` or \O`$ or similar (4 bytes) sort in original order or sort nothing
• Replace - best I could do was a single newline (1 byte) replace nothing with nothing - this means that all Retina cat programs that contain a newline can be reduced to 1 byte
• Split - best I could do was \S`\n (5 bytes) split on newlines and join with newlines
• Transliteration - best I could do was \T` (3 bytes) translate nothing

Answer 5

Japt, 125 bytes

I'm very far from sure that this is valid but I am somewhat sure it can be beaten!

Ov"11111111111111111111111111111111111111111111111111111"n2 a"11111111111111111111111111111111111111111111110110001"n2  d  qR

Try it

Answer 6

Python 3, ^{8+(10*(85+(10*749535276648396287585636512750330369605831039396714237143337)))} infinite bytes

exec("\U0000006e\U0000003d\U00000030\U0000003b\U00000063\U0000003d\U00000022\U00000030\U00000030\U00000030\U00000030\U0000002e\U0000002e\U0000002e\U0000002e\U0000002e\U00000022\U0000000a\U00000066\U0000006f\U00000072\U00000020\U0000005f\U00000020\U00000069\U0000006e\U00000020\U00000063\U0000003a\U0000006e\U0000002b\U0000003d\U00000031\U0000000a\U00000073\U0000003d\U00000062\U00000079\U00000074\U00000065\U00000061\U00000072\U00000072\U00000061\U00000079\U00000028\U00000029\U0000000a\U00000077\U00000068\U00000069\U0000006c\U00000065\U00000020\U0000006e\U0000003a\U00000073\U0000002e\U00000061\U00000070\U00000070\U00000065\U0000006e\U00000064\U00000028\U0000006e\U00000026\U00000032\U00000035\U00000035\U00000029\U0000003b\U0000006e\U0000003e\U0000003e\U0000003d\U00000038\U0000000a\U00000065\U00000078\U00000065\U00000063\U00000028\U00000073\U0000002e\U00000064\U00000065\U00000063\U0000006f\U00000064\U00000065\U00000028\U00000029\U00000029")

The exec("") adds 8 characters, and unicode-escapes multiply the count by 10.

Decoded:

n=0;c="\U00000030\U00000030\U00000030\U00000030....."
for _ in c:n+=1
s=bytearray()
while n:s.append(n&255);n>>=8
exec(s.decode())

This decoding routine adds the 85 characters.

The string inside c is the actual code, encoded in unary, with a unicode-escaped 0 character per unary digit.

This is too large to fit in the observable universe (approximately $$7.5 \times 10 ^ {60}$$ characters long), hence no TIO link.

The unary is then decoded and executed, to get a cat program:

while True:print(input())

I'm pretty sure you could recursively repeat these steps ad infinitum and it would still be irreducible (so I win by default), but I thought I'd keep my answer as an example finite.