На днях мне потребовалось написать решение задачи поиска максимально возрастающей последовательности цифр на C.
Однако я решил что решать эту задачу привычным методом будет скучно и я решил слегка усложнить себе задачу, чтобы поинтереснее было. Так и появилась идея написать этот код на brainfuck, а на C интерпретатор для него.
Естественно делать это голыми руками будет больно и не приятно, поэтому я решил написать генератор brainfuck кода на Java.
Немного про сам Brainfuck
Brainfck — эзотерический язык программирования, в качестве памяти классического Brainfuck мы имеем массив из 30 000 ячеек памяти и номер выбранной ячейки (изначально равный нулю), где каждая ячейка весит один байт. А привычного синтаксиса нас встречает последовательность из набора следующих символов: <>+-.,[]
:
Символы <
и >
изменяют индекс выбранной ячейки (index++
и index--
)
Символы +
и -
изменяют текущее значение выбранной ячейки на +1 или -1 (buffer[index]++
и buffer[index]--
)
Символы ,
и .
записывают введённый символ в значение ячейки / выводят значение ячейки в качестве символа (buffer[index] = getchar()
и putchar(buffer[index])
)
Однако самые интересные символы это [
и ]
, они открывают/закрывают цикл, который будет работать до тех пор пока значение выбранной ячейки не станет 0, важным моментом является то, что проверка этого происходит в начале ([
) и конце (]
) цикла, и если значение выбранной ячейки в начале цикла было равно 0, то интерпретатор мгновенно перейдет к концу цикла, пропустив все внутри
Приступаем к кодингу
Я создал класс Brainfuck.java
(кстати я хотел назвать его Brainf$ck
но подумал что так будет неудобно кодить) который будет генерировать и одновременно исполнять код, и прописал базовую логику без циклов:
public class Brainfuck { private int[] buffer = new int[30000]; public int minValue = 0, maxValue = 255; // Максимальное и минимальное значения ячеек private int index = 0; private CodeBuilder code = new CodeBuilder(); // Я создал CodeBuilder.java который иммет функционал StringBuilder-а, но с фозможность форматирования brainfuck кода protected boolean onlyCode = false; // Так как мы одновременно исполняем код и генерирум его, то будут моменты с циклами, когда создать код надо, а исполнять нет, ведь цикл будет пропущен в результате исполнения protected boolean shortVersion = false; // Для замены [-] на @ для того чтобы сделать код короче private StringBuilder output = new StringBuilder(); // Вывод результата исполнения Brainfuck-кода // Чтобы не вводить каждый раз с клавиатуры добавим возможность заранее заготовить input private String input = ""; private int inputIndex = 0; public Brainfuck(String input) { this.input = input; } // А теперь создадим базовые команды @Brainfucked // Команды для генерации кода у меня имеют эту антонацию private Brainfuck nextIndex() { code.append('>'); // Генерируем код index++; // И сразу его исполняем return this; } @Brainfucked private Brainfuck prevIndex() { code.append('<'); index--; return this; } @Brainfucked public Brainfuck add() { code.append('+'); if(!onlyCode) { maxMemoryUsed = Math.max(maxMemoryUsed, index); // Для дебага buffer[index]++; if(buffer[index] > maxValue) buffer[index] = minValue; // Переполнение } return this; } @Brainfucked public Brainfuck remove() { code.append('-'); if(!onlyCode) { buffer[index]--; maxMemoryUsed = Math.max(maxMemoryUsed, index); // Для дебага if(buffer[index] < minValue) buffer[index] = maxValue; // Переполнение } return this; } @Brainfucked public Brainfuck read() { code.append(','); if(!onlyCode) { if(inputIndex >= input.length()) { input = scanner.nextLine() + "\n"; inputIndex = 0; } buffer[index] = input.charAt(inputIndex++); } return this; } @Brainfucked public Brainfuck print() { code.append('.'); if(!onlyCode) { output.append((char)buffer[index]); } return this; } }
Добавим еще парочку методов упрощающим жизнь:
@Brainfucked public Brainfuck setIndex(int index) { // Будем выбирать нужный нам индекс в ячейке, автоматически добавляя нуное количество ">" и "<" while (index != this.index) { if(this.index > index) prevIndex(); if(this.index < index) nextIndex(); } return this; } @Brainfucked public Brainfuck resetCell() { // [-] - сбрасывает значение в текущей ячейке, так как цикл постоянно уменьшает значение на -1, а при достижении нуля цикл прерывается code.append(shortVersion ? "@" : "[-]"); if(!onlyCode) buffer[index] = 0; return this; } @Brainfucked // Аналогично setIndex добавляет нужное количество команд, но на этот раз это не смещение индекса, а изменение значения ячейки public Brainfuck addValue(int value) { if(value == 0) return this; if(value > 0) { for (int i = 0; i < value; i++) add(); return this; } for (int i = 0; i < -value; i++) remove(); return this; }
Так же я создал много функция для отладки таких как dump()
(выводит использованные ячейки памяти со значениями и именами переменных в виде таблички), comment(...)
(добавляет комментарий в код), log(...)
(вывод в консоль текст если кусок кода исполняется в brainfuck), подробнее их можно глянуть на гите.
Прежде чем реализовать циклы, создадим систему переменных
Хотя я и добавил возможность создавать переменные, занимающие несколько ячеек памяти, действий с ними я пока не реализовал
public class Variable { public final String name; // Имя переменной, ни на что не влияет, нужно для дебагинга public final int size; // Размер переменной, иначе говоря сколько ячеек памяти будет занимать public final int index; // Индекс начальной ячейки, занимаямой переменной (я хотел сделать массив из индексов чтобы можно было пихать переменные в любое место, но в итоге отказался от этой идеи) protected final Brainfuck brainfuck; // Ссылка на генератор private boolean exist = true; // Переменную можно будет удалять, чтобы освободить место protected Variable(Brainfuck brainfuck, String name, int size, int index) { this.brainfuck = brainfuck; this.name = name.replace('.', '/'); this.size = size; this.index = index; reset(); // Устанавливаем значение 0 при инициализации, чтобы избежать проблем в дальнейшем // "Дефолтные" переменные я буду начинать с "$", поэтому информацию об из объявлении не буду писать if(!name.startsWith("$")) Log.run("@ declarated at @", this.name, index); } @Brainfucked public void reset() { // Сбрасываем значение переменной if(isDeleted()) throw new DeletedVariableManipulation("change"); select(); brainfuck.resetCell(); } @Brainfucked public void select() { // Выбираем ячеку с этой переменной if(isDeleted()) throw new DeletedVariableManipulation("select"); brainfuck.setIndex(index); } @Brainfucked public void add(int i) { // Изменяем значение переменной if(isDeleted()) throw new DeletedVariableManipulation("change"); select(); brainfuck.addValue(i); } @Brainfucked public void delete() { // Удаление переменной if(isDeleted()) throw new DeletedVariableManipulation("delete already deleted"); for (int i = 0; i < size; i++) { brainfuck.variables[index + i] = null; } exist = false; } }
Так же создадим тип, который будет занимать 1 ячейку.
(Наверное стило назвать его как Cell, учитывая что размер ячейки у меня можно менять да в Java есть дефолтный класс с таким же именем, но что сделано то сделано)
brainfuck.Byte.java
:
public class Byte extends Variable { @Brainfucked public Byte(Brainfuck brainfuck, String name, int index) { super(brainfuck, name, 1, index); } }
Многие манипуляции в дальнейшем я буду прописывать как раз таки в Byte
классе
А в Barinfuck.java
пропишем следящее:
Variable[] variables = new Variable[buffer.length]; // Массив хранящий сущестующие переменные @Brainfucked public Variable variable(String name, int size) { // Поиск свободного места for (int i = 0; i < variables.length; i++) { if(variables[i] != null) continue; boolean free = true; for (int j = 0; j < size; j++) { if(variables[i+j] != null) { free = false; break; } } if(!free) continue; Variable variable = new Variable(this, name, size, i); for (int k = 0; k < size; k++) { // Занимаем место переменной variables[variable.index + k] = variable; } return variable; } throw new OutOfMemoryError("Not enoth memory for declarating varrible"); } @Brainfucked public Byte variable(String name) { // Анологично для переменной из одной ячейки for (int i = 0; i < variables.length; i++) { if(variables[i] != null) continue; Byte variable = new Byte(this, name, i); variables[variable.index] = variable; return variable; } throw new OutOfMemoryError("Not enoth memory for declarating varrible"); } @Brainfucked public Byte[] byteArray(String name, int size) { // Объявление массива for (int i = 0; i < variables.length; i++) { if(variables[i] != null) continue; boolean free = true; for (int j = 0; j < size; j++) { if(variables[i+j] != null) { free = false; break; } } if(!free) continue; Byte[] bs = new Byte[size]; for (int k = 0; k < size; k++) { bs[k] = new Byte(this, name + "/" + k, i+k); } return bs; } throw new OutOfMemoryError("Not enoth memory for declarating array"); }
Теперь наконец то можно приступить к созданию первого цикла. Если перевести на язык Java то это будет так:
while(var != 0) { ... var--; }
А вот уже реализация на Java:
@Brainfucked public void repeatWhile(Byte var, Runnable run) { var.select(); // Выбираем переменную для сравнения, т.к не гарантируется что выбрана именно ячейка переменной var CodeBuilder parent = code; parent.append('['); boolean runned = false; while (buffer[index] != 0 && !onlyCode) { code = new CodeBuilder(); run.run(); var.select(); // Снова выбираем переменную для сравнения, т.к "run" мог сместить индекс runned = true; if(!runnable) break; } if(!runned) { boolean oc = onlyCode; int ind = index; if(!var.toBoolean()) onlyCode = true; // Если ни ни одна итерация цикла не произошла, то тогда ключаем режим только генерации кода для блока внутри code = new CodeBuilder(); var.select(); run.run(); var.select(); onlyCode = oc; // Возвращаем режим к исходному состоянию if(!onlyCode) { index = ind; } } parent.append(code); parent.append(']'); code = parent; }
Отлично, базовые команды brainfuck-а реализованы, а значит что мы практически можем забыть про символы brainfuck-а и приступим к более сложным конструкциям:
Конструкция копирования переменной из одной ячейки в другую:
К сожалению в brainfuck нельзя просто написать a = b
, для этого нам даже понадобиться временная ячейка, если описать этот алгоритм словами то будет так:
Сбросить значение текущей ячейки Добавлять 1 к a и tmp b-раз (b используется в качестве счетчика и станет равным 0) Добавлять 1 к b tmp-раз (tmp используется в качестве счетчика и станет равным 0) Удалить tmp
Byte.java
:
@Brainfucked public void set(Byte var) { if(isDeleted()) throw new DeletedVariableManipulation("change"); Byte tmp = brainfuck.variable("$bf/tmp/byte/copy"); // Создаем временную переменную reset(); // Сбрасываем текущее значение brainfuck.repeatWhile(var, () -> { // Добавляем к текущему значению и временнуму, ценой значения переменной var (она используется как счетчик цикла) add(1); tmp.add(1); var.add(-1); }); brainfuck.repeatWhile(tmp, () -> { // Возвращаем значение в var ценой временной переменной var.add(1); tmp.add(-1); }); tmp.delete(); // Удаляем временную переменную }
На brainfuck это выглядело бы так:
a[-]b[a+t+b-]t[b+t-]
(где вместо a, b, t будут «>» и «<» в количестве нужном для переходя к этим ячейкам, иначе говоря a
значит перейти к ячейке «a»)
Конструкция if x != 0
Чтобы превратить цикл в условия достаточно сбросить значение выбранной ячейки до 0 или перейти к ячейке со значением 0, я выбрал первый вариант.
@Brainfucked public void ifNotZero(Byte var, Runnable run) { Byte lock = variable("$bf/ifByte/circle"); lock.set(var); repeatWhile(lock, () -> { run.run(); lock.reset(); }); lock.delete(); }
На brainfuck это выглядело бы так:
... // Копирование из var в lock lock[ ... // Код в if lock[-] ]
Конструкция if x == 0 else
Теперь, когда мы умеем делать if x != 0
мы можем создать обратное условие. Для этого нам понадобится еще одна временная переменная, которая будет иметь значение 1, а при выполнении x != 0
менять значение на 0, таким образом вход во второй цикл можно будет инвертировать
@Brainfucked public void ifZeroElse(Byte var, Runnable runZero, Runnable runNoZero) { Byte inversed = variable("$bf/ifByte/circle"); inversed.add(1); ifNotZero(var, () -> { // x != 0 runNoZero.run(); inversed.add(-1); }); ifNotZero(inversed, runZero); // x == 0 inversed.delete(); }
Конструкция if x == y else
Логика этой конструкции подобна if x == 0 else
но для получения 0 мы просто вычтем из x значение y
Конструкция if x < y else
Это самая сложная из реализованных конструкций. Для ее создания нам понадобиться массив из 6 ячеек, его можно создать функцией byteArray(name, size)
, массив надо заполнить следующим образом:
Номер: 0 1 2 3 4 5 Число: 0 1 0 x y 0
а затем перейти на [3]
элемент массива.
Алгоритм выглядит следующим образом
{ Вычитаем из [3] // ячейка и значальным значнием равным x Вычитаем из [4] // ячейка и значальным значнием равным y Если [4] != 0 { Сдвигаемся впрво на 1 ячейку } Сдвигаемся влево на 2 ячейки } Сдвигаемся влево на 1 ячейку Если [текущая] != 0 { // если мы оказались на [1], т.е x >= y Вычитаем из [1] ... // Код если x >= y Переходим к [1] } Сдвигаемся влево на 1 ячейку Если [текущая] != 0 { // если мы оказались на [0], т.е x < y Вычитаем из [0] ... // Код если x < y Переходим к [0] }
Рассмотри его при x < y
:
{ Вычитаем из [3] // ячейка и значальным значнием равным x Вычитаем из [4] // ячейка и значальным значнием равным y Если [4] != 0 { Сдвигаемся впрво на 1 ячейку, мы на [5] // т.к x > y то [4] не станет никогда 0, т.к мы сбыстрее выйдем из цикла при [3] = 0 } Сдвигаемся влево на 2 ячейкимы // Теперь мы на [3], но т.к x < y то [3] стало равной 0 быстрее, чем [4], а раз она 0 то цикл прерывается } Сдвигаемся влево на 1 ячейку // Мы на [2] ячейке Если [текущая] != 0 { // сюда не заходим т.к [2] равно 0 Вычитаем из [1] ... // Код если x >= y Переходим к [1] } Сдвигаемся влево на 1 ячейку // Мы на [1] ячейке Если [текущая] != 0 { // а вот сюда заходим, ведь [1] равно 1 Вычитаем из [0] ... // Код если x < y Переходим к [0] }
Рассмотрим при x >= y
:
{ Вычитаем из [3] // ячейка и значальным значнием равным x Вычитаем из [4] // ячейка и значальным значнием равным y Если [4] != 0 { // Это условие наступило т.к x >= y Сдвигаемся впрво на 1 ячейку // Теперь мы на [5] } Сдвигаемся влево на 2 ячейки // Теперь мы на [2], а она равна 0, что означает выход из цикла } Сдвигаемся влево на 1 ячейку // Теперь мы на [1] Если [текущая] != 0 { // Условие выполняется, ведь [1] равно 1 Вычитаем из [1] ... // Код если x >= y Переходим к [1] } Сдвигаемся влево на 1 ячейку // Теперь мы на [0] Если [текущая] != 0 { // Условие не выполняется, ведь [0] равно 0 Вычитаем из [0] ... // Код если x < y Переходим к [0] }
На Java я написал следующий код:
@Brainfucked public void ifLessThanElse(Byte x, Byte y, Runnable ifRun, Runnable elseRun) { Byte[] arr = byteArray("$bf/lessthan/array", 6); arr[1].add(1); arr[3].set(x); arr[4].set(y); arr[3].add(1); arr[4].add(1); arr[3].select(); code.append("[->-[>]<<]"); // Первый цикл в brainfuck вариации code.append("<[-"); // Начло первого условия int min = Math.min(x.value(), y.value()) + 1; // Вместо прописывания логики цикла я просто прописал это вручную boolean less = x.value() < y.value(); // Так как одно из них станет нулем, что создаст выход из цикла, я просто вычту минимум из x и y buffer[arr[3].index] -= min; buffer[arr[4].index] -= min; // if x >= y блок boolean oc = onlyCode; onlyCode = less; index = arr[1].index; // Опять установлю вручную elseRun.run(); arr[1].select(); onlyCode = oc; // Конец первого и начало второго условия code.append("]<[-<"); // if x < y блок oc = onlyCode; onlyCode = !less; index = arr[0].index; // Опять установлю вручную ifRun.run(); arr[0].select(); onlyCode = oc; code.append("]"); // Конец второго условия // Чистим память, занятую временным масивом for (int i = 0; i < arr.length; i++) { arr[i].delete(); } }
Brainfuck Математика
Теперь реализуем различные действия в классе Byte. Математику будем реализовывать именно с двумя ячейками x
и y
Умножение x = x * y
Ну тут все просто. Нам понадобятся 2 временные переменные, в tmp0
мы перенесем (не скопируем, а именно перенесем) значение . А затем будем использовать tmp0
как счетчик цикла. Внутри этого цикла мы будем прибавлять y каждой итерацией, таким образом мы возьмем х раз, что и является умножением. Добавлять y мы будет способом, похожим на копирование переменной, но на этот раз не будем сбрасывать ее значение, чтобы не приравнивать y раз, а прибавлять.
@Brainfucked public void multiply(Byte mul) { if(isDeleted()) throw new DeletedVariableManipulation("change"); select(); Byte tmp0 = brainfuck.variable("$bf/varible/multiply/tmp0"); Byte tmp1 = brainfuck.variable("$bf/varible/multiply/tmp1"); brainfuck.repeatWhile(this, () -> { // переносим значение из this (x) в tmp1 tmp1.add(1); add(-1); }); brainfuck.repeatWhile(tmp1, () -> { // Повторяем x - раз // На этот раз reset() не нужен brainfuck.repeatWhile(mul, () -> { add(1); tmp0.add(1); mul.add(-1); }); brainfuck.repeatWhile(tmp0, () -> { mul.add(1); tmp0.add(-1); }); tmp1.add(-1); }); tmp0.delete(); tmp1.delete(); }
Деление с остатком x + mod = x / y
Деление сделать чуть посложнее. На этот раз мне потребовалось аж 4 временных переменных и одну будем возвращать в качестве остатка.
mod
— будем возвращать, это наш остаток
umod
— нужно для вычисления остатка оно будет равняться , я буду называть его обратным mod
div
— сюда мы будем записывать результат деления, а потом перенесем его в ячейку x
lock
— оно будет в качестве условия для цикла и изначально равняться , чтобы мы могли задать значение и выйти из цикла
tmpDivider
— в него мы будем копировать y и использовать в качестве счетчика цикла
@Brainfucked public Byte divide(@Final Byte divider) { Byte mod = brainfuck.variable("$bf/byte/divide/mod"); Byte umod = brainfuck.variable("$bf/byte/divide/umod"); Byte div = brainfuck.variable("$bf/byte/divide/div"); Byte lock = brainfuck.variable("$bf/byte/divide/lock"); Byte tmpDivider = brainfuck.variable("$bf/byte/divide/lock"); lock.add(1); brainfuck.repeatWhile(lock, () -> { // Чтобы разделить мы должны посчитать сколько раз мы можем вычесть y div.add(1); // Увеличиваем счетчик brainfuck.ifZeroElse(this, () -> { // Если оказывается что x стал 0 то выходим из цикла lock.add(-1); umod.set(divider); // если х = 0 на этом этапе то значит что остаток от деления будет 0, поэтому в umod устанавливаем y }, () -> { tmpDivider.set(divider); tmpDivider.add(-1); // вычитаем еденицу, которую вернем после цикла, чтобы мы могли получить 0 внутри цикла brainfuck.repeatWhile(tmpDivider, () -> { // вычитаем по 1 (y-1) раз и если получаем 0 в процессе - выходим из цикла add(-1); // вичитаем по еденице tmpDivider.add(-1); // Уменьшаем счетчик цикла brainfuck.ifZero(this, () -> { // мы получили 0, значит деление завершено // Оставшееся значение счетцика будет обратным mod (y-mod) umod.add(1); brainfuck.repeatWhile(tmpDivider, () -> { umod.add(1); tmpDivider.add(-1); }); add(1); // возвращаем забранную еденицу lock.add(-1); // прерываем цикл }); }); }); add(-1); }); div.add(-1); // одно вычиание было не полным // Теперь посчитаем mod, зная обратный mod.set(divider); brainfuck.repeatWhile(umod, () -> { mod.add(-1); umod.add(-1); }); // Перенесем из div (счетчика итераций) в this (х) reset(); brainfuck.repeatWhile(div, () -> { add(1); div.add(-1); }); // Удаляем временные переменные umod.delete(); div.delete(); lock.delete(); tmpDivider.delete(); // Возвращаем остаток от деления, обарите внимание, что пользователь должен будет отчищать память для него сам return mod; }
BrainfuckIO — ввод / вывод
Для упрощения ввода вывода я создал класс BrainfuckIO.java
Чтение целого числа
Для чтения целого числа нам понадобятся 3 ячейки: variable
, в нее мы запишем результат и in
в нее мы будем читать входные символы, а так же временная ячейка neednext
она будет отвечать за цикл
Читать символы мы будем до стоп-символа. Первым делом мы должны считать первый символ и проверить, является ли он минусом, если да то в дальнейшем мы будем вычитать из ячейки variable
, а не прибавлять. Затем прочитаем следующий символ в in
, сравним на стоп-символ и если это он то выйдем из цикла, обнулив neednext
. Иначе же вечем из in
, это числовое значение символа «0», после чего будем умножать variable
на и прибавлять/вычитать значение in
:
@Brainfucked public static void readInt(Byte variable, char stop) { variable.reset(); Brainfuck bf = variable.brainfuck; Byte in = bf.$input(); bf.read(in); bf.ifEqualElse(in, '-', () -> { // Если первый символ 0 то мы будем вычитать из variable Byte needNext = bf.variable("$bf/io/neednext"); needNext.add(1); bf.repeatWhile(needNext, () -> { bf.read(in); // Читам еще один символ readAddInt$changeValue(bf, in, stop, needNext, variable, -1); // Передаем нужныее переменные и -1 как знак того что мы будем вычиаить }); needNext.delete(); }, () -> { // Если первый символ не 0 то мы будем прибавлять к variable Byte needNext = bf.variable("$bf/io/neednext"); needNext.add(1); readAddInt$changeValue(bf, in, stop, needNext, variable, 1); bf.repeatWhile(needNext, () -> { bf.read(in); // Читам еще один символ readAddInt$changeValue(bf, in, stop, needNext, variable, 1); }); needNext.delete(); }); } private static void readAddInt$changeValue(Brainfuck bf, Byte in, char stop, Byte needNext, Byte variable, int mul) { // Чтобы не код вынес его в функцию bf.ifEqualElse(in, stop, () -> { // Если считаный символ это стоп-символ то мы выходим из цикла путем установки neednext в 0 needNext.add(-1); }, () -> { in.add(-'0'); // Вычитаем 48 чтобы перевести символ в цифру variable.multiply(10); // Умножаем на 10 для разрядов bf.repeatWhile(in, () -> { in.add(-1); // in теперь счетчик цикла variable.add(mul); // добавляем/вычитаем 1 в variable }); }); }
Вывод числа
Ну и наконец самое сложное, код получился очень медленным (brainfuck-код), одна из причин этому это отсутствие реляции динамического списка, и мне приходится каждый раз делить большие числа.
Нам потребуется куча ячеек:
value
— ячейка, значение которой мы будем выводить
v
— для копии value
out
— ячейка для вывода символа
divider
— для деления, чтобы получить цифру из нужного разряда
length
— для хранения количества выходных символов
i
— копия length
Сначала нам надо посчитать сколько символов потребуется вывести, для этого откопируем из ячейки, значение которой мы будем выводить (назовем ее value
) во временную ячейку v
, теперь будем делить value
на до тех пор пока не получиться ноль, и после каждой итерации будем добавлять в length
, если длина получиться , то выведем , иначе же будем length
раз делать следующее:
@Brainfucked public static void printInt(Byte value) { Brainfuck bf = value.brainfuck; value.select(); Byte length = bf.variable("$bf/io/printInt/length"); Byte out = bf.variable("$bf/io/printInt/out"); Byte v = bf.variable("$bf/io/printInt/v"); Byte divider = bf.variable("$bf/io/printInt/divider"); Byte i = bf.variable("$bf/io/printInt/i"); v.set(value); // Зафиксируем value в v bf.repeatWhile(value, () -> { // Делим на 10 до тех пор пока value не станет равно 0 value.divide(10).delete(); length.add(1); // Считам количество делений }); bf.ifEqualElse(length, 0, () -> { // Длина 0, значит выводим 0 value.reset(); value.print(); }, () -> { value.set(v); // Копирум обратно bf.repeatWhile(length, () -> { // Выведем символы length раз i.set(length); // Надо для счета divider divider.reset(); divider.add(1); i.add(-1); bf.repeatWhile(i, () -> { // Уножаем divider на десять (length-1) раз divider.multiply(10); i.add(-1); }); out.set(value); // Копируем value в out чтобы потом разделить Byte mod = out.divide(divider); // Делим, нам нужен только остаток out.add('0'); // Переводим число в символ out.print(); // Выводим его value.set(mod); // Устанавливаем остаток в value mod.delete(); // Чистим за собой память length.add(-1); // Изменям счетчик цикла }); }); value.set(v); // Возвращаем value в прежнее состояние // Чистим память от временных ячеек length.delete(); out.delete(); v.delete(); i.delete(); divider.delete(); }
А теперь решим задачку
public class Brainfucker { public static Brainfuck brainfuck; public static void main(String[] args) throws Exception { String input = "7\n1 2 3 -1 3 4 8\n"; // пример входных значений brainfuck = new Brainfuck(input); // создаем генератор // Устанавливаем максим и минимум ячейки brainfuck.minValue = java.lang.Byte.MIN_VALUE; brainfuck.maxValue = java.lang.Byte.MAX_VALUE; Byte length = brainfuck.variable("length"); // Сюда запишем длинну последовательности для чтения BrainfuckIO.readInt(length, '\n'); // Прочитаем первую строчку с единственным числом - длиной последовательности length.add(-2); // Первое число последовательности запишем в last, а последнее будет иметь стоп символ не ' ', а '\n' Byte last = brainfuck.variable("last"); // Предидущее число последовательности BrainfuckIO.readInt(last, ' '); // Читаем первое число последовательноти (после него идет ' ') Byte max = brainfuck.variable("max"); // Сюда будем записывать длину максимальной последовательности из возрастающих чисел Byte count = brainfuck.variable("count"); // А это счетчик текущей длины последовательности из возрастающих чисел Byte a = brainfuck.variable("i"); // сюда будем записывать текущий элемент последовательности brainfuck.repeatWhile(length, () -> { // Повторим length раз logicForNextElement(a, ' ', last, count, max); // Обрбатываем элемент, т.к он не в кноце то стоп-символ это ' ' last.set(a); length.add(-1); }); logicForNextElement(a, '\n', last, count, max); // Обрбатываем элемент, т.к он в кноце то стоп-символ это '\n' BrainfuckIO.printInt(max); // Выводим результат String code = brainfuck.toString(); Log.result(code + "\n"); // выводим сгенерированный brainfuck код в консоль Log.info(brainfuck.dump()); // Навяк выводим дамп brainfuck памяти (и результат вывода brainfuck программы) } private static void logicForNextElement(Byte a, char stopCharacter, Byte last, Byte count, Byte max) { BrainfuckIO.readInt(a, stopCharacter); // Читаем следующее число a.add(1); // Займем еденицу чтобы заменить условие "last < a" на "last <= a" brainfuck.ifLessThanElse(last, a, () -> { // if last < a count.add(1); // Круто, последовательность возрастает, давайте прибавим 1 к счетчику brainfuck.ifLessThanElse(count, max, () -> { // Проверим больше ли максимального значения значение счетчика // Если меньше то ничего не будем делать }, () -> { // А если больше то зададим максимальному значению, значения счетчика max.reset(); max.set(count); }); }, () ->; { // Эх, возрастание нарушено, сброим счетчик до 1 count.reset(); count.add(1); }); a.add(-1); // Возвращаем занятую еденицу } }
Запускаем, и получаем следующий результат:
[-]>[-]+>[-]>[-]<[-]<<[>>+>+<<<-]>>>[<<<+>>>-]<[<->[-]][-]>[-]<[-]<[>+>+<<-]>>[<<+>>-]<[[-]]<<[-]>[-],>[-]>[-]<+>>[-]<[-]<<[>>+>+<<<-]>>>[<<<+>>>-]<---------------------------------------------[<->[-]>[-]+>[-]>[-]<+>>[-]<[-]<<<<<[>>>>>+>+<<<<<<-]>>>>>>[<<<<<<+>>>>>>-]<----------[<->[-]<<<<<------------------------------------------------>>>>>>[-]++++++++++<<<<<<<>>>>>>>>[-]>[-]<<<<<<<<<[>>>>>>>>>+<<<<<<<<<-]>>>>>>>>>[<<[<<<<<<<+>>>>>>>>+<-]>[<+>-]>-]<<<<<<<<[-<+>]>>>>>]<[<->-]<[<<<,>>>>[-]>[-]<+>>[-]<[-]<<<<<[>>>>>+>+<<<<<<-]>>>>>>[<<<<<<+>>>>>>-]<----------[<->[-]<<<<<------------------------------------------------>>>>>>[-]++++++++++<<<<<<<>>>>>>>>[-]>[-]<<<<<<<<<[>>>>>>>>>+<<<<<<<<<-]>>>>>>>>>[<<[<<<<<<<+>>>>>>>>+<-]>[<+>-]>-]<<<<<<<<[-<+>]>>>>>]<[<->-]<]<]<[>>[-]+[<<<,>>>>[-]>[-]<+>>[-]<[-]<<<<<[>>>>>+>+<<<<<<-]>>>>>>[<<<<<<+>>>>>>-]<----------[<->[-]<<<<<------------------------------------------------>>>>>>[-]++++++++++<<<<<<<>>>>>>>>[-]>[-]<<<<<<<<<[>>>>>>>>>+<<<<<<<<<-]>>>>>>>>>[<<[<<<<<<<+>>>>>>>>+<-]>[<+>-]>-]<<<<<<<<[-<->]>>>>>]<[<->-]<]<<-]<<-->>[-][-]<,>>[-]>[-]<+>>[-]<[-]<<<[>>>+>+<<<<-]>>>>[<<<<+>>>>-]<---------------------------------------------[<->[-]>[-]+>[-]>[-]<+>>[-]<[-]<<<<<<[>>>>>>+>+<<<<<<<-]>>>>>>>[<<<<<<<+>>>>>>>-]<--------------------------------[<->[-]<<<<<<------------------------------------------------>>>>>>>[-]++++++++++<<<<<<>>>>>>>[-]>[-]<<<<<<<<[>>>>>>>>+<<<<<<<<-]>>>>>>>>[<<[<<<<<<+>>>>>>>+<-]>[<+>-]>-]<<<<<<<<<[->+<]>>>>>>]<[<->-]<[<<<<,>>>>>[-]>[-]<+>>[-]<[-]<<<<<<[>>>>>>+>+<<<<<<<-]>>>>>>>[<<<<<<<+>>>>>>>-]<--------------------------------[<->[-]<<<<<<------------------------------------------------>>>>>>>[-]++++++++++<<<<<<>>>>>>>[-]>[-]<<<<<<<<[>>>>>>>>+<<<<<<<<-]>>>>>>>>[<<[<<<<<<+>>>>>>>+<-]>[<+>-]>-]<<<<<<<<<[->+<]>>>>>>]<[<->-]<]<]<[>>[-]+[<<<<,>>>>>[-]>[-]<+>>[-]<[-]<<<<<<[>>>>>>+>+<<<<<<<-]>>>>>>>[<<<<<<<+>>>>>>>-]<--------------------------------[<->[-]<<<<<<------------------------------------------------>>>>>>>[-]++++++++++<<<<<<>>>>>>>[-]>[-]<<<<<<<<[>>>>>>>>+<<<<<<<<-]>>>>>>>>[<<[<<<<<<+>>>>>>>+<-]>[<+>-]>-]<<<<<<<<<[->-<]>>>>>>]<[<->-]<]<<-][-]>[-]>[-]<<<<<[>>>>>[-]<<<<,>>>>>[-]>[-]<+>>[-]<[-]<<<<<<[>>>>>>+>+<<<<<<<-]>>>>>>>[<<<<<<<+>>>>>>>-]<---------------------------------------------[<->[-]>[-]+>[-]>[-]<+>>[-]<[-]<<<<<<<<<[>>>>>>>>>+>+<<<<<<<<<<-]>>>>>>>>>>[<<<<<<<<<<+>>>>>>>>>>-]<--------------------------------[<->[-]<<<<<<<<<------------------------------------------------>>>>>>>>>>[-]++++++++++<<<<<<>>>>>>>[-]>[-]<<<<<<<<[>>>>>>>>+<<<<<<<<-]>>>>>>>>[<<[<<<<<<+>>>>>>>+<-]>[<+>-]>-]<<<<<<<<<<<<[->>>>+<<<<]>>>>>>>>>]<[<->-]<[<<<<<<<,>>>>>>>>[-]>[-]<+>>[-]<[-]<<<<<<<<<[>>>>>>>>>+>+<<<<<<<<<<-]>>>>>>>>>>[<<<<<<<<<<+>>>>>>>>>>-]<--------------------------------[<->[-]<<<<<<<<<------------------------------------------------>>>>>>>>>>[-]++++++++++<<<<<<>>>>>>>[-]>[-]<<<<<<<<[>>>>>>>>+<<<<<<<<-]>>>>>>>>[<<[<<<<<<+>>>>>>>+<-]>[<+>-]>-]<<<<<<<<<<<<[->>>>+<<<<]>>>>>>>>>]<[<->-]<]<]<[>>[-]+[<<<<<<<,>>>>>>>>[-]>[-]<+>>[-]<[-]<<<<<<<<<[>>>>>>>>>+>+<<<<<<<<<<-]>>>>>>>>>>[<<<<<<<<<<+>>>>>>>>>>-]<--------------------------------[<->[-]<<<<<<<<<------------------------------------------------>>>>>>>>>>[-]++++++++++<<<<<<>>>>>>>[-]>[-]<<<<<<<<[>>>>>>>>+<<<<<<<<-]>>>>>>>>[<<[<<<<<<+>>>>>>>+<-]>[<+>-]>-]<<<<<<<<<<<<[->>>>-<<<<]>>>>>>>>>]<[<->-]<]<<-]<+>[-]>[-]>[-]>[-]>[-]>[-]<<<<+<[-]>>>[-]<<<<<<<[>>>>>>>+<<<+<<<<-]>>>>[<<<<+>>>>-][-]>>>>[-]<<<<<[>>>>>+<<<<+<-]>[<+>-]>>>+>+<[->-[>]<<]<[-<<<[-]+>>>]<[-<<<+>>[-]>[-]>[-]>[-]>[-]>[-]<<<<+<[-]>>>[-]<<<<<[>>>>>+<<<+<<-]>>[<<+>>-][-]>>>>[-]<<<<<<<[>>>>>>>+<<<<+<<<-]>>>[<<<+>>>-]>>>+>+<[->-[>]<<]<[-<<<<[-]>>>[-]<<<[-]>[<+>>>+<<-]>>[<<+>>-]>]<[-<]]<->[-]<<<<[-]>>>[<<<+>>>>+<-]>[<+>-]<<<<<<-]>>>>>[-]<<<<,>>>>>[-]>[-]<+>>[-]<[-]<<<<<<[>>>>>>+>+<<<<<<<-]>>>>>>>[<<<<<<<+>>>>>>>-]<---------------------------------------------[<->[-]>[-]+>[-]>[-]<+>>[-]<[-]<<<<<<<<<[>>>>>>>>>+>+<<<<<<<<<<-]>>>>>>>>>>[<<<<<<<<<<+>>>>>>>>>>-]<----------[<->[-]<<<<<<<<<------------------------------------------------>>>>>>>>>>[-]++++++++++<<<<<<>>>>>>>[-]>[-]<<<<<<<<[>>>>>>>>+<<<<<<<<-]>>>>>>>>[<<[<<<<<<+>>>>>>>+<-]>[<+>-]>-]<<<<<<<<<<<<[->>>>+<<<<]>>>>>>>>>]<[<->-]<[<<<<<<<,>>>>>>>>[-]>[-]<+>>[-]<[-]<<<<<<<<<[>>>>>>>>>+>+<<<<<<<<<<-]>>>>>>>>>>[<<<<<<<<<<+>>>>>>>>>>-]<----------[<->[-]<<<<<<<<<------------------------------------------------>>>>>>>>>>[-]++++++++++<<<<<<>>>>>>>[-]>[-]<<<<<<<<[>>>>>>>>+<<<<<<<<-]>>>>>>>>[<<[<<<<<<+>>>>>>>+<-]>[<+>-]>-]<<<<<<<<<<<<[->>>>+<<<<]>>>>>>>>>]<[<->-]<]<]<[>>[-]+[<<<<<<<,>>>>>>>>[-]>[-]<+>>[-]<[-]<<<<<<<<<[>>>>>>>>>+>+<<<<<<<<<<-]>>>>>>>>>>[<<<<<<<<<<+>>>>>>>>>>-]<----------[<->[-]<<<<<<<<<------------------------------------------------>>>>>>>>>>[-]++++++++++<<<<<<>>>>>>>[-]>[-]<<<<<<<<[>>>>>>>>+<<<<<<<<-]>>>>>>>>[<<[<<<<<<+>>>>>>>+<-]>[<+>-]>-]<<<<<<<<<<<<[->>>>-<<<<]>>>>>>>>>]<[<->-]<]<<-]<+>[-]>[-]>[-]>[-]>[-]>[-]<<<<+<[-]>>>[-]<<<<<<<[>>>>>>>+<<<+<<<<-]>>>>[<<<<+>>>>-][-]>>>>[-]<<<<<[>>>>>+<<<<+<-]>[<+>-]>>>+>+<[->-[>]<<]<[-<<<[-]+>>>]<[-<<<+>>[-]>[-]>[-]>[-]>[-]>[-]<<<<+<[-]>>>[-]<<<<<[>>>>>+<<<+<<-]>>[<<+>>-][-]>>>>[-]<<<<<<<[>>>>>>>+<<<<+<<<-]>>>[<<<+>>>-]>>>+>+<[->-[>]<<]<[-<<<<[-]>>>[-]<<<[-]>[<+>>>+<<-]>>[<<+>>-]>]<[-<]]<-<<>>>[-]>[-]>[-]>[-]>[-]>[-]<<<[-]<<<<<[>>>>>+>>>+<<<<<<<<-]>>>>>>>>[<<<<<<<<+>>>>>>>>-]<<<<<<<<[>>>>>>>>[-]++++++++++>[-]>[-]>[-]>[-]>[-]<+[<+>>>[-]+>[-]>[-]<[-]<<<<<<<<<<<<<<<[>>>>>>>>>>>>>>>+>+<<<<<<<<<<<<<<<<-]>>>>>>>>>>>>>>>>[<<<<<<<<<<<<<<<<+>>>>>>>>>>>>>>>>-]<[>[-]<<<[-]<<<<<[>>>>>+>>>+<<<<<<<<-]>>>>>>>>[<<<<<<<<+>>>>>>>>-]<<<-[<<<<<<<<<<<<<->>>>>>>>>>>>>->>>[-]+>[-]>[-]<[-]<<<<<<<<<<<<<<<<<[>>>>>>>>>>>>>>>>>+>+<<<<<<<<<<<<<<<<<<-]>>>>>>>>>>>>>>>>>>[<<<<<<<<<<<<<<<<<<+>>>>>>>>>>>>>>>>>>-]<[<->[-]][-]>[-]<[-]<[>+>+<<-]>>[<<+>>-]<[<<<<<<<+>>>[<<<+>>>-]<<<<<<<<<<<<<+>>>>>>>>>>>>->>>>>[-]]<<<<]>->[-]][-]>[-]<[-]<[>+>+<<-]>>[<<+>>-]<[<<<->>>>[-]<<<<<<[-]<<[>>+>>>>>>+<<<<<<<<-]>>>>>>>>[<<<<<<<<+>>>>>>>>-]<[-]]<<<<<<<<<<<<<<<->>>>>>>>>>>>]<->>>[-]<<<<<[-]<[>+>>>>>+<<<<<<-]>>>>>>[<<<<<<+>>>>>>-]<<<<[<->-]<<<<<<<<<<[-]>>>>>>>>>>>[<<<<<<<<<<<+>>>>>>>>>>>-]<<<<<<<<+<<<]>>>>>>>>[-]>[-]<+>>[-]<[-]<<<<<<[>>>>>>+>+<<<<<<<-]>>>>>>>[<<<<<<<+>>>>>>>-]<[<->[-]>[-]<<<<<<<<<<[-]>>>>>[<<<<<+>>>>>>>>>>+<<<<<-]>>>>>[<<<<<+>>>>>-]<<<<<<<[>>>>>>>[-]<<<[-]<<<<[>>>>+>>>+<<<<<<<-]>>>>>>>[<<<<<<<+>>>>>>>-]<<<<[-]+>-[>>>[-]++++++++++<<<<>>>>>[-]>[-]<<<<<<[>>>>>>+<<<<<<-]>>>>>>[<<[<<<<+>>>>>+<-]>[<+>-]>-]<<<<<-]>>>[-]<<<<<<[-]<<<<[>>>>+>>>>>>+<<<<<<<<<<-]>>>>>>>>>>[<<<<<<<<<<+>>>>>>>>>>-][-]>[-]>[-]>[-]>[-]<+[<+>>>[-]+>[-]>[-]<[-]<<<<<<<<<<<<[>>>>>>>>>>>>+>+<<<<<<<<<<<<<-]>>>>>>>>>>>>>[<<<<<<<<<<<<<+>>>>>>>>>>>>>-]<[>[-]<<<[-]<<<<<<<<[>>>>>>>>+>>>+<<<<<<<<<<<-]>>>>>>>>>>>[<<<<<<<<<<<+>>>>>>>>>>>-]<<<-[<<<<<<<<<<->>>>>>>>>>->>>[-]+>[-]>[-]<[-]<<<<<<<<<<<<<<[>>>>>>>>>>>>>>+>+<<<<<<<<<<<<<<<-]>>>>>>>>>>>>>>>[<<<<<<<<<<<<<<<+>>>>>>>>>>>>>>>-]<[<->[-]][-]>[-]<[-]<[>+>+<<-]>>[<<+>>-]<[<<<<<<<+>>>[<<<+>>>-]<<<<<<<<<<+>>>>>>>>>->>>>>[-]]<<<<]>->[-]][-]>[-]<[-]<[>+>+<<-]>>[<<+>>-]<[<<<->>>>[-]<<<<<<[-]<<<<<[>>>>>+>>>>>>+<<<<<<<<<<<-]>>>>>>>>>>>[<<<<<<<<<<<+>>>>>>>>>>>-]<[-]]<<<<<<<<<<<<->>>>>>>>>]<->>>[-]<<<<<[-]<<<<[>>>>+>>>>>+<<<<<<<<<-]>>>>>>>>>[<<<<<<<<<+>>>>>>>>>-]<<<<[<->-]<<<<<<<[-]>>>>>>>>[<<<<<<<<+>>>>>>>>-]<<<<<<<<++++++++++++++++++++++++++++++++++++++++++++++++.>>>>>>>[-]<<<<<<<<<<<[-]>>>>>>>>>>[<<<<<<<<<<+>>>>>>>>>>>+<-]>[<+>-]<<<<<<<<-]>>>>>>]<[<<<<<<<<[-].>>>>>>>>-][-]<<<<<<<<[-]>>>>>[<<<<<+>>>>>>>>+<<<-]>>>[<<<+>>>-] Index: 11 Memory (22/3000 bytes): #0 #1 #2 #3 #4 #5 #6 #7 #8 #9 [0] [10] [-3] [4] [4] [8] [0] [52] [4] [1] [ ] [\n] [ ] [ ] [ ] [ ] [ ] [4] [ ] [ ] l $ l m c i e i a a o n n s x u g p t n t u t h t Result: 4
Скопируем код и проверим его на этом замечательном сайте:
https://esolangpark.vercel.app/ide/brainfuck
Интерпретатор на C
Круто, все работает, теперь давайте пересеем это в переменные в C, где повторы из +-<>
символов будут убраны, а количество повторов будет в массив repeats
, получаем следующее:
char commands[] = "@>@+>@>@<@<[>+>+<-]>[<+>-]<[<->@]@>@<@<[>+>+<-]>[<+>-]<[@]<@>@,>@>@<+>@<@<[>+>+<-]>[<+>-]<-[<->@>@+>@>@<+>@<@<[>+>+<-]>[<+>-]<-[<->@<->@+<>@>@<[>+<-]>[<[<+>+<-]>[<+>-]>-]<[-<+>]>]<[<->-]<[<,>@>@<+>@<@<[>+>+<-]>[<+>-]<-[<->@<->@+<>@>@<[>+<-]>[<[<+>+<-]>[<+>-]>-]<[-<+>]>]<[<->-]<]<]<[>@+[<,>@>@<+>@<@<[>+>+<-]>[<+>-]<-[<->@<->@+<>@>@<[>+<-]>[<[<+>+<-]>[<+>-]>-]<[-<->]>]<[<->-]<]<-]<->@@<,>@>@<+>@<@<[>+>+<-]>[<+>-]<-[<->@>@+>@>@<+>@<@<[>+>+<-]>[<+>-]<-[<->@<->@+<>@>@<[>+<-]>[<[<+>+<-]>[<+>-]>-]<[->+<]>]<[<->-]<[<,>@>@<+>@<@<[>+>+<-]>[<+>-]<-[<->@<->@+<>@>@<[>+<-]>[<[<+>+<-]>[<+>-]>-]<[->+<]>]<[<->-]<]<]<[>@+[<,>@>@<+>@<@<[>+>+<-]>[<+>-]<-[<->@<->@+<>@>@<[>+<-]>[<[<+>+<-]>[<+>-]>-]<[->-<]>]<[<->-]<]<-]@>@>@<[>@<,>@>@<+>@<@<[>+>+<-]>[<+>-]<-[<->@>@+>@>@<+>@<@<[>+>+<-]>[<+>-]<-[<->@<->@+<>@>@<[>+<-]>[<[<+>+<-]>[<+>-]>-]<[->+<]>]<[<->-]<[<,>@>@<+>@<@<[>+>+<-]>[<+>-]<-[<->@<->@+<>@>@<[>+<-]>[<[<+>+<-]>[<+>-]>-]<[->+<]>]<[<->-]<]<]<[>@+[<,>@>@<+>@<@<[>+>+<-]>[<+>-]<-[<->@<->@+<>@>@<[>+<-]>[<[<+>+<-]>[<+>-]>-]<[->-<]>]<[<->-]<]<-]<+>@>@>@>@>@>@<+<@>@<[>+<+<-]>[<+>-]@>@<[>+<+<-]>[<+>-]>+>+<[->-[>]<]<[-<@+>]<[-<+>@>@>@>@>@>@<+<@>@<[>+<+<-]>[<+>-]@>@<[>+<+<-]>[<+>-]>+>+<[->-[>]<]<[-<@>@<@>[<+>+<-]>[<+>-]>]<[-<]]<->@<@>[<+>+<-]>[<+>-]<-]>@<,>@>@<+>@<@<[>+>+<-]>[<+>-]<-[<->@>@+>@>@<+>@<@<[>+>+<-]>[<+>-]<-[<->@<->@+<>@>@<[>+<-]>[<[<+>+<-]>[<+>-]>-]<[->+<]>]<[<->-]<[<,>@>@<+>@<@<[>+>+<-]>[<+>-]<-[<->@<->@+<>@>@<[>+<-]>[<[<+>+<-]>[<+>-]>-]<[->+<]>]<[<->-]<]<]<[>@+[<,>@>@<+>@<@<[>+>+<-]>[<+>-]<-[<->@<->@+<>@>@<[>+<-]>[<[<+>+<-]>[<+>-]>-]<[->-<]>]<[<->-]<]<-]<+>@>@>@>@>@>@<+<@>@<[>+<+<-]>[<+>-]@>@<[>+<+<-]>[<+>-]>+>+<[->-[>]<]<[-<@+>]<[-<+>@>@>@>@>@>@<+<@>@<[>+<+<-]>[<+>-]@>@<[>+<+<-]>[<+>-]>+>+<[->-[>]<]<[-<@>@<@>[<+>+<-]>[<+>-]>]<[-<]]<-<>@>@>@>@>@>@<@<[>+>+<-]>[<+>-]<[>@+>@>@>@>@>@<+[<+>@+>@>@<@<[>+>+<-]>[<+>-]<[>@<@<[>+>+<-]>[<+>-]<-[<->->@+>@>@<@<[>+>+<-]>[<+>-]<[<->@]@>@<@<[>+>+<-]>[<+>-]<[<+>[<+>-]<+>->@]<]>->@]@>@<@<[>+>+<-]>[<+>-]<[<->@<@<[>+>+<-]>[<+>-]<@]<->]<->@<@<[>+>+<-]>[<+>-]<[<->-]<@>[<+>-]<+<]>@>@<+>@<@<[>+>+<-]>[<+>-]<[<->@>@<@>[<+>+<-]>[<+>-]<[>@<@<[>+>+<-]>[<+>-]<@+>-[>@+<>@>@<[>+<-]>[<[<+>+<-]>[<+>-]>-]<-]>@<@<[>+>+<-]>[<+>-]@>@>@>@>@<+[<+>@+>@>@<@<[>+>+<-]>[<+>-]<[>@<@<[>+>+<-]>[<+>-]<-[<->->@+>@>@<@<[>+>+<-]>[<+>-]<[<->@]@>@<@<[>+>+<-]>[<+>-]<[<+>[<+>-]<+>->@]<]>->@]@>@<@<[>+>+<-]>[<+>-]<[<->@<@<[>+>+<-]>[<+>-]<@]<->]<->@<@<[>+>+<-]>[<+>-]<[<->-]<@>[<+>-]<+.>@<@>[<+>+<-]>[<+>-]<-]>]<[<@.>-]@<@>[<+>+<-]>[<+>-]"; char repeats[] = { 1,1,1,1,1,2,2,1,1,1,3,1,3,3,1,3,1,1,1,1,1,1,1,1,1,1,1,1,2,1,2,2,1,2,1,1,2,1,1,1,1,1,2,1,2,2,1,1,1,3,1,3,3,1,3,1,1,45,1,1,1,1,1,1,1,1,1,2,1,5,5,1,1,1,6,1,6,6,1,6,1,1,10,1,1,1,5,48,6,10,7,8,1,9,9,1,9,1,9,2,7,1,8,1,1,1,1,1,1,1,1,1,1,8,1,1,1,1,5,1,1,1,1,1,1,3,4,1,1,1,2,1,5,5,1,1,1,6,1,6,6,1,6,1,1,10,1,1,1,5,48,6,10,7,8,1,9,9,1,9,1,9,2,7,1,8,1,1,1,1,1,1,1,1,1,1,8,1,1,1,1,5,1,1,1,1,1,1,1,1,2,1,3,4,1,1,1,2,1,5,5,1,1,1,6,1,6,6,1,6,1,1,10,1,1,1,5,48,6,10,7,8,1,9,9,1,9,1,9,2,7,1,8,1,1,1,1,1,1,1,1,1,1,8,1,1,1,1,5,1,1,1,1,1,1,2,1,2,2,2,1,2,1,1,1,2,1,3,3,1,1,1,4,1,4,4,1,4,1,1,45,1,1,1,1,1,1,1,1,1,2,1,6,6,1,1,1,7,1,7,7,1,7,1,1,32,1,1,1,6,48,7,10,6,7,1,8,8,1,8,1,8,2,6,1,7,1,1,1,1,1,1,1,1,1,1,9,1,1,1,1,6,1,1,1,1,1,1,4,5,1,1,1,2,1,6,6,1,1,1,7,1,7,7,1,7,1,1,32,1,1,1,6,48,7,10,6,7,1,8,8,1,8,1,8,2,6,1,7,1,1,1,1,1,1,1,1,1,1,9,1,1,1,1,6,1,1,1,1,1,1,1,1,2,1,4,5,1,1,1,2,1,6,6,1,1,1,7,1,7,7,1,7,1,1,32,1,1,1,6,48,7,10,6,7,1,8,8,1,8,1,8,2,6,1,7,1,1,1,1,1,1,1,1,1,1,9,1,1,1,1,6,1,1,1,1,1,1,2,1,1,1,5,5,4,5,1,1,1,2,1,6,6,1,1,1,7,1,7,7,1,7,1,1,45,1,1,1,1,1,1,1,1,1,2,1,9,9,1,1,1,10,1,10,10,1,10,1,1,32,1,1,1,9,48,10,10,6,7,1,8,8,1,8,1,8,2,6,1,7,1,1,1,1,1,1,1,1,1,1,12,1,4,1,4,9,1,1,1,1,1,1,7,8,1,1,1,2,1,9,9,1,1,1,10,1,10,10,1,10,1,1,32,1,1,1,9,48,10,10,6,7,1,8,8,1,8,1,8,2,6,1,7,1,1,1,1,1,1,1,1,1,1,12,1,4,1,4,9,1,1,1,1,1,1,1,1,2,1,7,8,1,1,1,2,1,9,9,1,1,1,10,1,10,10,1,10,1,1,32,1,1,1,9,48,10,10,6,7,1,8,8,1,8,1,8,2,6,1,7,1,1,1,1,1,1,1,1,1,1,12,1,4,1,4,9,1,1,1,1,1,1,2,1,1,1,1,1,1,1,1,1,4,1,1,3,7,7,1,3,1,4,1,4,4,1,4,1,4,5,5,1,4,1,1,1,1,1,1,1,1,3,1,1,1,1,1,1,1,1,2,1,1,3,1,3,1,1,3,1,2,1,1,1,1,1,4,1,1,3,5,5,1,3,1,2,1,2,2,1,2,1,4,7,7,1,4,1,3,1,3,3,1,3,1,3,1,1,1,1,1,1,1,1,2,1,1,4,3,3,1,1,1,3,1,2,1,2,2,1,2,1,1,1,1,1,1,1,1,4,3,3,1,4,1,1,1,1,1,1,1,1,6,1,5,4,5,1,1,1,2,1,6,6,1,1,1,7,1,7,7,1,7,1,1,45,1,1,1,1,1,1,1,1,1,2,1,9,9,1,1,1,10,1,10,10,1,10,1,1,10,1,1,1,9,48,10,10,6,7,1,8,8,1,8,1,8,2,6,1,7,1,1,1,1,1,1,1,1,1,1,12,1,4,1,4,9,1,1,1,1,1,1,7,8,1,1,1,2,1,9,9,1,1,1,10,1,10,10,1,10,1,1,10,1,1,1,9,48,10,10,6,7,1,8,8,1,8,1,8,2,6,1,7,1,1,1,1,1,1,1,1,1,1,12,1,4,1,4,9,1,1,1,1,1,1,1,1,2,1,7,8,1,1,1,2,1,9,9,1,1,1,10,1,10,10,1,10,1,1,10,1,1,1,9,48,10,10,6,7,1,8,8,1,8,1,8,2,6,1,7,1,1,1,1,1,1,1,1,1,1,12,1,4,1,4,9,1,1,1,1,1,1,2,1,1,1,1,1,1,1,1,1,4,1,1,3,7,7,1,3,1,4,1,4,4,1,4,1,4,5,5,1,4,1,1,1,1,1,1,1,1,3,1,1,1,1,1,1,1,1,2,1,1,3,1,3,1,1,3,1,2,1,1,1,1,1,4,1,1,3,5,5,1,3,1,2,1,2,2,1,2,1,4,7,7,1,4,1,3,1,3,3,1,3,1,3,1,1,1,1,1,1,1,1,2,1,1,4,3,3,1,1,1,3,1,2,1,2,2,1,2,1,1,1,1,1,1,1,2,3,1,1,1,1,1,3,5,5,1,3,1,8,1,8,8,1,8,1,8,8,10,1,1,1,1,1,1,1,1,1,3,1,1,1,1,15,15,1,1,1,16,1,16,16,1,16,1,1,1,3,5,5,1,3,1,8,1,8,8,1,8,1,3,1,13,1,13,1,3,1,1,1,1,17,17,1,1,1,18,1,18,18,1,18,1,1,1,1,1,1,1,1,1,1,1,1,2,1,2,2,1,2,1,1,7,1,3,3,1,3,1,13,1,12,1,5,4,1,1,1,1,1,1,1,1,1,1,2,1,2,2,1,2,1,1,3,1,4,6,2,2,1,6,1,8,1,8,8,1,8,1,1,15,1,12,1,1,3,5,1,1,1,5,1,6,1,6,6,1,6,1,4,1,1,1,1,10,11,11,1,11,1,8,1,3,8,1,1,1,2,1,6,6,1,1,1,7,1,7,7,1,7,1,1,1,1,1,1,10,5,5,1,10,1,5,1,5,5,1,5,1,7,7,3,4,4,1,3,1,7,1,7,7,1,7,1,4,1,1,1,3,10,4,5,1,6,6,1,6,1,6,2,4,1,5,1,1,1,1,1,1,1,1,1,1,5,1,3,6,4,4,1,6,1,10,1,10,10,1,10,1,1,1,1,1,1,1,1,1,3,1,1,1,1,12,12,1,1,1,13,1,13,13,1,13,1,1,1,3,8,8,1,3,1,11,1,11,11,1,11,1,3,1,10,1,10,1,3,1,1,1,1,14,14,1,1,1,15,1,15,15,1,15,1,1,1,1,1,1,1,1,1,1,1,1,2,1,2,2,1,2,1,1,7,1,3,3,1,3,1,10,1,9,1,5,4,1,1,1,1,1,1,1,1,1,1,2,1,2,2,1,2,1,1,3,1,4,6,5,5,1,6,1,11,1,11,11,1,11,1,1,12,1,9,1,1,3,5,4,4,1,5,1,9,1,9,9,1,9,1,4,1,1,1,1,7,8,8,1,8,1,8,48,7,11,10,10,1,11,1,1,1,1,1,1,1,1,8,1,6,1,8,8,1,8,5,5,1,8,1,3,1,3,3,1,3,1 };
Выделим память для исполнения brainfuck-кода, наша версия интерпретатора будет иметь большую разрядность чтобы можно было работать с большими числами:
#define BUFFER_SIZE 220 short int buffer[BUFFER_SIZE]; for (int i = 0; i < BUFFER_SIZE; i++) { buffer[i] = 0; }
Если команды +-<>,.
максимально просты для реализации, то для реализации []
продеться немного потрудиться: создадим массив в котором будем хранить индексы пар скобок и индекс массива repeats
для каждой скобки:
unsigned int openi[sizeof(commands)]; unsigned int openr[sizeof(commands)];
Для определения индексов создадим стек:
int stack[10000]; // Тут будем хранить индексы команд int rstack[10000]; // Тут будем хранить индексы повторов int top = -1;
Теперь заполним массивы openi
и openr
:
int repatIndex = 0; for (int i = 0; i < sizeof(commands); i++) { if (commands[i] == ']') { // Забираем последний элемент из стека и записывам результаты в массивы индексов и повторений int openIndex = stack[top]; int openRs = rstack[top]; top--; openi[i] = openIndex; openr[i] = openRs; openi[openIndex] = i; openr[openIndex] = rs; continue; } openi[i] = 0; openr[i] = 0; if (commands[i] == '[') { // Добавляем в стек индекс и индекс повторения top++; stack[top] = i; rstack[top] = rs; continue; } if (commands[i] == '+' || commands[i] == '-' || commands[i] == '>' || commands[i] == '<') { // Если символ поддерживает повторение то смещаем индекс поторения rs++; openr[i] = rs; repatIndex++; continue; } }
Теперь, когда мы можем легко переходить к определенному элементу массива, то напишем код, который будет проходится по brainfuck-командам:
int index = 0; // Индек указывающий на выбранную ячейку памяти char c; unsigned int i = 0; // Индекс для чтения массива команд unsigned int ri = 0; // Индекс для чтения массива повторений while (1) { c = commands[i]; if (c == '@') { // Наш специальный символ для обнуления массива, он эпителиален конструкции [-] buffer[index] = 0; } else if (c == '>') { // Символ смещающий индекс ячейки (вправо) index+= repeats[ri]; // Смещаемм индекс на количество подряд идущих символов в сиходном коде ri++; } else if (c == '<') { // Символ смещающий индекс ячейки (влево) index-=repeats[ri]; // Смещаемм индекс на количество подряд идущих символов в сиходном коде ri++; } else if (c == '+') { // Символ изменения значения ячейки (добавление 1) buffer[index]+= repeats[ri]; // Изменяем значение на количество подряд идущих символов в сиходном коде ri++; } else if (c == '-') { // Символ изменения значения ячейки (вычитание 1) buffer[index]-= repeats[ri]; // Изменяем значение на количество подряд идущих символов в сиходном коде ri++; } else if (c == '.') { // Выводим значение ячейки в символьном виде printf("%c", buffer[index]); } else if (c == ',') { // Читаем значение в ячейку char read = 0; scanf_s("%c", &read); buffer[index] = read; } else if (c == '[') { // Начало цикла if (buffer[index] == 0) { // Если значение 0 то сразу переходи к паре int d = 0; ri = openr[i]; i = openi[i]; i++; continue; } } else if (c == ']') { if (buffer[index] != 0) { // Если значение не 0 то сразу переходи к парной открывающей скобке ri = openr[i]; i = openi[i]; // jump to pair - '[' continue; // prevent i++ } } if (i < 0) { printf("ERROR i < 0: %d", i); break; } i++; if (i >= strlen(commands)) break; }
В итоге получился следующий код:
#include #include #include #include #define BUFFER_SIZE 220 char commands[] = ...; char repeats[] = {...}; unsigned int openi[sizeof(commands)]; unsigned int openr[sizeof(commands)]; void init() { int stack[10000]; int rstack[10000]; int top = -1; int rs = 0; int repatIndex = 0; for (int i = 0; i < sizeof(commands); i++) { if (commands[i] == ']') { int openIndex = stack[top]; int openRs = rstack[top]; top--; openi[i] = openIndex; openr[i] = openRs; openi[openIndex] = i; openr[openIndex] = rs; continue; } openi[i] = 0; openr[i] = 0; if (commands[i] == '[') { top++; stack[top] = i; rstack[top] = rs; continue; } if (commands[i] == '+' || commands[i] == '-' || commands[i] == '>' || commands[i] == '<') { rs++; openr[i] = rs; repatIndex++; continue; } } } int main() { init(); short int buffer[BUFFER_SIZE]; for (int i = 0; i < BUFFER_SIZE; i++) { buffer[i] = 0; } int index = 0; char c; unsigned int i = 0; unsigned int ri = 0; while (1) { c = commands[i]; if (c == '@') { buffer[index] = 0; } else if (c == '>') { index+= repeats[ri]; ri++; } else if (c == '<') { index-=repeats[ri]; ri++; } else if (c == '+') { buffer[index]+= repeats[ri]; ri++; } else if (c == '-') { buffer[index]-= repeats[ri]; ri++; } else if (c == '.') { printf("%c", buffer[index]); } else if (c == ',') { char read = 0; scanf_s("%c", &read); buffer[index] = read; } else if (c == '[') { if (buffer[index] == 0) { ri = openr[i]; i = openi[i]; i++; continue; } } else if (c == ']') { if (buffer[index] != 0) { ri = openr[i]; i = openi[i]; continue; } } if (i < 0) { printf("ERROR i < 0: %d", i); break; } i++; if (i >= strlen(commands)) break; } return 0; }
Запускаем программу для проверки и вводим:
7 1 2 3 -1 3 4 8
Отлично, программа вывела 4
Что можно улучшить?
-
Насколько мне известно существуют более быстрые версии интерпретаторов
-
Скорее всего математические действия в brainfuck можно улучшить при помощи хитрой математики, но я пока что в эту область не лазил
-
Ну естественно стоит написать больше различных функций по типу возведения в степень и так далее
-
Можно добавить переменные занимающие несколько ячеек и математику с ними
-
Добавить разные массивы, стеки и прочие полезные штуки
А зачем все это было?
Ну почему бы и нет, решить задачу таким образом было достаточно интересно.
Полезные ссылки
Удобнейшая среда разработки под Brainfuck и не только: https://esolangpark.vercel.app/ide/brainfuck
Wiki по эзотерическим языкам программирования: https://esolangs.org/wiki
Мой генератор: https://github.com/Agzam4/BrainfuckCodeGeneraor
PS:
жду дум на brainfuck-е
ссылка на оригинал статьи https://habr.com/ru/articles/846076/
Добавить комментарий