In this post, we will solve BrainF_k interpreter HackerRank Solution. This problem (BrainF_k interpreter) is a part of HackerRank Functional Programming series.
Task
BrainF__k is an esoteric programming languages. It is designed to provide a tongue-twister to programmers, where even adding two numbers can be more difficult than writing a complex algorithm in imperative languages.
For this problem, a BrainF__k program is allocated a continuous memory of infinite bytes, where memory locations are indexed from 0 onwards.
Following are the commands used in this language:
> Increment data pointer so that it points to next location in memory.
< Decrement data pointer so that it points to previous locaion in memory.
+ Increment the byte pointed by data pointer by 1. If it is already at its maximum value, 255, then new value will be 0.
- Decrement the byte pointed by data pointer by 1. If it is at its minimum value, 0, then new value will be 255.
. Output the character represented by the byte at the data pointer.
, Read one byte and store it at the memory location pointed by data pointer.
[ If the byte pointed by data pointer is zero, then move instruction pointer to next matching ']', otherwise move instruction pointer to next command.
] If the byte pointed by data pointer is non-zero, then move instruction pointer to previous matching '[' command, otherwise to next command.Each of the above command represents a single operation.
Objective
Given a valid BrainF__k program and an input string, you have to print the result of the program when executed. All those characters of the program which does not represent a valid command can be considered as comment and should be ignored.
You have to print the output for first 105 operations. If program executes more than 105 operations then you have stop execution and print “PROCESS TIME OUT. KILLED!!!” (without quotes) in the next line.
NOTE:
- Initally all memory locations contain 0. A location can store integer in range [0 .. 255].
- At the start of program, data pointer is at memory location 0. It is guaranteed that data pointer will never point to a negative memory index during the execution of program.
- Number of read operations will not exceed input string length.
- Program will not have a mis-matched bracket (
[or]).
Input
First line will contain two space separated integers, n m, which represent number of characters in input to BrainF__k program and number of lines in the program, respectively. Next line contains n+1 characters which represents the input for the BrainF__k program. This line ends with character ‘$‘ which represent the end of input. Please ignore this in input. Then follows m lines which is the BrainF__k program.
Output
You have to print the output of program as mentioned in Objective. For programs with more than 100000 operations, print the output till then followed by “PROCESS TIME OUT. KILLED!!!” in the next line.
Constraints
- 0 <= n <= 150
- 1 <= m <= 150
- Length of Brain__k program will not exceed 5000.
Sample Input #00
0 20
$
+++++ +++++ initialize counter (cell #0) to 10
[ use loop to set the next four cells to 70/100/30/10
> +++++ ++ add 7 to cell #1
> +++++ +++++ add 10 to cell #2
> +++ add 3 to cell #3
> + add 1 to cell #4
<<<< - decrement counter (cell #0)
]
> ++ . print 'H'
> + . print 'e'
+++++ ++ . print 'l'
. print 'l'
+++ . print 'o'
> ++ . print ' '
<< +++++ +++++ +++++ . print 'W'
> . print 'o'
+++ . print 'r'
----- - . print 'l'
----- --- . print 'd'
> + . print '!'Sample Output #00
Hello World!Explanation #00
Here n = 0 means that there’s no input to the BrainF__k program. That’s why second line only contains $ which represents the end of input. Then follows m = 20 lines which represents the complete BrainF__k program.
Sample Input #01
6 6
abcxyz$
,+. This program will 6 characters
,+. For first 3 characters it will
,+. print its successor
,-. For last 3 characters it will
,-. print its predecessor
,-.Sample Output #01
bcdwxyExplanation #01
This program six characters, for first three it prints its successor and for rest its predecessor.
Sample Input #02
2 10
pm$
++
[ loop will execute only 2 time
>
, reads a value
+++ increase by 3
. print it
<
-
]
+[]Sample Output #02
sp
PROCESS TIME OUT. KILLED!!!Explanation #02
Total number of operations executed here is 22 till second last line in program. Then it enters in a infinte loop in next line.
Solution – BrainF_k interpreter – HackerRank Solution
Scala
trait Command {
def call(machine: Machine): Machine
def check(machine: Machine, f: Machine => Machine): Machine = {
val m = machine.copy(count = machine.count + 1)
if (machine.count < Program.maxCommandCount)
f(m)
else m
}
}
object Command {
val brainChars = "><+-.,[]"
def parse(text: List[Char]): (List[Command], List[Char]) = text match {
case Nil => (Nil, Nil)
case c :: cs =>
val (command, rest) = c match {
case '>' => (Greater(), cs)
case '<' => (Less(), cs)
case '+' => (Plus(), cs)
case '-' => (Minus(), cs)
case '.' => (Point(), cs)
case ',' => (Comma(), cs)
case '[' =>
val (commands, rest) = parse(cs)
(Open(commands), rest)
case ']' => (Close(), cs)
}
command match {
case _: Close => (command :: Nil, rest)
case _ =>
val (list, restOfRest) = parse(rest)
(command :: list, restOfRest)
}
}
}
case class Greater() extends Command {
override def call(machine: Machine): Machine = check(machine, m => m.copy(cursor = m.cursor + 1))
}
case class Less() extends Command {
override def call(machine: Machine): Machine = check(machine, m => m.copy(cursor = m.cursor - 1))
}
case class Plus() extends Command {
override def call(machine: Machine): Machine = check(machine,
m => {
m.memory.update(m.cursor, (m.memory(m.cursor) + 1).toByte)
m
}
)
}
case class Minus() extends Command {
override def call(machine: Machine): Machine = check(machine,
m => {
m.memory.update(m.cursor, (m.memory(m.cursor) - 1).toByte)
m
}
)
}
case class Point() extends Command {
override def call(machine: Machine): Machine = check(machine,
m => {
print(m.memory(m.cursor).toChar)
m
}
)
}
case class Comma() extends Command {
override def call(machine: Machine): Machine = check(machine,
m => {
m.memory(m.cursor) = m.input.head
m.copy(input = m.input.tail)
}
)
}
case class Close() extends Command {
override def call(machine: Machine): Machine = check(machine,
m => m.copy(count = m.count + (if (m.memory(m.cursor) == 0) -2 else 0))
)
}
trait CommandSequence extends Command {
def commands: List[Command] = Nil
}
case class Open(override val commands: List[Command]) extends CommandSequence {
@scala.annotation.tailrec
final override def call(machine: Machine): Machine = {
val m = machine.copy(count = machine.count + 1)
if (machine.count < Program.maxCommandCount) {
if (m.memory(m.cursor) == 0) m.copy(count = m.count + 1)
else call(commands.foldLeft(m)((innerMachine, command) => command.call(innerMachine)))
}
else m
}
}
class Program(text: List[Char]) extends CommandSequence {
override val commands: List[Command] = Command.parse(text)._1
override def call(machine: Machine): Machine = commands.foldLeft(machine)((m, command) => command.call(m))
}
object Program {
val maxCommandCount = 100000
}
case class Machine(
cursor: Int,
input: Seq[Byte],
memory: Array[Byte],
count: Int
)
object Solution {
def main(args: Array[String]): Unit = {
val sc = new java.util.Scanner(System.in)
val (_, m) = (sc.nextInt, sc.nextInt)
sc.nextLine()
val input = sc.nextLine.map(c => c.toByte)
val text = (0 until m).flatMap(_ => sc.nextLine.filter(c => Command.brainChars.contains(c))).toList
val program = new Program(text)
val machine = program.call(Machine(0, input, new Array[Byte](Program.maxCommandCount), 0))
if (machine.count > Program.maxCommandCount) {
println
println("PROCESS TIME OUT. KILLED!!!")
}
}
}
Note: This problem (BrainF_k interpreter) is generated by HackerRank but the solution is provided by CodingBroz. This tutorial is only for Educational and Learning purpose.