About 4 months ago, a friend of mine sent me a link to this fun challenge proposed by Redmart. The goal is to find not the shortest but the longest path in a mountain.
It is a perfect exercise to dive into some functional code and apprehend recursion for new comers. In this article, I will explain my initial solution and some ways to make it faster.
Then, in a second post, I will expose a naive solution using akka-streams. As you may have already noticed, I am quite excited about this open source library build upon akka and this problem to solve is a good way to think about how to solve a graph puzzle in a multi-threaded environment.

A single threaded functional solution

Core algorithm

If we put aside the parsing of the file and the building of the global graph the algorithm is simple. For the resolution of this puzzle, let's consider that the mountain is a map made of tiles. Tiles are located at an (x,y) coordinates and also feature an height coordinate as well as a list of neighbors.

When thinking functional, the solution of a puzzle like this one often ends using a recursive algorithm. This means that we will solve the puzzle locally for each tile of the map and then we will gather those local solutions to reduce it and find the maxof them. That's enough theory, let's code now.

The behavior of a tile is written using a Tile case class. it boils down to the following:

case class Tile(x: Int, y: Int, height: Int, neighbors: List[Tile]) {

    lazy val accessibleNeighbors =  neighbors.filter(n => n.height < height)
    lazy val longestAndSteepestPath = computeLongestAndSteepestPath()

    private def computeLongestAndSteepestPath(): Path = {
      accessibleNeighbors match{
        case Nil => Path(height, height, 1, List(this))
        case _ => accessibleNeighbors.map{n =>
            val p = n.computeLongestAndSteepestPath()
            // Include this node
            Path(height, p.endHeight, p.length + 1, this :: p.stack)
          }.max
      }
    }
  }

As said earlier, a Tile is just three coordinates and a list of neighbors (north, south, east, west). A list of accessible ones is build using a filter on the neighbors since we can only travel from one node to an other one which is lower. We made this accessibleNeighbors list lazy so that it will be computed only once.
When trying to find the longest and steepest path available for a given node, we are actually asking for the longest and steepest path for the neighbors of this node and we will only keep the max of them. This introduce the concept of Path which will represent our solutions. It consists of a starting height (the height of the starting tile), an end height (the one of the ending tile), a length (the number of tiles involved in the path) and a list of the tiles traversed by the path.

case class Path(startHeight: Int, endHeight: Int, length: Int, stack: List[Tile]){
    def drop = startHeight - endHeight
  }

We also provided a drop method, computing the total drop of the path.
To compare paths and use the max function to keep the longest and steepest path of the path accessible for the current node, we need to provide an ordering for paths. This is done through the implicit object PathOrdering.

implicit object PathOrdering extends Ordering[Path]{
    override def compare(x: Path, y: Path): Int = {
      val lengthCompare = x.length.compareTo(y.length)
      if (lengthCompare == 0){
        x.drop compareTo y.drop
      } else {
        lengthCompare
      }
    }
  }

Now that we have all the bricks needed, let's focus on the algorithm :

private def computeLongestAndSteepestPath(): Path = {
      accessibleNeighbors match{
        case Nil => Path(height, height, 1, List(this))
        case _ => accessibleNeighbors.map{n =>
            val p = n.computeLongestAndSteepestPath()
            // Include this node
            Path(height, p.endHeight, p.length + 1, this :: p.stack)
          }.max
      }
    }

This method is very simple actually and here is what we do in it :

• If there is no other node accessible from the current tile, it means that we are at the bottom of mountain. Hence, the longest and steepest path for this tile is a drop of 0. It is our termination handler.
• Otherwise, for each available node, we make a recursive call to determine which one has the longest and steepest path. We do not forget to make this comparison on paths including the current Tile, thats why we are building a new path build upon the longest and steepest path provided by the neighbor currently being processed. Finally the max function keeps the best solution.

All we need to do now is to go through all the tiles to find the max of these max.

The SkiMap

So far we were focused on one starting Tile, assuming we had a list of neighbors already available for each tile. That is not completely the case and building the list of tiles, each one resolving its own neighbors is not as trivial as exposed earlier. The SkiMap class will help us in building tiles, and finding the global longest and steepest path. As tiles contains references to other tiles, we need a way to build this list in an immutable fashion. That is why we modify the Tile class to :

case class Tile(x: Int, y: Int, height: Int, neighbors: () => List[Tile])

Neighbors are no longer given as an existing list, but as a function which is able to give them :

def feeder( source:() => Map[(Int, Int), Tile])( x: Int, y: Int): ()=>List[Tile] = () => {

    def north: Option[Tile] = source().get(x-1, y)
    def south: Option[Tile] = source().get(x+1, y)
    def east: Option[Tile] = source().get(x, y-1)
    def west: Option[Tile] = source().get(x, y+1)
    List(north, south, east, west).flatten
  }

This looks like a complicated function ! In fact, it is a curried one which could have this documentation : "given a map of tiles where keys are (x,y) coordinates, and then an (x, y) coordinates, returns a function which builds a list of neighbors for the supplied coordinates.
We are doing this rather sophisticated builder because the neighbors of a given tile are not already in the source map. This has to be done "lazily". This means that this feeder function will actually be called only when a tile will compute its accessibleNeighbors.
In fact, the SkiMap class is build from a rawMap of type Map[(Int,Int),Int]. From this map which maps (x, y) coordinates to an height, we need to have a map of type Map[(Int, Int), Tile]. That is where we use the previously defined feeder function.

lazy val fullMap: Map[(Int, Int), Tile ] = rawMap.map{
    case ((x, y), h) => (x, y) -> Tile(x, y, h, feeder(() =>fullMap)(x, y))
  }

This constant is lazily built. Which allows us to use it in a function we pass as parameter to the feeder function.

The last point now is to find the best solution. For this, we only need to map every node to its longest and steepest path and keep the max of them.

Conclusion

The solution is not the best one and we could highly optimize it. We will see in an other entry how using akka-streams helps, for instance.

This small puzzle was an interesting way to dive into recursion and immutable data structures in Scala. Explaining lazy and immutable graphs is not trivial, I realize, but I hope I gave you enough things to think about to dive deeper into these concepts. The complete code for this puzzle is available on my github account in this repository, on the master branch.

Happy coding !