# Fair size comparison across languages with different source alphabets

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?

## migrated from codegolf.stackexchange.comSep 10 '12 at 23:23

This question came from our site for programming puzzle enthusiasts and code golfers.

• – dmckee Sep 10 '12 at 23:25
• "what is the best known upper bound on the source entropy?" -- There is no upper bound, and the lower bound of 1 bit per symbol is attained in languages such as Jot (which has only the two symbols 0 and 1, every {0,1}-string being a valid program). – r.e.s. Sep 11 '12 at 1:05
• This is a slippery slope. After a while, this gets into insane territory like people compressing their programs before counting the size, etc. Just say no. Instead, it's probably better to just go with the flow and accept that some languages are naturally more succinct than others, and that yes, they will have a golfing advantage. – Chris Jester-Young Sep 11 '12 at 12:21
• Also, for a real-life example of golfing advantage being used for military advantage, see en.wikipedia.org/wiki/Code_talker. Yes, this stuff matters. :-) – Chris Jester-Young Sep 11 '12 at 12:31
• @ChrisJester-Young "people compressing their programs before counting the size" is exactly what we're seeing with some languages that allow 8-bit strings. as much data as possible, and sometimes some code to be eval()'d, gets put in a string and then zipped up to save the empty bits in a 6-7 bit language. – Sparr Jun 26 '15 at 20:17
• @r.e.s. - For a fixed-size alphabet, it's log2(size of alphabet) bits per symbol as the upper bound. – SuperJedi224 Jun 30 '15 at 11:36
• There is a spectrum of measuring techniques. At one end, we measure pure information (think atomic-code-golf), which is language independent. At the other end we measure the information representation (measuring by characters/bytes), which is what we using for code-golf. Anything in the middle of that spectrum is optional and up to the OP – Nathan Merrill Jun 30 '15 at 16:48

Most 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 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 questions. If they don’t, they won’t.

Be certain that method X is clearly defined.

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?

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.

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.

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

• Scoring should either be pure entropy or pure code-golf. Although high-entropy languages will (when someone makes one) theoretically always win code golf, and scoring by entropy has its own problems, there's no need for anything in between--especially an answer that requires more work. (On the other hand, this will tend towards entropy as people make increasingly better compression scripts...) – lirtosiast Jul 7 '15 at 21:35
• If I've understood this correctly, this doesn't really solve the problem because I foresee a lot of PHP/CJam combos – Sp3000 Jul 8 '15 at 1:08
• @Sp3000 I don't see why that would be a problem (or at least I see it causing less of a problem than language differences cause with golf already). – trichoplax Jul 8 '15 at 5:33

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

• Defining languages is one thing, but we usually expect an actual interpreter to exist before the challenge was posted. Otherwise you can define an infinite number of languages whose source code is always empty and where the actual behaviour is encoded in a number in the language name. – Martin Ender Jun 26 '15 at 20:02
• @MartinBüttner The encoder/decoder is, as Dennis has illustrated, just a few bytes of code. You just pipe the output of that into the normal language's interpreter. It seems almost superfluous to actually implement all of the possible different encoders/decoders. – Sparr Jun 26 '15 at 20:05
• It's worth noting that this actual language definition is rather tongue-in-cheek. What I'm actually saying with all of this is "Yes, it would be fair to count code sized based on alphabet size". – Sparr Jun 26 '15 at 20:08
• I think this might be better received as a challenge type than an override for golf scores. For example, someone might choose to post a question where the winning condition takes into account the number of characters in the language, as you describe. Trying to apply the new approach to all golf questions is likely to meet with resistance. – trichoplax Jul 7 '15 at 17:30
• It's a step towards scoring based on the Kolmorogov complexity of the source code: Write code to answer the question, then write shorter code that outputs the source code that answers the question. The score is the length of the shorter code that outputs the longer code. – trichoplax Jul 7 '15 at 17:31
• @trichoplax that meta-answer idea is nifty and I might steal it for my next challenge, if I ever write one. – Sparr Jul 7 '15 at 17:42
• I've added it as an answer to see how the community feels about it. If it doesn't get heavily downvoted I'll try posting something in the sandbox to see if it survives on main. – trichoplax Jul 7 '15 at 19:06
• The result of my new answer seems to be both of our answers getting downvotes, and the question. Oh well... – trichoplax Jul 7 '15 at 19:13