Brainfuck - эзотерический язык программирования. Он не используется как удобный инструмент решения практических задач (ввиду своей неудобности и непрактичности), но решать простые задачи на нем может быть интересно и полезно - так же как решать любую головоломку. К тому же brainfuck является наглядным примером тьюринг-полного языка.

Описание и синтаксис

В этом языке нет переменных и функций, модель языка гораздо проще:

Есть большой массив 8-битных значений (т.е. каждый элемент от 0 до 255) - так называемая лента памяти. Есть указатель на ячейку памяти. При запуске программы он указывает на первую ячейку. Значения всех ячеек в момент запуска программы равны нулю.

Команды языка brainfuck:

• > - сдвинуть указатель ячейки памяти вправо к следующей ячейке
• < - сдвинуть указатель ячейки памяти влево к предыдущей ячейке
• + - увеличить значение текущей ячейки на 1
• - - уменьшить значение текущей ячейки на 1
• . - напечатать символ из текущей ячейки в соответствии с ASCII-таблицей
• , - считать в текущую ячейку символ из консоли
• [ - если значение текущей ячейки ноль, то перейти вперёд по тексту программы на команду, следующую за соответствующей ], иначе продолжить исполнение
• ] - если значение текущей ячейки не ноль, то вернуться назад на команду, следующую за соответствующей [, иначе продолжить исполнение

Интерпретаторы

Интерпретатор написать очень просто, их существует очень много. Например есть интерпретатор с визуализацией доступный из браузера. Или другой интепретатор тоже из браузера, но этот вычисляет быстро. Есть также интепретатор который требует установки, но обладает расширенным функционалом.

Как с этим жить

Давайте подумаем как напечатать тривиальный Hello world.

Для начала нам надо руководствуясь ASCII-таблицей понять, какие это символы в представлении ASCII-кодов:

Hello world = 72, 101, 108, 108, 111, 32, 119, 111, 114, 108, 100

P.S. Это можно делать не обязательно глазами и руками, а например с помощью онлайн-конвертера

Можно было бы напечатать огромное число операций + (и небольшое количество .) и напечатать заветный Hello world, но можно воспользоваться умножением и циклами:

                // H = 72 = 9*8
                // Давайте в первой ячейке положим число 9
+++++++++
[               // Этот блок кода будет выполняться пока в текущей ячейке не ноль (в данном случае текущая = первая)

                // И будем 9 раз увеличивать вторую ячейку на 8
                // Тогда во второй ячейке окажется 72 а это та буква которая нам нужна

    >           // Переходим ко второй ячейке
    ++++++++    // Увеличиваем ее на 8
    <           // Возвращаемся к первой ячейке
    -           // Уменьшаем ее на единицу ведь еще одна итерация прошла успешно
]
                // Раз мы пришли сюда значит цикл исполнился 9 раз значит во второй ячейке лежит 72 проверяем:
>               // Переходим ко второй ячейке
.               // Выводим символ

                // Дальше в том же духе

Заметим, что можно сэкономить, ведь при переходе от буквы e к l (т.е. от 101 к 108) достаточно увеличить значение всего лишь на 7, а третья и четвертая буквы совпадают.

Еще несколько примеров:

[-]             // Зануляет текущую ячейку

[->+<]          // Сдвигает переменную в соседнюю ячейку

[->+>+<<]
>>[-<<+>>]<<    // Копирует ячейку в сосденюю

[. [-]]         // Выводит текущую ячейку, если она не ноль (обратите внимание, что если ее не занулить, или не сдвинуть вместо этого указатель - то этот цикл зависнет)

Упражнение 1

Условие: Выведите Hello world

Упражнение 2

Условие: Выведите английский алфавит (заглавные буквы): ABCDEFGHIJKLMNOPQRSTUVWXYZ

Комментарии:

• Обратите внимание, что английские буквы в ASCII-таблице - символы от 65 до 90 (26 символов).
• Попробуйте минимизировать число инструкций (онлайн счетовод символов, пробелы в исходном коде за символы не считаются)
• Посоревнуйтесь с друзьями у кого программа короче (у меня заняло 38 инструкций: ++++++++[->++++++++>+++<<]>+>++[<.+>-])

Упражнение 3

Условие: Пользователь вводит два символа - выведите наименьший

Комментарии:

• Пример выводящий второй введенный символ: ,>,.
• Пример выводящий первый введенный символ: ,>,<.
• Придумайте сначала как сделать операцию Если текущая ячейка x == 0, то делаем А
• Спойлер про предыдущий комментарий: пусть справа от текущей лежат 0 1 0, тогда подумайте что сделает инструкция [>]>>, заметьте что в случае если изначальная клетка была ноль, то указатель теперь на единице, если же изначально был не ноль - то теперь указатель на нуле
• Спойлер2 итого чтобы сделать предложенную в комментарии выше операцию надо положить справа от текущей ячейки 0 1 0 и выполнить код [>]>> [ A ]

Упражнение 4

Условие: Пользователь вводит буквы одну за другой, пока не введет символ точки (код 46). Выведите введенные символы в алфавитном порядке (с повторениями)

Комментарии:

• Попробуйте алгоритм ищем максимум, поднимаем его вверх или делаем n^2 сравнений соседей, если они в неправильном порядке - swap между собой или сортировкой подсчетом
• Поймите сколько вам нужно было бы переменных, и оставьте между хранящамися на ленте символами зазор в столько ячеек, сколько вам нужно переменных
• Пока вы будете реализовывать - постоянно будет оказываться что зазор надо было брать больше, так что удобнее брать зазор с запасом :)

