Write a near crystalline program

Question

A pristine program is a program that does not have any errors itself but will error if you modify it by removing any contiguous substring other than the entire program.

A crystalline program is sort of the opposite. It is a program which doesn't have any errors itself but will error if you modify it by adding any 1 character anywhere. We call these crystalline because adding an impurity will cause it to break.

Now a true crystalline program is quite hard to come by so in this challenge we will be just trying to get as close as possible.

You will write a program which does not error and count the number of 1 character insertions that also don't error. If your program were crystalline this number would be 0. Also count the number of total 1 character insertions possible.

Your score is then:

\$ \dfrac{\mathrm{number\,\,of\,\,nonbreaking\,\,insertions}+2}{\mathrm{number\,\,of\,\,total\,\,insertions}} \$

And your goal is to minimize this measure.

Specifics

• Since different languages use different codepages and different ranges of characters, for this challenge a character is just any byte. The number of characters in your program is just the number of bytes it occupies and insertions are just that, the insertion of a new byte between any existing bytes or at the beginning and end of the program. You may select which characters you want to consider relevant for this challenge. When we insert any byte it will be one of those selected. The selected bytes must include:

  • At least 96 distinct characters
  • All characters used in your program

• For counting, insertions are considered different if they produce different programs. For example if your program is ABBA, then inserting a B after the first A, after the first B and after the second B all produce ABBBA, this counts as 1 insertion.

• A program errors if any of the following happens:

  • The compiler exits with a non-zero return code when run on the program.
  • The program exits with a non-zero return code when run.
  • The compiler produces non-empty output to STDERR when run on the program.
  • The program produces non-empty output to STDERR when run.

  If your programming language of choice always triggers some of these options, ignore those specific options and treat them as non-errors. If your programming language of choice doesn't have a compiler just ignore options that mention a compiler.

Answer 1

Ellipsis, score → 0

The program consists of \$144 \times 8^n + 23\$ ASCII periods . for \$n \geq 0\$, and gets a perfect score (i.e. every possible insertion causes an error, and any of the 256 possible octets can be inserted). As such, this is a true crystalline program, in addition to scoring arbitrarily close to 0 (even though being a true crystalline program isn't required for a perfect score). Because the scoring gives an advantage to longer programs, you can get a score arbitrarily close to 0 by increasing n.

Try it online! for \$n=1\$

The Ellipsis implementation is a compiler to brainfuck, so for this answer to be valid, the resulting brainfuck program needs to be executed via using a brainfuck compiler that will notice a syntax error (but there are plenty of those to choose from).

Explanation

Ellipsis is a Lenguage variant, caring only about the length of the program it's compiling. It divides the length of the program by 3 (using floor division), interprets it as an octal number, and maps each octal digit to a brainfuck command.

If the program has length \$144 \times 8^n + 23\$, then floor-dividing this by 3 gives us \$48 \times 8^n + 7\$. In octal, that's 6, followed by \$n\$ 0s, followed by 7; the brainfuck program is therefore of the form [>…>] with \$n\$ > characters. This is a valid brainfuck program that does nothing (it's a zero-iteration loop).

