Scala's Delimited Continuations -- A Use Case

When I first talked about the upcoming Scala 2.8 Delimited Continuations, I did not go into what uses I foresaw for them, mostly because I was pretty sure people would find uses I could never have imagined for it.

Well, people did find uses I could never have imagined, it turns out! If Scala and Distributed Computing are your things -- hell, if even one of them is your thing! -- do go check Swarm out.

Is rewritting really bad?

Paul Chiusano tell us his Scala success story, and while I find it interesting, there's something that attracts my attention in it. He says:

Finally, I'd like to scrutinize the folk wisdom that rewrites are generally a bad idea.

That got me thinking a bit. That wisdom predates some developments which only became widespread practices recently. In particular, BDD and Continuous Integration.

It occurs to me that if I decide to rewrite something from scratch, I'll have a large set of tests in the form of BDD (which tests for Behavior, so a lot of it should still apply), plus the tests for all bugs that were caught and fixed, for which you them add tests to help with CI.

Furthermore, because you are doing BDD and CI, and possibly TDD for low level stuff, you won't get far with the same errors in case you re-introduce them.

That's something to think about... maybe the old wisdom requires some revisiting.

At any rate, I'd like to point out that this particular piece of wisdom might have become widespread because of this article by Joel Spolsky. I'll quote one part of it, though:

These problems can be solved, one at a time, by carefully moving code, refactoring, changing interfaces. They can be done by one programmer working carefully and checking in his changes all at once, so that nobody else is disrupted. Even fairly major architectural changes can be done without throwing away the code.

Well, that's precisely what Paul Chiusano did! So, on the other hand, perhaps is too soon to dispose of that wisdom...

Type Safe Builder Pattern

I was reading these days an interesting article by Jim McBeath about type safe builder patterns. The interesting part was the use of Church encoding to be able to control the ordinality of certain types, but as I went to the original article by Rafael de F. Ferreira, I found the silliest criticism, which I quote below:

My but it's sad that Java/Scala has to resort to a design pattern for this (if I'm understanding the post correctly).

In Python, we have keyword arguments and default argument values, which allows for very rich parameter declarations.

Well, first of all, a builder pattern is targetted at complex objects. Imagine, for instance, a maze with multiple rooms and passages, where the creation process might entail adding hundred of such components. Not exactly the sort of thing you want to pass as a single parameter list, I'd imagine. In fact, it might not even be possible to do it, because you might not have all information needed in the same place and/or time.

But, most importantly, "keyword arguments" do not enforce type safety. So even if it were an alternative to any problem requiring the Builder pattern, it would fail at the basic premise of the article, which is providing type safety.

So, I decided to show something you can't do with keyword arguments, which, by the way, are called "named parameters" in Scala 2.8, which is mutual exclusion. I'm adapting this example from here, which was written in reply to a follow up by Jim on his original article.

For this example, I assume a "Car" builder, where one has to make a choice about number of doors and brand, and may also choose to get a convertible, but the convertible is incompatible with cars with five doors. This code is nowhere as clear as Jim's, but gets the job done faster, so I could get on with my life. :-)

So, I hope you like it. And if you can clean it up, or come up with more likely scenarios, please share it.

// This code is based on an idea of Rafael de F. Ferreira and was implemented as a response to
// Jim McBeath's blog post http://jim-mcbeath.blogspot.com/2009/09/type-safe-builder-in-scala-part-2.html
// Everyone is free to use, modify, republish, sell or give away this work without prior consent from anybody.

