Brainf*** code golf challenge - write a Brainf*** program that searches for the first non-zero cell

2

The challenge is to write a brainf*** program that searches sequentially through memory for the first NON-zero cell.

The program should start somewhere in fairly low memory (there will probably be some overhead/counters/etc.). Once the program starts checking cells, it should continue to the right, checking every cell in sequence until it reaches the first non-zero cell, then stop.

Testing will be performed for several random cells and values. Examples might look like: m(13) = 1, or m(144) = 137, or m(983) = 231. The actual values will be randomly generated once and used for all entries. The cell values of 1 and 255 will also be tested.

Scoring - different from the usual
- code golf, lowest score wins
- in the case of a tie, earlier entry wins
- any continuous series of identical commands that changes pointer position or cell value counts as 1 point.

>                           1 point  
> >                         1 point  
> > > > > > > > > > > > > > > > > > > > > > > > > > 1 point  
< < < < < < < < < < <       1 point  
+ + + + + +                 1 point  
- -                         1 point  

[       opening a loop = 1 point  

]       closing a loop required, so 0 points  

one point for EACH input or output  
. .             2 points  
. . . . . .     6 points  
,               1 point  
, ,             2 points (not that anyone would ever do this)  

The python 3 program I will use for scoring is found here:
http://pastebin.com/RJi72BHa

a62

Posted 2015-08-10T15:57:36.197

Reputation: 67

4Welcome to PPCG. We tend to prefer challenges that are not language specific. The language restriction means this challenge has a most definite shortest answer, which is rather limiting. Also I'm a little confused by the idea of a brainfuck program searching memory. Brainfuck is normally run as a virtual machine whose memory is set to all zeroes at the start. Do you have or know of a brainfuck interpreter that allows data to be poked into the memory before running? also, where in the memory can the submitted brainfuck program store its own variables? – Level River St – 2015-08-10T16:03:50.677

Thanks for your questions. I knew this one would be a confusing one to ask. So I will try to clarify. This question only makes sense for BF, any other language and it wouldn't be an issue. What got me wondering about this is: you have probably seen the simple example of BF code [>] that is go through memory and stop on the first zero cell. Well I wanted to write the opposite version. Go through memory with an unknown series of zero cells and stop on the first non-zero cell. As for testing programs, I will place a random value (1-255) somewhere in a random cell. All of the cells before it ... – a62 – 2015-08-10T16:16:09.100

...will be zero. So a valid program will start at the first available cell (to the right of the program itself) and if zero, continue checking to the right, maybe for hundreds of cells, until the first non-zero cell is found. – a62 – 2015-08-10T16:17:11.403

Also, this is regular vanilla BF, so where you store your variables? That's what BF is all about. – a62 – 2015-08-10T16:19:49.610

Do you want it to output the first non-zero cell, or just find it? Can it change the value there, or must it remain the same? Does the state of the tape at the end matter at all, or is the position of the pointer the only thing that matters? – BrainSteel – 2015-08-10T16:37:11.413

@BrainSteel the location of the first non-zero cell would be more relevant, but that's a way, way more difficult problem. And it would need some boundaries on how long the memory was. – Level River St – 2015-08-10T16:46:57.077

3

@vihan Consensus is that we do not censor language names. Brainfuck is the correct name for this language, and it is only profane if you insist on viewing it that way. In any case the profane part of the name is not insulting to any particular group, so should not cause offence among adults. http://meta.codegolf.stackexchange.com/q/1136/15599 . This type of censorship makes the questions less searchable. Anyway I have decided not to roll back your edit as it would be yet another pointless edit, but please bear this in mind in future.

– Level River St – 2015-08-11T05:14:53.403

@steveverrill Although it is not offensive for humans, entreprises' proxies (word blacklist) happen to find it offensive, which means the page can't be accessed without overpassing security... – Thrax – 2015-08-25T12:11:38.313

1@Thrax that point was mentioned in one of the answers to the meta question I linked. I'm still against censoring it. You shouldn't be using your work computer to access Programming Puzzles and Code Golf anyway. I never do ;-) – Level River St – 2015-08-25T13:13:59.203

Do we just have to move the pointer to the first non-zero cell, or do we have to do something special to it? – ASCIIThenANSI – 2015-08-25T18:06:24.837

Answers

6

11 24 Points

Edit: Now, we do not change the value that is there and do not output it. This now behaves as expected for 255 as well.

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

This program searches for the first non-zero byte and exits. We expect the first value pointed at to be 0, and we require that the pointer be at least at cell 1 to begin with ("The program should start somewhere in fairly low memory"). Here's a little test, no funky interpreter required:

[ Search for the first non-zero cell            ]
[ http://codegolf.stackexchange.com/q/54432/31054   ]

[We require moving one cell to the right from the left end ] >

[Testing code: ]
>>>>>>>>> [... any number of > ...] >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
[ASCII code '0'] ++++++[-<++++++++>]
<<<<<<<<< [... the same number of < ...] <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<


[Find it and stop:  ]
+[-[[-<<+>>]<<+>>-<]>+]-<<[->>+<<]>>



>[Output, for checking: ]<
.   

Example run:

~ Me$ bf f.bf
0

BrainSteel

Posted 2015-08-10T15:57:36.197

Reputation: 5 132

It's not entirely clear from the spec whether or not you can guarantee that the head starts at a 0-byte, but this solution will output nothing if the head starts at a 255 byte. – ymbirtt – 2015-08-10T21:09:39.320

@ymbirtt Yeah, I noticed that. I'm still not entirely sure what should be output (if anything) anyway, so I decided to leave it unless a62 told me it was broken. I may make a longer solution for all the edge cases when I have time. – BrainSteel – 2015-08-10T21:54:06.603

Nothing needs to be output or input, just find. The description in the code section is just to explain how the scoring works. – a62 – 2015-08-11T04:32:00.500

The value should not change the value once it is found. – a62 – 2015-08-11T04:32:19.203

The location of the pointer will be examined when the program ends, it should be on the cell with the non-zero value. – a62 – 2015-08-11T04:32:35.427

Boundaries - there should be no inherent limit for how far it can search. – a62 – 2015-08-11T04:32:51.787

@a62 Is there a guarantee that the initial value pointed to is 0? – BrainSteel – 2015-08-11T04:34:57.117

@BrainSteel and ymbirtt, sorry, I misunderstood, Ideally the program would stop immediately if it started actually on a cell with a non-zero value, but it is acceptable if the program requires at least one zero cell. – a62 – 2015-08-11T04:44:27.500

1

@a62 regarding "the value shound not change the value once it is found": this was not stated anywhere when this answer was posted, and still isn't edited into the question. This very clever answer was valid according to the rules at the time. Changing or adding rules is considered bad form. This actually makes writing a challenge very hard. You can post your next one at http://meta.codegolf.stackexchange.com/q/2140/15599 to try to get some feedback before posting.

– Level River St – 2015-08-11T05:47:44.820

@a62 Please edit the question to clarify these rules. Since I have the only answer, I will happily edit the answer to comply with these new rules, so little damage is done. – BrainSteel – 2015-08-11T14:54:44.580

I did not specify in the original description that something should be printed or that the value can change, and yet these are points of confusion. It is difficult to anticipate how things will be interpreted. I expected that most of the confusion would be about my unique scoring method, but no problem there. In the event that I create another challenge, I will certainly make use of that link to get feedback. – a62 – 2015-08-11T18:20:30.920

Since it is bad form to change the rules after submitting a challenge I'm going to have to go with not changing the original spec. This reverses a couple of the 'clarifications' I made. Result: If you wrote a program that you feel covers the specs, then it will be acceptable. – a62 – 2015-08-11T20:21:20.460

4

Command count: 12
Golf score: 10
+[-[<-<]>+]>
This is my first attempt for a Brainfuck program
This seems to work fine. the program was inspired from the answer of Brainsteel(Though seems to be highly optimized and hardly the same program)
My first attempt(Without brainsteels answer also it solves the negative 1 problem in brainsteel and my answer) was:
+[>[[<+>-]>]<[->+<]>]<<[->+<]>-
With Command count: 31
Golf score: 25

spidersanghvi

Posted 2015-08-10T15:57:36.197

Reputation: 41

2

18 bytes, 15 points

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

Code requires to have at least two 0s before searched value. It finds any number, even -1 and doesn't change it.

CoffeeCloud

Posted 2015-08-10T15:57:36.197

Reputation: 31

1

12 bytes, 8 points

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

  • Does not change the non-0 cell value
  • Does not work if the non-0 cell is the 1st or 2nd cell
  • Stops on the second cell before the non-0 cell (e.g. [][][pointer][][non-0][][])

or... +[-->>[<]<+]>> (14b 9pts) which will stop on the non-0 cell

Quelklef

Posted 2015-08-10T15:57:36.197

Reputation: 441

0

Here is my attempt. After doing it, I see that it is similar to other entries.

+[-[[-]>-<]>+]<   has 15 commands not including part that puts number in memory

             does not maintain original value
             stops at P for value 1~254
             stops at P-1 for value = 255

Satic Acar

Posted 2015-08-10T15:57:36.197

Reputation: 1