Тестовое задание: "Написать Интерпретатор на язык 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)

ЧТОБЫ ПОСМОТРЕТЬ ВСЕ КОММЕНТАРИИ ИЛИ ОСТАВИТЬ КОММЕНТАРИЙ,
ПЕРЕЙДИТЕ В ПОЛНУЮ ВЕРСИЮ

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();
    }
}


  

  Roman_kh
      Уровень 33

      

      
    7 февраля 2017
      
  А что по поводу поддержки на входе именно String brainFuckCode = "++++++++++[>+++++++>++++++++++>+++>+<<<<-]>++

.>+.+++++++..+++.>++.<<+++++++++++++++.>.+++.

------.--------.>+.>."?

  


  Java-boy
      Уровень 27

      

      
    7 февраля 2017
      
  Так-как в задании не указано откуда он берется, предположил что будет в файле, можно подправить и под строку конечно.

  


  Roman_kh
      Уровень 33

      

      
    7 февраля 2017
      
  Тестировать сложно твой код, если он с файлом. Много мороки.

  


  Java-boy
      Уровень 27

      

      
    7 февраля 2017
      
  <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>



  Torin
      Уровень 27

      

      
    6 февраля 2017
      
  Т.е. это должна быть программа, которая на вход получит текст написанный в стиле BrainFuck а на выход выдаст результат Hello World? я читал про этот язык, видел на нем программы, подтверждаю, название соответствует истине. Но от этого не менее интересно. Спасибо за задачу, обязательно решу позже. Жаль похвастаться решением перед всеми не получится, но зато я возьму ее на вооружение :)



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



1) палиндром

2) анализ картинок

3) брэинфак

4) Spreadshit Simulator

  

  Himeg
      Уровень 15

      

      
    6 февраля 2017
      
  Spreadshit Simulator это где такое задание? ps Поржал с дословного перевода spreadshit

  


  Torin
      Уровень 27

      

      
    6 февраля 2017
      
  А фиг его, тип какой-то выкладывал, я просто себе его в блокнот загнал даже не разбираясь) буду за компом, могу скинуть

  


  Himeg
      Уровень 15

      

      
    6 февраля 2017
      
  Ога, скинь плз

  


  Torin
      Уровень 27

      

      
    6 февраля 2017
      
  ps Поржал с дословного перевода spreadshit


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



Еле откопал на форуме

  


  Himeg
      Уровень 15

      

      
    6 февраля 2017
      
  Дадада)))

Просто Spreadshit это помимо всего прочего ещё и «раздвинуть булки» на сленге )))))



  dit
      Уровень 6

      

      
    6 февраля 2017
      
  Я правда не знаю, но тут должно быть два варианта:

1. На данной вакансии Вам предлагают звиздец какие деньги.

2. Над Вами жестко глумятся и Вам это ой как нравится.



Вся эта чухня взята из википедии и вшита в тесты каким-то задротом, либо смотреть на Вашу реакцию или реально стебутся. Отсюда вывод, или деньги или мазохизм.

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

  

  JuriMik
      Уровень 26

      

      
    8 февраля 2017
      
  Про десятую дорогу согласен на 100%.



А вообще видел это тестовое где-то в нете, посмеялся и не более.