object Scotch {
sealed abstract class Preparation
case object Neat extends Preparation
case object OnTheRocks extends Preparation
case object WithWater extends Preparation

case class OrderOfScotch private[Scotch](val brand:String, val mode:Preparation, val isDouble:Boolean)

trait Option[+X]
case class Some[+X](x:X) extends Option[X]{
  def get:X = x
}
trait None extends Option[Nothing] // this differs in the original implementation
case object None extends None

case class Builder[HAS_BRAND<:Option[String],HAS_MODE<:Option[Preparation],HAS_DOUBLE<:Option[Boolean]] private[Scotch]
             (brand:HAS_BRAND
             ,mode:HAS_MODE
             ,isDouble:HAS_DOUBLE
             ) {
  def ~[X](f:Builder[HAS_BRAND,HAS_MODE,HAS_DOUBLE] => X):X = f(this)
}
           
def withBrand[M<:Option[Preparation],D<:Option[Boolean]](brand:String)(b:Builder[None,M,D]):Builder[Some[String],M,D] =
  Builder(Some(brand),b.mode,b.isDouble)
def withMode[B<:Option[String],D<:Option[Boolean]](mode:Preparation)(b:Builder[B,None,D]):Builder[B,Some[Preparation],D] =
  Builder(b.brand,Some(mode),b.isDouble)
def isDouble[B<:Option[String],M<:Option[Preparation]](isDouble:Boolean)(b:Builder[B,M,None]):Builder[B,M,Some[Boolean]] =
  Builder(b.brand,b.mode,Some(isDouble))

def build(b:Builder[Some[String],Some[Preparation],Some[Boolean]]):OrderOfScotch =
  OrderOfScotch(b.brand.get,b.mode.get,b.isDouble.get)

def builder:Builder[None,None,None] = Builder(None,None,None)

def test {
  val x:OrderOfScotch = builder ~ isDouble(true) ~ withMode(Neat) ~ withBrand("Blubber") ~ build
  // builder ~ isDouble(true) ~ withMode(Neat) ~ build // fails
  // builder ~ isDouble(true) ~ withMode(Neat) ~ withBrand("Blubber") ~ withBrand("Blubber") ~ build // fails
  x
}
}

A Number Puzzle

My friend came up with a new puzzle. Given a 3x3 matrix, fill it with the numbers 1 through 9, without repetition, in such a way that adding the three digits from any line, column or diagonal will yield exactly the same result.

This time I went for conciseness. Instead of laying out a 3x3 array -- or what have you -- I'll take a list of 9 elements, and assume the elements are laid out left to right, then top to down, so that the third element of the second line is the sixth element of the list, for example. Now, before I try to solve it, I have to devise a way to test the conditions. First, let's create a list of list of indices for each line, column of diagonal possible. This can be done programmatically, of course, like this:

 
val cols = List.range(0,3)
val lines = cols map (_ * 3)
val allLines = lines map (l => cols map (l + _))
val allCols = cols map (c => lines map (c + _))
val diagLR = lines zip cols map Function.tupled(_+_)
val diagRL = lines zip cols.reverse map Function.tupled(_+_)
val indices = diagLR :: diagRL :: allLines ::: allCols

I decided just to enter it by hand, though:

 
val indices = List(List(0,1,2), List(3,4,5), List(6,7,8), List(0,3,6), List(1,4,7), List(2,5,8), List(0,4,8), List(2,4,6))

Now, I want to test this. Suppose I have a list of numbers representing the solution. I can replace the indices by the corresponding number like this:

 
indices map (_ map (solution(_)))

from which is quite easy to compute how much each line, column and diagonal adds to:

 
indices map (_ map (solution(_)) sum)

One way, then, to check if all numbers are equal is to simply compare them:

 
indices map (_ map (solution(_)) sum) match { case head :: tail => tail forall (_ == head) }

Not concise enough for me, though. I prefer this:

 
(indices map (_ map (solution(_)) sum) removeDuplicates).size == 1

Our test function, then, is:

 
def test(solution: List[Int]) = (indices map (_ map (solution(_)) sum) removeDuplicates).size == 1

Now, how to compute the solutions? We can do it recursively with lists, recursions, filters, etc. Too much work. Let's just enumerate the possible solutions. The first element can be represented by the index over a nine-elements list of a "seed" solution. The second element can be represented by an index over the eight-element list of remaining elements, and so on. We can disambiguate the first index from the second by multiplying the second by 9, and add both. We can repeat this over and over for every other element in the list. So, to go from a number representing the solution, plus a seed list, to the solution, we can write this function:

 
def numToIndices(n: Int, l: List[Int]): List[Int] =
  if (l.isEmpty) Nil else l(n % l.size) :: numToIndices(n / l.size, l filter (_ != l(n % l.size)))

