Last updated on Saturday, October 18, 2025

Additional midterm-prep problems

This extra exercise is intended to help you get ready for the midterm. You do not have to complete it to succeed.

Exercises marked with 🔥 are the most challenging ones.

While solving these exercises, take a moment to reflect on how they relate to the three pillars of this course: 🧩 modularity, ✅ correctness, and 🛠️ real-world engineering.

Halves and interleavings

Halves

Write a recursive function halves that splits a list into two lists, such that, when counting elements from 1, the first list has all items that were at odd positions, and the second one has all items that were at even positions. For example, the list a b c d e f g should be split into a c e g and b d f.

def halves[A](l: List[A]): (List[A], List[A]) =
  ???

Halves with foldRight

Rewrite this function using foldRight, using HalvesHelper below for the accumulator type (that is, your function should start with l.foldRight[HalvesHelper[A]]:

enum HalvesHelper[A]:
  case ExpectingEven(evens: List[A], odds: List[A])
  case ExpectingOdd(evens: List[A], odds: List[A])
import HalvesHelper.*

def foldHalvesWithHelper[A](l: List[A]): (List[A], List[A]) =
  ???

New order 🔥

Can you simplify your implementation if you’re allowed to return the pair of lists in any order (that is, if we allow b d f, a c e g instead)?

Interleave

Write a recursive function interleave(lists: (List[A], List[A])) such that interleave(halves(l)) == l.

def interleave[A](ls: (List[A], List[A])): List[A] =
  ???

Unfold the folded 🔥

The interleave function is perfectly fine, but fans of higher-order functions often like to phrase everything in terms of these functions, and since halves can be written using fold, surely interleave can be written using unfold?!

Look up the function List.unfold in the documentation and rewrite interleave using it.

Mutual recursion

Until now, we have only looked at self-recursive types and function: an IntList contains an IntList, and length calls length. But we can also have mutual recursion: trees may contains lists that contain trees, and a tree function may call a list function that calls the original tree function, etc.

Let us look at a concrete example. The following snippets define n-ary trees (a tree with an arbitrary number of branches at each level), along with a type of lists of such trees.

enum Tree[+V]:
  case Leaf(value: V)
  case Node(subtrees: TreeList[V])

enum TreeList[+V]:
  case Nil
  case Cons(t: Tree[V], ts: TreeList[V])

Notice how the two enums refer to each other; that’s mutual recursion!

First, write the following functions, making sure that they call each other:

1. Sums on lists and trees, returning the sum of tree leaves reachable from the argument.

   def listSum(ts: TreeList[Int]): Int =
     ???
   

   midterm-practice/src/main/scala/MutualRecursion.scala

   def treeSum(t: Tree[Int]): Int =
     ???
   

   midterm-practice/src/main/scala/MutualRecursion.scala

2. Max on lists and trees, returning the largest leaf value reachable from the argument. Raise InvalidArgumentError when given a list or tree without leaf values.

   def listMax(ts: TreeList[Int]): Int =
     ???
   

   midterm-practice/src/main/scala/MutualRecursion.scala

   def treeMax(t: Tree[Int]): Int =
     ???
   

   midterm-practice/src/main/scala/MutualRecursion.scala

🔥 Second, write a pair of higher-order functions, treeReduce and listReduce, that capture both cases. That is, both treeSum/listSum and treeMax/listMax should be special cases of treeReduce/listReduce.

Sudoku

Sudoku is a popular logic-based number puzzle that involves filling a 9x9 grid with numbers so that each row, each column, and each of the nine 3x3 subgrids (called “regions” or “boxes”) contain all of the numbers from 1 to 9 without repetition.

The puzzle starts with some cells already filled with numbers, and some to be filled.

By applying the rules of Sudoku and using various solving techniques, the entire grid can be completed without violating any constraints.

Here’s a breakdown of how Sudoku works:

A standard Sudoku puzzle consists of a 9x9 grid, totaling 81 cells. The grid is divided into nine 3x3 regions, each containing nine cells.

At the beginning of the puzzle, some of the cells are pre-filled with numbers, forming a partially completed grid. The number of pre-filled cells can vary, but it’s typically around 17 to 25 cells to ensure uniqueness in the solution.

The rules are:

• Each row must contain all numbers from 1 to 9 without repetition.
• Each column must also contain all numbers from 1 to 9 without repetition.
• Each of the nine 3x3 region must contain all numbers from 1 to 9 without repetition.

The puzzle is considered solved when all cells are filled with numbers, and all three Sudoku rules are satisfied (each row, column, and 3x3 region contains all numbers from 1 to 9).

Our goal in this exercise is to implement an automated Sudoku solver!

Solver architecture

Take a moment to think about the problem. How would you implement a solver? What functions would you create?

While a single, big solveSudoku function might do the trick, when facing a problem, it is easier to reason about it when we split it in reasonably smaller parts. How would you split this problem?

There are many right answers to this question. In the following steps, we provide one answer and ask you to implement the required functions. Feel free to go for your own answer and implement the functions as you envisioned it, as a learning opportunity and a challenge 🔥.

Baby steps

We represent a Sudoku with the following type:

type Sudoku = Vector[Vector[Int]]

Thus, with grid of type Sudoku, grid(0)(1) will give us the value of the first row at the second column. We represent empty cells by the value of 0.

Let’s warm up by implementing a function that checks whether a column contains a certain number.

def columnHas(grid: Sudoku, col: Int, num: Int): Boolean =
  ???

Same for checking whether a row contains a certain number:

def rowHas(grid: Sudoku, row: Int, num: Int): Boolean =
  ???

sbt:project> testOnly -- "*columnHas: *"
sbt:project> testOnly -- "*rowHas: *"

regionHas

After columns and rows, the third unit of a Sudoku grid that must contain all digits from 1 to 9 is a region. Write a similar function as the two above for one of the nine regions of the grid.

def regionHas(grid: Sudoku, row: Int, col: Int, num: Int): Boolean =
  ???

isSafe

With those out of the way, let’s start doing some actual Sudoku logic. Implement the isSafe method that checks whether num can be placed at (row, col) without violating any of the Sudoku rules (refer to them above if necessary).

def isSafe(grid: Sudoku, row: Int, col: Int, num: Int): Boolean =
      ???

updateCell

While solving the sudoku, we want to be able to easily create a copy of the original sudoku with modified cells. To this end, we write a short utility function, whose purpose is to return a new Sudoku instance with the desired cell modified to a certain value.

For example, updateCell(grid, 0, 0, 1) should put a 1 in the top-left cell of the grid.

def updateCell(grid: Sudoku, row: Int, col: Int, num: Int): Sudoku =
      ???

solveFrom

We now have everything we need to write a proper solver. We provide you with a skeleton of a solveFrom function, with missing parts to be filled in.

We approach the problem in the following way:

1. Start at the top-left corner of the grid (with indices (0,0))
2. Check which digits are possible for this cell
3. For each possible digit, create a new grid with the selected digit in the corresponding cell, and solve recursively for the new grid, starting from the next cell (going left-to-right, top-to-bottom)

The solveFrom function should return None if no possible solution is found, and Some(solutionGrid) if a solution is found.

The row and col parameter define where the function should start filling the grid, moving right and then down as described earlier. You can assume all previous cells are already filled.

For example, if row is 1 and col is 2, you can assume the top row is filled with numbers, and the two first cells of the second row as well.

Implement where needed (look for the ??? parts):

def solveFrom(currentGrid: Sudoku, row: Int, col: Int): Option[Sudoku] =
  val N = 9

  if row == N - 1 && col == N then ???
  else if col == N then ???
  else if currentGrid(row)(col) != 0 then ???
  else
    val solutions =
      for
        num <- 1 to N
      yield ???
    if solutions.isEmpty then None else Some(solutions.head)

sudoku

Finally, the solver to rule them all!

Given an incomplete Sudoku grid, fill in the missing cells and return the solution. If no solution is found, None should be returned.

def sudoku(grid: Sudoku): Option[Sudoku] =
      ???

Representing Trees

We often work with tree-like data structures, but it can be hard to debug programs using those since they are difficult to read once printed.

There are ways to improve readability, by defining custom ways of printing those data structures. For example, would you prefer reading this in your terminal?

Tree("hello", Seq(Leaf("world"), Tree("and", Seq(Tree("welcome", Seq(Tree("to", Seq(Leaf("cs214")))))))))

or this?

Tree(
  "hello",
  Seq(
    Leaf("world"),
    Tree("and",
      Seq(Tree(
        "welcome", Seq(Tree(
          "to", Seq(
            Leaf("cs214")
          )
        ))
      ))
    )
  )
)

or this?

hello
  world
  and
    welcome
      to
        cs214

In the two following exercises, we implement better printers for our trees. For the purpose of those exercises, we represent trees in the following way:

case class Tree(val value: String, val children: Seq[Tree])

/** Utility function to define a Tree with no children (a leaf) */
def Leaf(value: String): Tree = Tree(value, Nil)

Note however that the following functions can be adapted to fit other definitions of a Tree type.

Indented trees

Implement the indentTree function that returns a human-readable representation of a tree, where each level of the tree is further indented. Refer to the third example above.

Note the indentation is of two spaces for each level of indentation.

def indentTree(tree: Tree): String =
  ???

sbt:project> testOnly -- "*indentTree*"

Unix trees 🔥

Implement the unixTree function, inspired from the tree UNIX command. For the same example tree as before (refer to the examples above), the function should return:

hello
├── world
└── and
    └── welcome
        └── to
            └── cs214

Some special characters are used (such as ├, └ and ─), you can copy them from the example above and paste them in your code to use them.

The ─ character is not the same as a - (hyphen). Make sure to use ─ instead of a normal hyphen, as our tests expect this special character (and it looks nicer in the terminal, style has its importance).

def unixTree(tree: Tree): String =
  ???

sbt:project> testOnly -- "*unixTree*"

Unix forests

A forest is (surprisignly) composed of multiple trees. We define forests in the following way:

type Forest = Seq[Tree]

Implement unixForest, that prints multiple trees at once by displaying them with a . at the root. For example, this forest:

Seq(
  Tree("hello", Seq(Leaf("world"))),
  Tree("we", Seq(Tree("are", Seq(Leaf("cs214")))))
)

should be printed in the following format:

.
├── hello
│   └── world
└── we
    └── are
        └── cs214

def unixForest(forest: Forest): String =
  ???

© 2023–2025 EPFL. All rights reserved.