JavaRush /Java блог /Архив info.javarush /Тестовое задание: "Написать Интерпретатор на язык BrainFu...
Roman_kh
33 уровень
Харьков

Тестовое задание: "Написать Интерпретатор на язык BrainFuck"

Статья из группы Архив info.javarush
Привет всем! Сегодня хочу поделится другой задачей, которая была у меня на собеседовании. Задача, которая проверит как Вы можете мыслить, как пишете код. Задача в общем полезная для развития. Написать интерпретатор на язык программирования BrainFuck. Для примера взять исходный код на BrainFuck: ++++++++++[>+++++++>++++++++++>+++>+<<<<-]>++ .>+.+++++++..+++.>++.<<+++++++++++++++.>.+++. ------.--------.>+.>. печатающий «Hello World!» У вас есть на это 1.5 - 2 часа. Вперед! Вот и всё... Вот и всё условие задачи. Я вас всех прекрастно понимаю. Для того, чтобы понять вообще что делать, нужно разобраться с двумя терминами:
  • Что такое интерпретатор?
  • Что такое BrainFuck?
Вам придется с этим разобраться, т.к. задача действительно интересная. Для тех, кто будет разбираться скажу - сложность в том, чтобы построить логику циклов. Всем кому задача стала полезной - ставим "+". Решайте задачи, пишите код и вы станете Java разработчиками! Удачи! См. также мои другие статьи: Тестовое задание "Image Comparison"
Java - быстрее, сильнее и выше! Зарплаты украинских программистов.
История успеха спустя 1.5 года от начала обучения
Технические вопросы на собеседовании.
Как найти работу? Рассылка резюме
Профессиональное выгорание. Как устоять?
Английский для IT и для собеседования
Паттерн Command своими словами.
Паттерн Singleton своими словами.
Как создать исполняемый jar в Intellij IDEA / how to create jar in IDEA
Помогите, нужна мотивация!
Комментарии (16)
ЧТОБЫ ПОСМОТРЕТЬ ВСЕ КОММЕНТАРИИ ИЛИ ОСТАВИТЬ КОММЕНТАРИЙ,
ПЕРЕЙДИТЕ В ПОЛНУЮ ВЕРСИЮ
alexeyfrei Уровень 34
10 февраля 2017
Почему вдруг задание идитское? А какие надо давать задания при том, что ты не хочешь, чтобы какой-то товарищ сидел у тебя в офисе неделю?
Задание гораздо проще, чем про обработку картинок. Достаточно прочитать про brainfuck операторы (а их всего 8) и соответсвенно написать 8 switch-case. Чуть приходиться попыхтетть над обработкой циклов, но тут помогает очередь.
Java-boy Уровень 27
8 февраля 2017
Понял что первая версия не обрабатывает вложенные циклы, поэтому вот:
<code>public class Interpreter {

    private static char[] fuckCode;
    private static char[] resultCode = new char[30000];

    public void readCodeFromString(String code) {
        fuckCode = code.toCharArray();
    }

    public void logic() {
        int j = 0;
        Deque<Integer> stackIndex = new ArrayDeque<>();

        for (int i = 0; i < fuckCode.length; i++) {
            switch (fuckCode[i]) {
                case '>':
                    j++;
                    break;
                case '<':
                    j--;
                    break;
                case '+':
                    resultCode[j]++;
                    break;
                case '-':
                    resultCode[j]--;
                    break;
                case '.':
                    System.out.print(resultCode[j]);
                    break;
                case '[':
                    stackIndex.addLast(i);
                    break;
                case ']':
                    if (resultCode[j] != 0) {
                        i = stackIndex.pollLast();
                        --i;
                    } else {
                        if (!stackIndex.isEmpty()) {
                            stackIndex.removeLast();
                        }
                    }
                    break;
            }
        }
    }

    public static void main(String[] args) {
        Interpreter interpreter = new Interpreter();
        interpreter.readCodeFromString(args[0]);   //Не хотите cmd замените на строку.
        interpreter.logic();
    }
}</code>
Himeg Уровень 15
7 февраля 2017
Хелоуворлд, например! А также, раз варианты уже публикуют, то:
public class BrainFuckInterpreter
{
    private static Class c;
    private static String code;
    private static int[] memory;
    private static HashMap<Character, String> syntax;
    private static int currentCell, charIndex;
    private static ArrayList<Integer> cyclePositions;

    private static void activateSyntax()
    {
        memory = new int[30000];
        currentCell = 0;
        charIndex = 0;
        cyclePositions = new ArrayList<>();
        syntax = new HashMap<>();
        syntax.put('+', "increase");
        syntax.put('-', "decrease");
        syntax.put('.', "print");
        syntax.put('>', "nextCell");
        syntax.put('<', "previousCell");
        syntax.put('[', "cycle");
        syntax.put(']', "repeat");
    }

    private static void increase() { memory[currentCell]++; }
    private static void decrease() { memory[currentCell]--; }
    private static void print() { System.out.print((char) memory[currentCell]); }
    private static void nextCell() { currentCell++; }
    private static void previousCell() { currentCell--; }

    private static void cycle()
    {
        int index = code.length() - 1;
        for (int i = 1; i <= cyclePositions.size() + 1; i++) while (code.charAt(index) != ']') index--;
        if (memory[currentCell] == 0) charIndex = index;
        else cyclePositions.add(charIndex);
    }

    private static void repeat()
    {
        if (memory[currentCell] != 0) charIndex = cyclePositions.get(cyclePositions.size() - 1);
        else cyclePositions.remove(cyclePositions.size() - 1);
    }

    private static void interpretNext() throws NoSuchMethodException, InvocationTargetException, IllegalAccessException
    {
        c.getDeclaredMethod(syntax.get(code.charAt(charIn
Java-boy Уровень 27
7 февраля 2017
Ну как-то так:
Код берем из файла, путь к файлу из командной строки.
public class Interpretator {

    private static String path;
    private static char[] fuckCode = new char[30000];
    private static char[] resultCode = new char[30000];

    public void readCode() {
        try (FileReader reader = new FileReader(new File(path))) {
            reader.read(fuckCode);
        }
        catch (IOException e) {
            e.printStackTrace();
        }
    }

    public void logic() {
        int j = 0;
        int n = 0;
        
        for (int i = 0; i < fuckCode.length; i++) {
            switch (fuckCode[i]) {
                case '>':
                    j++;
                    break;
                case '<':
                    j--;
                    break;
                case '+':
                    resultCode[j]++;
                    break;
                case '-':
                    resultCode[j]--;
                    break;
                case '.':
                    System.out.print(resultCode[j]);
                    break;
                case '[':
                    n = i;
                    if (resultCode[j] != 0) {
                        if (fuckCode[i] == ']') resultCode[j]--;
                        continue;
                    }
                    break;
                case ']':
                    if (resultCode[j] != 0) {
                        i = n;
                        continue;
                    }
                    break;
            }
        }
    }

    public Interpretator(String path) {
        this.path = path;
    }

    public static void main(String[] args) {
        Interpretator interpretator = new Interpretator(args[0]);
        interpretator.readCode();
        interpretator.logic();
    }
}
Torin Уровень 27
6 февраля 2017
Т.е. это должна быть программа, которая на вход получит текст написанный в стиле BrainFuck а на выход выдаст результат Hello World? я читал про этот язык, видел на нем программы, подтверждаю, название соответствует истине. Но от этого не менее интересно. Спасибо за задачу, обязательно решу позже. Жаль похвастаться решением перед всеми не получится, но зато я возьму ее на вооружение :)

ЗЫ еще хотелось бы как-то что бы в куче были задания для trainee, все таки штука ОЧЕНЬ полезная, и хотелось бы видеть их в одном месте (например, в блоге). Сейчас я насчитал 4 задачи для трейни:

1) палиндром
2) анализ картинок
3) брэинфак
4) Spreadshit Simulator
dit Уровень 6
6 февраля 2017
Я правда не знаю, но тут должно быть два варианта:
1. На данной вакансии Вам предлагают звиздец какие деньги.
2. Над Вами жестко глумятся и Вам это ой как нравится.

Вся эта чухня взята из википедии и вшита в тесты каким-то задротом, либо смотреть на Вашу реакцию или реально стебутся. Отсюда вывод, или деньги или мазохизм.
Пусть пока что у меня нет примеров тестовых заданий в сфере программирования, но я работаю админом, и когда мне задают идиотские вопросы из разряда «почему вы считаете что вы нам подходите» (и да я понимаю что все это чисто психологический тест), то порой мне просто хочется встать и уйти со словами «почему вы считаете что вы мне подходите? Ибо пригласили меня к вам именно вы, а я собственно не навязывался». Вот такие конторы я обхожу десятой дорогой.