esoforum.kidsquid.com

calamari · Last edited by calamari on Sat Nov 12, 2005 12:38 pm; edited 5 times in total

If you notice any typos, ambiguities, or problems, please let me know. Thanks a lot, and enjoy the competition. Very Happy

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

L := { aⁱ 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⁴b⁴c⁴, 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, linefeed ASCII character 10, 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 stripped code length (only counting Brainf*** instructions). 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 have provided a compliant Brainf*** interpreter at http://kidsquid.com/programs/bf/bfgolf.tar.gz or, if you prefer, http://kidsquid.com/programs/bf/bfgolf.zip. It requires an ANSI C compatible compiler. Also included is a program that strips a program of all non-Brainf*** characters. Please let me know if you run into any problems.

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. Please also include the stripped length of the program. 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.

Have fun!
calamari

lvl · Joined: 06 Nov 2005 Posts: 1

you didn't define the ASCII value of '\n'. is it 10, or 13?

Laurent

ORBAT · Guest

Isn't the "standard" interpretation supposed to be that 10 (LF) == \n?

Like anyone adheres to standards in the esoteric world anyhow :)

Keymaker · Guest

Indeed, it's not defined, but I'd say it's 10.

jix · Joined: 05 Nov 2005 Posts: 1

\n is newline
\r is carriage return

ascii defines newline as 10 and carriage return as 13... where is the problem?

ORBAT · Guest

Gotcha!

At least in C \n does NOT equal LF (10). It's implementation-specific, and when you're reading or writing a file in text mode, it translates to the implementation's native newline (CR for old Macs, CR+LF for Windozes, LF for UN*X). When you're using binary mode, it translates to LF.

The problem here is that all versions of Windows use CR+LF as their newline character, so any BF interpreter that assumes 10 to be "\n", will be caught off guard by the extra 13 that comes around the corner.

I love standards: there's so many of them

calamari · Posted: Sun Nov 06, 2005 10:33 pm Post subject:

Let's use '\n' = 10.

calamari · Posted: Sun Nov 06, 2005 11:14 pm Post subject:

I've uploaded the reference interpreter and BF stripper to http://kidsquid.com/programs/bf/bfgolf.tar.gz. Please let me know if you encounter any problems.

calamari · Posted: Mon Nov 07, 2005 12:29 am Post subject:

I've changed the reference interpreter to ignore carriage returns. This should hopefully work for both Linux and Windows.

I have also made a zip version of the archive available.

http://kidsquid.com/programs/bf/bfgolf.tar.gz
http://kidsquid.com/programs/bf/bfgolf.zip

Keymaker · Guest

Here's my first submission.

Keymaker
15f3841715a134387bc663687daf6167

(Edit by calamari: entry was approximately 570 bytes, original timestamp before I edited was 12 Nov 2005 12:33 pm)

calamari · Posted: Sat Nov 12, 2005 12:44 pm Post subject:

It seems that I forgot to request a length with entries. I've amended the rules... so any further entries will require a program length as well. Very Happy

Keymaker · Guest

Here's my second entry. I finished this one days ago, but finally got myself posting it.

Keymaker
3792badda159e66d363aec0f4b7d52e1
402 bytes

Bertram · Guest

Here's my first entry - I've finally got around to code one :)

Bertram (int-e)
f1b04426325ad75f0d06872bdd3f4481
349 bytes

Keymaker · Guest

I just knew this would happen.. Twisted Evil

Well, enjoy your abacus..

Bertram · Guest

Some hours of micro-optimization later ...

Bertram (int-e)
1aaa945c464dec3ac855434befa15a80
332 bytes

Keymaker · Guest

This entry isn't very big improvement to my previous entry; it's only two instructions smaller. Oh well, at least the amount of instructions in this one is a nice number. Cool

Keymaker
08eec49920ac38499f569c9c3feb0aae
400 bytes

Bertram · Guest

Daniel · Guest

I procrastinated as usual, but here's my first entry

Daniel Cristofani
266 bytes
d20b981fbed760f6ee25e8c0f577fda0

Guest · Posted: Mon Dec 05, 2005 5:48 am Post subject: Re: Hello.

Keymaker · Guest

Woah, now there's some byte-magick! Very Happy

Can't wait either.

Guest · Posted: Mon Dec 05, 2005 3:40 pm Post subject:

It's great to see so many entries.. I'm afraid I probably won't be able to personally enter before the deadline (I really wanted to). Too much going on.

I will be able to write up testcases and judge the entries after finals week (so basically a couple weeks from now). Or, if I have time, I'll do it sooner Smile

Good luck everyone!

calamari
Edit: hmm why I am I not logged in.. ahh well, hehe

Daniel · Guest

Second entry. By the way, this problem actually doesn't need a Turing-complete language; a language with power equivalent to a linear bounded automaton will do.

Daniel Cristofani
263 bytes
9654d61a53a7d779253113425acd1c68

Daniel · Guest

Since it's just past the deadline, here's the code for my second entry.

Daniel Cristofani
263 bytes
+>+>>+[,-[>++++<[[->]<<]<[>]>]>[-[<<<+>+>+>-]<<<-[-[-[<[-]>-]]]+++>[<->-]>[-[>]+>]>>>[>>>]+[<<<]<[-<]>+<]>]+<+<+[>>+>]<<[>+>>]<<[<<<]+<<[>>+>]>>[>>>]>+++++[<++++>>++<-]<-[<<++++++>+++++>-]<++<<-[-[-[>>.++..++.<--.++>>]]]>[.>++++.+++++.-----.--.++>>]<<<++.>.-.>>>.

Daniel · Guest

Keymaker · Guest

Woah, very nice! :) I need to inspect it a bit more to understand it fully, though. Seems we have quite a different solutions.

