Competitive Programming With Swift

Competitive Programming With Swift

Competitive programming is a great way to master a specific programming language. Even if you're not interested in competing in world events like the Facebook Hacker Cup, tackling difficult algorithm problems using nothing but the language's bread and butter will expose you to aspects/shortcuts of the language you would otherwise never see, such as how efficient certain methods/operations are and how to code better alternatives. This is a cool hobby to have, and as a bonus you'll even be indirectly preparing yourself to the feared Big 4 interviews where you have to solve algorithm problems in a whiteboard!

Even though in a real competition coding in Swift would be a big disavantage (as it's slightly slow compared to other languages and has few native data structures), lots of popular online platforms like LeetCode, HackerRank and Codefights support Swift and they are a great way to make yourself a better iOS developer, specially since competitive problems will only accept very fast algorithms as possible solutions. If you've never did this before, I highly recommend giving it a shot.

In this article, I'll give a brief tutorial on how to use Swift to read input data and some tips for tackling competitive problems in Swift.

Reading Standard Input with Swift

In competitive programming, the problem's input is usually fed into a command line application which makes some sense of it and prints the desired result.

Platforms like LeetCode and CodeFights will automatically process input data for you and expose an empty Swift method that should return the problem's solution, but other platforms like HackerRank will sometimes have you manually read, parse the standard input and then print the result. Thankfully, that's not as complex as it sounds.

To simulate a competitive programming environment, create a Command Line Tool project in Xcode:

Be aware that a Command Line Tool is not a Cocoa app, so you'll have no access to things like UIKit! The core frameworks like Foundation are all you have here.

In main.swift, type and run the following code:

let line = readLine()
print("Got something! \(line)")

At this point, the program will be frozen. readLine() is a Standard Library method that synchronously reads the standard input and returns a String? once a full line is retrieved or nil if EOF is reached.

If you type something in Xcode's console, the program's execution will continue and print what you wrote:

However, a competitive programming problem will likely have several hundred lines of input. You can use a while loop to make your code run until the input ends:

while let line = readLine() {
    print("Got something! \(line)")
}

That is all you need to know to get started. From here forward, your skill with pure Swift is the only variable.

Here's an example problem if you've never done this before:

Example Problem

Given an array of integers, find the sum of its elements.

Input Format

The first line contains an integer, denoting the size of the array.

The second line contains n space-separated integers representing the array's elements.

Output Format

Print the sum of the array's elements as a single integer.

Sample Input

6
1 2 3 4 10 11

Sample Output

31

Solution

Every problem has multiple possible solutions. For this one, we can harness the power of reduce:

import Foundation

_ = readLine() //Read and drop the array size line.
//Knowing the size of the array beforehand is needed for some languages
//But as readLine() returns the whole line, Swift doesn't need it!

let array = readLine()!.components(separatedBy: " ").map { Int($0)! }
let result = array.reduce(0, +)
print(result)

Swift tips for Competitive Programming

The beauty of competitive programming is that merely solving the problem is not enough - your program must solve it as fast as possible.

There's a lot to talk about runtime complexity, but this section is supposed to cover Swift tips that are useful when things need to be quick.

If you have a tip that is not here, feel free to contact me and I'll add it and credit you!

Use Overflow Operators

Swift naturally protects you from numbers overflowing at the cost of performance. This can cost you some valuable nano-seconds, and some problems might even want you to overflow numbers. Luckily, Swift has special arithmetic operators that ignore overflow checks, making them faster than the regular operators:

1 &+ 1
1 &- 1
1 &* 1
1 &>> 1

Printing is slow

The print(_:) method is very slow, and it can be particularly painful when printing things like Arrays. You can gain some performance if you print everything at once.

let array = [String](repeating: "A", count: 1000)

for a in array {
    print(separated, terminator: " ") // slow
}

/////

let separated = array.joined(separator: " ")
print(separated) // a lot quicker, even though we're processing the array beforehand

Allocate Array capacities in advance

Swift's Arrays have dynamic sizes, meaning that the language automatically allocates more memory space for it as it increases in size. Even if this is quite fast, you can make it even faster if you know the array size in advance by using the Array.reserveCapacity(_:) method. This is useful if you have a problem where the solution is an Array with a specific size.

let arraySize = Int(readLine()!)!
var array = [Int]()
array.reserveCapacity(arraySize) //Runtime is slightly slower without manually setting the array's capacity.
for i in 0..<arraySize {
    array.append(solve(for: i))
}

Alternatively, you can use the repeating:count: initializer when you need a pre-filled array:

let fiveZs = Array(repeating: "Z", count: 5)
print(fiveZs)
// Prints "["Z", "Z", "Z", "Z", "Z"]"

Abuse Implicitly Unwrapped Optionals

While the dreaded ! should be avoided in real applications, safety is not a concern in competitive programming. Since inputs are guaranteed to always be the same, you can completely skip the overhead of unwrapping optionals.

Use inout - Dmitry Volevodz

Using inout arguments can be really useful when passing data around recursive functions, and I was able to confirm that inout arguments are even faster to create than regular ones when passing around value types with inner reference types.

Subtract Dates to measure performance - Rodrigo Carvalho

The following snippet will measure how long it takes to run something:

func measure(function: () -> Void) {
    let start = Date()
    function()
    let end = Date()
    print("Elapsed time: \(end.timeIntervalSince(start))")
}

measure {
    timeIntensiveTask()
}

This can be useful when you have multiple approaches and is not sure which one is faster. Be sure to run this with optimizations turned on to properly measure things, as most of the Swift compiler's tricks require it.

Swift Algorithm Club

Most competitive programming problems will rely on a specific data structure, and since Swift unfortunately has no native support for most of them, that means you'll have to code them yourself.

Fortunately, the swift-algorithm-club repo has Swift implementations of pretty much everything, making it a great place to learn how to code popular data structures in Swift.

What else?

Regardless if you are studying for an interview, wanting to compete at world events or just trying to get better at iOS development, solving competitive programming problems is a very interesting way of increasing your Swift skills. I've personally benefited a lot from it, and would love to know what you think of it.

Follow me on my Twitter - @rockthebruno, and let me know of any suggestions and corrections you want to share.

References and Good reads

Big O Notation
Performant Arrays In Swift
Apple Docs: readLine()

Contact Info

Bruno Rocha
Senior iOS Developer
bruno@swiftrocks.com

Newsletter

Click here to subscribe to my newsletter and receive new posts via e-mail.

RSS / Social