Last updated on Wednesday, January 08, 2025

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:

• All coordinates are integers.
• You may only move up (i.e. go from $(x, y)$ to $(x, y+1)$) or to the right (i.e., go from $(x, y)$ to $(x+1, y)$); never down or to the left.
• The starting and ending points never have obstacles.
• You may assume that the number of paths in tests is always $< 2^{31}$.

You are given the following inputs:

• The coordinates of a starting point src: Coord.
• The coordinate of a destination dst: Coord.
• A predicate hasObstacle: Coord => Bool indicating which coordinates are blocked by obstacles.

The type Coord is shown below for your reference:

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

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)?

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(???)
  ???

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(???)
  ???

© 2023, 2024 EPFL. All rights reserved.