Can you solve this code challenge in Swift?

Well, can you?

Paul Hudson December 13th 2017 @twostraws

Earlier this year I had the privilege of volunteering at my daughters’ school, and it was my job to introduce the year 5 and 6 girls (ages 9+) to Python. I’m returning again next year, except this time we’ll be looking at the UK Bebras Computational Thinking Challenge and its related competition the TCS Oxford Computing Challenge (OCC).

I was curious what the OCC looked like, so I tried out the 2017 test. One of the questions struck me as particularly interesting for Swift developers, so I tweeted it out. It looks like I wasn’t alone in finding it interesting, because many of you replied with possible answers, and I think learned something interesting along the way!

So, in the interests of pedagogy, let’s take a look at the problem together, then see how it might be solved – and why it’s interesting in Swift.

First, the problem:

Georgina loves making up weird sequences. Here is her latest: “1 2 4 8 10 20 22 44 46 92 94 188 190 380...” Write a program (using any programming language) that finds the sum of the first 150 numbers in Georgina's series.

In our case, the “any programming language” is Swift, and at this point I encourage you to stop reading and try the problem for yourself – open a playground and write some code.

Seriously, go and try it now.

I’m just writing this so you don’t read any further by accident.

What’s blue and smells like red paint?

Blue paint.

OK, let’s take a look at this problem in Swift. There are three parts to the problem, and several folks missed one of them:

Figuring out that sequence doubles and adds two.
Writing code to follow that sequence 150 times, avoiding off-by-one errors.
Summing the numbers in the sequence.

Once you have that, the naïve solution looks like this:

var total = 0
var current = 1

for i in 0 ..< 150 {
    total += current

    if i % 2 == 0 {
        current *= 2
    } else {
        current += 2
    }
}

print(total)

That will compile cleanly, but will not run – it will crash, because the number it generates is too big for Swift’s integers. Swift won’t tell you that’s why it crashed, of course, so instead you’ll get error: Execution was interrupted, reason: EXC_BAD_INSTRUCTION (code=EXC_I386_INVOP, subcode=0x0) – lovely.

You might then have tried using a larger integer type, like this:

var total: UInt64 = 0
var current: UInt64 = 1

However, even unsigned 64-bit integers are too small to hold the solution’s number. Keep in mind that the sequence is 150 items, of which half are produced through doubling, so you have 75 doubles. The largest number an unsigned 64-bit integer can hold is 18,446,744,073,709,551,615 – big, but still over 10,000 times too small for our needs.

Based on the replies I received, many people tried switching to a Double instead, which yields a result like “3.40010386766614e+23”. That looks like it might be correct, but floating-point mathematics is always a tricky thing. Annoyingly, Swift prints instances of Double using scientific notation by default, but we can print the full number using a string formatter, like this:

let stringTotal = String(format: "%.0f", total)
print(stringTotal)

With that you’ll see the output as 340010386766614455386112, which is clearly wrong. I say “clearly” because of the sequence: “1 2 4 8 10 20 22 44 46 92 94 188 190 380” – all numbers are even except the first one, so the sum of all numbers must be odd. As the Double solution ends in “112” it is clearly not correct, and floating-point mathematics has claimed another victim.

Hopefully now you can see why the problem is an interesting one: Swift’s native integers can’t handle numbers of this magnitude, and its floating-point types introduce small (but important) errors.

However, there is one type available to us that can solve the problem, provided by Foundation: Decimal. This is designed to hold extremely large numbers – even large enough to be used to monitor the average Swift compile time – and it’s perfect for this problem.

To try it out, change both total and current to use Decimal instead, like this:

var total: Decimal = 0
var current: Decimal = 1

When that runs, you’ll see the correct answer: 340010386766614455385653.

The reason this challenge is tricksy in Swift is because it specifically asks for item 150 in the sequence. As Nick Lockwood pointed out the precision part of the problem would have disappeared if they had gone for something like 50 instead, because even Swift’s regular Int type can handle 25 doubles.

Other languages (Java, VB, Ruby, SmallTalk, Lisp, and so on) have built-in support for big numbers, and some like Python even support them transparently. As a result, the Python script is exactly what you would expect:

total = 0
current = 1

for i in range(0, 150):
    total += current

    if i % 2 == 0:
        current *= 2
    else:
        current += 2

print(total)

Perhaps Swift 5.0 will bring native big integers to Swift, but until then I hope you learned something new: UInt64 isn’t as big as you think, Decimal is a great type to keep in your toolbox, and floating-point mathematics continues to be a computing science gotcha.

PS: In case you were curious, the youngest kids sitting the test in which this question appeared were 10 years old. I think this means we have a bright computing future ahead of us!