Last updated on Friday, December 19, 2025

Exercise Set

Points: 40 points
Files to submit: src/main/scala/exercises/MapFormatter.scala; src/main/scala/exercises/GeneratingFunction.scala

Welcome to the CS-214 final exam! This first problem is a set of small exercises.

Make sure that all exercises compile successfully when you submit (try sbt compile), otherwise you will get 0 points for all exercises!

Map Formatter (20 points)

Topics: Contextual abstraction, Webapps

In this exercise, we want to transfer guidebooks, containing useful tourist information, over the Internet through a data format called MiniJSON.

MiniJSON is a simplified version of JSON, where there can only be numbers, strings and arrays. In an array, each value is another MiniJSON value, so nested arrays are possible. We represent MiniJSON in Scala with the MiniJSON enum:

/** A simplified version of JSON where only numbers, strings and arrays are
  * available.
  */
enum MiniJSON:
  case JSONNumber(n: Int)
  case JSONString(s: String)
  case JSONArray(items: List[MiniJSON])

exercises/src/main/scala/exercises/MapFormatter.scala

For example, [0, ["one", 2], 3] is a valid MiniJSON value, represented in Scala as:

JSONArray(List(
  JSONNumber(0),
  JSONArray(List(JSONString("one"), JSONNumber(2))),
  JSONNumber(3)
))

The logic to perform encoding and decoding between Scala values and MiniJSON is defined with the WireFormat[T] trait, where:

the encode method takes a value of type T, and returns a MiniJSON value.
the decode method takes a MiniJSON value and attempts to convert it back to a T. If the conversion fails, it returns a Failure.

/** The encoder and decoder between values of type `T` and the wire encoding
  * [[MiniJSON]].
  */
trait WireFormat[T]:
  /** Encodes a value of type `T` into a [[MiniJSON]] value. */
  def encode(item: T): MiniJSON

  /** Decodes a [[MiniJSON]] value back to a value of type `T`. */
  def decode(json: MiniJSON): Try[T]

exercises/src/main/scala/exercises/MapFormatter.scala

You can find implementations of the WireFormat for Scala primitive types (Int, Char, Boolean and String) as well as Coordinate and Monument in the WireFormat object.

A guidebook contains a list of bus stops (as Coordinates and a list of bus route numbers) and scenic routes. Each scenic route is a list of Monuments to visit.

/** A guidebook includes useful information such as bus stop locations and
  * scenic routes.
  */
case class Guidebook(info: List[Information])

enum Information:
  /** A bus stop with location and served bus lines. */
  case BusStop(where: Coordinate, busLines: List[Int])

  /** A scenic route is a list of monuments to visit in order. */
  case ScenicRoute(monuments: List[Monument])

/** An attraction on the map, with a name and a coordinate. */
case class Monument(name: String, where: Coordinate)

/** A coordinate on the map. */
case class Coordinate(x: Int, y: Int)

exercises/src/main/scala/exercises/MapFormatter.scala

💪 Task: Implement `WireFormat` for `Guidebook`

Your task is to implement WireFormat for Guidebook. You are free to pick any representation for the encoded MiniJSON.

/** The wire format for [[Guidebook]]. */
given WireFormat[Guidebook] = ???

exercises/src/main/scala/exercises/MapFormatter.scala

You can run tests for this exercise using the testOnly command.

sbt:exercises> testOnly -- *mapformatter*

Generating Functions (20 points)

Topics: Laziness

Mathematicians sometimes like to reason about inifinite polynomials, which are also often called series, or generating functions.

We define a generating function $G$ as a possibly infinite sequence of coefficients $G = (G_0, G_1, \ldots)$ that represents the following function: $$ G(x) = \sum\limits_{i=0}^\infty G_ix^i = G_0 + G_1 x + G_2 x^2 + G_3 x^3 + \ldots $$

Because of their infinite length, we represent the coefficients as a LazyList in Scala, where each element is a Rational number (i.e. a fraction of two integers).

type GeneratingFunction = LazyList[Rational]

exercises/./src/main/scala/exercises/GeneratingFunction.scala

You can use regular number operations (+, *, …) on Rational.

Examples

The zero function $Z(x) = 0$ is represented as $Z = (0, 0, …)$. In Scala,
```
/** Generating function of the zero polynomial G(x) = 0. */
val zero: GeneratingFunction = LazyList.continually(Rational(0))
```
exercises/./src/main/scala/exercises/GeneratingFunction.scala

A regular (finite) polynomial can be represented by its coefficients, followed by a sequence of zeroes:

/** Generating function of a polynomial.
  *
  * We simply set the coeffients to match the polynomials, and set the later
  * coefficients to zero.
  */
def fromPolynomial(coefficients: Seq[Rational]): GeneratingFunction =
  LazyList.from(coefficients) #::: zero

exercises/./src/main/scala/exercises/GeneratingFunction.scala

The exponential function $e^x$ can be represented as a generating function by its Taylor expansion $G = (1, \frac{1}{1!}, \frac{1}{2!}, \frac{1}{3!}, …)$:
```
/** Exponential function e^x by Taylor expansion */
val exp: GeneratingFunction =
  def fac(n: Int): Long =
    if n == 0 then 1L else fac(n - 1) * n
  LazyList.from(0).map(n => Rational(1, fac(n)))
```
exercises/./src/main/scala/exercises/GeneratingFunction.scala

💪 Task: Implement operations on `GeneratingFunction`

Your task is to implement three basic operations on generating functions, as extension methods of a GeneratingFunction g (you can implement them in any order), as documented below.

You can run tests for this exercise using the testOnly command.

sbt:exercises> testOnly -- "*generatingfunction*"

Two tests, marked difficult, may take a long time to complete if your solution is inefficient. They are disabled by default and will not run nor give you points until you enable them. Once you’re ready, you can enable them by changing enableDifficultTests to true.

object GeneratingFunction:
  /** Set this value to true to enable difficult tests. */
  val enableDifficultTests: Boolean =
    false

exercises/./src/main/scala/exercises/GeneratingFunction.scala

Addition

The addition of two generating functions $G, F$ is defined by a generating function $H = G + F$ such that for all $i$, $$ H_i = G_i + F_i $$

extension (g: GeneratingFunction)
  /** Adds two generating functions G and F. */
  def +(f: GeneratingFunction): GeneratingFunction =
    ???

exercises/./src/main/scala/exercises/GeneratingFunction.scala

Multiplication

The multiplication of two generating functions $G, F$ is defined by a generating function $H = GF$ such that for all $i$, $$ H_i = \sum\limits_{k = 0}^i G_k F_{i-k} = G_iF_0 + G_{i-1}F_1 + … + G_1F_{i-1} + G_0F_i $$

extension (g: GeneratingFunction)
  /** Multiplies two generating functions G and F. */
  def *(f: GeneratingFunction): GeneratingFunction =
    ???

exercises/./src/main/scala/exercises/GeneratingFunction.scala

Evaluation

Given an input $x$ and a bound $l$, evaluate $G(x)$ on the first $l$ terms of $G$. $$ G\text{.evaluate}(x, l) = \sum\limits_{i=0}^{l-1} G_ix^i = G_0 + G_1x + \ldots + G_{l-1}x^{l-1} $$

extension (g: GeneratingFunction)
  /** Evaluate G(x), taking only the first `l` terms. */
  def evaluate(x: Rational, l: Int): Rational =
    ???

exercises/./src/main/scala/exercises/GeneratingFunction.scala