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.
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.
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.
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.
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.
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
If you’re interesting in seeing an Elixir implementation of this puzzle, click here.
Thanks for sharing, Josh! I sat down for 30 minutes with pen and paper just now to solve this cold (in part to evaluate it as an interview question). I agree it’s a fun problem. 🙂 My initial C# solution is similar in nature to your imperative solution – with fewer allocations, though perhaps more overhead.
At least in C#, I find myself rewriting the nice and functional parts to imperative approach because of the debugging. Functional parts are nice and short but if they do not work the only way to debug them is by making code changes, introducing intermediate variables etc.
Maybe one day will debuggers enable easy debugging of functional code.
I have also made a small exploration of FP in Swift, leaving Cocoa/ObjC behind. Enums shine in Swift!
Pingback: Dew Drop – December 1, 2014 (#1905) | Morning Dew
Interestingly this is one of the problems in the Coursera Scala course. Looking back on my code, I’ve found the function:
def countChange(money: Int, coins: List[Int]): Int =
if (coins.isEmpty || money < 0)
else if (money == 0)
countChange(money – coins.head, coins) +
Very concise, although i can't recall how it works now :-S
And as a gist to preserver formatting:
This is one of the SICP exercises, and the resolution chooses one type of coin, any type will do, no order is assumed, then it partitions the solutions set into 2 complementary disjoint subsets: Those using that chosen coin, those that don’t, and cardinal wise, the answer will be the sum of the cardinal of each subset. Then a specific reasoning is used for each subset:
– Not using that coin is like resolving the same problem with the same “money” target but with with a smaller choice of coins.
– Using it, means that it’s used at least once in each solution. So it can be removed from each of them, providing a solution to the same problem with a smaller “money” target, using the same choice of coins.
In Swift, arrays could be used instead of lists, but it’s easier to work with last entry of the array. Array.last is an optional.
Thanks Jean-Pierre. That’s a totally different way of thinking about the problem!
Pingback: Logic Puzzle with Swift Using Imperative and Functional Programming [iOS developer:tips];
Pingback: Tutorial: A Nice Guide And Example Introducing Functional Programming With Swift
Hi, wouldn’t that be a great use of XCode Playgrounds?
I copied the whole code into one Playground. Unfortunately I’m not yet a github expert, otherwise I would create a pull request.
If you are interested, mail me.
Pingback: 用Swift的函数式编程解决硬币问题 | 闲散人生 | idlelife