Create Better code with Swift Algorithms

The Swift Standard Library includes types and functions to quickly and efficiently solve common code problems, but it doesn't cover everything. Therefore, for more complex tasks, we often need to use Swift algorithms: Apple's on-demand algorithms and data collection package, with the source code tuned for performance and flexibility.

A great time to see at the upcoming Advent of Code 2021 how Swift Algorithms can help you write faster, simpler, and safer code. There is functionality to create unique sequences, divide them, select multiple random elements, compress them, etc. And most of them return new types of sequences, highly optimized, more efficient than reducing everything to a simple array.

Apple also said that Swift Algorithms provides an opportunity to study the problems and solutions of algorithms before translating them into the main standard library: you get better code today, and see what the standard library can become in the future. Isn't it great?

Best of all, adding Swift Algorithms to your Xcode project only takes a few minutes: go to File, select Add Packages, select Apple Swift Packages, then select "swift-algorithms" and click Add Package. Now just add import Algorithms to your code and you're done!

In this article, I'm going to highlight just a few of what Swift Algorithms can already do, focusing on nine specific algorithms that I find most useful. Let's get started...

Sequence chain

If you have two arrays of data and want to iterate over both of them, you can write something like this:

let names1 = ["Jane", "Elizabeth", "Mary", "Kitty"]
let names2 = ["Daphne", "Eloise", "Francesca", "Hyacinth"]

for name in names1 + names2 {
    print(name)
}

This will print all eight names, but in doing so we had to create a new temporary array by concatenating names1and names2together. In this case, this is not a problem, but if your arrays were much larger, it would be quite expensive.

Swift Algorithms has a solution called chain() it creates a new sequence by concatenating two others without doing any further distributions. Here's what it looks like:

for name in chain(names1, names2) {
    print(name)
}

Behind the scenes, chain() keeps references to your two existing sequences and just effectively chains their iterators together so that when one ends, another begins.

This works with other types of sequences too, so we can check exactly if a value is in two different ranges:

let tooLow = 0...20
let tooHigh = 80...100
let outOfBounds = chain(tooLow, tooHigh)

let value = 35
print(outOfBounds.contains(value))

What's more, this works for any type of sequence, so we can link a range and an array:

let reservedSeats = 0...50
let unavailableSeats = [61, 68, 75, 76, 77, 92]
let disallowed = chain(reservedSeats, unavailableSeats)

let requestedSeat = 39
print(disallowed.contains(requestedSeat))

Splitting sequences

Have you ever wanted to split a sequence into equal parts, or perhaps based on certain criteria? Swift Algorithms provides several flavors of split functions that do just that: they are extremely efficient at turning complex, error-prone work into single-line code.

As an example, we could create an array of students with names and grades as letters like this:

struct Student {
    let name: String
    let grade: String
}

let results = [
    Student(name: "Taylor", grade: "A"),
    Student(name: "Sophie", grade: "A"),
    Student(name: "Bella", grade: "B"),
    Student(name: "Rajesh", grade: "C"),
    Student(name: "Tony", grade: "C"),
    Student(name: "Theresa", grade: "D"),
    Student(name: "Boris", grade: "F")
]

Using Swift Algorithms, we could split this array of results based on the scores, and then neatly print them out:

let studentsByGrade = results.chunked(on: \.grade)

for (grade, students) in studentsByGrade {
    print("Grade \(grade)")

    for student in students {
        print("\t\(student.name)")
    }

    print()
}

It will automatically create a new fragment whenever the value being checked changes, so you need to be careful if your value jumps around. In the code above, all student grades are displayed in order - two "A"s together, as well as two "Cs", so this is not a problem. But if we need to split the array by taking student names, we must first sort them to make sure the initial letters are grouped together:

let studentsByName = results.sorted { $0.name < $1.name }.chunked(on: \.name.first!)

for (firstLetter, students) in studentsByName {
    print(firstLetter)

    for student in students {
        print("\t\(student.name)")
    }

    print()
}

There is an alternative fragmentation method that allows us to split the sequence by the number of elements in each fragment. For example, we could pair our students like this:

let pairs = results.chunks(ofCount: 2)

for pair in pairs {
    let names = ListFormatter.localizedString(byJoining: pair.map(\.name))
    print(names)
}

It will print "Taylor and Sophie", "Bella and Rajesh", and "Tony and Teresa", but since "Boris" does not have a match, it will be a one-piece fragment.

Be careful: data fragmentation will return a slice of the array, not an array, because that's more efficient. This means that if you try to read indices like 0 and 1 for our pair, you will run into a problem. So avoid code like this:

