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 


//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, tp: Tape) {
  
  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 steps(n: Int) : Config = steps(Config(1, tp), n)

  def run(cf: Config) : Config = {
    if (cf.is_final) cf else run(step(cf))
  }
 
  def run : 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)), new STape(n))

println((new TMCopy(0)).run)