Any insertion will cause the program to have length \$144 \times 8^n + 24\$. Floor-dividing that by 3 will give us \$48 \times 8^n + 8\$, i.e. slightly higher, which will corrupt the ] at the end of the program. For \$n=0\$, the program is now ]> which is a syntax error due to the unmatched brackets. For larger \$n\$, the program is now [ followed by \$n-1\$ > followed by <>; again, a syntax error due to unmatched brackets.

How does this program work in other comparable languages?

• I couldn't find a valid Unary interpreter; the web interpreter seems to have fallen off the Internet. As such, I couldn't verify its error behaviour. Essentially the same program as the Ellipsis can be written in Unary according to the spec, though.
• Lenguage does not work (unless you consider a very slow memory leak to be an error because it will eventually exhaust all of memory); the Lenguage interpreter, upon finding an unmatched [ or ], will go into an infinite loop trying to find the other, because (probably by mistake) the search for matching brackets wraps around the program. Eventually its count of unmatched brackets will overflow, but it's a bignum that uses memory proportional to the logarithm of its value, so this will take a very, very long time.
• The Ecstatic and MGIFOS implementations ignore invalid characters, so wouldn't notice insertions of things other than exclamation marks and asterisks respectively, and thus wouldn't score very well.
• Unary Except Every Zero Is Replaced with the Title of This Programming Language or, Alternately, Is Replaced with the Smallest Counter-Example to the Goldbach Conjecture. Compilers and Interpreters Only Have to Implement the Former Option almost works (with a character being placed inside the title of the language reducing the count, something that could break the bracket matching), but would not notice a character being inserted between two copies of the title of the programming language, and as such couldn't get a perfect score.

ais523, this looks like a challenge that could be cheesed by checksums, why didn't you write an answer in A Pear Tree

A Pear Tree prints its main error message a partridge to standard output. Although this is an error by any normal definition, it doesn't fit the definition of an error in the question.

Additionally, the scoring favours longer programs. In A Pear Tree, the size of the checksum doesn't scale with the length of the program, so very long programs tend to have checksum collisions that prevent the normal checksumming behaviour of the language working correctly.

Answer 2

Java -encoding utf-16, \$2^{-37}\$

Try to insert a single byte to UTF-16 file would resulting invalid encoding. So javac reports invalid utf-16 and refuse to compile the source code. That doesn't really matter what your source code is doing as long as it is a valid Java source code. Java supports at most 1GB source code. So maybe there are 256G different insertions, and the score should be 1/128G here. I'm not sure if this is a valid submission through.

---

Java, \$2^{-37}\$

After thinking this twice. I just found out that you doesn't really need the -encoding utf-16 compile parameter. Since javac will fail to compile your source code if it is larger that 1GB. So you simply need to submit a valid 1GB-1B program in Java. Any insertion would simply cause javac refuse to compile due to source code too long.

Answer 3

R, score=0.000000000202, 2000000021 bytes

Edit: corrected score (increased by 1.04-fold) thanks to JDL

t(1)[nchar("aaaaaaaaaa...2000 million and 1 letter 'a's...aaaaaaaaaaa")-2e9,]

Try it online with a smaller version of the program!

Score calculated by hand so may contain (hopefully small) errors.
The longest allowed string in R is 2^31-1 ≈ 2e9 bytes.

Nonbreaking insertions: '#' at the start, position 4, or end (3 insertions), '!', '.', '+' or '-' at position 3 (4 insertions), '.' or 'i' at position 4 (2 insertions), any digit at positions 3 or 4 (20 insertions), whitespace (space or tab) at positions 0,3,4,6 or at positions 0,2,3,6,7,8 from the end (20 insertions), for a total of 49 insertions.

Total possible insertions: All ASCII except 'a' (126 possible characters) at 2000000021 positions, plus 'a' at 21 positions, for a total of 2.52e11 possible insertions.

Score: (49+2)/(126*2000000021+21) = 2.02381e-10

---

We could also improve the score by gaming the relevant character set to exclude most of the nonbreaking characters: that is, excluding any of '#!.+-01345678i \t'. This leaves 4 nonbreaking insertions (by inserting one of '2' or '9' at positions 3 or 4), giving a score of (4+2)/(110*2000000021+21) = 2.727273e-11

---

Of course, an even more extreme (but boring) extension of this approach would be just the string "aaaaaaaaaa...2147483647 letter 'a's...aaaaaaaaaa". Any single character added within the string will trigger an Error in "aaa...aaa" : R character strings are limited to 2^31-1 bytes error. Once we exclude whitespace and the '#' character from our character set, this would give a score of 2/(124*2147483649) = 7.510666e-12.

Answer 4

Zsh, score \$ \frac {2+0} {497} \approx 0.00402 \$ (1 byte)

;

Attempt This Online!

For the purposes of this answer, the "character set" of Zsh shall be all bytes except tab, newline, space, #, -, :, w, making the total number of characters 249. Since the program is only 1 byte, there are \$ 2 * 249 - 1 = 497 \$ unique possible insertions.

Every one of these 497 insertions breaks the program - Zsh is particularly good at producing errors :)

Validator / auto-scoring program: Attempt This Online!

This scoring program can be modified to test almost any language if you run it on TIO, where a Zsh program can access the interpreters of any other language (which is not the case on ATO).

Answer 5

Python 3, score \$\frac{2}{6841}\approx0.00029\$

