## Primitive Scala

A lower level (Scala) solution to this puzzle: There’s a path from the car to the exit on the right following the lines at corners, and emerging only at arrowheads. This is just a directed graph.  The two directions on a street segment are independent nodes.  I stole from Daniel Sobral the text representation of the graph, and implemented breadth first (shortest path) search just like he did.  The difference is that I explicitly represent the directed graph, and I do so in typical programming contest style.  He has a nice ASCII art printout; I just used simple debug prints to verify that I built the graph right.

It bothers me that in JVM languages, wrapping a primitive in a type requires boxing (no matter how awesome just-in-time compilation is, there’s still memory overhead).  So I end up using a lot of bare primitives and arrays of primitives, probably to my detriment.  Clearly it’s not relevant for this problem (which even a human can solve), but it might eventually compel me to use C++ again (where things are miserable, but at least there’s no abstraction penalty).  I believe .NET allows C-like structures of unboxed primitives, but I’m not satisfied that F# is as pleasant or efficient as Scala (even using my primitive-happy style).

Obviously, most of the code is about translating the text graph description to the directed adjacency list.  It’s about half the lines of his version, but I won’t claim it’s easier to understand.

final case class Roadmap(rows: Int,cols: Int) {
val RC=rows*cols
val ndir=4
val goal=RC*ndir
val DRC=RC*ndir
/* 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)       checkdir(from,to)
checkdir(to,from)
}
// 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       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)
}
var r=0
for ((line,row)=0) zipWithIndex) {
}
}
}
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: _*)
val
seen(h)=true
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]) { 