Now, given this representation of the solutions of this problem, it should be clear that the number of solutions is the factorial of 9, so there are solutions from 0 to 9! - 1. So, let's create a seed, and, non-strictly (to avoid out of memory errors), generate our possible solutions:

 
val seed = 1 to 9 toList
val possibleSolutions = Stream.range(0, seed reduceLeft (_*_)) map (numToIndices(_, seed))

Keeping the head of a stream is not a good idea, though. We need to filter for the actual solutions before assigning it to any val. Which, of course, we'll give you the final solutions:

 
val solutions = (0 until seed.reduceLeft(_*_)).toStream map (numToIndices(_, seed)) filter (test(_)) toList

Not particularly efficient, but the line count is good:

 
val indices = List(List(0,1,2), List(3,4,5), List(6,7,8), List(0,3,6), List(1,4,7), List(2,5,8), List(0,4,8), List(2,4,6))
def test(solution: List[Int]) = (indices map (_ map (solution(_)) sum) removeDuplicates).size == 1
def numToIndices(n: Int, l: List[Int]): List[Int] =
  if (l.isEmpty) Nil else l(n % l.size) :: numToIndices(n / l.size, l filter (_ != l(n % l.size)))
val seed = 1 to 9 toList
val solutions = (0 until seed.reduceLeft(_*_)).toStream map (numToIndices(_, seed)) filter (test(_)) toList

Which we can then print with:

 
println(solutions map (_.iterator grouped 3 map (_ mkString) mkString "\n") mkString "\n")

A Puzzle

A couple of days ago a friend of mine was playing with a puzzle I knew of a few years ago: a maze through which one had to drive a car. Here's the setup:

At each intersection, the car must take one of a limited number of allowed paths, as indicated by the arrows. The goal is to reach the exit on the other side.

At any rate, I felt an urge to solve it programmatically -- in Scala, of course. So, later, I sat down and started coding the solution. The first step, obviously, was getting the maze into some sort of data structure. I briefly tried to find the data being used in the puzzle, but gave up on it. Instead, I'd input the maze by hand.

I had two problems to solve, then. First, I had to figure out a good data structure to represent the maze. I thought a directed graph with the intersections as vertices seemed like a good representation to me, but the matricial nature of the maze was also appealing. So I decided on a compromise: I'd store the maze as a matrix, but each element of the matrix would be a vertex, which would be represented as a set of arrows.

The second problem related to how I'd represent the maze before inputting it. I decided to write it down as a big string and then parse it, but that still leaves the problem of what to write. I pondered writing each edge, but that seemed a bit error-prone. So I decided on a rather unconventional format: I'd write the directions going out from each intersection, as well as undirected edges represented by the two directions the edge connects.

In effect, the actual vertices of my graph are not the intersections, but the streets! Each intersection is just a set of directed edges.

So, having decided all that, I wrote down the data I expected to be used for the maze:

 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

Ugly as hell, but it should do the job. My task, then, was to specify the data structure, and write a parser for that.

First, directions. Not only my input is written in terms of directions, I was thinking of solving the problem by manipulating directions. So, let's create them. I don't particularly like Scala's Enumeration class, so I went with case objects:

object DirectionSet {
 sealed abstract class Direction
 case object Up extends Direction
 case object Down extends Direction
 case object Left extends Direction
 case object Right extends Direction
 val U = Up
 val D = Down
 val L = Left
 val R = Right
}

That gives me warnings on pattern matching, and short aliases for each direction. Please note, though, that Scala already has objects called Left and Right. This shouldn't present much of a problem, but, once I improved on these objects a bit, I made sure Scala knew to which objects I was referring to. Let's talk about these improvements and show them.

As I wrote the code, I found myself needing to get the opposite direction to the one I had. This was clearly a method to be added to Direction, and so I did. Another thing I did was to write a function to convert a Char into a Direction. Later, while refactoring, it was clear this function was better as a DirectionSet method, so I added it, and, while doing it, wrote a variant for Strings, though I never use it in my final code. Let's see, them, the full object:

