This forum is closed to new posts due to low activity and a deluge of spam. It is kept online as a static historical record. If you want to read about or discuss esoteric programming languages, the Esolang wiki is the place to go. An archive of the forum is available.

BrainF*** Golf contest starting Nov 7th (4)

1 Name: calamari : 2005-11-05 22:32 ID:Oda5G9uo

Hi,

I'm starting a new BF golf contest. The goal is to accept valid input for the canonical non-context-free language L := { a^i b^j c^k : i = j = k } in as few instructions as possible. This is something only Turing complete languages are capable of.

A full description, examples, and rules can be found at:

http://kidsquid.com/phpBB2/viewtopic.php?p=387

Everyone is welcome to compete :) The forum does not require registration.

Thanks,
calamari

2 Name: Anonymous : 2005-11-05 23:56 ID:foo@bar.invalid

Why not use this forum?

Copy-pasted text:

Task
Write a BrainF*** program that accepts the language:

L := { a^i b^j c^k : i = j = k }

Where a, b, and c are the ASCII characters 'a', 'b', and 'c'.

The language accepts the set of all input strings consisting of a sequence of a's, followed by a sequence of b's, followed by a sequence of c's, having the same number of a's, b's, and c's. All other strings are rejected. It is considered the canonical example of a non-context-free (stack based) language, meaning that it may only be computed by a machine equivalent in power to a Turing machine. Since BrainF*** is Turing complete, it should be up to the task.

Examples
The string 'aaaabbbbcccc' is in the language L, as it is a^4b^4c^4, so i = 4, j = 4, and k = 4, thus i = j = k.

The string 'aaabccc' is not in the language L, as i = 3, j = 1, k = 3, and so i =/= j.

The string 'bac' is not in the language L, despite i = j = k, as it is not a sequence of a's, followed by b's, followed by c's. Similarly, 'abcabc' is not in the language L, as 'a' cannot follow 'c'.

The input 'ab' is valid input, but is not in the language L, as j = 1 and k = 0, so j =/= k. Any arrangement of a's b's and c's is valid input string, but not all strings are in the language L, as above.

The empty string '' is in the language L, as i = j = k = 0.

Input and Output
The input may be assumed to consist only of the letters 'a', 'b', 'c', and '\n' (newline character). Other input is undefined and will not be considered for the purposes of the contest.

Input consists of a string of 'a', 'b', and 'c' characters (as given in the above examples), terminated by '\n' (the newline character, NOT the characters '\' 'n'). Every string, including the empty string, must be followed by the newline character.

Once the '\n' newline character is detected, no further input may be read. It is not necessary to read all the input (for example, if a determination can be reached before the newline is encountered).

The program output must be one of: 'accepted\n' (meaning that the string was found to be in the language L) or 'rejected\n' (the string was not in the language L), where '\n' is again the newline character.

The input string may be of any length. Therefore, imposing an arbitrary limit, such as accepting a maximum of 255 a's, is unwise. It should be assumed that this will be tested with extremely long inputs.

Language details
The interpreter used will have 8-bit memory cells. Memory will be unbounded to the right (within the limits of the machine it is being run on). Programs must not wrap cell values (either by executing '-' on a cell with the value 0 or '+' on a cell with the value 255). Programs must not wrap the memory array (by executing '<' at cell 0).

Scoring
The winning entry must first be correct. If an entry does not conform to the above specification, it is disqualified.

Ranking is then by the shortest code length, not including whitespace. If two programs are tied in code length, the winner shall be the program that was submitted first.

Multiple entries are allowed. Entry corrections will require a new entry. Do not modify old entries.

Reference interpreter and code stripper
I will be providing c source code for a compliant BrainF*** interpreter shortly and will update this with a link to it when it is ready. I will also provide a c source that strips a program to only the 8 BrainF*** characters. Use of such a stripping program is recommended, as that is what the MD5 hashes will be verified against.

Contest deadline
The contest will start Monday, November 7, and end Monday, December 5, 11:59pm, and entries will be scored. Please do not post code until after the ending time. Contest entries should be posted to this thread in the form of an md5 hash. The date and time of the forum will be considered the official date and time for the contest and contest entries. Once the contest has ended, entries will be matched against their MD5 hash. Any found to be different will be disqualified.

Prizes
The contest winner will receive a free abacus by mail. It is a generic abacus with 9 rods. I reserve the right not to award the prize if there is only a single contest entry.

3 Name: Anonymous : 2005-11-06 01:37 ID:IIdsJDaH

Sounds like you're just trying to get rid of an abacus.

4 Name: calamari : 2005-11-06 06:10 ID:Oda5G9uo

Hi,

Using my forum I have a single date/time standard for entries. Also, I find this forum difficult to use and navigate :). So, while I don't really mind what you post here, the only entries I'll be scoring are the ones posted to my forum.

You're free to forfeit the abacus prize if you win. I didn't orignally offer a prize, but it was requested in #esoteric, and I thought it'd be fun. Definitely go for the challenge and fun of the contest, not just for the abacus, hehehe.

Thanks,
Jeff

This thread has been closed. You can not post in this thread any longer.