Busy Brain Beaver reboot

6

1

Introduction

I found a really interesting puzzle it was called Busy Brain Beaver. But it has been 3 years since the latest activity and there are some things I didn't like about it. So I decided to make a new one.

The Rules

I want this one to be more brainfuck focused:

  • Your goal is to make a brainfuck program that outputs the biggest number.
  • It has to output that number in finite time so you can't say +[+]. outputs infinity (it doesn't have to terminate ex: +.[+] is OK)
  • Your program can only be 500 useful characters(non-brainfuck characters don't count)
  • You can assume . outputs your number (in decimal notation).
  • Only the first output counts (so you can't say +[+.] outputs infinity)
  • You can't ask for input so , is ignored
  • This takes place in a special brainfuck environment:
    • There are an infinite amount of cell to the left and to the right.
    • All cells start at 0
    • All cells can hold any integer (so - at 0 becomes -1)
  • Give an approximation (lower bound) for which number your program would output (given an arbitrarily finite time) (if you are using a special notation please say which one or provide a link)
  • An explanation of your algorithm would be appreciated. (posting the formatted and commented version will be appreciated too)

Not a duplicate

It was marked as a possible duplicate of Largest Number Printable I think this is different because:

  • This question is brainfuck focused. And in largest number printable brainfuck isn't even allowed. Yes they are both a busy beaver. But if you think these two are duplicates then any two busy beavers are duplicates. The difference between a brainfuck contest and a non-brainfuck contest is really big. And before it got closed people seemed to have a lot of interest in this one.
  • The goal here is to output a long number not a lot of bytes

Leader Board (top 10)

  1. Gabriel Benamy 2↑↑↑411
  2. Mike Bufardeci 4277772 = 163*(162*162)
  3. fejfo 60762 = 246*247

fejfo

Posted 2016-12-19T13:52:47.933

Reputation: 359

Question was closed 2016-12-19T21:34:47.853

5I think without a character limit this is too broad because no matter what the current best answer is, I can copy it and add one + to the end to get an even better score. If recommend removing the section about "alternative goal" and adding a character limit. – James – 2016-12-19T14:06:20.670

1

I find the sandbox very useful for getting feedback on challenge ideas to fine tune them before posting.

– trichoplax – 2016-12-19T14:38:53.360

4

@mbomb007, a better dupe target is http://codegolf.stackexchange.com/q/18028/194

– Peter Taylor – 2016-12-19T14:41:58.470

1I didn't know of the sandbox. Is it to late to use it now and post an edited question later? – fejfo – 2016-12-19T14:42:46.863

+++++++[>+++++++<-]>.......................... etc til 500 instantly wins surely (or something close to it) Just tested it and got an output of 480 1s in a row – Alfie Goodacre – 2016-12-19T14:44:30.433

1@fejfo No. Feel free to post in there and edit this question after, or post a new one if its significantly different. – mbomb007 – 2016-12-19T14:44:43.773

Would just like to mention that the modifications to brainfuck you are describing are very similar to P''.

– Post Rock Garf Hunter – 2016-12-19T15:14:35.433

@Alfie Goodacre the goal is not to have as many ones in a row as possible but to get the lagest number. And if I understand your code correctly it only outputs 7777777....7 that's easily beatable. – fejfo – 2016-12-19T15:21:07.517

@fejfo I was pointing out the lack of clarity, as far as I am concerned the number 1.1(recurring)e479 is a pretty big number – Alfie Goodacre – 2016-12-19T15:25:12.483

@AlfieGoodacre 1.1(recurring)e479 is beated by something like 3↑↑4 (3^7,625,597,484,987 and I made a program for chained arrow notation – fejfo – 2016-12-19T15:29:44.467

Relevant – Gabriel Benamy – 2016-12-19T16:36:35.180

What counts as the number? The output (1 is 49), or the value for the pointer (0x01 is 1)? – user41805 – 2016-12-19T16:52:40.243

@KritixiLithos With output number I meant the value of the cell where the pointer is at the . comment – fejfo – 2016-12-19T17:03:01.947

2

At this point, anything higher than what I provided will be purely theoretical, but you can test your algorithms by converting everything to COW and testing it here. + = MoO, - = MOo, < = mOo, > = moO, [ = MOO, ] = moo, . = OOM

– Gabriel Benamy – 2016-12-19T19:47:38.367

I suggest using this stack snippet for the leaderboard even though it may not work with the theoretical answers that will surely roll in.

– Mike Bufardeci – 2016-12-19T19:50:53.150

@MikeBufardeci does it work with arrow notation ect? – fejfo – 2016-12-19T19:55:16.913

@GabrielBenamy does COW need a space between commands? – fejfo – 2016-12-19T19:56:29.307

No, spaces are considered comments. – Gabriel Benamy – 2016-12-19T19:59:35.543

@fejfo I can't imagine it does, but I'm sure you could modify it to compare arrow numbers to each other, and assume that any number with an arrow is larger than a number without. – Mike Bufardeci – 2016-12-19T20:00:54.907

@MikeBufardeci it's probebly not worth the time to update the code every time a new notation is used. I think I will just keep updating it regularly. – fejfo – 2016-12-19T20:04:09.600

@fejfo I hope that arrow notation will be sufficient for all answers but it is up to you to decide how to update the scoreboard. – Mike Bufardeci – 2016-12-19T20:07:41.160

@GabrielBenamy I tried to get the converting too cow thing but I can't get it to work not sure if it is because I made a mistake or if the program simply takes to long to complete – fejfo – 2016-12-19T20:28:38.527

Here's my answer with two leading + signs – Gabriel Benamy – 2016-12-19T20:53:17.890

@trichoplax why was this closed? Didn't I make clear why it was different? – fejfo – 2016-12-21T14:03:16.773

@Peter Taylor can I just ask you all why you think this is a duplicate? (So you can explain to me how Largest Number Printable removes the need for my contest or I can explain to you why it is necessary) – fejfo – 2016-12-21T14:12:38.073

@Easterly Irk can I just ask you all why you think this is a duplicate? (So you can explain to me how Largest Number Printable removes the need for my contest or I can explain to you why it is necessary) – fejfo – 2016-12-21T14:12:49.830

@george can I just ask you all why you think this is a duplicate? (So you can explain to me how Largest Number Printable removes the need for my contest or I can explain to you why it is necessary) – fejfo – 2016-12-21T14:13:02.723

@Flp.Tkc can I just ask you all why you think this is a duplicate? (So you can explain to me how Largest Number Printable removes the need for my contest or I can explain to you why it is necessary) – fejfo – 2016-12-21T14:13:13.480

@Mego can I just ask you all why you think this is a duplicate? (So you can explain to me how Largest Number Printable removes the need for my contest or I can explain to you why it is necessary) – fejfo – 2016-12-21T14:13:20.713

Where on Earth do you get the idea that BF is prohibited in the earlier question? – Peter Taylor – 2016-12-21T14:37:01.423

1@Peter Taylor "You can use any language in which digits are valid characters (so that not using them is a real restriction);" – fejfo – 2016-12-21T15:29:38.720

@PeterTaylor And with only a 100 bytes brainfuck is completely useless compared to other languages. – fejfo – 2016-12-21T15:39:20.100

Since the restrictions in the previous challenge don't apply to BF, I can see why this might be seen as a duplicate, since it appears all the answers here could be posted there. However, since you pointed out that languages without numbers are explicitly forbidden in that challenge, it seems that either that restriction should be removed or this challenge should be reopened. I'm not sure which makes more sense. – trichoplax – 2016-12-21T15:48:16.440

@trichoplax I think reopening this one makes more sense because the other one has a a limit of 100 bytes which would have to be raised which would make all the answer that were already given useless. (And brainfuck is useless against higher level languages) – fejfo – 2016-12-21T16:09:38.003

1@trichoplax, removing the restriction makes more sense. Firstly, because it's so badly worded that I thought it was intended to say "This question doesn't ban languages which can use digits" rather than "This question bans languages which don't use digits". Secondly, because having one question for hundreds of languages which use digits and then one question per language which doesn't is a crazy asymmetry, and having two questions splitting on uses/doesn't would also be bizarre. – Peter Taylor – 2016-12-21T16:28:54.090

1Discussion on meta – Peter Taylor – 2016-12-21T16:43:16.613

Answers

9

22222222... (65536 twos) = 2↑↑↑4

Before I begin, this is not the largest number expressible using 500 bytes of New Brainfuck. It's simply where I gave up trying to wrap my head around how big the numbers were getting. This answer only uses 93 bytes and is therefore not the largest number, but it's proof of concept that mind-bogglingly large numbers are possible.

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

This is a modification of the exponentiation algorithm in Brainfuck.

This number is so large, it's almost impossible to describe in human terms. It isn't sufficient to say "the number has this many digits" because it has more digits than particles in the universe. In fact, the number of digits this number contains has more digits than the number of particles in the universe.

Let this number be x, and let f(0) = x. Recursively define f(n) = floor[log10[f(n-1)]]. The first n which is smaller than 1 googol is over 10,000.

This answer is 93 bytes.

If we removed removed a single leading +, the result would be 65536 = 2222. Removing another + gives us 4. This means that if we add another +, we would get a number tower with 2↑↑↑4 twos, which would be 2↑↑↑5. That answer would be 94 bytes. If I were to add another 406 plus signs to this, we would get 2↑↑↑411, which is mind-bogglingly big. Instead, if I were to add yet another outer loop, I could probably get something close to 2↑↑↑↑380. For the record, 2↑↑↑↑3 = 2↑↑↑4, and 2↑↑↑↑4 dwarfs 2↑↑↑4 much the same way that 2↑↑↑4 dwarfs 65536. In fact, it may just be possible to actually get close to Graham's Number using 500 bytes of brainfuck.

Gabriel Benamy

Posted 2016-12-19T13:52:47.933

Reputation: 2 827

1you can go way past Graham's number in 500 bytes. I tried to make chain arrow notation my rough draft was around 350 bytes! – fejfo – 2016-12-19T19:41:43.427

I would probably give this code credit for 2↑↑↑411 ? what does the rest think? – fejfo – 2016-12-19T19:42:53.027

Well sure, but my brain hurt and the COW interpreter didn't even print this number (which I suspect may be smaller than I thought) – Gabriel Benamy – 2016-12-19T19:43:33.607

1

4277772 = 163*(162*162)

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

As a reaction to the 60762 solution this is another simple solution. Here we multiply just like that answer but inside of another loop. I am somewhat concerned that I am interpreting this nested loop incorrectly but I think that this is correct and the output would be 4,277,772.

The loop looks like the code below except the first + is replaced with 163 +s and the other two +s are replaced with 162 +s:

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

Mike Bufardeci

Posted 2016-12-19T13:52:47.933

Reputation: 1 680

0

499

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

The naive approach, increments the starting cell 499 times before outputting that cell and terminating. I would submit a more complex answer, but there are no online testbeds for this variant of brainfuck and I do not want to post an answer that doesn't work.

Mike Bufardeci

Posted 2016-12-19T13:52:47.933

Reputation: 1 680

1I'm currently trying to set up a git hub pages for a custom interpreter. But I have never used git hub pages before so I might fail. – fejfo – 2016-12-19T17:22:14.797

I probably won't be making that interpreter since Gabriel Benamy suggested the COW interpreter and git for windows doesn't want to install. – fejfo – 2016-12-19T20:08:29.947

0

60762 = 246*247

As a reaction on the 499 solution I will do an other very simple solution it just multiplies 2 numbers

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

how it works is pretty self explanatory it uses the standard multiplication loop ++[>+++<-]>. would be 2*3 = 6

fejfo

Posted 2016-12-19T13:52:47.933

Reputation: 359