object DirectionSet {
 sealed abstract class Direction {
   def opposite: Direction
 }
 case object Up extends Direction { override def opposite = DirectionSet.Down }
 case object Down extends Direction { override def opposite = DirectionSet.Up }
 case object Left extends Direction { override def opposite = DirectionSet.Right }
 case object Right extends Direction { override def opposite = DirectionSet.Left }
 val U = Up
 val D = Down
 val L = Left
 val R = Right
 def apply(s: Char): Direction = s.toLowerCase match {
   case 'u' => Up
   case 'd' => Down
   case 'l' => Left
   case 'r' => Right
   case _ => throw new IllegalArgumentException
 }
 def apply(s: String): Direction = s.toLowerCase match {
   case "up" => Up
   case "down" => Down
   case "left" => Left
   case "right" => Right
   case _ => throw new IllegalArgumentException
 }
}

And that's that. So, let's proceed. Our graph is composed of intersections, each of which is composed of the arrows present at that intersection. The next step, then, is defining these arrows. Here's how I did it:

import DirectionSet.{apply => _, _}


case class Arrow(from: Direction, to: Direction) {
 override def toString = from+"->"+to
} 
object Arrow {
 def apply(t: Tuple2[Direction,Direction]): Arrow = new Arrow(t._1, t._2)
}

Each arrow is described as going from a Direction to another Direction. A couple of helper methods, and we are done. At first, it might seem that the intersection being just a set of arrows, so it doesn't need a class of it's own. However, to validate the correctness of the maze I inputted, it would be nice to have a more "graphical" representation of it. I could leave that to the graph class, but, as it happens, it's a rather long code, so I separated it into a class of its own.

So, first, I decided on the ASCII-art I'd be using to represent an intersection. I got it in as a literal, converted it into an array of arrays, and then, in the class main constructor, changed each relevant character from the ASCII-art into a space if the intersection didn't contain the corresponding arrow. The central character was a little bit more complex than that, and I used some pattern matching on it. Here's the final result:

case class Intersection(arrows: List[Arrow]) {
 private val drawing = """|  ^ 
                          | /|\
                          |<-+->
                          | \|/
                          |  v  """.stripMargin split "\n" map (_ toArray)
 private def hasUp = arrows exists (_.to == Up)
 private def hasDown = arrows exists (_.to == Down)
 private def hasLeft = arrows exists (_.to == Left)
 private def hasRight = arrows exists (_.to == Right)
 private def hasArrowBetween(a: Direction, b: Direction) = (arrows contains Arrow(a, b)) || (arrows contains Arrow(b, a))
 private def testAndSet(line: Int, col: Int, test: Boolean) =
   if (!test) drawing(line)(col) = ' '

 testAndSet(0, 2, hasUp)
 testAndSet(1, 1, hasArrowBetween(Left, Up))
 testAndSet(1, 2, hasArrowBetween(Up, Down))
 testAndSet(1, 3, hasArrowBetween(Up, Right))
 testAndSet(2, 0, hasLeft)
 testAndSet(2, 1, hasArrowBetween(Left, Right))
 testAndSet(2, 3, hasArrowBetween(Left, Right))
 testAndSet(2, 4, hasRight)
 testAndSet(3, 1, hasArrowBetween(Left, Down))
 testAndSet(3, 2, hasArrowBetween(Up, Down))
 testAndSet(3, 3, hasArrowBetween(Down, Right))
 testAndSet(4, 2, hasDown)
 drawing(2)(2) = (hasArrowBetween(Left, Right), hasArrowBetween(Up, Down)) match {
   case (false, false) => ' '
   case (false, true) => '|'
   case (true, false) => '-'
   case (true, true) => '+'
 }
  
 override def toString = drawing map (_ mkString) mkString "\n"
}
object Intersection {
 def apply(arrows: Arrow*): Intersection = new Intersection(arrows.toList)
}

The main class, the graph, started as simple as this:

