Last updated on Wednesday, January 08, 2025

Codebreaking puzzles

Points: 100 pts
Topics: Specifications, Higher-order functions, Modularity
Files to submit: src/main/scala/codebreaking/Common.scala; src/main/scala/codebreaking/Wordle.scala; src/main/scala/codebreaking/BullsAndCows.scala; src/main/scala/codebreaking/MasterMind.scala

The aim of this exercise is to build solvers for multiple closely-related code-breaking and word-guessing games. In these games, one player, the secret-holder, picks a sequence of $n$ digits or letters, and the other, the code-breaker, tries to guess the sequence.

On every turn, the code-breaker makes a guess, and the secret holder gives it a score, revealing partial information about the secret. Each game of this form is represented as an instance of the Puzzle abstract class:

abstract class Puzzle[Word, Score]:
  def score(guess: Word, secret: Word): Score
  def guess(previousGuesses: List[ScoredGuess[Word, Score]]): GuessResult[Word]

src/main/scala/codebreaking/Common.scala

We will study three games:

Distinct Wordle. In this version the secrets are dictionary words without repeated letters, and the score indicates which letters are “Green” (found in the secret at the same position as in the guess), “Yellow” (found in the secret at a different position), or “Grey” (not found in the secret). Guesses are not allowed to have repeated letters.

For example, guessing the word dries if the secret is fruit would yield a score equal to Grey, Green, Yellow, Grey, Grey: the Green indicates that r is found in the secret at this exact position, and the yellow that i is found in the secret but at a different position.
```
object Wordle:
  type Word = String

  enum Result:
    case Grey, Yellow, Green
  type Score = List[Result]

  val allLetters = ('a' to 'z').toSet

  class Game(wordLength: Int, wordList: Set[Word]) extends Puzzle[Word, Score]:
```
src/main/scala/codebreaking/Wordle.scala
Bulls and cows. In this version the secrets are numbers without repeated digits, such as 12534 or 3476, and the score has two components: “bulls”, the number of digits found at the same positions in the guess and in the secret, and “cows”, the number of digits found in the guess that appear at a different position in the secret. Guesses are allowed to have repeated digits.

For example, guessing 527233 when the secret is 527346 would score “3 bulls, 1 cow”: one bull for the correctly placed 5, one bull for the correctly placed 2, one bull for the correctly placed 7, and one cow for one misplaced 3.
```
object BullsAndCows:
  type Word = List[Int]
  case class Score(bulls: Int, cows: Int)

  val allDigits = List(0, 1, 2, 3, 4, 5, 6, 7, 8, 9)

  class Game(wordLength: Int) extends Puzzle[Word, Score]:
```
src/main/scala/codebreaking/BullsAndCows.scala
Mastermind. In this version the secrets are color patterns, such as Red Blue Green Red, and the score has two parts: “red keys”, the number of positions where both sequences agree, and “white keys”, the number of positions in the guess whose color appears at a different position in the secret, with each position of the secret counted at most once. Both guesses and secrets are allowed to have repeated colors.

For example, guessing Carmine Purple Fuchsia Pink Purple when the secret Carmine Pink Pink Purple Purple would give a score of “2 red keys, 2 white keys”: one red key for Carmine, one white key for the first Purple, one white key for Pink, and one red key for the last Purple).
```
object MasterMind:
  enum Color:
    case Red, Purple, Brown, Blue, White, Pink, Green, Carmine, Fuchsia

  type Word = List[Color]
  case class Score(redKeys: Int, whiteKeys: Int)
  val allColors: List[Color] = Color.values.toList

  class Game(wordLength: Int) extends Puzzle[Word, Score]:
```
src/main/scala/codebreaking/MasterMind.scala

Part 1: Scoring functions (60 pts)

Your first task is to write a scoring function for each of these games. The scoring function takes a guess and a secret, and returns a score:

def score(guess: Word, secret: Word): Score =
  require(guess.length == wordLength, f"Guess length must be $wordLength.")
  require(secret.length == wordLength, f"Secret length must be $wordLength.")
  require(guess.distinct == guess, f"Guess $guess cannot have duplicates.")
  require(secret.distinct == secret, f"Secret $secret cannot have duplicates.")
  ???

src/main/scala/codebreaking/Wordle.scala

def score(guess: Word, secret: Word): Score =
  require(guess.length == wordLength, f"Guess must have length $wordLength.")
  require(secret.length == wordLength, f"Secret must have length $wordLength.")
  require(secret.distinct == secret, f"Secret $secret cannot have duplicates.")
  ???

