Fair size comparison across languages with different source alphabets

Question

For fair comparison of codegolf solutions in languages with different source alphabets, there should be a common unit of information.

Most sizes here are expressed in "characters" or "bytes", but not all characters are created equal. A brainfuck character can only have 8 values.

The standard measure of information in information theory is a bit. A brainfuck character is better counted as 3 bits.

Syntactic constraints may further reduce the entropy of program source.

In brainfuck not all 3^n length n programs are valid, because brackets must balance. A fancier measure of information content per character would be the limit for n->infinity of

log (# valid programs of n charcters) / n

but that is generally hard to compute.

For your favorite language, what is the number of possible values of a character? And what is the best known upper bound on the source entropy?

Answer 1

Most code-golf questions clearly include the winning criteria, and one of those is usually “the shortest code in bytes wins”. I don’t believe there are any restrictions on your asking a code-golf question with a slightly different winning criterion: “The shortest code as measured by method X wins.”

Go ahead and do that. If people like it, they might imitate it in their own code-golf questions. If they don’t, they won’t.

Be certain that method X is clearly defined.

Answer 2

For fair comparison of codegolf solutions in languages with different source alphabets, there should be a common unit of information.

Define 'fair'. How do you want to count that in languages allowing the full range of utf-8 for example?

Answer 3

I think this would be permissible for languages that are literally written as binary, hex, or similar, but NOT as unary. Unary programs should be treated as if they were written in binary.

This is all unless the poster of the question says otherwise in their question description.

Answer 4

Keep the existing approach

Encourage new challenge types / scoring methods for variety and balance

I don't think a general approach to making language differences fair will work - different languages have different advantages that vary from question to question. However, having a variety of scoring methods for question posters to choose from means that in addition to standard golf questions, other questions can have a scoring method that seems to fit best.

Inspired by Sparr's unpopular suggestion for making a fair size comparison between languages with different sized alphabets, I wondered if something vaguely similar might be better received as a new challenge type / scoring method, rather than trying to apply it to every code golf question.

---

For this challenge type, you submit two pieces of source code, your primary code and your secondary code.

• Primary code solves the problem posed in the question.
• Secondary code outputs the primary source code.

Your score is the length in bytes of your secondary code, which need not be in the same language as your primary code.

---

This doesn't make any changes for standard code golf questions, just adds an alternative that some questions can use if the poster sees fit. If there are no strong objections here, I'll post an example question using this scoring method in the sandbox.

Answer 5

Well, I for one, agree in principle.

I also agree with all the obstacles to accomplishing something like this. "How are you gonna handle ...?" [shrug!]

But everyone says a thing can't be done until someone does it.

Answer 6

As of the time of posting this answer, for the purpose of the site rules about only using languages published before a question is asked, I am defining the meta-language "Simple Bit Encoding", which might be abbreviated "SBE-". This meta-language can be applied to any other language, so you might write a program in "SBE-Python" or "SBE-Brainfuck".

The meta-language is loosely defined as follows:

Given a language with a character set representable in N bits, reversibly encode an M-character program in that language as a series of M*N bits. This bitstream is the SBE-[language] program. Executing a SBE-[language] involves decoding the bitstream back to M separate characters, then the resulting string is provided to the original language's compiler or interpreter.

By convention, SBE-[language] programs are presented in their decoded format, which conveniently and coincidentally happens to be indistinguishable from the original program in the original language.

Examples:

SBE-Brainfuck is equivalent to Binaryfuck without the leading 1. Brainfuck has only 8 non-comment characters, which can be encoded as 3 bits each. A 240-byte Brainfuck program is thus equivalent to a 90-byte SBE-Brainfuck / Binaryfuck program.

Python uses 7-bit ASCII for program text (ref). A 240-byte Python program is equivalent to a 210-byte SBE-Python program.

The practical result of this meta-language definition is that any code-golf solution written in a language using a N-bit character set can claim to be a decoded representation of a SBE-[language] program that will be smaller by a factor of (8-N)/8.

EDIT: SBE-Python converter, written in CJam, thanks to @Dennis: q256b128b:c