CrossTheMaze.scala

object CrossTheMaze extends App {

  class Maze(mazeLines: Vector[String]) {

    case class Vec(x: Int, y: Int) { def +(v: Vec) = Vec(x + v.x, y + v.y) }

    class Direction(val toChar: Char, val v: Vec) {
      lazy val id: Int = directions indexOf this
      lazy val searchingOrder: Stream[Direction] =
        (directions ++ directions).toStream drop (id + 3) % 4 take 4
    }

    val directions = Vector(
      new Direction('N', Vec(-1, 0)),
      new Direction('E', Vec(0, 1)),
      new Direction('S', Vec(1, 0)),
      new Direction('W', Vec(0, -1)))

    private val wall = {
      val middles = for (line <- mazeLines) yield true +: line.map(_ == '#') :+ true
      val b = Vector.fill(middles.head.size)(true)
      b +: middles :+ b
    }
    def isWall: Vec => Boolean = { case Vec(x, y) => wall(x)(y) }

    def step(pos: Vec, face: Direction): Option[(Vec, Direction)] = (for {
      d <- face.searchingOrder
      next = pos + d.v if !isWall(next)
    } yield (next, d)).headOption

    def findPath(sx: Int, sy: Int, ex: Int, ey: Int): Option[String] = {

      val (start, end) = (Vec(sx, sy), Vec(ex, ey))
      val history = collection.mutable.Set.empty[(Vec, Direction)]

      @annotation.tailrec
      def loop(pos: Vec, face: Direction, path: String = "", i: Int = 0): Option[String] =

        if ((i > 10000) || (history contains (pos, face))) None
        else if (pos == end) Some(path)
        else step(pos, face) match {
          case Some((v0, d)) =>
            history += ((pos, face))
            loop(v0, d, path + d.toChar, i + 1)
          case None => None
        }

      val startingFace = directions.find { d =>
        val left = d.searchingOrder.head
        isWall(start + left.v)
      }.get

      loop(start, startingFace)

    }

  }

  def process(lineIn: Iterator[String])(lineOut: String => Unit) =
    for (i <- 1 to lineIn.next().toInt) {
      val n = lineIn.next().toInt
      val maze = new Maze(Vector.fill(n)(lineIn.next()))
      val Array(sx, sy, ex, ey) = lineIn.next() split ' ' map (_.toInt)
      lineOut(s"Case #$i: ${
        (for (path <- maze findPath (sx, sy, ex, ey)) yield s"${path.size}\n$path") getOrElse
          "Edison ran out of energy."
      }")
    }

  val writer = new java.io.PrintWriter("d.large.out")
  try {
    process(io.Source.fromFile("D-large-practice.in").getLines)(writer.println)
  } finally {
    writer.flush(); writer.close()
  }

}

CrossTheMazeTest.scala

import org.scalatest._

import CrossTheMaze._

class CrossTheMazeTest extends FunSuite {

  test("sample case") {
    val input = """3
2
.#
#.
1 1 2 2
5
.##.#
.....
...#.
.###.
...#.
1 1 5 3
3
...
.#.
...
1 1 3 3""".lines

    val expected = """Case #1: Edison ran out of energy.
Case #2: 22
SEEENSESSSNNNWWSWWSSEE
Case #3: 4
EESS""".lines

    process(input) { s => for (line<-s.lines)
      assert(line === expected.next())
    }
  }

  test("full small case") {
    val input = io.Source.fromFile("D-small-practice.in").getLines()
    val expected = io.Source.fromFile("d.small.out.ref").getLines()

    process(input) { s => for (line<-s.lines)
      assert(line === expected.next())
    }
  }

  test("full large case") {
    val input = io.Source.fromFile("D-large-practice.in").getLines()
    val expected = io.Source.fromFile("d.large.out.ref").getLines()

    process(input) { s => for (line<-s.lines)
      assert(line === expected.next())
    }
  }

}