case class Graph(g: Array[Array[Intersection]])

After that, I started on the parser. The first thing was breaking up the string into basic components: each line, each intersection on the line, the outgoing arrows and the edges:

def brkString(s: String) = s.trim split "\n" map (_.trim split "," map (_.trim split ":"))

Lot's of "trim" just so I needn't worry where there were space. The next two steps were easy: for each line, for each intersection... It looks like a for-comprehension, but to return an array of arrays I'd need to nest two for-comprehensions, which makes them unyieldy. It's better simply to go with "map". So, given the input string representing each intersection, return an intersection instance. The mapping code ended looking like this:

   (
     brkString(s)
     map (line =>
       line map (col =>
         Intersection(arrows(col): _*)
       )
     )
   )

Which leaves just "arrows" to be defined. The idea behind "arrows" is to convert each letter into a direction, then, for each direction representing an outgoing arrow, find all undirected edges containing that direction and yield a directed edge in the form of an Arrow instance:

   def arrows(a: Array[String]): List[Arrow] = {
     def str2Directions(s: String): List[Direction] = s map (DirectionSet(_)) toList
     val dsts = str2Directions(a(0).trim)
     val paths = a(1).trim split "\\s+" map str2Directions
     for(dst <- dsts;
         path <- paths if path contains dst;
         org <- path filter (_ != dst))
     yield Arrow(org, dst)
   }

These functions were all independent originally, but, as I refactored, they came to be part of the Graph object:

object Graph {
 def apply(s: String) = new Graph(str2Graph(s))

 def str2Graph(s: String) = {
   def brkString(s: String) = s.trim split "\n" map (_.trim split "," map (_.trim split ":"))
   def arrows(a: Array[String]): List[Arrow] = {
     def str2Directions(s: String): List[Direction] = s map (DirectionSet(_)) toList
     val dsts = str2Directions(a(0).trim)
     val paths = a(1).trim split "\\s+" map str2Directions
     for(dst <- dsts;
         path <- paths if path contains dst;
         org <- path filter (_ != dst))
     yield Arrow(org, dst)
   }
   (
     brkString(s)
     map (line =>
       line map (col =>
         Intersection(arrows(col): _*)
       )
     )
   )
 }
}

With that I could now create an instance of my graph. I could verify each intersection individually, but printing them side by side posed a problem: each intersection was composed of multiple lines, so I needed to interpolate the lines of all intersections belonging the the same "line" in the graph before I could concatenate them.

I approached this as a general problem in concatenating string with multiple lines. I'd split each string into its component lines, and keep a list of those. I'd then try to "fold" them into a big string, but that was too hacky for my tastes. I then modified it to iterate over these lists, concatenating the "heads" and looping with the "tails". Finally, I'd take each of those lines of intersection, and concatenate with interpoling newlines to the next. Here's the final result:

 override def toString = {
   def concatStrings(ss: String*) = {
     // Turn my arguments into a list of lists of lines, get the length
     // of the biggest chunk, a pad of the same size, and a function to
     // make them all the same length
     val lines = ss.toList map (_ split "\n" toList)
     val maxLineSize = lines flatMap (_ map (_ length)) reduceLeft (_ max _)
     val pad = " " * maxLineSize
     def fmtStr(s: String) = "%"+maxLineSize+"s" format s

     // Make an iterator for "lines"
     def tailOrNil[T](l: List[T]) = if (l.isEmpty) Nil else l.tail
     def getTails[T](l: List[List[T]]): List[List[T]] = l map tailOrNil[T]
     def hasLines(l: List[List[_]]) = l exists (!_.isEmpty)
     val linesIterator = Iterator.iterate(lines)(getTails) takeWhile hasLines

     // Get the head of each list, or a pad in the absence of a head,
     // make them all the same size, and then concatenate with an interpoling
     // pad.
     def concatHead(l: List[List[String]]): String =
       l map (_.headOption getOrElse pad) map fmtStr mkString pad
    
     // Iterate over lines, concatenating the heads of the list, and then
     // concatenate them all with interpolating newlines
     (for(nextLines <- linesIterator)
      yield concatHead(nextLines)) mkString "\n"
   }
   g map (line => concatStrings(line map (_ toString): _*)) mkString "\n\n\n"
 }

