gistfile1.txt

final case class Roadmap(rows: Int,cols: Int) {
  type Onto=Array[Int] // adjacency list
  type Roads=Array[Onto] // vertices (unidirectional road segments)
  val RC=rows*cols
  val ndir=4
  val goal=RC*ndir
  val DRC=RC*ndir
  val roads=new Roads(DRC) // one dimensional array allows for simpler adjacencies at the cost of uglier addressing
  /* separate road segment for each direction right left down up (0 1 2 3)
   so that (row,col) is the location of the upper/left corner of that segment (be consistent!)
   */
  def index(rldu: Int,row: Int, col: Int) = RC*rldu+row*cols+col
  def coord(i: Int) = { val rldu=i/RC;val r=i%RC;(rldu,r/cols,r%cols) }
  val R=0
  val L=1
  val D=2
  val U=3
  val NONE=4
  def c2dir(a: Char) = a match {
    case 'R' => R
    case 'L' => L
    case 'D' => D
    case 'U' => U
    case _ => NONE
  }
  def dir2c(d: Int) = "RLDUN"(d)
  def coordname(t: (Int,Int,Int))=t match {case (rldu,row,col) => "%c%d%d".format(dir2c(rldu),row,col)}
  def i2s(i: Int)=coordname(coord(i))
  /* set the transitions that meet in the intersection on row r, col c.
     exits(dir) if there's an arrowhead; undir is a list of pairs of linked dirs */
  def setCorner(r: Int, c: Int, exits: Array[Boolean], undirs: Array[(Int,Int)], goaldir: Int) {
    // remember, r,c gives the upper/left part of road
    val froms=Array(index(L,r,c),index(R,r,c-1),index(U,r,c),index(D,r-1,c))
    // to approach from the right, you head left.  froms and tos are identical except opposite directions
    val tos=  Array(index(R,r,c),index(L,r,c-1),index(D,r,c),index(U,r-1,c))
    val ways= Array.fill(ndir)(new collection.mutable.ArrayBuffer[Int](ndir))
    def checkdir(from: Int,to: Int) {
      if (goaldir==to) ways(from)+=goal
      else if (exits(to)) ways(from)+=tos(to)
    }
    for ((from,to)<-undirs) {
      checkdir(from,to)
      checkdir(to,from)
    }
    for ((f,w)<-froms zip ways) {
      if (w.size>0) roads(f)=w.toArray
      // since we didn't pad the border, we've considered indices that are off the array.
      // user input must not ask us to move from somewhere off the array
      // a padded border would prevent this, and allow a single start and goal state
    }
  }
  def s2dirs(s: String) = (c2dir(s(0)),c2dir(s(1)))
  def readCorner(r: Int, c: Int, desc: String) {
    val a=desc.trim split ":"
    val exits=new Array[Boolean](ndir)
    var lastdir=NONE
    var goaldir=lastdir
    for (c<-a(0).trim) {
      if (c=='!') goaldir=lastdir
      else {
        val d=c2dir(c)
        if (d!=NONE) {
          exits(d)=true
          lastdir=d
        }
      }
    }
    setCorner(r,c,exits,a(1).trim split " " map s2dirs toArray,goaldir)
  }
  def read(s: String) = {
    var r=0
    for ((line,row)<-s split "\n" filter (_.indexOf(',')>=0) zipWithIndex) {
      for ((s,col)<-line split "," zipWithIndex) {
        readCorner(row,col,s)
      }
    }
  }
  def path2goal(starts: Int*) = {
    type Path=List[Int]
    val q=new collection.mutable.Queue[Path]
    val seen=new Array[Boolean](DRC)
    starts foreach (seen(_)=true)
    val s=starts map (x=>List(x))
    q.enqueue(s: _*)
    var p=q.head
    while (p.head != goal) {
      val h=p.head
      seen(h)=true
      val n=roads(h) map (_::p)
      q enqueue (n: _*)
      p=q dequeue
    }
    p
  }
  def prettypath(p: List[Int]) = p reverseMap i2s
}

object car {
/* from http://dcsobral.blogspot.com/2009/09/puzzle.html */
  val graphString = """|
                       |DR: DR, RLD: RD LD, L: DL LR, LR: DR LR, DL: DL
                       |UR: LU RU DU LR, LRD: LR UD LU RU LD RD, UDLR: UD LR UR LD, UDLR: UD LR RD, UL: UD UL
                       |UDR: UD RU RD, UDLR: LR LD DR RU, UD: UD UL DL, UDR: UD UR, UD: UD LD
                       |UDR: UD RU RD, UDLR: UR UL LR RD, UR: UD LR LU RU DR, ULR: LR UR UL DR DL, UDLR!: UD UL DR
                       |UR: UR, ULR: UL UR LR, ULR: UL UR RL, ULR: UL UR RL, UL: UL
                       |""".stripMargin
  def main(args: Array[String]) {
    val r=Roadmap(5,5)
    r.read(graphString)
    println(r.prettypath(r.path2goal(r.index(r.R,1,0),r.index(r.U,0,0))))
  }
}