let pairs = results.chunks(ofCount: 2)

for pair in pairs {
    if pair.count == 2 {
        print("\(pair[0].name) and \(pair[1].name) are working together")
    } else {
        print("\(pair[0].name) is working alone")
    }
}

If you definitely want an array and not a slice of an array, transform each element before the loop, like this:

let pairs = results.chunks(ofCount: 2).map(Array.init)

Random sampling
One of my favorite features of Swift Algorithms is the randomSample(count:) method and its analog randomStableSample(count:), both of which are improved forms of randomElement() and vice versa select N random non-repeating elements.

Of the two methods, randomSample(count:) is the fastest and works on all sequences. However, it doesn't preserve the order of your elements, so you'll end up with N random non-repeating elements in any order.

For example:

let lotteryBalls = 1...50
let winningNumbers = lotteryBalls.randomSample(count: 7)
print(winningNumbers)

If you specify a number equal to or greater than the number of elements in your sequence, the entire sequence will be returned, again in random order.

An alternative is randomStableSample(count:), which works a little differently. First, it only works with collections, because it needs to know how many elements it is sampling from, and is also slightly slower than randomSample(count:). However, it preserves the order of your elements, which can be useful:

let people = ["Chidi", "Eleanor", "Jason", "Tahani"]
let selected = people.randomStableSample(count: 2)
print(selected)

Walking in sequence

Swift Algorithms has added a new striding(by:) method that moves through a sequence in steps of a certain size, similar to stride(from:through:by), except that it works directly with sequences and is therefore much more efficient.

First, a simple example so that you can see the direct difference between the old and the new. This code prints all odd numbers from 1 to 1000:

let numbers = 1...1000
let oddNumbers = numbers.striding(by: 2)

for oddNumber in oddNumbers {
    print(oddNumber)
}

We can get the same result using stride(from:through:by:) like this:

let oddNumbers = stride(from: numbers.lowerBound, through: numbers.upperBound, by: 2)

The advantage of using striding() is that it works on more complex collections such as strings and array fragments. So we can efficiently extract parts of a string like this:

let inputString = "a1b2c3d4e5"
let letters = inputString.striding(by: 2)

for letter in letters {
    print(letter)
}

Lately I've been using this to handle the decryption of columnar transposition ciphers, where plaintext letters are spaced at fixed intervals in a string.

Finding Unique Items

Swift Algorithms has useful functionality for finding unique elements in a sequence, either based on their natural uniqueness (if your type is Hashable compliant) or using a function you specify.

Let's start with a simple example: you ask a group of people about their lucky number and get different answers. If you want to select each unique response, you can do this:

let allNumbers = [3, 7, 8, 8, 7, 67, 8, 7, 13, 8, 3, 7, 31]
let uniqueNumbers = allNumbers.uniqued().sorted()

for number in uniqueNumbers {
    print("\(number) is a lucky number")
}

If you need something a little more advanced, uniqued(on:) allows you to provide a function that takes one element from a sequence and returns a Hashable of whatever type you want to use in your uniqueness test. Using key paths as functions, we can write code to iterate through an array of cities and select only one city for each country:

struct City {
    let name: String
    let country: String
}

let destinations = [
    City(name: "Hamburg", country: "Germany"),
    City(name: "Kyoto", country: "Japan"),
    City(name: "Osaka", country: "Japan"),
    City(name: "Naples", country: "Italy"),
    City(name: "Florence", country: "Italy"),
]

let selectedCities = destinations.uniqued(on: \.country)

for city in selectedCities {
    print("Visit \(city.name) in \(city.country)")
}

In this situation, uniqued(on:) will always return the first unique element from multiple choices, so the above code will return Hamburg, Kyoto, and Naples.

Removing an optionality

The Swift standard library provides compactMap() to convert an element to some optional result, but then unwrap that optional and remove any nil's. However, it's common to think of compactMap { $0 } as a way of not doing a transformation, but just storing the optional expanded and removing steps, for example:

let numbers = [10, nil, 20, nil, 30]
let safeNumbers = numbers.compactMap { $0 }
print(safeNumbers.count)

This works, but Swift Algorithms offers an improved version called simply compacted():

let numbers = [10, nil, 20, nil, 30]
let safeNumbers = numbers.compacted()
print(safeNumbers.count)

Ok, a little less typing, but much clearer what you mean. The use of $0 in compactMap() has always seemed more of a workaround than intentional.

However, compacted() has another major advantage, which is that it is always lazy, not just when you request it. This way the deployment and removal process will only happen when you actually use it, which makes it much more efficient when you chain operations together.

