abstract class Cell
case object Bk extends Cell { override def toString = "0" }
case object Oc extends Cell { override def toString = "1" }

abstract class Action
case object WBk extends Action
case object WOc extends Action
case object R extends Action
case object L extends Action
case object Nop extends Action

type State = Int
type Prog = List[(Action, State)]

//some list functions
def tl[A](xs: List[A]) : List[A] = xs match {
  case Nil => Nil
  case x::xs => xs
}

def hd[A](xs: List[A]) : A = xs.head

def nth_of[A](xs: List[A], n: Int) = 
  if (n <= xs.length) Some(xs(n)) else None 

//some map functions
def dget(m: Map[Int, Int], n: Int) = m.getOrElse(n, 0)



//tapes
case class Tape(l: List[Cell], r: List[Cell]) {
  def update(a: Action) = a match {
    case WBk => Tape(l, Bk::tl(r))
    case WOc => Tape(l, Oc::tl(r))
    case L => if (l == Nil) Tape(Nil, Bk::r) else Tape (tl(l), hd(l)::r)
    case R => if (r == Nil) Tape(Bk::l, Nil) else Tape(hd(r)::l, tl(r))
    case Nop => Tape(l, r)
  }

  def read = r match {
    case Nil => Bk
    case x::_ => x
  }

  override def toString = 
    l.reverse.map(_.toString).foldLeft("")(_+_) + 
    ">" + r.map(_.toString).foldLeft("")(_+_)
}

// standard tapes
def std(n: Int) : List[Cell] = n match {
  case 0 => List(Oc)
  case n => Oc::std(n - 1)
}

class STape(ns: Int*) extends Tape(Nil, ns.map(std).reduceLeft(_ ::: List(Bk) ::: _))
  
// configurations
case class Config(s: State, tp: Tape) {
  def is_final = s == 0

  override def toString = tp.toString
}


// Turing Machines
case class TM(p: Prog) {
  
  def fetch(s: State, a: Cell) = (s, a) match {
    case (0, _) => (Nop, 0)
      case (s, Bk) => nth_of(p, 2 * (s - 1)) match {
        case None => (Nop, 0)
        case Some(i) => i
      }
    case (s, Oc) => nth_of(p, 2 * (s - 1) + 1) match {
      case None => (Nop, 0)
      case Some(i) => i
    }
  } 

  def step(cf: Config) : Config = fetch (cf.s, cf.tp.read) match {
    case (a, s_next) => Config(s_next, cf.tp.update(a))
  }

  def steps(cf: Config, n: Int) : Config = n match {
    case 0 => cf
    case n => steps(step(cf), n - 1)
  } 

  def run(cf: Config) : Config = {
    if (cf.is_final) cf else run(step(cf))
  }
 
  def run(tp: Tape) : Tape = run(Config(1, tp)).tp
}



// examples
class TMCopy(n: Int) extends 
  TM(List((WBk, 5), (R, 2), (R, 3), (R, 2), (WOc, 3), 
          (L, 4), (L, 4), (L, 5), (R, 11), (R, 6), 
          (R, 7), (WBk, 6), (R, 7), (R, 8), (WOc, 9), 
          (R, 8), (L, 10), (L, 9), (L, 10), (L, 5), 
          (L, 0), (R, 12), (WOc, 13), (L, 14), (R, 12), 
          (R, 12), (L, 15), (WBk, 14), (R, 0), (L, 15)))

println("TM: " + (new TMCopy(0)).run(new STape(3)))


// Abacus
abstract class AInst 
case class Inc(n: Int) extends AInst
case class Dec(n: Int, l: Int) extends AInst
case class Goto(l: Int) extends AInst

type AProg = List[AInst]
type Regs = Map[Int, Int]



case class AConfig(s: Int, regs: Regs)  

case class Abacus(p: AProg) {
  
  def step(cf: AConfig) : AConfig = (nth_of(p, cf.s), cf.s) match {
    case (None, _) => cf
    case (Some(Inc(n)), s) => AConfig(s + 1, cf.regs + (n -> (dget(cf.regs, n) + 1)))
    case (Some(Dec(n, l)), s) => {
      if (dget(cf.regs, n) == 0) AConfig(l, cf.regs)
      else AConfig(s + 1, cf.regs + (n -> (dget(cf.regs, n) - 1)))
    }
    case (Some(Goto(l)), _) => AConfig(l, cf.regs)
  }  

  def steps(cf: AConfig, n: Int) : AConfig = n match {
    case 0 => cf
    case n => steps(step(cf), n - 1)
  } 

  def steps(regs: Regs, n: Int) : AConfig = steps(AConfig(0, regs), n)

  def run(cf: AConfig) : AConfig = {
    if (cf.s >= p.length || cf.s < 0) cf else run(step(cf))
  }
 
  def run(regs: Regs): Regs = run(AConfig(0, regs)).regs
}

// examples
class Copy(in: Int, out: Int) extends 
  Abacus(List(Dec(in, -1), Inc(out), Goto(0))) 

class Plus(in1: Int, in2: Int, out: Int) extends 
  Abacus(List(Dec(in1, 4), Inc(in2), Inc(out),
              Goto(0), Dec(out, -1), Inc(in1), Goto(4))) 


println("Ab: " + (new Plus(0, 1, 2)).run(Map(0 -> 3, 1 -> 4)))