You can tell by the amount of comments that I'm not really satisfied with it yet, but it does its job. Here's an example:

   >     <   >     <---      <--->     <
  /       \ /       \           /       \
 v         v                             v




 ^                   ^         ^         ^
/|\       /|\        |\        |        /|
-+->     <-+->     <-+->     <-+->     < |
 |        \|/       \|         |/        |
           v         v         v




 ^         ^         ^         ^         ^
 |\         \       /|         |\        |
 | >     <--->       |         | >       |
 |/       \ /       \|         |        \|
 v         v         v         v         v




 ^         ^         ^         ^         ^
 |\       / \       /|\       / \       /|
 | >     <--->      -+->     <--->     < | >
 |/         /        |/       \ /        |/
 v         v                             v




 ^         ^         ^         ^         ^
  \       / \       / \       / \       /
   >     <--->     <--->     <--->     <

Now I started on the solving algorithm properly. This part of it was rather faster and problem-free. First, I had to have a way to indicate where my car was. I created a class Position for that. This class has two components: one is the actual coordinates, indicating at which intersection the car had stopped -- I called it Coordinates. The other component is the direction from which the car was entering the intersection. Here's the class:

case class Coordinates(line: Int, column: Int) {
 override def toString = "("+line+","+column+")"
}
case class Position(from: Direction, at: Coordinates) {
 override def toString = from.opposite.toString.toLowerCase+" to "+at
}

They didn't have any toString method originally. When I finally got to print the answer, I changed those methods to make the answer more readable.

Finally, I added a couple of methods to Graph. First, given a Position, to which directions the car could go? This one is quite natural:

 def directionsFrom(pos: Position):List[Direction] = (
   g(pos.at.line)(pos.at.column).arrows
   filter (_.from == pos.from)
   map (_.to)
 )

Next, given a Position, which would be the next available positions? This one required a helper method, which would compute the correct coordinates when moving in a given direction. I use "opposite" here. The idea is that, if I'm going "down", for example, I'd end at the upper side of the next intersection.

 def positionsFrom(pos: Position): List[Position] = {
   def moveTo(to: Direction) = Position(to.opposite, to match {
       case Up => Coordinates(pos.at.line - 1, pos.at.column)
       case Down => Coordinates(pos.at.line + 1, pos.at.column)
       case Left => Coordinates(pos.at.line, pos.at.column - 1)
       case Right => Coordinates(pos.at.line, pos.at.column + 1)
   })
   directionsFrom(pos) map moveTo
 }

And, with that, we are ready to solve the problem. All we need to do is keep following the coordinates. Since I receive a list of coordinates at each intersection, I have to try all of them. There's two ways of going about it. First, I can take the first option out of each intersection and keep going, until I start looping around, get to a dead end, or arrive at my destination. I can then opt to backtrack and try one of the other options. That's a depth first algorithm, a natural for recursion.

Alternatively, I can keep a list of all possible paths, and keep extending each one until one arrives. That can be done nicely with queues. I take one path from the beginning of a queue, compute all possible paths from there, and add them to the back of the queue. Once I find a path that has arrived at the goal, I stop. This is what I decided to do. Here's the algorithm:

 val graph = Graph(graphString)
 val origin = Position(Left, Coordinates(1, 0))
 val goal = Coordinates(3, 5)

 def solve = {
   import scala.collection.mutable.{Set, Queue}
  
   def nextPaths(path: Path, visited: Set[Position]): List[Path] = (
     graph
     positionsFrom path.head
     filter (to => !(visited contains to))
     map (to => to :: path)
   )
   val visited = Set[Position]()
   val next = new Queue[Path]()
   var path = List(origin)
   while(path.head.at != goal) {
     visited += path.head
     next enqueue (nextPaths(path, visited): _*)
     path = next dequeue
   }
   printAnswer(path)
 }