ConnectionRefusedError.with_traceback.__subclasshook__.__subclasshook__

Try it online! Footer verifies and scores the program.

The 96 bytes are codepoints from 27 to 127, without , #,\\,, and ;. In theory I could append .__subclasshook__ arbitrarily many times to get a lower score.

Answer 6

Ruby, score \$ \to 0 \$

<<abcdefghijklmnopqrstuvwxyz
abcdefghijklmnopqrstuvwxyz

Attempt This Online!

Add arbitrarily more letters to abcdefghijklmnopqrstuvwxyz in both places to achieve a lower and lower score, asymptotically approaching zero. (with \$ n \$ letters, the score is \$ \frac 1 {279+239n} \$). The example shown here has a score of \$ \frac 1 {6693} \approx 0.00015 \$. With 1 million letters, the score would be \$ \approx 0.0000000042 \$.

The charset is all bytes except \x00, \x04, tab, newline, \x0b, \x0c, \x0d, \x1a, space, !, #, +, -, ;, \, and ~.

Explanation:

<< starts a "here-doc", which takes a single word, and turns the rest of the source code upto the first occurrence of that word again as a literal string.

This was originally going to be an(other) answer in Zsh, which also has here-docs, but unlike Zsh, Ruby produces an error when a heredoc isn't closed. (compare lone <<abcdefghijklmnopqrstuvwxyz in Ruby to in Zsh).

By having an error whenever the same word is not used twice, we can detect any single-character insertion to inside that word.

A few quirks of Ruby's syntax mean we can discard some ASCII characters, but they can be more than made up for by invalid UTF-8 bytes.

Answer 7

BitCycle, score 0.0737

1...v
...^ ^

where ... is an arbitrary number of spaces

Try it online!

Bitcycle has 70 operating bytes: ><^=+/\|-10!?~{}@abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ (plus newline)
Per the challenge, I am considering 26 more, all of which are no-ops: 23456789#$%&*()_,.;:'"[] (plus "`")

Note that any position other than the first will have a duplicate case in a previous insertion location, and thus will only be 95 insertions instead of 96. Insertion space will be indicated by an asterisk *. For the examples, the region ... will be indicated by quotation marks "".

*1""v   any char except newline offsets   1 nonbreaking
""^ ^   "v", so "1" enters a loop         96 total

1"*"v   like case 1, but chars "^vV^/\+{~!?@"   13 nonbreaking
""^ ^   will also redirect the "1" elsewhere    95 total

1""v*   no chars   95 nonbreaking
""^ ^   will err   95 total

1""v     identical   1 nonbreaking
"*"^ ^   to case 1   95 total

1""v     no chars   95 nonbreaking
""^* ^   will err   95 total

1""v     no chars   95 nonbreaking
""^ *^   will err   95 total

1""v     no chars   95 nonbreaking
""^ ^*   will err   95 total

The score can be expressed as a fraction: \$\frac{3+4c+14n}{1+5c+2cn}\$ where \$c\$ is the number of characters in the set minus 1, and \$n\$ is the length of .... To generate the score listed, \$c=95, n \to\infty\$, which evaluates to \$\frac{7}{95}\$.
Previously, I had missed a nonbreaking insertion, but this didn't change my score because of the assumed infinitely large \$n\$

Answer 8

Python 3, score \$\frac2{239}\$ (0 bytes)

And our hero program is...

NOTHING!!!

Same approach as above. The "bad characters" are:

\t (tab), \n (newline), \x0c (something IDK), \r (newline sort of), # (comment), \ (line continuation), (space) , and 0123456789 (numbers).

Thus we define the range of bytes that can be added to be all single byte characters that are not in the above list.

Python testing script:

characterset=[chr(x) for x in range(256)]
noerr=''
for char in characterset:
 try: exec(char)
 except: pass
 else: noerr+=char; print(char)

noerr
len(noerr)

(Designed to be directly runned in the interactive console.)

However, sometimes _ will work in REPL and the \ somehow works, so be warned.

Answer 9

C(gcc)

m\
a\
i\
n(){}

score:
118/3840 -> 120/3840

Explanation

main must be a part of the program, so almost no characters are valid there. To lower the score I expanded that part of the code with backslash-newline, which allows for very few characters(and thus more errors).

