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