I still did a little trick to print the answer in a readable way, but it was hacky enough that I won't get into details. Here's the whole program, though. You can paste it directly into REPL and run it with "Problem.solve", or compile it and run Problem. So, how would you code this in YOUR favorite language? Please drop me a link on the comments below if you take this challenge too.

object DirectionSet {
 sealed abstract class Direction {
   def opposite: Direction
 }
 case object Up extends Direction { override def opposite = DirectionSet.Down }
 case object Down extends Direction { override def opposite = DirectionSet.Up }
 case object Left extends Direction { override def opposite = DirectionSet.Right }
 case object Right extends Direction { override def opposite = DirectionSet.Left }
 val U = Up
 val D = Down
 val L = Left
 val R = Right
 def apply(s: Char): Direction = s.toLowerCase match {
   case 'u' => Up
   case 'd' => Down
   case 'l' => Left
   case 'r' => Right
   case _ => throw new IllegalArgumentException
 }
 def apply(s: String): Direction = s.toLowerCase match {
   case "up" => Up
   case "down" => Down
   case "left" => Left
   case "right" => Right
   case _ => throw new IllegalArgumentException
 }
}

import DirectionSet.{apply => _, _}

case class Arrow(from: Direction, to: Direction) {
 override def toString = from+"->"+to
} 
object Arrow {
 def apply(t: Tuple2[Direction,Direction]): Arrow = new Arrow(t._1, t._2)
}

case class Intersection(arrows: List[Arrow]) {
 private val drawing = """|  ^ 
                          | /|\
                          |<-+->
                          | \|/
                          |  v  """.stripMargin split "\n" map (_ toArray)
 private def hasUp = arrows exists (_.to == Up)
 private def hasDown = arrows exists (_.to == Down)
 private def hasLeft = arrows exists (_.to == Left)
 private def hasRight = arrows exists (_.to == Right)
 private def hasArrowBetween(a: Direction, b: Direction) = (arrows contains Arrow(a, b)) || (arrows contains Arrow(b, a))
 private def testAndSet(line: Int, col: Int, test: Boolean) =
   if (!test) drawing(line)(col) = ' '

 testAndSet(0, 2, hasUp)
 testAndSet(1, 1, hasArrowBetween(Left, Up))
 testAndSet(1, 2, hasArrowBetween(Up, Down))
 testAndSet(1, 3, hasArrowBetween(Up, Right))
 testAndSet(2, 0, hasLeft)
 testAndSet(2, 1, hasArrowBetween(Left, Right))
 testAndSet(2, 3, hasArrowBetween(Left, Right))
 testAndSet(2, 4, hasRight)
 testAndSet(3, 1, hasArrowBetween(Left, Down))
 testAndSet(3, 2, hasArrowBetween(Up, Down))
 testAndSet(3, 3, hasArrowBetween(Down, Right))
 testAndSet(4, 2, hasDown)
 drawing(2)(2) = (hasArrowBetween(Left, Right), hasArrowBetween(Up, Down)) match {
   case (false, false) => ' '
   case (false, true) => '|'
   case (true, false) => '-'
   case (true, true) => '+'
 }
  
 override def toString = drawing map (_ mkString) mkString "\n"
}
object Intersection {
 def apply(arrows: Arrow*): Intersection = new Intersection(arrows.toList)
}

case class Coordinates(line: Int, column: Int) {
 override def toString = "("+line+","+column+")"
}
case class Position(from: Direction, at: Coordinates) {
 override def toString = from.opposite.toString.toLowerCase+" to "+at
}

