Solve Logic Puzzles with Functional Programming - Swift Version

This translated article uses two methods to solve the same logic problem. The first method uses a programming style similar to that of most iOS developers and implements an imperative programming solution. The second method uses some language features of Swift and implements a functional programming solution.

The source code can be downloaded here: https://github.com/ijoshsmith/break-a-dollar

Logic puzzles

A while ago, a friend told me that there are 293 ways to break down a dollar into smaller denominations. In other words, if a guy tells you he has a dollar, he has 293 possible combinations, which could be two 50 cents or four 25 cents. The next day, I started trying to solve this problem with code. This blog reviews the two solutions I thought of at the time.

Dollar Coin

For those who are not familiar with US dollar coins, you can first learn about US dollar coins. As shown in the figure below, 1 US dollar = 100 cents:

Initial exploration of the problem

After thinking about it, I found that it was not difficult to solve this problem with a simple and dirty method, but this was far from enough. I wanted to find an elegant solution, so I tried to think about this problem from all angles, and finally got the answer I wanted.

The key to solving this problem lies in recursive decomposition of the problem. "How to use various combinations of coins to make 1 dollar" is actually "how to use various combinations of coins to make a specified amount of money".

Let's take the example of RMB. You owe someone RMB 100, and they say you won't give me RMB 100. You say OK, I'll give it to you! So you take out two RMB 50 bills, and this is a 50+50 solution.

At this time, you find a brand new 50-dollar bill, and you don't want to give it to him, so your problem becomes: how to use the small change in your hand to make a 50-dollar bill.

Later you changed the 50 into 5 10-yuan notes, which is a solution of 50+10*5. Then you felt that one of the 10-yuan notes was brand new, so you changed it into coins for him.

So the question becomes: how to combine the 10 denominations of money.

Click here for a full review of the algorithm.

First, make coins

I mentioned the word "coin" a lot, and a coin is actually just an integer value that represents how many cents it is worth. I wrote an enum class to store all the coin denominations, and then used a static method to return all the values ​​in descending order:

 enum Coin: Int {
 case SilverDollar = 100  
 case HalfDollar = 50  
 case Quarter = 25  
 case Dime = 10  
 case Nickel = 5  
 case Penny = 1  
 static func coinsInDescendingOrder() -> [Coin] {
 return [
            Coin.SilverDollar,
 Coin.HalfDollar,
 Coin.Quarter,
 Coin.Dime,
 Coin.Nickel,
 Coin.Penny,
 ]
 }
 }

Solution 1: Imperative Programming

An important point of imperative programming is that variables change state. An imperative program is like a microcontroller that tells the computer how to complete a task. The following Swift code should look familiar to everyone, because objc is an imperative programming language:

 func countWaysToBreakAmout(amount: Int, usingCoins coins:[Coin]) -> Int{
 let coin = coins[ 0 ]
 if (coin == .Penny) {
 return   1  
 }
    var smallerCoins = [Coin]()
 for index in 1 ..!=coins.count {
        smallerCoins.append(coins[index])
 }
 var sum = 0  
 for coinCount in 0 ...(amount/coin.rawValue) {
        let remainingAmount = amount - (coin.rawValue * coinCount)
        sum += countWaysToBreakAmout(remainingAmount, usingCoins: smallerCoins)
 }
 return sum
 }

Looking carefully at the code above, the calculation process is divided into three steps:

First, take out the first coin in the available array. If this coin is already 1 cent, which is the smallest denomination, there is no possibility of further splitting, and return 1 directly as the end.

Then an array (smallerCoins) is created to store coins smaller than the current coin, which will be used as parameters for the next call.

Finally, calculate how many solutions there are after removing the first coin taken out.

Such code is common for imperative programming. Next, let's see how to solve this problem using functional programming.

Solution 2: Functional Programming

Functional programming relies on functions, not state changes. Not having too much shared data means fewer errors and fewer times of needing to synchronize data. Functions are first-class citizens in Swift, which makes higher-order functions possible, that is, a function can be composed of other functions. With the introduction of blocks in objc, iOS developers should be familiar with this.

Here is my functional solution:

 func countWaysToBreakAmount(amount: Int, usingCoins coins:Slice) -> Int{
    let (coin, smallerCoins) = (coins[ 0 ], coins[ 1 ..<coins.count]) if (coin = "= .Penny) {"           return   1 = "" }= "" let coincounts = " [Int](0...amount/coin.rawValue)"       return coincounts.reduce( 0 ) { (sum, coincount) in= "" let remainingamount = " amount - (coin.rawValue * coinCount)"           return sum + self.countwaystobreakamount(remainingamount, usingcoins: smallercoins)= "" }
 </coins.count])>

<="" pre="">

The second parameter is Slice Instead of an array, there is no need to copy the coins to a new array. We just need to use a slice of the array, which is smallerCoins in the first line of code, which is called tail in functional programming. We call the first element of the data head and the rest tail. Splitting the array will not cause an exception if the subscript is out of bounds. If there is only one element left in the array, smallerCoins is empty.

I used the tuple syntax to get both coins and smallerCoins at the same time, because getting the head and tail is the same operation. Instead of writing a bunch of code to explain how to get the first element first and then get the rest of the elements, it is better to use a semantic way of "getting the head and tail" to get it done in one step.

Next, we don’t use the method of looping and changing local variables to calculate the number of remaining combinations, but use the reduce function. If you are not familiar with the reduce function, you can read this article to get a general understanding.

First, coin refers to the current coin being processed, and coinCounts is an array that stores the possible number of coins of all current denominations. For example, if amount is 10 and coin is 3, then the value of coinCounts is the number of coins of denomination 3 that can appear. Obviously, there should be at most 3, so coinCounts is a series of numbers like [1,2,3]. Then, we decompose and calculate each case separately.

think

Swift's support for functional programming makes me feel excited! Thinking in a different way may be a big challenge, but it's worth it. I taught myself some Haskell a few years ago, and I was very happy to find some functional thinking habits that benefited me a lot in iOS development.

The source code for the example project can be downloaded here.