• ,

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

Привет всем!

Сегодня хочу поделится другой задачей, которая была у меня на собеседовании. Задача, которая проверит как Вы можете мыслить, как пишете код. Задача в общем полезная для развития.

Написать интерпретатор на язык программирования 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 комментариев

dit
  • dit
  • 0
Я правда не знаю, но тут должно быть два варианта:
1. На данной вакансии Вам предлагают звиздец какие деньги.
2. Над Вами жестко глумятся и Вам это ой как нравится.

Вся эта чухня взята из википедии и вшита в тесты каким-то задротом, либо смотреть на Вашу реакцию или реально стебутся. Отсюда вывод, или деньги или мазохизм.
Пусть пока что у меня нет примеров тестовых заданий в сфере программирования, но я работаю админом, и когда мне задают идиотские вопросы из разряда «почему вы считаете что вы нам подходите» (и да я понимаю что все это чисто психологический тест), то порой мне просто хочется встать и уйти со словами «почему вы считаете что вы мне подходите? Ибо пригласили меня к вам именно вы, а я собственно не навязывался». Вот такие конторы я обхожу десятой дорогой.
JuriMik
  • JuriMik
  • 0
  • Комментарий отредактирован 2017-02-08 23:29:22 пользователем JuriMik
Про десятую дорогу согласен на 100%.

А вообще видел это тестовое где-то в нете, посмеялся и не более.
Torin
  • Torin
  • +1
  • Комментарий отредактирован 2017-02-06 18:02:29 пользователем Torin
Т.е. это должна быть программа, которая на вход получит текст написанный в стиле BrainFuck а на выход выдаст результат Hello World? я читал про этот язык, видел на нем программы, подтверждаю, название соответствует истине. Но от этого не менее интересно. Спасибо за задачу, обязательно решу позже. Жаль похвастаться решением перед всеми не получится, но зато я возьму ее на вооружение :)

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

1) палиндром
2) анализ картинок
3) брэинфак
4) Spreadshit Simulator
Himeg
Spreadshit Simulator это где такое задание? ps Поржал с дословного перевода spreadshit
Torin
  • Torin
  • 0
  • Комментарий отредактирован 2017-02-06 22:48:22 пользователем Torin
А фиг его, тип какой-то выкладывал, я просто себе его в блокнот загнал даже не разбираясь) буду за компом, могу скинуть
Himeg
Ога, скинь плз
Torin
ps Поржал с дословного перевода spreadshit

Как ты сейчас увидишь по ссылке, я люто тупанул с переносом названия xD

Еле откопал на форуме
Himeg
Дадада)))
Просто Spreadshit это помимо всего прочего ещё и «раздвинуть булки» на сленге )))))
Java-boy
  • Java-boy
  • 0
  • Комментарий отредактирован 2017-02-07 13:37:46 пользователем Java-boy
Ну как-то так:
Код берем из файла, путь к файлу из командной строки.
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();
    }
}
Roman_kh
А что по поводу поддержки на входе именно String brainFuckCode = "++++++++++[>+++++++>++++++++++>+++>+<<<<-]>++
.>+.+++++++..+++.>++.<<+++++++++++++++.>.+++.
------.--------.>+.>."?
Java-boy
Так-как в задании не указано откуда он берется, предположил что будет в файле, можно подправить и под строку конечно.
Roman_kh
Тестировать сложно твой код, если он с файлом. Много мороки.
Java-boy
  • Java-boy
  • 0
  • Комментарий отредактирован 2017-02-07 14:17:21 пользователем Java-boy
<code>public class Interpretator {

    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;
        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 static void main(String[] args) {
        Interpretator interpretator = new Interpretator();
        if (args.length != 1) {
            System.exit(0);
        } else {
            interpretator.readCodeFromString(args[0]);
        }
        interpretator.logic();
    }
}</code>
Himeg
Хелоуворлд, например! А также, раз варианты уже публикуют, то:
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(charIndex))).invoke(null, null);
        charIndex++;
    }

    private static void interpret(String code)
    {
        activateSyntax();
        try
        {
            while (charIndex < code.length()) interpretNext();
        }
        catch (Exception E)
        {
            System.out.println("Interpretation failed");
        }
    }

    public static void main(String[] args) throws ClassNotFoundException
    {
        c = Class.forName(BrainFuckInterpreter.class.getName());
        code = "++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---.+++++++..+++.>>.<-.<.+++.------.--------.>>+.>++.";
        interpret(code);
        code = "++++++++++[>+++++++>++++++++++>+++>+<<<<-]>++.>+.+++++++..+++.>++.<<+++++++++++++++.>.+++.------.--------.>+.>.";
        interpret(code);
    }
}
Java-boy
  • Java-boy
  • 0
  • Комментарий отредактирован 2017-02-08 11:22:19 пользователем Java-boy
Понял что первая версия не обрабатывает вложенные циклы, поэтому вот:
<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>
alexeyfrei
Почему вдруг задание идитское? А какие надо давать задания при том, что ты не хочешь, чтобы какой-то товарищ сидел у тебя в офисе неделю?
Задание гораздо проще, чем про обработку картинок. Достаточно прочитать про brainfuck операторы (а их всего 8) и соответсвенно написать 8 switch-case. Чуть приходиться попыхтетть над обработкой циклов, но тут помогает очередь.
Только зарегистрированные и авторизованные пользователи могут оставлять комментарии.