This article examines two implementations of a logic puzzle written in Swift. The first example uses an imperative programming style, which is the style familiar to most iOS developers. Then we see the same small program written in a functional style, which is facilitated by several Swift language features.

Get the source code at https://github.com/ijoshsmith/break-a-dollar

The logic puzzle

A few days ago my friend mentioned over beers that there are 293 ways to break an American dollar. In other words, if someone hands you a one dollar bill, there are exactly 293 distinct coin combinations you can give them back to make it an equal exchange. The next day I started working out how to write code that counts the number of ways to break any amount of money. This article reviews two implementations of this logic puzzle.

If you are looking for an interesting puzzle to solve, consider putting this article aside until after you’ve written your own solution. I found this puzzle to be a very enjoyable challenge.

American coins

For readers unfamiliar with American coins, here is a quick overview of the coins and their values. Note, a one dollar bill and a one dollar coin are both worth 100 cents.

Algorithm overview

After quite a bit of pondering, making odd hand gestures, and mumbling to myself about nickels and pennies, I eventually figured out a very simple way to solve this puzzle. I knew it would be easy to write a quick and dirty solution, but why settle for less? I wanted to find an elegant solution, so I kept attacking the problem from different angles until I found exactly that.

The key to the algorithm is to recursively subdivide the problem space. Determining how many ways you can break a dollar using all available types of coin is just a specific instance of the more general problem of determining how many ways you can break any amount of money using any subset of coins.

For example, suppose you wanted to find all possible ways to break a quarter. What this really means is finding all combinations of dimes, nickels, and pennies whose sum is 25 cents. If you were to start with a dime, then the problem becomes finding how many ways you can create 15 cents using dimes, nickels, and pennies. If you then add another dime, the problem is then to determine how many ways you can create 5 cents using nickels and pennies (of which there are only two: 1 nickel or 5 pennies).

Click here to read a more detailed review of the algorithm, in a text file included with the Xcode project.

Representing a coin

The algorithm I invented manipulates “coins.” A coin is simply an integer value that represents how many cents it is worth. I wrote an enum to define all available coin types, which also includes a static method that returns all coins in descending value order.

Imperative solution

A significant aspect of the imperative programming style is that variables change state. An imperative program is something like a micro-manager; it tells the computer exactly how to do its job. The following Swift code should look pretty familiar to most iOS developers, because Objective-C is an imperative language.

This code creates an array to hold the coins of smaller value than the current coin of interest. It appends items to the array in a loop, using a familiar loop-with-index construct. Then it uses a variable named ‘sum’ to count the number of ways to break some amount of money using an increasing number of the current coin of interest.

Code like this is the bread and butter of imperative programs. Now let’s venture into the weird world of functional programming to see how this same problem can be solved in a new way.

Functional solution

The functional programming style is heavy on functions and light on mutable state. By not having shared values change there are fewer ways for things to go wrong and less need for synchronization. Having functions as first-class entities in the language makes it possible to support higher-order functions, which allows functions to be composed out of other functions. iOS development has been heading in this direction for years with the introduction of blocks in Objective-C, and the host of APIs that started taking completion handler block arguments.

Here is my functional style solution:

This method’s second parameter is a Slice<Coin> instead of a Coin array because it does not need to copy coins into a new array. A “slice” of an array makes a portion of the array available, without creating a new array. The first line of the method creates a slice of the array, named ‘smallerCoins,’ which contains what functional programmers often call the array’s “tail.” The first item in a list is called the head, and the rest is called the tail. It’s worth noting that slicing an array will not cause an error if the specified range is out of bounds. In this example, when the array only contains one Coin (a Penny) the ‘smallerCoins’ slice is empty.

I created  ‘coin’ and ‘smallerCoins’ on the same line, using tuple syntax, because taking the head and tail of an array is arguably really just one task. Instead of writing separate lines of code to explain how to take the head, and then take the tail, we can instead be more descriptive and express the “take the head and tail” semantic in one fell swoop.

Instead of writing a loop and mutating a local variable to count the number of ways to break an amount of money, we can instead leverage the higher-order function named reduce. If you need a brief overview of what reduce is all about, check out my article about it here. This code reduces a list of integers, such as [0, 1, 2, 3, 4], where each value represents the number of a certain type of coin, such as 3 Quarters. The first argument passed to reduce is zero, which is the initial value of the sum parameter used by the closure/function that contains the reduction logic.

Parting thoughts

I’m excited by Swift’s support for a functional programming style. It can be a challenge to think in different ways, but in this case it’s worth the effort. A couple of years ago I taught myself enough Haskell to be dangerous. I was pleasantly surprised to find myself thinking of new ways to solve problems in my iOS development work because of my exposure to functional thinking.

Get the source code at https://github.com/ijoshsmith/break-a-dollar