My smallest code interpreter in Java

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:

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(); } }
Code language: Java (java)

Option 2:

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; } }
Code language: Java (java)

Option 3:

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(); } }
Code language: Java (java)

Test cases to validate our solution

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")); } }
Code language: Java (java)
Tags:
Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments