Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

Number Letter Counts

If the numbers \(1\) to \(5\) are written out in words: one, two, three, four, five, then there are \(3 + 3 + 5 + 4 + 4 = 19\) letters used in total.

If all the numbers from \(1\) to \(1000\) (one thousand) inclusive were written out in words, how many letters would be used?

Note: Do not count spaces or hyphens. For example, \(342\) (three hundred and forty-two) contains \(23\) letters and \(115\) (one hundred and fifteen) contains \(20\) letters. The use of “and” when writing out numbers is in compliance with British usage.

Solution

Well, that’s a lot of numbers to cover. Let’s start with something easy, changing one-digit numbers to strings:

private def writeDigit(i: Int): String = i match {
  case 0 => "zero"
  case 1 => "one"
  case 2 => "two"
  case 3 => "three"
  case 4 => "four"
  case 5 => "five"
  case 6 => "six"
  case 7 => "seven"
  case 8 => "eight"
  case 9 => "nine"
  case _ => throw IllegalArgumentException(s"Received unexpected input: $i")
}

Plenty of code, but it’s very straightforward. We could make it more concise by using an Array, but I like this very explicit pattern match. What’s next? We can write numbers from 10 to 19:

private def writeTenToNineteen(i: Int): String = i match {
  case 10 => "ten"
  case 11 => "eleven"
  case 12 => "twelve"
  case 13 => "thirteen"
  case 14 => "fourteen"
  case 15 => "fifteen"
  case 16 => "sixteen"
  case 17 => "seventeen"
  case 18 => "eighteen"
  case 19 => "nineteen"
  case _  => throw IllegalArgumentException(s"Received unexpected input: $i")
}

There’s not much to simplify there yet, because too many words are irregular. 17 is regular, it consists of “seven” + “teen”, so it might seem appealing to pick the last digit to form a prefix, and add “teen” as a suffix, but due to the fact that it’s not very regular, we’d end up with such oddities as 11 represented as “oneteen” :)

Higher numbers, fortunately, are much more regular. For all the numbers between 20 and 99, we can separate the last digit from those numbers, convert it to a string using the previously defined writeDigit function, and append it to a string representation of the two-digit number like 20 or 30. Finally, we can reuse some of our previous functions.

If the number is divisible by 10, then we don’t need the output of writeDigit, or we’ll end up with numbers like 20 being written out as “twenty-zero”.

private def writeTens(i: Int): String = {
  val remainder = i % 10
  val maybeRemainder = if (remainder != 0) Some(writeInt(remainder)) else None
  val tens = i - remainder match {
    case 20 => "twenty"
    case 30 => "thirty"
    case 40 => "forty"
    case 50 => "fifty"
    case 60 => "sixty"
    case 70 => "seventy"
    case 80 => "eighty"
    case 90 => "ninety"
    case _  => throw IllegalArgumentException(s"Received unexpected input: $i")
  }
  
  maybeRemainder match {
    case Some(digits) => s"$tens-$digits"
    case None         => tens
  }
}

What’s writeInt in the code above? It’s a function that writes any int. That’s where we put the guards not to pass the int into a function that wouldn’t be able to process it. Right now it looks like that:

private def writeInt(i: Int): String = i match {
  case i if i >= 0 && i < 10     => writeDigit(i)
  case i if i >= 10 && i < 20    => writeTenToNineteen(i)
  case i if i >= 20 && i < 100   => writeTens(i)
}

The last part are the hundreds. They’re the most regular, we’ll be able to reuse almost everything we’ve written so far. A number like 123 consists of:

  • Written digit (1), using the writeDigit function
  • “hundred” word
  • Written last two digits, using the writeInt function, since we don’t know if we should use writeDigit,writeTenToNineteen or writeTens

And here’s the code for hundreds:

private def writeHundreds(i: Int): String = {
  val remainder = i % 100
  val maybeRemainder = if (remainder != 0) Some(writeInt(remainder)) else None
  val hundred = s"${writeDigit((i - remainder) / 100)} hundred"

  maybeRemainder match {
    case Some(tens) => s"$hundred and $tens"
    case None       => hundred
  }
}

We also need to handle 1000 as “one thousand” and we’re almost done. Here’s the complete solution that convers numbers to strings and counts the letters:

object Euler017 extends EulerApp {
  override def execute(): Any = (1 to 1000)
    .map(writeInt)
    .map(_.count(_.isLetter))
    .sum

  private def writeInt(i: Int): String = i match {
    case i if i >= 0 && i < 10     => writeDigit(i)
    case i if i >= 10 && i < 20    => writeTenToNineteen(i)
    case i if i >= 20 && i < 100   => writeTens(i)
    case i if i >= 100 && i < 1000 => writeHundreds(i)
    case 1000                      => "one thousand"
  }

  private def writeDigit(i: Int): String = i match {
    case 0 => "zero"
    case 1 => "one"
    case 2 => "two"
    case 3 => "three"
    case 4 => "four"
    case 5 => "five"
    case 6 => "six"
    case 7 => "seven"
    case 8 => "eight"
    case 9 => "nine"
    case _ => throw IllegalArgumentException(s"Received unexpected input: $i")
  }

  private def writeTenToNineteen(i: Int): String = i match {
    case 10 => "ten"
    case 11 => "eleven"
    case 12 => "twelve"
    case 13 => "thirteen"
    case 14 => "fourteen"
    case 15 => "fifteen"
    case 16 => "sixteen"
    case 17 => "seventeen"
    case 18 => "eighteen"
    case 19 => "nineteen"
    case _  => throw IllegalArgumentException(s"Received unexpected input: $i")
  }

  private def writeTens(i: Int): String = {
    val remainder = i % 10
    val maybeRemainder = if (remainder != 0) Some(writeInt(remainder)) else None
    val tens = i - remainder match {
      case 20 => "twenty"
      case 30 => "thirty"
      case 40 => "forty"
      case 50 => "fifty"
      case 60 => "sixty"
      case 70 => "seventy"
      case 80 => "eighty"
      case 90 => "ninety"
      case _  => throw IllegalArgumentException(s"Received unexpected input: $i")
    }

    maybeRemainder match {
      case Some(digits) => s"$tens-$digits"
      case None         => tens
    }
  }

  private def writeHundreds(i: Int): String = {
    val remainder = i % 100
    val maybeRemainder = if (remainder != 0) Some(writeInt(remainder)) else None
    val hundred = s"${writeDigit((i - remainder) / 100)} hundred"

    maybeRemainder match {
      case Some(tens) => s"$hundred and $tens"
      case None       => hundred
    }
  }
}

Epilogue

Was it necessary to convert everything to a string? Not at all. We were asked to count the letters only, so if we wanted to be more efficient, the pattern matching could look like that:

case 8 => 5

There are \(5\) letters in the word “eight”. There’s one problem with that approach. Debugging it would be a nightmare. It would be not reusable for anything. The program runs fast already, after all.

There’s one improvement that we could make, though. Those cases aren’t good:

case _ => throw IllegalArgumentException(s"Received unexpected input: $i")

Due to them, our functions aren’t pure. They have a very nasty side effect. Even though they all accept Int parameter, they can only operate on a subset of numbers. That’s a risky, error-prone design. A much better solution would use refined types. For example, a separate Digit type that could be only created from numbers 0 to 9. Such types can be also checked by compiler, so a Digit(10) throws a compilation error rather than a runtime exception.