fork download

class Knowledge(private val formula: Long) extends AnyVal {
  import Knowledge._
 
  def &&(that: Knowledge) = Knowledge(this.formula & that.formula)
  def ||(that: Knowledge) = Knowledge(this.formula | that.formula)
  def unary_! = Knowledge(~formula)
 
  def implies(that: Knowledge) = ((!this || that) == TAUTOLOGY)
 
  def frontIsClear = implies(FRONT_IS_CLEAR)
  def frontIsBlocked = implies(!FRONT_IS_CLEAR)
 
  def leftIsClear = implies(LEFT_IS_CLEAR)
  def leftIsBlocked = implies(!LEFT_IS_CLEAR)
 
  def backIsClear = implies(BACK_IS_CLEAR)
  def backIsBlocked = implies(!BACK_IS_CLEAR)
 
  def rightIsClear = implies(RIGHT_IS_CLEAR)
  def rightIsBlocked = implies(!RIGHT_IS_CLEAR)
 
  def onBeeper = implies(ON_BEEPER)
  def noBeeper = implies(!ON_BEEPER)
 
  def beeperAhead = implies(BEEPER_AHEAD)
  def nothingAhead = implies(!BEEPER_AHEAD)
 
  // TODO Can this be improved with bit twiddling?
  def moveForward = {
    val temp = this && FRONT_IS_CLEAR
 
    if (temp.beeperAhead) BACK_IS_CLEAR && ON_BEEPER
    else if (temp.nothingAhead) BACK_IS_CLEAR && NO_BEEPER
    else BACK_IS_CLEAR
  }
 
  // see http://p...content-available-to-author-only...a.de/calcperm.php
  private def bit_permute_step(x: Long, mask: Long, shift: Int) = {
    val t = ((x >>> shift) ^ x) & mask
    (x ^ t) ^ (t << shift)
  }
 
  def turnLeft = {
    var x = forgetAhead
    x = bit_permute_step(x, 0x2222222222222222L, 1)
    x = bit_permute_step(x, 0x0c0c0c0c0c0c0c0cL, 2)
    x = bit_permute_step(x, 0x00f000f000f000f0L, 4)
    Knowledge(x)
  }
 
  def turnRight = {
    var x = forgetAhead
    x = bit_permute_step(x, 0x00aa00aa00aa00aaL, 7)
    x = bit_permute_step(x, 0x00cc00cc00cc00ccL, 6)
    x = bit_permute_step(x, 0x00f000f000f000f0L, 4)
    Knowledge(x)
  }
 
  def turnAround = {
    var x = forgetAhead
    x = bit_permute_step(x, 0x0a0a0a0a0a0a0a0aL, 3)
    x = bit_permute_step(x, 0x00cc00cc00cc00ccL, 6)
    Knowledge(x)
  }
 
  def pickBeeper = Knowledge(formula >>> 32)
 
  def dropBeeper = Knowledge(formula << 32)
 
  // see http://p...content-available-to-author-only...a.de/calcperm.php
  private def bit_permute_step_simple(x: Long, mask: Long, shift: Long) = {
    val t = (x >>> shift) & mask
    ((x & mask) << shift) | t
  }
 
  def forgetAhead = formula | bit_permute_step_simple(formula, 0x0000ffff0000ffffL, 16)
 
  override def toString = "%016x".format(formula)
}
 
object Knowledge {
  private def apply(x: Long) = new Knowledge(x)
 
