15
\$\begingroup\$

It's a funny accident that this world happens to have just 1 time dimension, but it doesn't have to be like that. It's easy to imagine worlds with 2 or more time dimensions, and in those worlds you could build computers and run software on them, just like in this one.

The System

Here is a system for running Brainf*ck programs in two time dimensions:

The two time dimensions are x and y. Each Brainf*ck program consists of an x half-program, and a y half-program, e.g., a program could be

x: +>+
y: [-]

The two half-programs each have their own program pointer, but they share a single tape pointer (that is, they both operate on the same cell of the tape).

Time is 2-dimensional, so it consists of a grid of moments:

A 3x3 grid of times, connection by x and y actions

Moving along the x dimension, the x half-program executes one time step. Moving along the y dimension, the y half-program executes one time step.

So, for example, let's say the tape starts out as [0] 0 0 ([] represents the tape pointer) and the x/y programs are + and ->-. The execution of this program would look like this:

x y  tape         x-action  y-action
0 0  [ 0]  0   0   + at 0    - at 0
1 0  [ 1]  0   0   (done)    - at 0
0 1  [-1]  0   0   + at 0    move >
1 1  [ 0]  0   0   (done)    move >

Notice that, as time moves in the y direction, the x half-program keeps doing the same thing over and over, because its time does not progress.

The tape at each moment includes the cumulative effect of all actions that feed into it (each action counts once). So, for example, the tape at time (2, 1) contains the cumulative effect of:

Which actions feed into a tape snapshot, as listed below

  • the x-action from (0, 0)
  • the x-action from (1, 0)
  • the x-action from (0, 1)
  • the x-action from (1, 1)
  • the y-action from (0, 0)
  • the y-action from (1, 0)
  • the y-action from (2, 0)

Cumulative means:

  • All the increments and decrements to a cell sum together.
  • All the left (-1) and right (+1) movements to the tape pointer sum together.

Instruction pointers do not accumulate. Each half-program gets its instruction pointer from the previous moment in its dimension. That is, x program pointers progress only in the x dimension, and y program pointers progress only in the y dimension. So, for example, in the program ([], +) starting from [0] 0 0, the execution would be

x y  tape   x-action  y-action  x-prog-ptr        y-prog-ptr
0 0  0 0 0            + at 0    0                 0
1 0  0 0 0            + at 0    2 (from jump)     0
0 1  1 0 0                      0                 1
1 1  2 0 0                      1 (from NO jump)  1

Some more moments from the above (+, ->-) simulation are:

x y   tape          x-action  y-action  x-prog-ptr y-prog-ptr
0 0   [ 0]  0   0   + at 0    - at 0    0          0
1 0   [ 1]  0   0             - at 0    1          0
2 0   [ 1]  0   0             - at 0    1          0
0 1   [-1]  0   0   + at 0         >    0          1
1 1   [ 0]  0   0                  >    1          1
2 1   [-1]  0   0                  >    1          1
0 2    -1 [ 0]  0   + at 1    - at 1    0          2
1 2     0   1 [ 0]            - at 2    1          2
2 2   [-1]  1   0             - at 0    1          2

The Brainf*ck operators allowed are the following (they have their standard meaning):

  • +, -: increment, decrement;
  • [, ]: loop until zero (processing a [ or ] takes one time-step, as in standard Brainf*ck);
  • <, >: move left/right on the tape.

Complex Example

For the program (>, +) starting with [0] 0 0:

x y   tape          x-action  y-action  x-prog-ptr y-prog-ptr
0 0   [ 0]  0   0        >    + at 0    0          0
1 0     0 [ 0]  0             + at 1    1          0
0 1   [ 1]  0   0        >              0          1
1 1     1   1 [ 0]                      1          1

For (+, -) starting with [0] 0 0:

x y   tape          x-action  y-action  x-prog-ptr y-prog-ptr
0 0   [ 0]  0   0   + at 0    - at 0    0          0
1 0   [ 1]  0   0             - at 0    1          0
0 1   [-1]  0   0   + at 0              0          1
1 1   [ 0]  0   0                       1          1

Note that the tape ends as [0] 0 0 because each + and - happens twice, summing to 0.

For the program (>+, [-]) starting with [0] 0 0:

x y   tape          x-action  y-action  x-prog-ptr y-prog-ptr
0 0   [ 0]  0   0        >              0          0
1 0     0 [ 0]  0   + at 1              1          0
2 0     0 [ 1]  0                       2          0
0 1   [ 0]  0   0        >              0          3
1 1     0   0 [ 0]  + at 2              1          3
2 1     0   1 [ 1]            - at 2    2          1
0 2   [ 0]  0   0        >              0          3
1 2   [ 0]  0   0   + at 0              1          3
2 2   [ 1]  1   0                       2          2

Diagram with Arrows

The below diagram shows how to calculate the actions and the tape:

Diagram with arrows showing how parts of the program are calculated

The Puzzle

Write a 2D Brainf*ck program (with an x half-program and a y half-program) to run on a 3-cell tape, that satisfies both the following conditions:

  • If the tape starts as [0] 0 0, at time (5, 5) it has a 0 in the zeroth cell.
  • If the tape starts as [1] 0 0, at time (5, 5) it has a 0 in the zeroth cell.

Shortest program meeting the requirements wins.

\$\endgroup\$
15
  • \$\begingroup\$ Just to verify: What's the result of running + and >? If it's 1 1 [0] (pretty crazy but it's what the spec seems to suggest), How do instruction pointers combine? If the two threads are + and [], then at 1 2 the data tape would be [3], but is the second instruction pointer inside the loop ([]+ path), or outside ([+] path) or even illegal(+[])? \$\endgroup\$ Apr 6 '17 at 17:07
  • \$\begingroup\$ @JanDvorak Ah, I think I see what you're asking. I forgot to add the each program gets its instruction pointer from the adjacent moment in its dimension. I'll edit that in, and try running (+, >) to see if I get the same result as you. \$\endgroup\$
    – Owen
    Apr 6 '17 at 17:10
  • \$\begingroup\$ This is a nice challenge but it needs an objective winning criterion to be able to rank answers. \$\endgroup\$ Apr 6 '17 at 17:11
  • 3
    \$\begingroup\$ The challenge still isn't really clear to me. How exactly does time progress through the grid. According to your graphic it seems that I can arrive at (1,1) through either (1,0) or (0,1), but it one program starts with > and one starts with +, then surely their relative order matters? \$\endgroup\$ Apr 6 '17 at 17:20
  • 2
    \$\begingroup\$ Uh what. I think we need a chatroom. \$\endgroup\$ Apr 6 '17 at 17:37
8
\$\begingroup\$

4 bytes total: ([-], >)

I wrote a brute-forcer to find the smallest such program.

Here are the diagrams of this program in action. This grids are arranged in a similar manner to the grid in the spec, with (0,0) the bottom-left corner, x-time along the x-axis, and y-time along the y-axis. The upper-right corner contains the result.

First, with a tape of 0 0 0:

|  0 ( 0)  0 |  0   0 ( 0)|( 0)  0   0 |  0 ( 0)  0 |  0   0 ( 0)|( 0)  0   0 
|([)-]       |[-]         |[-]         |[-]         |[-]         |[-]         
|>           |>           |>           |>           |>           |>           
+------------+------------+------------+------------+------------+------------
|  0 ( 0)  0 |  0   0 ( 0)|( 0)  0   0 |  0 ( 0)  0 |  0   0 ( 0)|( 0)  0   0 
|([)-]       |[-]         |[-]         |[-]         |[-]         |[-]         
|>           |>           |>           |>           |>           |>           
+------------+------------+------------+------------+------------+------------
|  0 ( 0)  0 |  0   0 ( 0)|( 0)  0   0 |  0 ( 0)  0 |  0   0 ( 0)|( 0)  0   0 
|([)-]       |[-]         |[-]         |[-]         |[-]         |[-]         
|>           |>           |>           |>           |>           |>           
+------------+------------+------------+------------+------------+------------
|  0 ( 0)  0 |  0   0 ( 0)|( 0)  0   0 |  0 ( 0)  0 |  0   0 ( 0)|( 0)  0   0 
|([)-]       |[-]         |[-]         |[-]         |[-]         |[-]         
|>           |>           |>           |>           |>           |>           
+------------+------------+------------+------------+------------+------------
|  0 ( 0)  0 |  0   0 ( 0)|( 0)  0   0 |  0 ( 0)  0 |  0   0 ( 0)|( 0)  0   0 
|([)-]       |[-]         |[-]         |[-]         |[-]         |[-]         
|>           |>           |>           |>           |>           |>           
+------------+------------+------------+------------+------------+------------
|( 0)  0   0 |( 0)  0   0 |( 0)  0   0 |( 0)  0   0 |( 0)  0   0 |( 0)  0   0 
|([)-]       |[-]         |[-]         |[-]         |[-]         |[-]         
|(>)         |(>)         |(>)         |(>)         |(>)         |(>)         
+------------+------------+------------+------------+------------+------------

Now with a tape of 1 0 0:

|  1 ( 0)  0 |  1   0 ( 0)|( 0)  0   0 |  0 ( 0)  0 |  0   0 ( 0)|( 0)  0   0 
|([)-]       |[-]         |[-]         |[-]         |[-]         |[-]         
|>           |>           |>           |>           |>           |>           
+------------+------------+------------+------------+------------+------------
|  1 ( 0)  0 |  1   0 ( 0)|( 0)  0   0 |  0 ( 0)  0 |  0   0 ( 0)|( 0)  0   0 
|([)-]       |[-]         |[-]         |[-]         |[-]         |[-]         
|>           |>           |>           |>           |>           |>           
+------------+------------+------------+------------+------------+------------
|  1 ( 0)  0 |  1   0 ( 0)|( 0)  0   0 |  0 ( 0)  0 |  0   0 ( 0)|( 0)  0   0 
|([)-]       |[-]         |[-]         |[-]         |[-]         |[-]         
|>           |>           |>           |>           |>           |>           
+------------+------------+------------+------------+------------+------------
|  1 ( 0)  0 |  1   0 ( 0)|( 0)  0   0 |  0 ( 0)  0 |  0   0 ( 0)|( 0)  0   0 
|([)-]       |[-]         |[-]         |[-]         |[-]         |[-]         
|>           |>           |>           |>           |>           |>           
+------------+------------+------------+------------+------------+------------
|  1 ( 0)  0 |  1   0 ( 0)|( 0)  0   0 |  0 ( 0)  0 |  0   0 ( 0)|( 0)  0   0 
|([)-]       |[-]         |[-]         |[-]         |[-]         |[-]         
|>           |>           |>           |>           |>           |>           
+------------+------------+------------+------------+------------+------------
|( 1)  0   0 |( 1)  0   0 |( 0)  0   0 |( 0)  0   0 |( 0)  0   0 |( 0)  0   0 
|([)-]       |[(-)]       |[-(])       |[-]         |[-]         |[-]         
|(>)         |(>)         |(>)         |(>)         |(>)         |(>)         
+------------+------------+------------+------------+------------+------------

There were a couple things that weren't clearly explained in the spec, such as the fact that the 3-cell tape wraps around.


As a bonus, here is the visualization of the (>+, [-]) example:

|( 0)  0   0 |( 0)  0   0 |( 1)  1   0 
|(>)+        |>(+)        |>+          
|[-]         |[-]         |[-(])       
+------------+------------+------------
|( 0)  0   0 |  0   0 ( 0)|  0   1 ( 1)
|(>)+        |>(+)        |>+          
|[-]         |[-]         |[(-)]       
+------------+------------+------------
|( 0)  0   0 |  0 ( 0)  0 |  0 ( 1)  0 
|(>)+        |>(+)        |>+          
|([)-]       |([)-]       |([)-]       
+------------+------------+------------

And one of the (>+, +>) example:

|( 1)  0   0 |  1   1 ( 0)|  1   3 ( 1)
|(>)+        |>(+)        |>+          
|+(>)        |+(>)        |+(>)        
+------------+------------+------------
|( 0)  0   0 |  0 ( 0)  0 |  0 ( 1)  0 
|(>)+        |>(+)        |>+          
|(+)>        |(+)>        |(+)>        
+------------+------------+------------

Note that the upper-right corner is different than what you have listed, I think this is an error in your example because my code matches every other example I've tried.

\$\endgroup\$
1
  • \$\begingroup\$ This is amazing! You may well be right about the error. I will check it again. \$\endgroup\$
    – Owen
    Feb 10 '18 at 21:04

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.