// Part 1 about an Interpreter for the Brainf*** language

//========================================================

object CW10a {  // only for generating the Jar file

type Mem = Map[Int, Int]

import io.Source

import scala.util._

// (1) Write a function that takes a file name as argument and

// and requests the corresponding file from disk. It returns the

// content of the file as a String. If the file does not exists,

// the function should return the empty string.

def load_bff(name: String) : String = 

  Try(Source.fromFile(name)("ISO-8859-1").mkString).getOrElse("")

// (2) Complete the functions for safely reading  

// and writing brainf*** memory. Safely read should

// Return the value stored in the Map for a given memory

// pointer, provided it exists; otherwise it Returns 0. The

// writing function generates a new Map with the

// same data, except at the given memory pointer the

// value v is stored.

def sread(mem: Mem, mp: Int) : Int = 

  mem.getOrElse(mp, 0)

def write(mem: Mem, mp: Int, v: Int) : Mem =

  mem.updated(mp, v)

// (3) Implement the two jumping instructions in the 

// brainf*** language. In jumpRight, given a program and 

// a program counter move the program counter to the right 

// until after the *matching* ]-command. Similarly, 

// jumpLeft implements the move to the left to just after

// the *matching* [-command.

def jumpRight(prog: String, pc: Int, level: Int) : Int = {

  if (prog.length <= pc) pc 

  else (prog(pc), level) match {

    case (']', 0) => pc + 1

    case (']', l) => jumpRight(prog, pc + 1, l - 1)

    case ('[', l) => jumpRight(prog, pc + 1, l + 1)

    case (_, l) => jumpRight(prog, pc + 1, l)

  }

}

def jumpLeft(prog: String, pc: Int, level: Int) : Int = {

  if (pc < 0) pc 

  else (prog(pc), level) match {

    case ('[', 0) => pc + 1

    case ('[', l) => jumpLeft(prog, pc - 1, l - 1)

    case (']', l) => jumpLeft(prog, pc - 1, l + 1)

    case (_, l) => jumpLeft(prog, pc - 1, l)

  }

}

// test cases

//jumpRight("""--[..+>--],>,++""", 3, 0)         // => 10

//jumpLeft("""--[..+>--],>,++""", 8, 0)          // => 3

//jumpRight("""--[..[+>]--],>,++""", 3, 0)       // => 12

//jumpRight("""--[..[[-]+>[.]]--],>,++""", 3, 0) // => 18

//jumpRight("""--[..[[-]+>[.]]--,>,++""", 3, 0)  // => 22 (outside)

//jumpLeft("""[******]***""", 7, 0)              // => -1 (outside)

// (4) Complete the compute function that interprets (runs) a brainf***

// program: the arguments are a program (represented as a string), a program 

// counter, a memory counter and a brainf*** memory. It Returns the

// memory at the stage when the execution of the brainf*** program

// finishes. The interpretation finishes once the program counter

// pc is pointing to something outside the program string.

// If the pc points to a character inside the program, the pc, 

// memory pointer and memory need to be updated according to 

// rules of the brainf*** language. Then, recursively, the compute 

// function continues with the command at the new program

// counter. 

// Implement the run function that calls compute with the program

// counter and memory counter set to 0.

def compute(prog: String, pc: Int, mp: Int, mem: Mem) : Mem = {

  if (0 <= pc && pc < prog.length) { 

    val (new_pc, new_mp, new_mem) = prog(pc) match {

      case '>' => (pc + 1, mp + 1, mem)

      case '<' => (pc + 1, mp - 1, mem)

      case '+' => (pc + 1, mp, write(mem, mp, sread(mem, mp) + 1))

      case '-' => (pc + 1, mp, write(mem, mp, sread(mem, mp) - 1))

      case '.' => { print(sread(mem, mp).toChar); (pc + 1, mp, mem) }

      case ',' => (pc + 1, mp, write(mem, mp, Console.in.read().toByte))

      case '['  => 

	if (sread(mem, mp) == 0) (jumpRight(prog, pc + 1, 0), mp, mem) else (pc + 1, mp, mem) 

      case ']'  => 

	if (sread(mem, mp) != 0) (jumpLeft(prog, pc - 1, 0), mp, mem) else (pc + 1, mp, mem) 

      case _ => (pc + 1, mp, mem)

    }		     

    compute(prog, new_pc, new_mp, new_mem)	

  }

  else mem

}

def run(prog: String, m: Mem = Map()) = compute(prog, 0, 0, m)

// some sample bf-programs collected from the Internet

//=====================================================

// first some contrived (small) programs

// clears the 0-cell

run("[-]", Map(0 -> 100))    // Map will be 0 -> 0

// copies content of the 0-cell to 1-cell

run("[->+<]", Map(0 -> 10))  // Map will be 0 -> 0, 1 -> 10

// copies content of the 0-cell to 2-cell and 4-cell

run("[>>+>>+<<<<-]", Map(0 -> 42))

// prints out numbers 0 to 9

run("""+++++[->++++++++++<]>--<+++[->>++++++++++<<]>>++<<----------[+>.>.<+<]""")

// some more "useful" programs

// hello world program 1

run("""++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---.+++++++

       ..+++.>>.<-.<.+++.------.--------.>>+.>++.""")

// hello world program 2

run("""++++++++++[>+++++++>++++++++++>+++>+<<<<-]>++.>+.+++++++..+++.>+

       +.<<+++++++++++++++.>.+++.------.--------.>+.>.""")

// hello world program 3

run("""+++++++++[>++++++++>+++++++++++>+++++<<<-]>.>++.+++++++..

       +++.>-.------------.<++++++++.--------.+++.------.--------.>+.""")

// draws the Sierpinski triangle

run("""++++++++[>+>++++<<-]>++>>+<[-[>>+<<-]+>>]>+[-<<<[

      ->[+[-]+>++>>>-<<]<[<]>>++++++[<<+++++>>-]+<<++.[-]<<

      ]>.>+[>>]>+]""")

run(load_bff("sierpinski.bf"))

//fibonacci numbers below 100

run("""+++++++++++

      >+>>>>++++++++++++++++++++++++++++++++++++++++++++

      >++++++++++++++++++++++++++++++++<<<<<<[>[>>>>>>+>

      +<<<<<<<-]>>>>>>>[<<<<<<<+>>>>>>>-]<[>++++++++++[-

      <-[>>+>+<<<-]>>>[<<<+>>>-]+<[>[-]<[-]]>[<<[>>>+<<<

      -]>>[-]]<<]>>>[>>+>+<<<-]>>>[<<<+>>>-]+<[>[-]<[-]]

      >[<<+>>[-]]<<<<<<<]>>>>>[+++++++++++++++++++++++++

      +++++++++++++++++++++++.[-]]++++++++++<[->-<]>++++

      ++++++++++++++++++++++++++++++++++++++++++++.[-]<<

      <<<<<<<<<<[>>>+>+<<<<-]>>>>[<<<<+>>>>-]<-[>>.>.<<<

      [-]]<<[>>+>+<<<-]>>>[<<<+>>>-]<<[<+>-]>[<+>-]<<<-]""")

//outputs the square numbers up to 10000

run("""++++[>+++++<-]>[<+++++>-]+<+[

    >[>+>+<<-]++>>[<<+>>-]>>>[-]++>[-]+

    >>>+[[-]++++++>>>]<<<[[<++++++++<++>>-]+<.<[>----<-]<]

    <<[>>>>>[>>>[-]+++++++++<[>-<-]+++++++++>[-[<->-]+[<<<]]<[>+<-]>]<<-]<<-]""")

//collatz numbers (needs a number to be typed in)

run(""">,[[----------[

      >>>[>>>>]+[[-]+<[->>>>++>>>>+[>>>>]++[->+<<<<<]]<<<]

      ++++++[>------<-]>--[>>[->>>>]+>+[<<<<]>-],<]>]>>>++>+>>[

      <<[>>>>[-]+++++++++<[>-<-]+++++++++>[-[<->-]+[<<<<]]<[>+<-]>]

      >[>[>>>>]+[[-]<[+[->>>>]>+<]>[<+>[<<<<]]+<<<<]>>>[->>>>]+>+[<<<<]]

      >[[>+>>[<<<<+>>>>-]>]<<<<[-]>[-<<<<]]>>>>>>>

      ]>>+[[-]++++++>>>>]<<<<[[<++++++++>-]<.[-]<[-]<[-]<]<,]""")

// infinite collatz (never stops)

run(""">>+>+<[[->>[>>]>>>[>>]+[<<]<<<[<<]>[>[>>]>>+>[>>]<+<[<<]<<<[<

      <]>-]>[>>]>>[<<<<[<<]>+>[>>]>>-]<<<<[<<]+>>]<<[+++++[>+++++++

      +<-]>.<++++++[>--------<-]+<<]>>[>>]+[>>>>[<<+>+>-]<-[>+<-]+<

      [<<->>-[<<+>>[-]]]>>>[<<<+<<+>>>>>-]<<<[>>>+<<<-]<<[[-]>+>>->

      [<+<[<<+>>-]<[>+<-]<[>+<-]>>>>-]<[>+<-]+<[->[>>]<<[->[<+++>-[

      <+++>-[<+++>-[<[-]++>>[-]+>+<<-[<+++>-[<+++>-[<[-]+>>>+<<-[<+

      ++>-[<+++>-]]]]]]]]]<[>+<-]+<<]>>>+<[->[<+>-[<+>-[<+>-[<+>-[<

      +>-[<+>-[<+>-[<+>-[<+>-[<[-]>>[-]+>+<<-[<+>-]]]]]]]]]]]<[>+<-

      ]+>>]<<[<<]>]<[->>[->+>]<[-[<+>-[<->>+<-[<+>-[<->>+<-[<+>-[<-

      >>+<-[<+>-[<->>+<-[<+>-[<->>+<-[<+>-[<->>+<-[<+>-[<->>+<-[<+>

      -[<->>+<-[<+>-[<->>+<-[<+>-]]]]]]]]]]]]]]]]]]]>[<+>-]<+<[<+++

      +++++++>-]<]>>[<+>->>]<<[>+>+<<-]>[<+>-]+>[<->[-]]<[-<<-]<<[<

      <]]++++++[>+++++++<-]>++.------------.[-]>[>>]<<[+++++[>+++++

      +++<-]>.<++++++[>--------<-]+<<]+<]>[<+>-]<]>>>[>>]<<[>[-]<-<

      <]++++++++++.[-]<<<[<<]>>>+<[->[<+>-[<+>-[<+>-[<+>-[<+>-[<+>-

      [<+>-[<+>-[<+>-[<[-]>>[-]+>+<<-]]]]]]]]]]<[>+<-]+>>]<<[<<]>>]""")

// 2 to the power of 6 

//(example from a C-to-BF compiler at https://github.com/elikaski/BF-it)

run(""">>[-]>[-]++>[-]++++++><<<>>>>[-]+><>[-]<<[-]>[>+<<+>-]>[<+>-]

       <><[-]>[-]<<<[>>+>+<<<-]>>>[<<<+>>>-][-]><<>>[-]>[-]<<<[>>[-]

       <[>+>+<<-]>[<+>-]+>[[-]<-<->>]<<<-]>>[<<+>>-]<<[[-]>[-]<<[>+>

       +<<-]>>[<<+>>-][-]>[-]<<<<<[>>>>+>+<<<<<-]>>>>>[<<<<<+>>>>>-]

       <<>>[-]>[-]<<<[>>>+<<<-]>>>[<<[<+>>+<-]>[<+>-]>-]<<<>[-]<<[-]

       >[>+<<+>-]>[<+>-]<><[-]>[-]<<<[>>+>+<<<-]>>>-[<<<+>>>-]<[-]>[-]

       <<<[>>+>+<<<-]>>>[<<<+>>>-][-]><<>>[-]>[-]<<<[>>[-]<[>+>+<<-]>

       [<+>-]+>[[-]<-<->>]<<<-]>>[<<+>>-]<<][-]>[-]<<[>+>+<<-]>>[<<+>

       >-]<<<<<[-]>>>>[<<<<+>>>>-]<<<<><>[-]<<[-]>[>+<<+>-]>[<+>-]<>

       <[-]>[-]>[-]<<<[>>+>+<<<-]>>>[<<<+>>>-]<<>>[-]>[-]>[-]>[-]>[-]>

       [-]>[-]>[-]>[-]>[-]<<<<<<<<<<>>++++++++++<<[->+>-[>+>>]>[+[-<+

       >]>+>>]<<<<<<]>>[-]>>>++++++++++<[->-[>+>>]>[+[-<+>]>+>>]<<<<<

       ]>[-]>>[>++++++[-<++++++++>]<.<<+>+>[-]]<[<[->-<]++++++[->++++

       ++++<]>.[-]]<<++++++[-<++++++++>]<.[-]<<[-<+>]<<><<<""")

// a Mandelbrot set generator in brainf*** written by Erik Bosman

// (http://esoteric.sange.fi/brainfuck/utils/mandelbrot/)

run(load_bff("mandelbrot.bf"))

// a benchmark program (counts down from 'Z' to 'A')

val b1 = """>++[<+++++++++++++>-]<[[>+>+<<-]>[<+>-]++++++++

            [>++++++++<-]>.[-]<<>++++++++++[>++++++++++[>++

            ++++++++[>++++++++++[>++++++++++[>++++++++++[>+

            +++++++++[-]<-]<-]<-]<-]<-]<-]<-]++++++++++."""

def time_needed[T](n: Int, code: => T) = {

  val start = System.nanoTime()

  for (i <- 0 until n) code

  val end = System.nanoTime()

  (end - start)/(n * 1.0e9)

}

time_needed(1, run(b1))

}