Project Euler, Challenge #17 in Swift

Question

Number letter counts, Problem 17:

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.

Result:

\$21124\$ (Correct according to Project Euler)

Time: \$0.0172510147094727\$ seconds

Since this hasn't been solved in Swift, I'd like a code review of this challenge which talks about the efficiency of the code, and how to correct bad practices or violations of any concepts. Here is the code:

import Foundation

let unitNames:[String] = [
    "", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine", "ten", "eleven", "twelve", "thirteen", "fourteen", "fifteen", "sixteen", "seventeen", "eighteen", "nineteen"
]

let tensNames:[String] = [
    "", "ten", "twenty", "thirty", "forty", "fifty", "sixty", "seventy", "eighty", "ninety", "hundred"
]

func convertIntegerToWords(number:Int) -> String {
    var words:String = ""

    if number >= 0 && number <= 19 {

        words = words + unitNames[number]

    } else if number >= 20 && number <= 99  {

        var digits = number.array

        words = words + tensNames[digits[0]]
        words = words + unitNames[digits[1]]

    } else if number >= 100 && number <= 999 {

        var digits = number.array

        if number % 100 == 0 {
            words = words + unitNames[digits[0]] + "hundred";
        } else {
            words = words + unitNames[digits[0]] + "hundredand";
            var newNumber = number - digits[0] * 100;
            words = words + convertIntegerToWords(newNumber)
        }

    } else if number == 1000 {

        words = words + "onethousand"

    }

    return words
}

extension Int {
    var array: [Int] {
        return Array(description).map{String($0).toInt() ?? 0}
    }
}

func EulerSeventeen() -> Int {

    var length:Int = 0

    for iterator in 1...1000 {
        length = length + count(convertIntegerToWords(iterator))
    }
    let end = NSDate();

    return length
}

let start = NSDate();
var result = EulerSeventeen()
let end = NSDate();

let timeInterval: Double = end.timeIntervalSinceDate(start);

println("Result: \(result) found in \(timeInterval) seconds")

Answer 1

I find it confusing that you first assign an empty string and then append to it. I suggest returning directly, like

// var words:String = "" Delete this

if number >= 0 && number <= 19 {

    return unitNames[number]

And a return for each branch. When I see a return I can rest my mind that the function has ended, if I see a string appending, maybe it will grow more before being returned.

---

The line:

 let end = NSDate();

Inside Euler17 should be deleted as it is useless.

---

Euler17 can be simplified a lot.

return (1...1000).map{count(convertIntegerToWords($0)}.sum

Use functional programming where it is worth it.

---

 var digits = number.array

Should be at the start of the function as you repeat it in almost every branch.

---

About @jimbo 's comment:

For speed, I'd put the >= 100 && number <= 999 as the first > if, because 899 times out of 999, that'll be the one that's hit, > > and you don't want that being the last one.

Do not do it. Readibility will decrease and the performance impact will likely be minimal (benchmark needed).

Answer 2

Just a few thoughts

• instead of newNumber = number - digits[0] * 100 I would use the modulo operator % as you did a few lines above

• you could increase performance by using dynamic programming. In the section for numbers >= 100 - where you look for newnumber - you have already calculated this and would just need to look it up.

• as you have already written out the numbers one to twenty I don't see why not fill the results with this (saves you an if).

• technically you are only interested in the number of characters so you could just instead of strings sum up the numbers. Concatenation of strings is much more expensive than addition. Though that will make things hard to read.

Also about @jimbo 's comment: It's not true! Because inside the section you call the function again with a number < 100. So in total you call the function 1000 + 890 times - and only 899 will be with numbers in this branch.

about dynamic programming

On wikipedia is a good definition. Basically it is good for cases like this where you need to repeatedly call a function with the same values. In your case you call eg. convertIntegerToWords(21) for the number 21 - but also in the function for 121, 221, 321, ... So instead of calculating the function 10 times you could store the result from the first time in a list like you do for unitNames and quickly access it for the other 9 times.

The function would simply look this im pseudocode:

convertIntegerToWords(i)
  if length(listOfWords) >= i and listOfWords[i] is not empty
    return (listOfWords[i])
  otherwise
    figure out the required words
    and store them in listOfWords[i]

The nice thing is if you initialize the listOfWords with the spelled out words for the numbers 1 to 20 - they will no longer be a special case! Making the whole function simpler.

Also as you check the numbers in order the case that listOfWords[i] is empty will never occur.