sealed abstract class Cell {

  def * (n: Int) : List[Cell] = n match {

    case 0 => Nil

    case n => this :: this * (n - 1)

  }

}

case object Bk extends Cell { override def toString = "0" }

case object Oc extends Cell { override def toString = "1" }

sealed 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 Inst = (Action, State)

type Prog = List[Inst]

//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 = join(l.reverse) + ">" + join(r)

}

// 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 ++ (that: TM) = TM(this.p ::: that.p)

  def shift(n: Int) =

    TM(p.map{case (a, s) => (a, if (s == 0) 0 else s + n)})

  def adjust(n: Int) : TM =

    TM(p.map{case (a, s) => (a, if (s == 0) n else s)})

  def adjust : TM = adjust(p.length / 2 + 1)

  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)

  } 

  @tailrec

  final def run(cf: Config) : Config = {

    if (cf.is_final) cf else run(step(cf))

  }

  def run(tp: Tape) : Tape = run(Config(1, tp)).tp

}

}