8
\$\begingroup\$

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

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

\$\endgroup\$
16
  • 3
    \$\begingroup\$ While this challenge is clear enough to avoid any major issues, I'd highly recommend that for later challenges you check out the Sandbox, even if it's just to get a screen for duplicates before posting. This is especially true for winning criteria other than code-golf, which can be difficult to get right, and if not worded properly, can lead to challenge-breaking answers (e.g. infinite scores). (cont) \$\endgroup\$ Commented Sep 25, 2020 at 23:00
  • \$\begingroup\$ (cont) I can't see any major issues with this challenge (partly due to the simplicity of the task, ignoring the scoring criteria), but it's very easy to made a mistake or to misword something, which is what the Sandbox is for. \$\endgroup\$ Commented Sep 25, 2020 at 23:00
  • 4
    \$\begingroup\$ Is there reason to expect approaches used here for cat to be different from the earlier Hello World challenge? \$\endgroup\$
    – xnor
    Commented Sep 25, 2020 at 23:00
  • 4
    \$\begingroup\$ @Shaggy Respectfully, I disagree. If done well, code bowling challenges can be just as fun as code golf, or really any other type of challenge. Rather, code bowling can be a difficult scoring criteria to get right, and so many people avoid it. This challenge, however, is, imo, a good use of code bowling vs any other scoring criteria. \$\endgroup\$ Commented Sep 26, 2020 at 0:05
  • 6
    \$\begingroup\$ I'm going to vote to close this for now, since it seems all of the answers (besides the Retina one, which doesn't exactly matter since Retina can't exactly evaluate code) are doing the same thing as was effective last time: finding a way to encode a regular version of the program as a number, then converting that number into a string of the code and evaluating it. If you or anyone else comes up with a convincing reason these are different I'll be happy to reopen. \$\endgroup\$ Commented Sep 26, 2020 at 5:27

6 Answers 6

5
\$\begingroup\$

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!

\$\endgroup\$
3
  • 2
    \$\begingroup\$ I just noticed that the highlighter really doesn't know what to do with trigraphs. Bug or feature? :-) \$\endgroup\$
    – ErikF
    Commented Sep 26, 2020 at 6:19
  • 1
    \$\begingroup\$ You can remove the 3 spaces after the 3 includes. \$\endgroup\$
    – Noodle9
    Commented Sep 28, 2020 at 20:49
  • \$\begingroup\$ You can remove the f in fprintf together with the stdout, inside. \$\endgroup\$
    – xigoi
    Commented Sep 12, 2021 at 20:25
5
\$\begingroup\$

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.

\$\endgroup\$
2
  • 3
    \$\begingroup\$ I don't see a restriction that the removed characters have to be consecutive, so I think I can reduce this program to “...”LỌV (where there are 608 characters in the string). \$\endgroup\$
    – Neil
    Commented Sep 25, 2020 at 23:32
  • \$\begingroup\$ @Neil Yeah, I must've missed that in my first read-through :/ \$\endgroup\$ Commented Sep 25, 2020 at 23:33
3
\$\begingroup\$

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\$:

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 -~[].

\$\endgroup\$
1
  • \$\begingroup\$ Could you make it longer by using function() instead of =>? \$\endgroup\$
    – xigoi
    Commented Sep 12, 2021 at 20:28
3
\$\begingroup\$

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
\$\endgroup\$
2
  • 1
    \$\begingroup\$ given the answers to the last challenge, I definitely didn't expect to see a submission with 11 bytes XD \$\endgroup\$
    – Mason
    Commented Sep 26, 2020 at 0:02
  • 2
    \$\begingroup\$ @Mason I was stuck on 5 bytes for quite some time, then clawed my way up to 7 and 10 before eventually reaching the giddy heights of 11! \$\endgroup\$
    – Neil
    Commented Sep 26, 2020 at 0:08
2
\$\begingroup\$

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

\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$
3
  • 9
    \$\begingroup\$ Given that a proof has been found that every language has a maximum finite score, it would appear as though your program cannot be increased ad infinitum and that at some point it reaches a point where it’s no longer irreducible. My guess would be that if you attempt to encode the exec('...') in the same manner, you’d be able to remove a subset from ... to reduce it back down to the original exec(...) form. \$\endgroup\$ Commented Sep 26, 2020 at 8:09
  • \$\begingroup\$ @cairdcoinheringaahing to be honest I've not tried very hard to work out if the unary part is reducible \$\endgroup\$
    – pxeger
    Commented Sep 26, 2020 at 8:11
  • 1
    \$\begingroup\$ I don't think you can claim the 10* for the Unicode escapes of digits; \U00000038 can be reduced to 8 for example. \$\endgroup\$
    – Neil
    Commented Oct 18, 2020 at 18:38

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