Last updated on

Counting paths

Points
40 points
Topics
Recursion, State, Specifications
Files to submit
src/main/scala/paths/CountPaths.scala

In this exercise, your task is to write a function that counts the number of ways to travel from one point to another an infinite integer grid, without encountering obstacles, under the following constraints:

You are given the following inputs:

The type Coord is shown below for your reference:

case class Coord(x: Int, y: Int)

pathcounting/src/main/scala/paths/CountPaths.scala

Warm up

Use the following examples to check your understanding of the problem:

Base cases
  1. How many ways are there to travel from (-2, -2) to (-2, -2)?
  2. How many ways are there to travel from (3, 4) to (3, 1)?
  3. How many ways are there to travel from (3, 4) to (0, 4)?
Recursion

If obstacles are laid out such that there are 18 ways to travel from (0, 0) to (4, 5) and 21 ways to travel from (0, 0) to (5, 4), how many ways are there to travel from (0, 0) to (5, 5)?

Examples
  1. How many ways are there to travel from (0, 0) to (1, 3) if there are no obstacles?
  2. How many ways are there to travel from (0, 0) to (1, 3) if hasObstacle is _ == Coord(1, 0)?
Answers
Base cases
  1. 1
  2. 0
  3. 0
Recursion

18 + 21 = 39

Examples
  1. 4
  2. 3

Naive implementation (10 points)

Implement the function countPathsNaive without worrying about efficiency. countPathsNaive should throw an IllegalArgumentException if src or dst has an obstacle.

def countPathsNaive(
    src: Coord,
    dst: Coord,
    hasObstacle: Coord => Boolean
): Int =
  require(???)
  ???

pathcounting/src/main/scala/paths/CountPaths.scala

The problem definition gives us three cases:

  1. If src == dst, there is a single path;
  2. If src has an obstacle or is to the right or above dst, there is a no path;
  3. Otherwise, we recursively count from the right and from above and sum the results.

The solution below does the following, with an additional check in the main function to make implement the required precondition:

def countPathsNaive(
    src: Coord,
    dst: Coord,
    hasObstacle: Coord => Boolean
): Int =
  require(!hasObstacle(src) && !hasObstacle(dst))
  def countFrom(src: Coord): Int =
    if src == dst then 1
    else if hasObstacle(src) || src.x > dst.x || src.y > dst.y then 0
    else
      math.addExact(
        countFrom(src.copy(x = src.x + 1)),
        countFrom(src.copy(y = src.y + 1))
      )
  countFrom(src)

pathcounting/src/main/scala/paths/CountPaths.scala

Optimized implementation (30 points)

Implement the function countPathsFast, making sure that it runs in time at proportional to at most $|\texttt{dst.x} - \texttt{src.x}| \cdot |\texttt{dst.y} - \texttt{src.y}|$:

def countPathsFast(src: Coord, dst: Coord, hasObstacle: Coord => Boolean): Int =
  require(???)
  ???

pathcounting/src/main/scala/paths/CountPaths.scala

The last two tests (related to stack overflows) are hard to pass and worth very few points (2 out of 40). Do not waste time on them! Use testOnly -- *Naive* and testOnly -- *Fast* to run the naive and fast tests without the last two tests.

The expected implementation, which passes all the tests except the final two, is the following one (using a mutable map makes it a two-lines change from the original recursive solution):

def countPathsFastRec(
    src: Coord,
    dst: Coord,
    hasObstacle: Coord => Boolean
): Int =
  require(!hasObstacle(src) && !hasObstacle(dst))
  val cache = scala.collection.mutable.Map.empty[Coord, Int]
  def countFrom(src: Coord): Int =
    cache.getOrElseUpdate(
      src,
      if src == dst then 1
      else if hasObstacle(src) || src.x > dst.x || src.y > dst.y then 0
      else
        math.addExact(
          countFrom(src.copy(x = src.x + 1)),
          countFrom(src.copy(y = src.y + 1))
        )
    )
  countFrom(src)

pathcounting/src/main/scala/paths/CountPaths.scala

Passing the last two tests is a bit more challenging. A naive attempt at converting this solution into a loop passes one more test, but runs into a performance issue due to the shape of the final test:

def countPathsFastLoop(
    src: Coord,
    dst: Coord,
    hasObstacle: Coord => Boolean
): Int =
  require(!hasObstacle(src) && !hasObstacle(dst))
  val cache = scala.collection.mutable.Map.empty[Coord, Int].withDefaultValue(0)
  cache(dst) = 1
  for x <- dst.x to src.x by -1 do
    for y <- dst.y to src.y by -1 do
      val c = Coord(x, y)
      if c != dst then
        cache(c) =
          if hasObstacle(c) then 0
          else cache(Coord(x + 1, y)) + cache(Coord(x, y + 1))
  cache(src)

pathcounting/src/main/scala/paths/CountPaths.scala

The reason this looping solution doesn’t work for all tests is that it does too much work. Instead, the last solution below first collects the set of all coordinates to explore, then computes their values:

def countPathsFastTopo(
    src: Coord,
    dst: Coord,
    hasObstacle: Coord => Boolean
): Int =
  require(!hasObstacle(src) && !hasObstacle(dst))

  def neighbors(c: Coord) =
    List(c.copy(x = c.x + 1), c.copy(y = c.y + 1)).filter: c =>
      c.x <= dst.x && c.y <= dst.y && !hasObstacle(c)
  def dependents(c: Coord) =
    List(c.copy(x = c.x - 1), c.copy(y = c.y - 1)).filter: c =>
      c.x >= src.x && c.y >= src.y && !hasObstacle(c)

  def bfs(
      boundary: List[Coord],
      previous: List[List[Coord]]
  ): List[List[Coord]] =
    if boundary.contains(src) || boundary.isEmpty then
      previous.reverse
    else
      val next = boundary.flatMap(dependents).distinct
      bfs(next, next :: previous)

  val cache =
    bfs(List(dst), Nil).foldLeft(Map(dst -> 1)): (cache, boundary) =>
      boundary.map(c =>
        c -> neighbors(c).map(n => cache.getOrElse(n, 0)).sum
      ).toMap

  cache.getOrElse(src, 0)

pathcounting/src/main/scala/paths/CountPaths.scala

© 2023–2025 EPFL. All rights reserved.