28
\$\begingroup\$

Your task is to write a piece of code that zeros the current cell in the Brainfuck variant that, each cell can contain a signed integer of arbitrarily large magnitude, instead of the normal 0 to 255.

You may assume there are l cells to the left and r cells to the right of the current cell that are initially zero. You program may only access these l+r+1 cells. After your code ends it should leave the l+r extra cells zero and the pointer to the current cell at the original position.

You may not use any input/output.

The code with smallest l+r wins. If there is a tie, the shortest code wins. It is recommended to also state the time complexity of your program for reference, where n is the absolute value of the original integer in the current cell.

Useful tools

You can test a Brainfuck program in this variation using this interpreter on TIO by mbomb007.

You can also use the interpreter in this answer by boothby (other Python answers probably also work, but I didn't test).

\$\endgroup\$
  • \$\begingroup\$ I have tagged it code-golf because I think we will reach the optimal l+r quickly. \$\endgroup\$ – jimmy23013 May 2 '17 at 15:23
  • 2
    \$\begingroup\$ It sounds like from your comment, you meant arbitrarily large magnitude integer, which may be positive or negative. This is a difference in english dialect for some people, so it might be helpful to clarify that it can be very positive or very negative. \$\endgroup\$ – isaacg May 2 '17 at 15:29
  • 4
    \$\begingroup\$ @jimmy23013 Do you have a BF interpreter with signed cells we can use for this? \$\endgroup\$ – mbomb007 May 2 '17 at 15:35
  • \$\begingroup\$ @mbomb007 codegolf.stackexchange.com/a/3085/25180 but probably too golfy... \$\endgroup\$ – jimmy23013 May 2 '17 at 15:54
  • 1
    \$\begingroup\$ @Mego Why? In the "real" challenge, you must also get the optimal l+r, which will probably make it more difficult to reduce the code size. \$\endgroup\$ – jimmy23013 May 2 '17 at 16:05
17
\$\begingroup\$

l+r = 0+2 = 2, 55 53 51 bytes

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

l+r = 1+2 = 3, 46 44 bytes

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

My own algorithm. The pointer should begin at the number that needs to be zeroed. The time complexity is O(n^2).

How it works:

  • We start with the number n.
  • We increment one, so the number becomes n+1.
  • We decrement two, so the number becomes n+1-2 = n-1
  • We increment three, so the number becomes n-1+3 = n+2.
  • We decrement four, so the number becomes n+2-4 = n-2.

We repeat the process, increasing the in-/decrement each step, until we get zero.

\$\endgroup\$
  • 2
    \$\begingroup\$ Exactly the algorithm I thought of after I got past the "this isn't even possible" stage :P \$\endgroup\$ – ETHproductions May 2 '17 at 16:14
9
\$\begingroup\$

l + r = 0 + 2 = 2; 58 bytes

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

The complexity is O(n^2).

The following is my testing program generator, so you can see that I actually tried to test it in case it doesn't work...

p='''
>+<
[
>
[<->>+<-]
>+<
<[>]>
[<<+>+>-]
<
[->+<]
>[<]>
+ [-<+>]
<<
]
> [-] <
'''

p = ''.join(p.split())

cpp = '''
#include <bits/stdc++.h>
using namespace std;
void test(int q) {
long long t[3] = {q, 0, 0};
int i = 0;
ZZZ
printf("q=%d %lld %lld %lld\\n", q, t[0], t[1], t[2]);
}
int main() {
while(true) {
    int q; cin >> q; test(q);
}
}
'''

d = {
'>': '++i; assert(i<3);',
'<': '--i; assert(i>=0);',
'+': '++t[i];',
'-': '--t[i];',
'[': 'while(t[i]){',
']': '}',
}

print cpp.replace('ZZZ', ''.join(d[c] for c in p))
\$\endgroup\$
  • \$\begingroup\$ You can test it using the interpreter I just made. See comment \$\endgroup\$ – mbomb007 May 2 '17 at 17:23
  • \$\begingroup\$ It looks like it works to me. \$\endgroup\$ – mbomb007 May 2 '17 at 17:29
  • 2
    \$\begingroup\$ This has got to be the optimal l+r. Quick proof that 1 is impossible: at each point at which the spare cell hits zero, you can only store a finite amount of data in addition to the value of the original cell (in the tape head position and instruction pointer), which means that you're limited in how far you can adjust the main cell from that point in at least one direction. \$\endgroup\$ – user62131 May 2 '17 at 17:53
  • \$\begingroup\$ @ais523 There could be other equivalent ones. It'd be interesting if someone creates l+r = 1+1. \$\endgroup\$ – mbomb007 May 2 '17 at 18:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.