Question

What would be a very rough approximation of the ratio of the number of compilable C++ code to the number of possible character strings of length N? Character set includes all possible characters allowed in C++.

Example:
swapTwo ("ABCDEFGH") ➞ "CDABGHEF"

Answer 1

Answer:

A string can be treated as an integer, a 1,000 byte program can be though of as a just a very wide integer.

So we have two sets of strings, Legal and not Legal.

Being numbers they can of course be ordered and counted. Thus there is the first illegal program, second, etc.

Counting is the process of mapping an integer to a set. We could if we chose count a set by only using the even numbers, odd numbers, primes, or numbers that end in the digit 7.

I choose to count the illegal programs by using the very wide integers that you get by treating legal programs as an integer.

int a;

is a valid C++ program, arguably the first.

I map it to the illegal program

a

So I have a counting a bit like this

int a; -> a

int b; -> b

int c; -> c

…

for (I=0;i!=0;++I) - >dfgfgt^4

and so on.

So for any illegal program I can provide an illegal program so that allows me to count to it in this curious counting sequence.

Another way is to imagine that I use some form of Map class, whre the key is the code.

For me to say one set is bigger than another I must specify that I run out of the set of legal programs before I run out of the set of legal programs.

Or vice versa.. .

For instance, my set of fingers is bigger than my set of noses, because I find a finger that does not have a corresponding nose.

However the C++ standard does not set a maximum length for a legal program,.

This means the set of legal programs is infinitely large.

I can generate a set of illegal programs by taking each member of the set of legal programs and adding something which makes it illegal.

That set is also infinite because it’s based on an infinite set.

So the set of illegal programs is also infinite.

That means that for each set I can order and count them with each other. I have as above an infinite number of noses and an infinite number of fingers to count them with.

There can be no illegal or illegal program that does not have a count in the other set.

Thus the sets are the same size.

Since they are the same, dividing one by the other gives a ratio of 1.