Here is my first entry, 574 instructions (yes, I'm embarassed):
+>>>>>+>+++<<,----------[-----<<+>+++++++++[>---------<-]+>[-<->>>>+>+<<<<[[-]<+>>>>->-<<<<]]<[<<<->>>-]>]<<[>>+<<-]+>>[-[----<+++++++++[>---------<-]>[<+<<+>>>-]<++<[>-<-]<[>+<-]+>>[-[-<<->>[->+<[-<<+>>>-<]]]]<<[-<[-]>>>>[<+>-]>>[>>]<<[[-]+<<]<[>+<-]<<]>>>[->[>>]<<[-<<]>>+<]>[>>]+>+<[<<]>],----------]>>[>>]<<[>+<[-[-[->[-]<]]]>[[-]<<<[<<]<<<<[-]>>>>>>[>>]>]<<<]<<<+<[>++++++++[<+++++++++++>-]<---.++..++.+++++++++++.++++.---------------.-.[-]++++++++++.[-]]>[+++++++++[<+++++++++++>-]<++++.-------------.+++++.-----.--.+++++++++++++++++.---------------.-.[-]++++++++++.>]

Here is my second entry, 402 instructions:
+>>>>>+>+++<<+[-[----<+++++++++[>---------<-]>[<+<<+>>>-]<++<[>-<-]<[>+<-]+>>[-[-<<->>[->+<[[-]<<+>>>-<]]]]<<[-<[-]>>>>>>[>>]<<[[-]+<<]<<<]>>>[->[>>]<<[-<<]>>+<]>[>>]+>+<[<<]>],----------]>>[>>]<<[>+<[-[-[->-<]]]>[-<<<[<<]<<<<[-]>>>>>>[>>]>]<<[-]<]<<[-]<+<[+++++++++++++++[>++++++>+++++++<<-]>.++..++.>.++++.<.-.[-]<]>[+++++++++++++[>+++++++>++++++++<<-]>>++.<+++.+++++.-----.--.>++.<++.-.<]++++++++++.

And here is the third, that is only two instructions shorter than the previous, thus 400 instructions:
+>>>>>+>+++<<+[-[-<++++++++++++[>-------<-]>[<+<<+>>>-]<++<[>-<-]<[>+<-]+>>[-[-<<->>[->+<[[-]<<+>>>-<]]]]<<[-<[-]>>>>>>[>>]<<[[-]+<<]<<<]>>>[->[>>]<<[-<<]>>+<]>[>>]+>+<[<<]>],----------]>>[>>]<<[>+<[-[-[->-<]]]>[-<<<[<<]<<<<[-]>>>>>>[>>]>]<<[-]<]<<[-]<+<[+++++++++++++++[>++++++>+++++++<<-]>.++..++.>.++++.<.-.[-]<]>[+++++++++++++[>+++++++>++++++++<<-]>>++.<+++.+++++.-----.--.>++.<++.-.<]++++++++++.

It was a nice competition overall.

Daniel, please post the picture of that abacus on your site when you receive it. :) Congratulations.

Bertram · Guest

First entry:
+>+>>+[->>>++++++++[<+++++++++++>-],----------]<[-]<+<[>-<[[<->-]+<[->->+<<[->>->+<<<]]<<]>>>>>[>>>]<[>>>]+<[>>>]+>>[<+>-]<[<->[-]]<[[[[>>>]<<<-<<<[<<<]+<<<[>>>-<<<-]>>>]<<[>>>>]>>>[>>>]<]>>[>]>>[<+>-]<[<+>-]<[>>]<[<<<]]]>>[-]>[-]++>[-]+++++++++++[<<<<+>>+++++++++>++++++++++>-]<<<[>--.++..++.>.>>[-]]<[>>>++.--<++.+++++.-----.--.++>>]<++++.<.-.<<-.

Second entry:
>+[->>>,<++++++++++[<+++++++++>>-<-]>]<<<[[[>-<-]>-[[>]+[<]>-]+[>]+<[-<]<<<]+>>>>>>>>[>>>]<[>>>]+<[>>>]+>>[<+>-]<[<->[-]]<[[[[>>>]<<<-<<<[<<<]+<<<[-<]>>>]>-<<[>>>]>>[>>>]>]>[>]>>[<+>-]<[<+>-]<[>>]<[<<<]]]>>[-]>[-]++>[-]+++++++++++[<<<<+>>+++++++++>++++++++++>-]<<<[>--.++..++.>.>>[-]]<[>>>++.--<++.+++++.-----.--.++>>]<++++.<.-.<<-.

Somewhat more formatted:

Daniel · Guest

Keymaker's algorithm was actually better than mine. And that makes me wonder if we should start a new custom: after each brainfuck contest, see if we can collaboratively find anything shorter than the winning solutions. At least, when the problem is hard enough that all submitted programs are likely to be suboptimal. Anyone want to work on improving this 252-byte program?

Keymaker · Guest

Bertram · Guest

Here's a 250 byte version:

Daniel · Guest

That's excellent. Now how about if we also reconsider the linefeed detection method... 247 bytes

Daniel · Guest

Dunno why I didn't spot this before:

Keymaker · Guest

Hehe, yeah, that has happened to me sometimes too. Very Happy

Another byte out; excellent!

About Daniel's question; yeah, it'd be very interesting to see. Personally I've got to 32 bytes;
http://bf-hacks.org/hacks/selfsize.b

Keymaker · Guest

I just got to 31 too.

Keymaker · Guest

Not sure if it's possible to get it any shorter than 31 bytes in a non-wrapping implementation. Crying or Very sad

At least I haven't succeeded in it yet, although that doesn't mean anything. Very Happy

However, with wrapping 8-bit cells it's possible to get it down to 30 bytes;