  val /*  */ FRONT_IS_CLEAR = apply(0xaaaaaaaaaaaaaaaaL) // 01...
  val /**/ FRONT_IS_BLOCKED = !FRONT_IS_CLEAR
  val /*   */ LEFT_IS_CLEAR = apply(0xccccccccccccccccL) // 0011...
  val /* */ LEFT_IS_BLOCKED = !LEFT_IS_CLEAR
  val /*   */ BACK_IS_CLEAR = apply(0xf0f0f0f0f0f0f0f0L) // 00001111...
  val /* */ BACK_IS_BLOCKED = !BACK_IS_CLEAR
  val /*  */ RIGHT_IS_CLEAR = apply(0xff00ff00ff00ff00L) // 0000000011111111...
  val /**/ RIGHT_IS_BLOCKED = !RIGHT_IS_CLEAR
  val /*    */ BEEPER_AHEAD = apply(0xffff0000ffff0000L) // 00000000000000001111111111111111...
  val /*   */ NOTHING_AHEAD = !BEEPER_AHEAD
  val /*       */ ON_BEEPER = apply(0xffffffff00000000L) // 0000000000000000000000000000000011111111111111111111111111111111...
  val /*       */ NO_BEEPER = !ON_BEEPER
 
  val /*     */ TAUTOLOGY = apply(0xffffffffffffffffL)
  val /* */ CONTRADICTION = apply(0x0000000000000000L)
}
 
class Detective(semantics: KarelSemantics) {
 
  private val visited = new HashSet[Def]
  private val postcondition = new HashMap[Def, Knowledge]
 
  private var hints = new ArrayBuffer[Diagnostic]
 
  private def warnAbout(msg: String, node: Node) {
    hints += Diagnostic(node.pos, msg, 2)
  }
 
  private def stopWithBug(msg: String, node: Node): Knowledge = {
    hints += new Diagnostic(node.pos, msg, 1)
    CONTRADICTION
  }
 
  val result: Seq[Diagnostic] = {
    semantics.defs.values.foreach(check)
    hints.sortWith(_.pos < _.pos)
  }
 
  private def check(deF: Def): Knowledge = postcondition.getOrElseUpdate(deF, {
    if (visited.add(deF)) {
      check(deF.body, TAUTOLOGY)
    } else {
      // TODO How do we deal with recursive calls?
      TAUTOLOGY
    }
  })
 
  private def check(block: Block, initial: Knowledge): Knowledge = {
    var knowledge = initial
    for (statement <- block.statements) {
      if (knowledge == CONTRADICTION) {
        warnAbout("dead code", statement)
        return CONTRADICTION
      }
      knowledge = check(statement, knowledge)
    }
    knowledge
  }
 
  private def check(statement: Statement, above: Knowledge): Knowledge = statement match {
 
    case x @ Call("moveForward") =>
      if (above implies FRONT_IS_BLOCKED) stopWithBug("cannot move through wall", x)
      else above.moveForward
 
    case Call("turnLeft") =>
      above.turnLeft
    case Call("turnAround") =>
      above.turnAround
    case Call("turnRight") =>
      above.turnRight
 
    case x @ Call("pickBeeper") =>
      if (above implies NO_BEEPER) stopWithBug("there is no beeper to pick", x)
      else above.pickBeeper
 
    case x @ Call("dropBeeper") =>
      if (above implies ON_BEEPER) stopWithBug("cannot drop another beeper", x)
      else above.dropBeeper
 
    // TODO How do we deal with preconditions?
    // Should we simply check each function again for each client?
    // That would probably require a static "stack trace" to be readable.
    // TODO Recursive functions yield TAUTOLOGY as of now;
    // Can we do better for tail-recursive functions?
    case Call(target) => check(semantics.defs(target))
 
    case x @ IfThen(condition, th3n) =>
      val p = learn(condition)
      if (above implies p) {
        warnAbout("condition is always true", x)
        check(th3n, above)
      } else if (above implies !p) {
        warnAbout("condition is always false", x)
        above
      } else {
        check(th3n, above && p) || (above && !p)
      }
 
    case x @ IfThenElse(condition, th3n, e1se) =>
      val p = learn(condition)
      if (above implies p) {
        warnAbout("condition is always true", x)
        check(th3n, above)
      } else if (above implies !p) {
        warnAbout("condition is always false", x)
        check(e1se, above)
      } else {
        check(th3n, above && p) || check(e1se, above && !p)
      }
 
    case x @ While(condition, body) =>
      val p = learn(condition)
      if (above implies !p) {
        warnAbout("loop is never entered", x)
        above
      } else {
        if (check(body, p) implies p) stopWithBug("infinite loop", x)
        else !p // TODO Do we know anything else besides !p below the loop?
      }
 
    case Repeat(times, body) =>
      Stream.iterate(above)(check(body, _)).drop(times).head
  }
 
