Quickest brainfuck program to print something

A place to discuss the implementation and style of computer programs.

Moderators: phlip, Moderators General, Prelates

userxp
Posts: 436
Joined: Thu Jul 09, 2009 12:40 pm UTC

Quickest brainfuck program to print something

Postby userxp » Tue Dec 22, 2009 11:10 pm UTC

I had this doubt some time ago: How can we find the Brainfuck program that outputs a certain sequence of characters/numbers in the shortest possible number of operations?
For example, the quickest program to print value 100 is:

Code: Select all

++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.

Note: this is about the fastest program, not the shortest program.

To recall, brainfuck has 8 operations:
[] : loops
>< : increase/decrease pointer
+- : increase/decrease value
,. : input/output
Loops count as two instructions and are not really necessary to print a string, so they can be left out. Input is also unnecessary here.

The fastest way to output value n is n times "+" followed by ".", but when printing multiple values it gets more difficult. The simplest way to do it is "print n1, next cell, print n2, next cell, print n3..." but this is obviously not the fastest way, for example, printing 4,5,6 would be:

Code: Select all

++++.>+++++.>++++++.

I tried the following algorithm:

Code: Select all

For each character:
   Find quickest cell to use (distance to cell+value difference)
   Move to that cell
   Output character

So 4,5,6,10,1,9 is:

Code: Select all

++++.+.+.++++.>+.<-.
Which much more efficient, but still not perfect. You can see it with the following example: 6,10,6,10,6,10,6,10,6,10

Code: Select all

++++++.++++.----.++++.----.++++.----.++++.----.++++.
vs
++++++.>++++++++++.<.>.<.>.<.>.<.>.


My ideas were some sort of statistical analysis or an evolutive algorithm, but I wondered If there was a simple algorithm to find the quickest program other than brute-forcing. (I have the feeling it is NP-complete)

_THE_PLAGUE
Posts: 1
Joined: Wed Jun 29, 2011 4:26 pm UTC

Re: Quickest brainfuck program to print something

Postby _THE_PLAGUE » Wed Jun 29, 2011 4:33 pm UTC

To print 100:

++++++++++[>++++++++++<-]>.

Generally to print N, go:

(NUMBER OF + SIGNS EQUALS SQUARE_ROOT_OF_N)[>(NUMBER OF + SIGNS EQUALS SQUARE_ROOT_OF_N)<-]>.

So, if N = 100, basically I count 10 a total of 10 times to get 10 * 10 = 100.

Program length (including output char): 2*SQUARE_ROOT_OF_N + 7

(in the case of printing 100, program length is 27 chars).

This does not obviously work of N has a non-integer square root. :-)

User avatar
phlip
Restorer of Worlds
Posts: 7535
Joined: Sat Sep 23, 2006 3:56 am UTC
Location: Australia
Contact:

Re: Quickest brainfuck program to print something

Postby phlip » Thu Jun 30, 2011 5:38 am UTC

_THE_PLAGUE wrote:Program length (including output char): 2*SQUARE_ROOT_OF_N + 7

(in the case of printing 100, program length is 27 chars).

userxp wrote:Note: this is about the fastest program, not the shortest program.

Your program may be shorter than a simple +++etc+++. but it will take a longer time to run.

Code: Select all

enum ಠ_ಠ {°□°╰=1, °Д°╰, ಠ益ಠ╰};
void ┻━┻︵​╰(ಠ_ಠ ⚠) {exit((int)⚠);}
[he/him/his]

Patagonicus
Posts: 1
Joined: Sun Jul 03, 2011 5:04 pm UTC

Re: Quickest brainfuck program to print something

Postby Patagonicus » Sun Jul 03, 2011 5:55 pm UTC

The problem is that the decision which cell to use depends on the following numbers (and, of course, on the previous numbers). I had some ideas but they all turned out to be flawed. Can't think of anything better than brute-forcing right now. But we can rule out loops as they always use more instructions than the unrolled version and no user interaction is need (= all loop conditions can be evaluated at "compile" time and can be eliminated)

Oh, and by the way:

Code: Select all

++++++.++++.>++++++.<.>.<.>.<.>.<.

This uses one instruction less to print 6,10,6,10,6,10,6,10,6,10 than the version you provided as there is one movement of the memory pointer less.

Ankit1010
Posts: 135
Joined: Fri Feb 11, 2011 11:32 am UTC

Re: Quickest brainfuck program to print something

Postby Ankit1010 » Mon Jul 11, 2011 3:34 pm UTC

On a side note, anyone have a clue on how to prove that this is NP-complete if it is?

Proving the first condition, that it is in NP is easy enough, since we can verify the solution in [imath]O(n)[/imath] time where [imath]n[/imath] is the length of the program.

Proving that some other NP-complete problem reduces to this.. thats hard.


Return to “Coding”

Who is online

Users browsing this forum: No registered users and 7 guests