src/main/scala/codebreaking/BullsAndCows.scala

def score(guess: Word, secret: Word): Score =
  require(guess.length == wordLength, f"Guess must have length $wordLength.")
  require(secret.length == wordLength, f"Secret must have length $wordLength.")
  ???

src/main/scala/codebreaking/MasterMind.scala

You can run specific tests using the testOnly command. As the tests contain spaces and special characters, make sure to quote your patterns appropriately. For example:

sbt:codebreaking> testOnly -- "*BullsAndCows: *"
sbt:codebreaking> testOnly -- "*Wordle.score(\\\"purchasing\\\", \\\"bracketing\\\")*"

Part 2: Guessing functions (40 pts)

A guessing function is a function which takes a sequence of previous guesses and their scores and either proposes a new guess or reports that the puzzle is solved and gives its solution.

With a guessing function, solving a game is simple. We start with an empty list of guesses, then repeatedly call the guessing function. If it reports that the puzzle is solved, then we are done. Otherwise we score the guess that it returns and call the guessing function again with this additional scored guess. Our testing code includes an implementation of this algorithm.

Example

Imagine that we are given the following guesses:

List(1, 2, 3): 1 bull, 1 cow
List(5, 3, 2): 2 bulls, 0 cows

At this point, only two possible solutions remain: List(7, 2, 1) and List(3, 2, 5).

The guessing function for Bulls and Cows could guess List(7, 2, 1). The solver would then submit this guess to the secret holder, who would return a score. Assume that score is “1 bull, 0 cows”: the solver would then call the guessing function again with the additional guess and its score:

List(1, 2, 3): 1 bull, 1 cow
List(5, 3, 2): 2 bulls, 0 cows
List(7, 2, 1): 1 bull, 0 cows # Added

With this additional information, the guessing function would then return List(3, 2, 5) as the solution (the one possibility left).

Of course, the guessing function could pick a different combination (any sequence of three digits would be valid):

If it had picked List(1, 3, 7), then the secret holder would have reported “0 bulls, 1 cow”, and the guessing function could have again solved the game on the next round.
If it had picked List(0, 0, 8), then the secret holder would have reported “0 bulls, 0 cows”; this time the guessing function could not have completed the game on the next round, since more than one possible secret would remain.

Your second task is to implement guessing functions for our three games:

def guess(previousGuesses: List[ScoredGuess[Word, Score]]): GuessResult[Word] =
  require(
    previousGuesses.forall(_._1.length == wordLength),
    f"Previous guesses must have length $wordLength."
  )
  require(
    previousGuesses.map(_._1).forall(wordList.contains),
    "Previous guesses must all be valid words."
  )
  ???

src/main/scala/codebreaking/Wordle.scala

def guess(previousGuesses: List[ScoredGuess[Word, Score]]): GuessResult[Word] =
  require(
    previousGuesses.forall(_._1.length == wordLength),
    f"Previous guesses must have length $wordLength"
  )
  ???

src/main/scala/codebreaking/BullsAndCows.scala

def guess(previousGuesses: List[ScoredGuess[Word, Score]]): GuessResult[Word] =
  require(
    previousGuesses.forall(_._1.length == wordLength),
    f"Previous guesses must have length $wordLength"
  )
  ???

src/main/scala/codebreaking/MasterMind.scala

In each case, you receive a list of previous guesses and their scores, and you must return one of three results:

enum GuessResult[+Word]:
  case StillGuessing(nextGuess: Word)
  case FoundSolution(solution: Word)
  case NoSolution extends GuessResult[Nothing]

src/main/scala/codebreaking/Common.scala

StillGuessing(nextGuess) indicates that there are more than one possible solutions left, and that your program picked nextGuess.
FoundSolution(secret) indicates that only one possible secret remains, and your code has found it.
NoSolution indicates that no possible secret is compatible with all the guesses.

Each complete game (repeated guesses until the secret is found) may not take more than 10 seconds. Since our CI machine may not run as fast as the VDI machines, we recommend staying well below that limit to be safe.
The tests are increasingly difficult to pass: the last tests require an efficient guessing strategy. They are hard to pass and worth very few points: do not waste time on them!
Your code must be deterministic. If you use Random, initialize it with a seed: using val rng = scala.util.Random(0) will make sure that running your code twice produces the same results.