case class Graph(g: Array[Array[Intersection]]) {
 def directionsFrom(pos: Position): List[Direction] = (
   g(pos.at.line)(pos.at.column).arrows
   filter (_.from == pos.from)
   map (_.to)
 )

 def positionsFrom(pos: Position): List[Position] = {
   def moveTo(to: Direction) = Position(to.opposite, to match {
       case Up => Coordinates(pos.at.line - 1, pos.at.column)
       case Down => Coordinates(pos.at.line + 1, pos.at.column)
       case Left => Coordinates(pos.at.line, pos.at.column - 1)
       case Right => Coordinates(pos.at.line, pos.at.column + 1)
   })
   directionsFrom(pos) map moveTo
 }

 override def toString = {
   def concatStrings(ss: String*) = {
     // Turn my arguments into a list of lists of lines, get the length
     // of the biggest chunk, a pad of the same size, and a function to
     // make them all the same length
     val lines = ss.toList map (_ split "\n" toList)
     val maxLineSize = lines flatMap (_ map (_ length)) reduceLeft (_ max _)
     val pad = " " * maxLineSize
     def fmtStr(s: String) = "%"+maxLineSize+"s" format s

     // Make an iterator for "lines"
     def tailOrNil[T](l: List[T]) = if (l.isEmpty) Nil else l.tail
     def getTails[T](l: List[List[T]]): List[List[T]] = l map tailOrNil[T]
     def hasLines(l: List[List[_]]) = l exists (!_.isEmpty)
     val linesIterator = Iterator.iterate(lines)(getTails) takeWhile hasLines

     // Get the head of each list, or a pad in the absence of a head,
     // make them all the same size, and then concatenate with an interpoling
     // pad.
     def concatHead(l: List[List[String]]): String =
       l map (_.headOption getOrElse pad) map fmtStr mkString pad
    
     // Iterate over lines, concatenating the heads of the list, and then
     // concatenate them all with interpolating newlines
     (for(nextLines <- linesIterator)
      yield concatHead(nextLines)) mkString "\n"
   }
   g map (line => concatStrings(line map (_ toString): _*)) mkString "\n\n\n"
 }
}
object Graph {
 def apply(s: String) = new Graph(str2Graph(s))

 def str2Graph(s: String) = {
   def brkString(s: String) = s.trim split "\n" map (_.trim split "," map (_.trim split ":"))
   def arrows(a: Array[String]): List[Arrow] = {
     def str2Directions(s: String): List[Direction] = s map (DirectionSet(_)) toList
     val dsts = str2Directions(a(0).trim)
     val paths = a(1).trim split "\\s+" map str2Directions
     for(dst <- dsts;
         path <- paths if path contains dst;
         org <- path filter (_ != dst))
     yield Arrow(org, dst)
   }
   (
     brkString(s)
     map (line =>
       line map (col =>
         Intersection(arrows(col): _*)
       )
     )
   )
 }
}

object FormatLines {
 def apply(s: String): String = {
   def breakAt80(s: String): (String, String) = {
     val m = """^(.{0,80})( (.*))?$""".r findFirstMatchIn s
     m match {
       case Some(result) =>
       val rest = if (result.group(3) == null) "" else result.group(3)
       (result.group(1), rest)
       case None => (s, "")
     }
   }
   def fmt(input: String, output: String): String =
   if (input.isEmpty)
   output
   else {
     val (nextLine, rest) = breakAt80(input)
     fmt(rest, output+nextLine+"\n")
   }
   fmt(s, "")
 }
}

object Problem {
 type Path = List[Position]
 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
 val graph = Graph(graphString)
 val origin = Position(Left, Coordinates(1, 0))
 val goal = Coordinates(3, 5)

 def printAnswer(path: Path) {
   val answer = FormatLines(
     "Arrived at "+path.head.at+
     " through "+path.tail.reverse.mkString(", ")+
     " and then "+path.head.from.opposite.toString.toLowerCase+"."
   )
   println(graph)
   println(answer)
 }

 def solve = {
   import scala.collection.mutable.{Set, Queue}
  
   def nextPaths(path: Path, visited: Set[Position]): List[Path] = (
     graph
     positionsFrom path.head
     filter (to => !(visited contains to))
     map (to => to :: path)
   )
   val visited = Set[Position]()
   val next = new Queue[Path]()
   var path = List(origin)
   while(path.head.at != goal) {
     visited += path.head
     next enqueue (nextPaths(path, visited): _*)
     path = next dequeue
   }
   printAnswer(path)
 }

 def main(args: Array[String]) {
   solve
 }
}