Nested Loops Improvement

Nested loops allow us to iterate over one sequence every time we iterate over another, and Swift Algorithms provides a product() function that gives us extra control in a situation like this.

For example, if we have two arrays of people and games, we could use product() to iterate over each combination so that each person could play each game:

let people = ["Sophie", "Charlotte", "Maddie", "Sennen"]
let games = ["Mario Kart", "Boomerang Fu"]

let allOptions = product(people, games)

for option in allOptions {
    print("\(option.0) will play \(option.1)")
}

The loop will print: "Sophie will play Mario Kart", "Sophie will play Boomerang Fu", "Charlotte will play Mario Kart", "Charlotte will play Boomerang Fu" and so on.

The first parameter to product() can be any sequence because it loops once, but the second parameter must be a collection because it iterates many times. Of course, you can also provide the same collection for both options if you like, which means we can print out the full set of multiplication tables, like this:

let range = 1...12
let allMultiples = product(range, range)

for pair in allMultiples {
    print("\(pair.0) x \(pair.1) is \(pair.0 * pair.1)")
}

You might think that this is no better than using nested for loops, but the magic is that product() gives us a new collection that we can manipulate further. For example, we want to select 20 random questions from all possible multiplication tables, like this:

let range = 1...12
let questionCount = 20
let allMultiples = product(range, range).shuffled().prefix(questionCount)

for pair in allMultiples {
    print("\(pair.0) x \(pair.1) is \(pair.0 * pair.1)")
}

If you've been following closely, you may have noticed that we can just use randomSample(count:) instead of shuffling and prepending:

let allMultiples = product(range, range).randomSample(count: questionCount)

One slight downside to using product() right now is that it only works with two parameters, meaning that if you need to iterate over multiple collections, you'll have to nest calls to your product(). So we could make the world's most tedious Cluedo/Clue (detective game) game like this:

let suspects = ["Colonel Mustard", "Professor Plum", "Mrs White"]
let locations = ["kitchen", "library", "study", "hall"]
let weapons = ["candlestick", "dagger", "lead pipe", "rope"]
let guesses = product(product(suspects, locations), weapons)

for guess in guesses {
    print("Was it \(guess.0.0) in the \(guess.0.1) with the \(guess.1)?")
}

This is how my 8 year old plays, so not bad for just a few lines of code!

Sliding windows in sequence

Another one of my favorite additions to Swift Algorithms is the ability to read duplicate (overlapping) subsequences of the main sequence, which is great for things like calculating moving averages over a sequence.

If you just want all adjacent pairs, you can use the lazy adjacentPairs() method in sequence, like this:

let numbers = (1...100).adjacentPairs()

for pair in numbers {
    print("Pair: \(pair.0) and \(pair.1)")
}

However, for more advanced tasks, there is also a windows(ofCount:) method that allows you to control how big your sliding window should be. So we could make groups of 5 like this:

let numbers = (1...100).windows(ofCount: 5)

for group in numbers {
    let strings = group.map(String.init)
    print(ListFormatter.localizedString(byJoining: strings))
}

When it runs, it will print "1, 2, 3, 4 and 5", "2, 3, 4, 5 and 6", "3, 4, 5, 6 and 7" and so on. These are all subsequences of the original sequence, so again, this is super efficient.

I recently used the windows(ofCount:) method when decoding a Vigenère cipher because it allowed me to look through a huge string of letters and find all repeated substrings.

Minimum and maximum

Finally, Swift Algorithms offers advanced methods for calculating the minimum and maximum values ​​in a sequence. You can provide your own test if you want, but if your sequence matches Comparable, you get the default test, with a < sign, like so:

let names = ["John", "Paul", "George", "Ringo"]

if let (first, last) = names.minAndMax() {
    print(first)
    print(last)
}

Methods are also provided for reading multiple highest and lowest values ​​at the same time, for example:

let scores = [42, 4, 23, 8, 16, 15]
let threeLowest = scores.min(count: 3)
print(threeLowest)

Under the hood, the results will be sorted and padded at the beginning or end if you try to read more than 10% of the entire sequence, but otherwise it uses a faster algorithm, just doing the right thing automatically, like a lot of things in Swift Algorithms.

And that is not all!

I just touched on just a few of my favorites in Swift Algorithms.

To learn more, I recommend you visit the Swift Algorithms GitHub repository: https://github.com/apple/swift-algorithms. All of this is Swift open source, so you can explore it for yourself and see how Swift Algorithms squeeze so much out of their code.