The challenge

Inspired from real-world Brainf**k, we want to create an interpreter of that language which will support the following instructions:

  • > increment the data pointer (to point to the next cell to the right).
  • < decrement the data pointer (to point to the next cell to the left).
  • + increment (increase by one, truncate overflow: 255 + 1 = 0) the byte at the data pointer.
  • - decrement (decrease by one, treat as unsigned byte: 0 – 1 = 255 ) the byte at the data pointer.
  • . output the byte at the data pointer.
  • , accept one byte of input, storing its value in the byte at the data pointer.
  • [ if the byte at the data pointer is zero, then instead of moving the instruction pointer forward to the next command, jump it forward to the command after the matching ] command.
  • ] if the byte at the data pointer is nonzero, then instead of moving the instruction pointer forward to the next command, jump it back to the command after the matching [ command.

The function will take in input…

  • the program code, a string with the sequence of machine instructions,
  • the program input, a string, eventually empty, that will be interpreted as an array of bytes using each character’s ASCII code and will be consumed by the , instruction

… and will return …

  • the output of the interpreted code (always as a string), produced by the . instruction.

Implementation-specific details for this challenge:

  • Your memory tape should be large enough – the original implementation had 30,000 cells but a few thousand should suffice for this challenge
  • Each cell should hold an unsigned byte with wrapping behavior (i.e. 255 + 1 = 0, 0 – 1 = 255), initialized to 0
  • The memory pointer should initially point to a cell in the tape with a sufficient number (e.g. a few thousand or more) of cells to its right. For convenience, you may want to have it point to the leftmost cell initially
  • You may assume that the command will never be invoked when the input stream is exhausted
  • Error-handling, e.g. unmatched square brackets and/or memory pointer going past the leftmost cell is not required in this challenge. 

The solution in Java code

Option 1:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

import java.util.*;

public class BrainLuck {

    private int selector, lenCode, iCode;
    private StringBuilder lstInput, out;
    private List<Integer> stack;
    private Map<Integer,Integer> bracketD;
    private String code;

    public BrainLuck(String code) {      
    
        selector = 0;
        lenCode = code.length();
        iCode = 0;
        this.code = code;
        out = new StringBuilder();
        stack = new ArrayList<Integer>();
        stack.add(0);
        bracketD = new HashMap<Integer,Integer>();
        
        List<Integer> stackD = new ArrayList<Integer>();
        for (int i=0 ; i<lenCode ; i++) {
            if (code.charAt(i) == '[') stackD.add(i);
            if (code.charAt(i) == ']') {
                int h = stackD.remove( stackD.size()-1 );
                bracketD.put(h, i);
                bracketD.put(i, h);
            }
        }
    }

    public String process(String input) {
        
        lstInput = new StringBuilder(input);
        
        while (iCode < lenCode) {
            if ( (code.charAt(iCode) == '>') && (selector++ == stack.size()-1) ) stack.add(0);
            if ( (code.charAt(iCode) == '<') && (selector-- == 0) ) stack.add(0, 0);
            if (code.charAt(iCode) == '+') stack.set(selector, (stack.get(selector)+1) % 256);
            if (code.charAt(iCode) == '-') stack.set(selector, (stack.get(selector)-1) % 256);
            if (code.charAt(iCode) == '.') out.append( (char) stack.get(selector).intValue() );
            if (code.charAt(iCode) == ',') {
                stack.set(selector, (int) lstInput.charAt(0));
                lstInput.deleteCharAt(0);
            }
            if (code.charAt(iCode) == '[' && stack.get(selector) == 0) iCode = bracketD.get(iCode);
            if (code.charAt(iCode) == ']' && stack.get(selector) != 0) iCode = bracketD.get(iCode);
            iCode++;
        }
        return out.toString();
    }
}

Option 2:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

import java.util.*;

public class BrainLuck {
    String code;
    public BrainLuck(String code) {      
      this.code=code;
    }

    public String process(String input) {
    System.out.println(code);
      Stack<Integer> brack = new Stack<Integer>();
      List<Byte> bytes = new ArrayList<Byte>();
      int pointer=0;
      String out="";
      bytes.add((byte)0);
      for(int i=0; i<code.length();i++) {
        char c = code.charAt(i);
        if(c=='>'){
          pointer++;
          if(pointer==bytes.size()) bytes.add((byte)0);
        }else if(c=='<'){
          pointer--;
          if(pointer==-1) {
            bytes.add(0,(byte)0);
            pointer=0;
          }
        }else if(c=='+'){
          bytes.set(pointer,(byte)(bytes.get(pointer)+1));
        }else if(c=='-'){
          bytes.set(pointer,(byte)(bytes.get(pointer)-1));
        }else if(c=='.'){
          out+=(char)(int)bytes.get(pointer);
        }else if(c==','){
          if(!input.isEmpty()){
            bytes.set(pointer,(byte)(int)input.charAt(0));
            input=input.substring(1);
          }
        }else if(c=='['){
          if(bytes.get(pointer)==0) {
            int left=1,k=i;
            while(left!=0){
              k++;
              if(code.charAt(k)=='[') left++;
              else if(code.charAt(k)==']') left--;
            }
            i=k;
          }
          else brack.push(i);
        }else if(c==']'){
          if(bytes.get(pointer)!=0) i=brack.peek();
          else brack.pop();
        }
      }
      return out;
    }
}

Option 3:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64

import java.util.LinkedList;
import java.util.stream.Collectors;

public class BrainLuck {
  
    private final String code;
    private LinkedList<Byte> input;
    private final LinkedList<Byte> memory;
    private final StringBuilder output;

    public BrainLuck(String code) {
      this.code = code;
      memory = new LinkedList<>();
      memory.add((byte)0);
      output = new StringBuilder("");
    }

    public String process(String inputStr) {
      input = inputStr.chars().mapToObj(n -> (byte) n).collect(Collectors.toCollection(LinkedList::new));
      LinkedList<Integer> parents = new LinkedList<>();
      int pointer = 0;
      for (int i = 0; i < code.length(); i++) {
        switch (code.charAt(i)) {
          case '>':
            if (memory.size() - 1 < ++pointer) memory.add((byte)0);
            break;
          case '<':
            pointer--;
            break;
          case '+':
            memory.set(pointer, (byte) (memory.get(pointer) + 1));
            break;
          case '-':
            memory.set(pointer, (byte) (memory.get(pointer) - 1));
            break;
          case '.':
            output.append((char) memory.get(pointer).byteValue());
            break;
          case ',':
            memory.set(pointer, input.pop());
            break;
          case '[':
            if (memory.get(pointer) != 0) {
              parents.push(i);
            } else {
              int size = parents.size();
              while (code.charAt(++i) != ']' || parents.size() != size) {
                if (code.charAt(i) == '[') parents.push(i);
                if (code.charAt(i) == ']') parents.pop();
              }
            }
            break;
          case ']':
            if (memory.get(pointer) != 0) {
              i = parents.peekFirst();
            } else {
              parents.pop();
            }
            break;
        }
      }
      return output.toString();
    }
}

Test cases to validate our solution

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

import org.junit.Test;

import java.util.Random;
import java.util.UUID;

import static org.hamcrest.CoreMatchers.is;
import static org.junit.Assert.assertThat;

public class BrainLuckTest {
    private final Random random = new Random(System.currentTimeMillis());

    @Test
    public void testEchoUntilByte255Encountered() {
        assertThat(new BrainLuck(",+[-.,+]").process("Codewars" + ((char) 255)), is("Codewars"));
    }

    @Test
    public void testEchoUntilByte0Encountered() {
        assertThat(new BrainLuck(",[.[-],]").process("Codewars" + ((char) 0)), is("Codewars"));
    }

    @Test
    public void testTwoNumbersMultiplier() {
        final char[] input = {8, 9};
        assertThat(new BrainLuck(",>,<[>[->+>+<<]>>[-<<+>>]<<<-]>>.").process(String.valueOf(input[0]) + String.valueOf(input[1])), is(String.valueOf((char) (input[0] * input[1]))));
    }

    @Test
    public void testHelloWorld() {
        assertThat(new BrainLuck("++++++++++[>+++++++>++++++++++>+++>+<<<<-]>++.>+.+++++++..+++.>++.<<+++++++++++++++.>.+++.------.--------.>+.").process(""), is("Hello World!"));
    }

    @Test
    public void testEchoUntilByte255EncounteredWithRandomSequence() {
        String randomSequence = UUID.randomUUID().toString();
        assertThat(new BrainLuck(",+[-.,+]").process(randomSequence + ((char) 255)), is(randomSequence));
    }

    @Test
    public void testEchoUntilByte0EncounteredWithRandomSequence() {
        String randomSequence = UUID.randomUUID().toString();
        assertThat(new BrainLuck(",[.[-],]").process(randomSequence + ((char) 0)), is(randomSequence));
    }

    @Test
    public void testTwoNumbersMultiplierWithRandomNumbers() {
        final char[] input = {(char) (random.nextInt(10) + 1), (char) (random.nextInt(10) + 1)};
        assertThat(new BrainLuck(",>,<[>[->+>+<<]>>[-<<+>>]<<<-]>>.").process(String.valueOf(input[0]) + String.valueOf(input[1])), is(String.valueOf((char) (input[0] * input[1]))));
    }

    @Test
    public void testFibonacci() {
        assertThat(new BrainLuck(",>+>>>>++++++++++++++++++++++++++++++++++++++++++++>++++++++++++++++++++++++++++++++<<<<<<[>[>>>>>>+>+<<<<<<<-]>>>>>>>[<<<<<<<+>>>>>>>-]<[>++++++++++[-<-[>>+>+<<<-]>>>[<<<+>>>-]+<[>[-]<[-]]>[<<[>>>+<<<-]>>[-]]<<]>>>[>>+>+<<<-]>>>[<<<+>>>-]+<[>[-]<[-]]>[<<+>>[-]]<<<<<<<]>>>>>[++++++++++++++++++++++++++++++++++++++++++++++++.[-]]++++++++++<[->-<]>++++++++++++++++++++++++++++++++++++++++++++++++.[-]<<<<<<<<<<<<[>>>+>+<<<<-]>>>>[<<<<+>>>>-]<-[>>.>.<<<[-]]<<[>>+>+<<<-]>>>[<<<+>>>-]<<[<+>-]>[<+>-]<<<-]").process(String.valueOf((char) 10)), is("1, 1, 2, 3, 5, 8, 13, 21, 34, 55"));
    }
}