Last updated on Saturday, December 20, 2025

Backronym

Points

40 points

Topics

Strings, Recursion

Files to submit

src/main/scala/backronym/Generator.scala

What’s a Backronym?

Given a sequence of words, we can form its acronym by taking the first characters of each of the words in the sequence. For example, the sequence “certainly accelerated rectangles” has the acronym “car”.

On the other hand, a backronym of a word $w$ is a sequence of words, such that $w$ is the acronym of this sequence. For example, “super convincing advertisement message” is a backronym for “scam”(!). On the other hand, “instant ramen” is not a backronym of “in” (but “instant noodle” is!)

In Scala, we represent a Backronym as a List[Word], each represented as a string.

/** A backronym is a sequence of words satisfying the backronym conditions. */
type Backronym = List[Word]

/** A word is a string. */
type Word = String

In addition, you are also provided with a Dictionary, which is a Map[Word, Category]. The Category of a word tells you which kind of word it is: either a Noun, Verb, Adjective or Adverb.

/** A dictionary is a map of words to its corresponding category. */
type Dictionary = Map[Word, Category]

extension (word: Word)(using dictionary: Dictionary)
  /** Returns the category of a word */
  def category = dictionary(word)

  /** Returns whether the word is a **Noun**. */
  def isNoun = word.category == Category.Noun

  /** Returns whether the word is a **Verb**. */
  def isVerb = word.category == Category.Verb

  /** Returns whether the word is a **Adjective**. */
  def isAdjective = word.category == Category.Adjective

  /** Returns whether the word is a **Adverb**. */
  def isAdverb = word.category == Category.Adverb

Good Backronyms

In reality, we want to use backronyms that convey some meaning. Therefore, in this mini-lab, we are interested in finding good backronyms.

A good backronym has to satisfy the following conditions:

1. There are no verbs in a backronym, and the final word in a good backronym must be a noun.

2. They have to satisfy a word ordering. Specificially,

   • Each non-final adjective or noun must come directly before a noun, and
   • Each non-final adverb must come directly before an adjective or another adverb.

💪 Task: Implement canComeBefore (6 points)

Your task is to implement the canComeBefore function, that takes two words a and b alongside a Dictionary, and returns whether a can come before b in a good backronym.

extension (a: Word)(using dict: Dictionary)
  /** Returns whether `a` can come directly before `b` in a good backronym. */
  def canComeBefore(b: Word) =
    require(dict.contains(a) && dict.contains(b))
    ???

sbt:exercises> testOnly -- *canComeBefore*

💪 Task: Implement a good backronym generator! (34 points)

Now that the rules are properly written down as Scala code, let’s generate good backronyms!

Your task is to implement a backronym generator: given an acronym, search the Dictionary and come up with all good backronyms satisfying the above conditions.

You will need to implement goodBackronyms, which takes an acronym (as a non-empty String) and a Dictionary and returns a Set of possible good backronyms:

/** Create good backronyms from the given acronym. */
def goodBackronyms(acronym: String)(using dict: Dictionary): Set[Backronym] =
  require(!acronym.isEmpty(), "acronym must be non-empty")
  ???

given Dictionary = Map(
  "advertisement" -> Noun,
  "announcement" -> Noun,
  "convincing" -> Adjective,
  "message" -> Noun,
  "super" -> Adverb,
  "soup" -> Noun,
  "silent" -> Adjective
)

sbt:backronym> testOnly -- *example*
sbt:backronym> testOnly -- *small*
sbt:backronym> testOnly -- *larger*
sbt:backronym> testOnly -- *largest*
sbt:backronym> testOnly -- *tricky*

© 2023–2025 EPFL. All rights reserved.