Отправка решения

Если вы сделали второе/третье/четвертое упражнение, то можете отправить мне ваше решение письмом:

• Пример темы письма: Brainfuck 16-1 Полярный Николай Упражнение 4 (в конце темы номер самого сложного упражнения, которое вы осилили)
• Если ваше решение короче лучшего на данный момент - ваше решение будет выложено ниже
• Исходный код можно прилагать либо файлом, либо прямо в тексте письма (желательно хоть как-то форматированный)

Лучшие результаты:

Ниже приведены самые короткие решения. (считаются только символы являющиеся корректными инструкциями, онлайн счетовод символов, интерпретатор, подобные задачки решают на codegolf)

P.S. По клику появляется исходный код

Упражнение 1 (Hello World)

Рекорды:

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

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

+++++ +++ .
----- ---.
+++.
----- -.
----- --- .

Упражнение 2 (Алфавит)

Рекорды:

• 35 символов: +++++++++++++[>++>+++++<<-]>[>.+<-] (11-1 Вирачев Арсений)

• 36 символов: +++++++++++++[>+++++>++<<-]>>[<.+>-] (10-1 Олейник Иван)

• 36 символов: +++[>++++<-]>+[>++>+++++<<-]>[>.+<-] (11-1 Думпис Сергей)

Упражнение 3 (Минимум)

Рекорды:

+>>>,>,<<<<[>>>->->+>+[<]<<]>>>>.

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

>>>>+
>

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

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

Упражнение 4 (Сортировка)

>>,[>>,]<<
[
[<<]>>>>
[<<
[>+<<+>-]>>
[>+<<<<[->]>[<]>>-]<<<
[[-]>>[>+<-]>>[<<<+>>>-]]>>
[[<+>-]>>]<
]<<
[>>+<<-]<<
]>>>>
[.>>]

//формат глобально такой: 
//Адрес 0: 1 если надо сделать ещё итерацию(и) вычитания единицы
//1) Дальше много фблоков вида
//2) (флаг начала/конца массива (0=начало/конец))010
//3) число
//4) (число для уменьшения)010
//5) (флаг вывода числа (1=выведено))010
//6) (вспомогательный флаг)010

//В самом конце вводим точку (46) и устанавливаем для неё флаг вывода в 1 и флаг конца в 0