  private def learn(condition: Condition): Knowledge = condition match {
 
    case False() => CONTRADICTION
    case True() => TAUTOLOGY
 
    case OnBeeper() => ON_BEEPER
    case BeeperAhead() => BEEPER_AHEAD
    case FrontIsClear() => FRONT_IS_CLEAR
    case LeftIsClear() => LEFT_IS_CLEAR
    case RightIsClear() => RIGHT_IS_CLEAR
 
    case Not(_, p) => !learn(p)
    case Conjunction(p, _, q) => learn(p) && learn(q)
    case Disjunction(p, _, q) => learn(p) || learn(q)
    case Parenthesized(p) => learn(p)
  }
}
 

/opt/scala/bin/scalac: line 50: /dev/null: Permission denied
Main.scala:1: error: value class needs to have a publicly accessible val parameter
class Knowledge(private val formula: Long) extends AnyVal {
                            ^
Main.scala:101: error: not found: type KarelSemantics
class Detective(semantics: KarelSemantics) {
                           ^
Main.scala:103: error: not found: type HashSet
  private val visited = new HashSet[Def]
                            ^
Main.scala:104: error: not found: type HashMap
  private val postcondition = new HashMap[Def, Knowledge]
                                  ^
Main.scala:106: error: not found: type ArrayBuffer
  private var hints = new ArrayBuffer[Diagnostic]
                          ^
Main.scala:108: error: not found: type Node
  private def warnAbout(msg: String, node: Node) {
                                           ^
Main.scala:112: error: not found: type Node
  private def stopWithBug(msg: String, node: Node): Knowledge = {
                                             ^
Main.scala:114: error: not found: value CONTRADICTION
    CONTRADICTION
    ^
Main.scala:117: error: not found: type Diagnostic
  val result: Seq[Diagnostic] = {
                  ^
Main.scala:122: error: not found: type Def
  private def check(deF: Def): Knowledge = postcondition.getOrElseUpdate(deF, {
                         ^
Main.scala:131: error: not found: type Block
  private def check(block: Block, initial: Knowledge): Knowledge = {
                           ^
Main.scala:143: error: not found: type Statement
  private def check(statement: Statement, above: Knowledge): Knowledge = statement match {
                               ^
Main.scala:145: error: not found: value Call
    case x @ Call("moveForward") =>
             ^
Main.scala:146: error: not found: value FRONT_IS_BLOCKED
      if (above implies FRONT_IS_BLOCKED) stopWithBug("cannot move through wall", x)
                        ^
Main.scala:149: error: not found: value Call
    case Call("turnLeft") =>
         ^
Main.scala:151: error: not found: value Call
    case Call("turnAround") =>
         ^
Main.scala:153: error: not found: value Call
    case Call("turnRight") =>
         ^
Main.scala:156: error: not found: value Call
    case x @ Call("pickBeeper") =>
             ^
Main.scala:157: error: not found: value NO_BEEPER
      if (above implies NO_BEEPER) stopWithBug("there is no beeper to pick", x)
                        ^
Main.scala:160: error: not found: value Call
    case x @ Call("dropBeeper") =>
             ^
Main.scala:161: error: not found: value ON_BEEPER
      if (above implies ON_BEEPER) stopWithBug("cannot drop another beeper", x)
                        ^
Main.scala:169: error: not found: value Call
    case Call(target) => check(semantics.defs(target))
         ^
Main.scala:171: error: not found: value IfThen
    case x @ IfThen(condition, th3n) =>
             ^
Main.scala:209: error: not found: type Condition
  private def learn(condition: Condition): Knowledge = condition match {
                               ^
Main.scala:172: error: not found: value condition
      val p = learn(condition)
                    ^
Main.scala:175: error: not found: value th3n
        check(th3n, above)
              ^
Main.scala:180: error: not found: value th3n
        check(th3n, above && p) || (above && !p)
              ^
Main.scala:183: error: not found: value IfThenElse
    case x @ IfThenElse(condition, th3n, e1se) =>
             ^
Main.scala:184: error: not found: value condition
      val p = learn(condition)
                    ^
Main.scala:187: error: not found: value th3n
        check(th3n, above)
              ^
Main.scala:190: error: not found: value e1se
        check(e1se, above)
              ^
Main.scala:192: error: not found: value th3n
        check(th3n, above && p) || check(e1se, above && !p)
              ^
Main.scala:195: error: not found: value While
    case x @ While(condition, body) =>
             ^
Main.scala:196: error: not found: value condition
      val p = learn(condition)
                    ^
Main.scala:201: error: not found: value body
        if (check(body, p) implies p) stopWithBug("infinite loop", x)
                  ^
Main.scala:205: error: not found: value Repeat
    case Repeat(times, body) =>
         ^
Main.scala:206: error: not found: value body
      Stream.iterate(above)(check(body, _)).drop(times).head
                                  ^
Main.scala:211: error: not found: value False
    case False() => CONTRADICTION
         ^
Main.scala:211: error: not found: value CONTRADICTION
    case False() => CONTRADICTION
                    ^
Main.scala:212: error: not found: value True
    case True() => TAUTOLOGY
         ^
Main.scala:212: error: not found: value TAUTOLOGY
    case True() => TAUTOLOGY
                   ^
Main.scala:214: error: not found: value OnBeeper
    case OnBeeper() => ON_BEEPER
         ^
Main.scala:214: error: not found: value ON_BEEPER
    case OnBeeper() => ON_BEEPER
                       ^
Main.scala:215: error: not found: value BeeperAhead
    case BeeperAhead() => BEEPER_AHEAD
         ^
Main.scala:215: error: not found: value BEEPER_AHEAD
    case BeeperAhead() => BEEPER_AHEAD
                          ^
Main.scala:216: error: not found: value FrontIsClear
    case FrontIsClear() => FRONT_IS_CLEAR
         ^
Main.scala:216: error: not found: value FRONT_IS_CLEAR
    case FrontIsClear() => FRONT_IS_CLEAR
                           ^
Main.scala:217: error: not found: value LeftIsClear
    case LeftIsClear() => LEFT_IS_CLEAR
         ^
Main.scala:217: error: not found: value LEFT_IS_CLEAR
    case LeftIsClear() => LEFT_IS_CLEAR
                          ^
Main.scala:218: error: not found: value RightIsClear
    case RightIsClear() => RIGHT_IS_CLEAR
         ^
Main.scala:218: error: not found: value RIGHT_IS_CLEAR
    case RightIsClear() => RIGHT_IS_CLEAR
                           ^
Main.scala:220: error: not found: value Not
    case Not(_, p) => !learn(p)
         ^
Main.scala:220: error: not found: value p
    case Not(_, p) => !learn(p)
                             ^
Main.scala:221: error: not found: value Conjunction
    case Conjunction(p, _, q) => learn(p) && learn(q)
         ^
Main.scala:221: error: not found: value p
    case Conjunction(p, _, q) => learn(p) && learn(q)
                                       ^
Main.scala:222: error: not found: value Disjunction
    case Disjunction(p, _, q) => learn(p) || learn(q)
         ^
Main.scala:222: error: not found: value p
    case Disjunction(p, _, q) => learn(p) || learn(q)
                                       ^
Main.scala:223: error: not found: value Parenthesized
    case Parenthesized(p) => learn(p)
         ^
Main.scala:223: error: not found: value p
    case Parenthesized(p) => learn(p)
                                   ^
59 errors found
spoj: The program compiled successfully, but Main.class was not found.
      Class Main should contain method: def main(args: Array[String]).

Standard output is empty