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
 }
}