+> //записываем в первую ячейку 1 (это нужно потом)
>>+ //делаем нулевой фиктивный блок 0010 0 0010 1010 0010
>>>>>+
>>+ //флаг вывода = 1
>>+
>>>>+
>>

//вводим остальные числа

+ //1 в начале блока
[
  >>+>
  ,
  [ //делаем 1010aaa
    >+>+>+
    <<<-
  ]
  >>>
  //вычитаем 46=7*7 минус 3 из последней a
  >+++++++
  [
    -
    <-------
    >
  ]
  <+++
  //делаем 1010aa(a минус 46)010
  >>+
  >>>>>>>>>+<<<<<<<<<<< //пихаем 1 в начало следующего блока
  [>]>>[ //если a=46
    >>>>>>>>>->>+<< <<<<<<<<< //пихаем 0010 в начало следующего блока
    <<<<<<<<- //делаем флаг конца=0
    >>>>>>>>
  >]
  <<<
  [-] //обнуляем место где было a минус 46
  >+
  >-
  >>>+
  >>>>+
  >> //перешли в начало следующего блока
]
<<<<<<<<+ //устанавливаем флаг вывода последнего символа (точки) в 

1
<<<<<<<<< //в начало последнего (фиктивного) блока
<<<<<<<<<<<<<<<<< //17 назад (начало последнего блока)

//теперь осталось посортить :)

[ //возвращаемся к нулевому блоку
  <<<<<<<<<<<<<<<<< //17 назад (начало предыдущего блока)
]
< //адрес=0 (там лежит 1)

[
  > //в начало нулевого блока
  >>>>>>>>>>>>>>>>> //в начало первого блока
  [ //цикла пока не дойдём до последнего блока
    >>>>>
    [>]>>[ //если текущее уменьшенное число = 0
      >>
      [>]>>[ //если флаг вывода = 0
        <<<<<<<. //выводим
        >>>>>+ //флаг вывода = 1
        >>
      >]
      <<<<<
    >]
    >
    [>]>>[ //если флаг вывода = 0
      <<<<<<- //уменьшаем
      >>>>>>>>+ //вспомогательные флаг = 1
      <<
    >]
    >>>>> //в начало следующего блока
  ]
  <<<<<<<<<<<<<<<<< //17 назад (начало последнего блока)
  [
    >>>>>>>>>>>>>>>>> //17 вперёд
    -
    [>]>>[ //если есть следующий блок (не фиктивный)
      >>>>>>>>>>> //вспомогательный флаг следующего блока
      [ //обнуляем этот флаг если он не = 0
        -
        <<<<<<<<<<<<<<<<< //17 назад (вспомогательный флаг данного 

блока)
        [>]>>[ //если он = 0
          <<+ //устанавливаем его
          >>
        >]
        >>>>>>>>>>>>>> //17 минус 3 вперёд
      ]
      <<<<<<<<<<<
    >]
    <<<+
    
    <<<<<<<<<<<<<<<<< //17 назад (начало данного блока)
    <<<<<<<<<<<<<<<<< //17 назад (начало предыдущего блока)
  ]
  //мы в начале нулевого блока
  //в вспомогательном флаге первого блока сейчас логическое ИЛИ
  //всех вспомогательных флагов
  //остальные вспомогательные флаги равны 0 
  
  <-> //обнуляем нулевую ячейку

  >>>>>>>>>>>>>>>>> //17 вперёд
  >>>>>>>>>>>>> //вспомогательный флаг первого блока
  [ //если там 1
    <<<<<<<<<<<<< //возвращаемся к адресу 0
    <<<<<<<<<<<<<<<<< //17 назад 
    <+ //ставим туда 1
    > //теперь опять обратно
    >>>>>>>>>>>>>>>>> //17 вперёд
    >>>>>>>>>>>>> //вспомогательный флаг первого блока
    - //обнуляем его
  ]
  <<<<<<<<<<<<< //начало первого блока
  <<<<<<<<<<<<<<<<< //17 назад 
  < //возвращаемся к адресу 0
]