4
\$\begingroup\$

Introduction

This challenge appeared in the 2020 Estonian Open Informatics Olympiad and was created Sandra Schumann. I thought it was interesting because it involves symmetry and is quite hard even to brute force by hand.

The problem author said that it's ok for me to post it here:proof

Challenge

You may use a modified version of BrainF**k with the following modifications:

  • Using - on a cell containing 0 keeps the value at 0.
  • Using < on cell 0 keeps the pointer at cell 0.
  • The values in the cells never overflow
  • The code may execute at most 10 million commands.

There are 5 separate tasks, for which you must write 5 separate programs:

  1. Cells 0 and 1 contain the integers x and y respectively (0 <= y <= x <= 200) and all other cells contain 0. Write the difference x - y into cell 0.
  2. Cell 0 contains an integer x (0 <= x <= 200) and all other cells contain 0. Write x modulo 7 into cell 0.
  3. Find the number of the leftmost cell containing 0 and write this number into cell 0. The answer will not exceed 100 and no cell will contain a value greater than 50 initially.
  4. Cell 0 contains an integer k (3 <= k <= 10) and cells 1 and 2 contain the integers F1 and F[2] (1 <= F1, F[2] <= 3), which are the first numbers in the sequence F[i] = F[i - 1] + F[i - 2]. Write F[k] in cell 0.
  5. Cell 0 contains 0, one or several consecutive cells after it contain positive integers, and the rest of the cells contain 0. Find the greatest integer contained in a cell and write its value in cell 0. The answer doesn't exceed 50 and there are at most 100 cells with positive integers.

Furthermore, each program must be in an N by N square of BrainF**k code. The code doesn't have to be the same when read in the two directions, but it must solve its task correctly in both cases.

The goal is to get each N to be as small as possible

Example Input and Output

Let's say a task was to add the values in cells 0 and 1 intead.

One possible output would be

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

Reading by rows: >[-<+>][++++<><----><+++++<<>---]><-<><>[>]><<<><

Reading by columns: >[<+>-][+-+-<>-+-+-><<+-+-<<++-+]><><><>[>]><<<><

Winning Criteria

The winner is whoever can minimize the sum of Ns over the five tasks.

\$\endgroup\$
2

0