18
\$\begingroup\$

Challenge

In this challenge, we will use a language that is very similar to Brainfuck but slightly different.

  • This variant of BF does not have any input and output commands; instead, it simply takes a tape as input and modifies it until it halts. The final state of the tape is considered the output of the program.
  • The tape is infinitely long to the right, and each cell of the tape can store nonnegative integers of arbitrary size. Each cell is referred to as tape[0], tape[1], ... from the leftmost cell.
  • If the data pointer tries to go left from the leftmost cell, it is a no-op. Similarly, if a zero cell is decremented, it is a no-op. Overflow never happens.
Command Behavior
+ Increment the current cell.
- Decrement the current cell. No-op if the current cell is zero.
> Move the data pointer by one cell to the right.
< Move the data pointer by one cell to the left. No-op if the current cell is the leftmost cell.
[ Jump to the right of the matched ] if the current cell is zero.
] Jump to the right of the matched [ if the current cell is nonzero.

At the start of the program, the data pointer is at the leftmost cell, as in regular BF.

No characters other than the six commands may appear in the source code. The brackets must be balanced.

For each of the five tasks below, create a square-shaped program that solves the task when interpreted both horizontally and vertically. For example, if a submission is

+[-
>+<
-+]

the two programs would be

  • horizontally: +[->+<-+]
  • vertically: +>-[++-<]

The two code can be the same or different. The score is the side length of the square. The lowest score wins for each task. You may choose to solve just one or several of the tasks in one answer.

Task 1

  • Input: tape[0] contains an integer \$x\$, and tape[1] contains an integer \$y\$, such that \$x \ge y\$. All the other cells are zero.
  • Output: tape[0] must contain the value of \$x - y\$. The other cells may contain any value.

Task 2

  • Input: tape[0] contains an integer \$x\$. All the other cells are zero.
  • Output: tape[0] must contain the value of \$x \operatorname{mod} 7\$. The other cells may contain any value.

Task 3

  • Input: The tape contains some random values. It is guaranteed that at least one cell is zero.
  • Output: tape[0] must contain the smallest index i such that tape[i] in the input is zero. The other cells may contain any value.

Task 4

  • Input: tape[0], tape[1], tape[2] contain integers \$m\$, \$a_1\$, \$a_2\$ respectively. \$m \ge 3\$, \$a_1, a_2 \ge 1\$. All the other cells are zero.
  • Output: tape[0] must contain the value of \$a_m\$, which is the \$m\$th value in the sequence defined by the first two terms \$a_1\$ and \$a_2\$, and the recurrence equation \$a_{n+2} = a_{n+1} + a_{n}\$. The other cells may contain any value.

Task 5

  • Input: tape[0] is zero. For some positive integer \$n\$, tape[1] through tape[n] contain positive integers. All the other cells are zero.
  • Output: tape[0] must contain the maximum of \$n\$ positive integers in the input. The other cells may contain any value.

A tester program is provided for you. Insert your BF program and change the task variable to test it.

My best scores:

  • Task 1: 3
  • Task 2: 10
  • Task 3: 7
  • Task 4: 10
  • Task 5: 9
  • In the original problem, you get 100% credit at 3/11/7/11/9 score respectively. I was able to outgolf it by 1 in tasks 2 and 4.


    Source: Estonian Informatics Olympiad 2020-2021 Open Competition, Problem 6 "Magical BF"


    If you think this is off-topic, please read the meta section of the sandbox post and leave comments.

    \$\endgroup\$

    3 Answers 3

    7
    \$\begingroup\$

    Task 2, Score: 9

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

    Attempt This Online!

    I wouldn't be too surprised if 8 was possible. I basically just solved the task in a few different ways, picked the one which seemed like it would square the best, chucked it into a 9x9 and tweaked things until it all lined up nicely. You'll note that the square is symmetric along the diagonal, so horizontal and vertical both result in the same code.

    The original code is

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

    We can see how the square code is built from the original:

    [>>+<+<-]>-<->-><<><>----[>+------<><>--<--<>+----+-++<>----]>>-<[<<+>>-]<>>>+>--
    [>>+<+<-]>-   -      ----[>  -----    --<--    ---        --]>   [<<+>>-]
    
    \$\endgroup\$
    1
    • 1
      \$\begingroup\$ Impressive work. I have never imagined a solution with exactly three pairs of brackets is possible. \$\endgroup\$
      – Bubbler
      Commented Mar 13 at 1:26
    5
    \$\begingroup\$

    Task 1, score = 3

    ><>
    [-<
    ->]
    

    Attempt This Online!

    \$\endgroup\$
    2
    \$\begingroup\$

    I will share my own solutions that are matched or outgolfed.

    Task 1, score 3

    >[-
    <->
    ><]
    

    Attempt This Online!

    This can be easily shown optimal: the shortest flattened BF program that solves the challenge is >[-<->] (7 instructions).

    Task 2, score 10

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

    Attempt This Online!

    I had to solve tasks 3 and 5 before I could finish this one. The approach I used: (spoilered for those who want to figure out themselves)

    When I failed to complete the square for Task 2, I thought this is mainly because of the parity of the number of instructions inside each loop. As I solved tasks 3 and 5, I found a trick that solves the problem: loop as comments. Specifically, if you put [ right after a ], the latter loop is automatically a bulk no-op. For this trick to work better, I needed a base solution that has many short loops.

    So I rewrote the base solution for Task 2 several times to finally get

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

    which also happens to be pretty short on its own (even shorter than CursorCoercer's by 1 byte).

    \$\endgroup\$

    Your Answer

    By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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