test code:

#include <stdio.h>
char prog[]="m\\\na\\\ni\\\nn(){}";
char tofile[0xff];
main(){
  long long bad=0;
  long long total=0;
  for(int i=0; i<sizeof(prog);i++){
    char c=0;
    do{
      FILE* tmpc=fopen("/tmp/tmp.c", "w");
      int j;
      for(j=0;j<i;j++) tofile[j]=prog[j];
      tofile[i]=c;
      for(j=i;prog[j];j++)tofile[j+1]=prog[j];
      fwrite(tofile, sizeof(prog), 1, tmpc);
      fclose(tmpc);

      FILE* gcc=popen("gcc /tmp/tmp.c", "r");
      char gccc=getc(gcc);
      while(gccc!=EOF){}
      int status=pclose(gcc);
      printf("code: \"%s\" Exit Status: %d\n", tofile, status);
      if(!status)
        bad++;
      total++;
    }while(++c!=0);
  }
  printf("score:\n %lld\n----\n %lld\n", bad, total);
}

It could be possible to do better, but the above code takes too long to run.

Answer 10

Forth, Score 0.001736111 4 bytes

: abcdefghijklmnopqrstuvwxyz01234 ;

When run from a terminal, this program will correctly return nothing and the interpreter will return OK to the terminal.

Any insertion into the 31 character name will result in the correct program name not compiling, so the program will not exist and will not run.

Any insertion that puts anything but a blank character beside the : or ; will result in the program not compiling correctly.

Possible insertions are

• blank before :,
• blank after :,
• blank before ;, and
• blank after ;.

The language parses with blanks and does not recognize any difference between one blank and two blanks between nonblank words. So there is no program that lacks these 4 insertions.

35 character program. At 36 locations we can insert any of 96 characters. 36*96 = 3456.

(4+2)/3456 = 0.001736111

Standard compilers must allow names up to 31 characters, and may allow larger names. So this program could be, say 259 characters long, but then it would not run on all Forth compilers.

By stuffing the program with more 31-character functions, in the limit we would have 1 valid insertion per 31-character name, and that's as low as it gets.

However, if we only consider an insertion valid if it changes the program, and : test ; compiles the same as : test ; then maybe we should not consider those insertions.

In that case the program

: abcdefghijklmnopqrstuvwxyz01234 ;
: test 
abcdefghijklmnopqrstuvwxyz01234 
abcdefghijklmnopqrstuvwxyz01234 
abcdefghijklmnopqrstuvwxyz01234 
abcdefghijklmnopqrstuvwxyz01234 ;

is also entirely crystalline and we can add as many lines as we like to reduce the score toward zero.

Answer 11

Wolfram Language (Mathematica), score \$ \to 0 \$

abcdef-abcdef+Null

Try it online!

Similar to the Ruby answer, add arbitrarily more letters to abcdef in both places to achieve a lower and lower score, asymptotically approaching zero. (with \$ n \$ letters, the score is \$ \frac {16}{315+92n} \$). Thanks Mathematica for no limits to variable names! The example shown here has a score of \$ \frac 2 {95} \approx 0.0210526 \$. With 1 million letters, the score would be \$ \approx 0.000000173912 \$.

The charset is 0x20 to 0x7F, printable ASCII, though there is nothing stopping any characters being input.

The 16 exceptions, in no order, include multiplying by one, replacing subtraction with adding a negative, and calling the local namespace:

+abcdef-abcdef+Null
`abcdef-abcdef+Null
 abcdef-abcdef+Null
1abcdef-abcdef+Null
abcdef+-abcdef+Null
abcdef -abcdef+Null
abcdef-+abcdef+Null
abcdef-`abcdef+Null
abcdef- abcdef+Null
abcdef-1abcdef+Null
abcdef-abcdef;+Null
abcdef-abcdef +Null
abcdef-abcdef+ Null
abcdef-abcdef+1Null
abcdef-abcdef+Null;

Other attempts included (0.0740741):

Quiet[0/0,{Power::infy,Infinity::indet}];

Which nicely throws an error if you mess with most of it, and (0.00126984)

If[#0==#1,,1,1]&[If[#0==#1,,1,1]&]

Which is a quine-like solution that tries to actively detect tampering.