Case study of Higher order function

Higher order function, HFO, Case studies

Posted on by Rayhan

So we are continuing from our last post on HOF, there we had the basic. Now let us move further to resolve a complex case study through higher order function, HOF.

HOF Chaining

Calling the higher order function one after another, we can construct a chain of higher order function.


let integerNumbers = Array(1 ... 100)
integerNumbers.filter({ $0 % 2 == 0}).reduce(into: 0, { $0 += $1 })
// output: 2550

On the above example we are getting the sum of first 100 even-integer number by using the favourite higher order function,HOF, chaining.

[Case Study] Character counting:

Let us play a game, a game of characters.

Here comes the problem definition. We will put two of our favourite quote and will find out the repetitive characters among them and finally we will print the repetitive characters in some fixed format.

Lets define some constraints.

  • For simplicity we will only count small caps character.
  • As we want to have the repetitive characters, so any char-repeat thats less than 2 will be discarded.
  • The print of characters will be tagged with colored heart, such as 💚 for first quote, 💙 for second quote and 💖  if the appearance of a character on both quote are equal.
  • Our print chronology will be max repetition first, then the lower repetition.

Now consider if different characters have same number of appearance. 

  • 💚 will have the highest precedence, so for any same number of repetition for a char on both quote, always 💚 will be preferred then 💙 and finally 💖.
  • For same number of repetition on a specific colored heart alphabetic order will be applied.

ok thats becoming confusing. Lets describe using example, We will use the following two quotes

To be or not To be

Nothing is permanent

The final output will be


💚 = [4 times o] oooo
💙 = [3 times n] nnn
💚 = [2 times b] bb
💙 = [2 times i] ii
💙 = [2 times t] tt
💖 = [2 times e] ee

So as we can see o has the max appearance, 4 ,that’s why its on the very first position. Then n has 3 appearance, though there is a cap n, N, which we will discard as we said on the very first constraint.

Rest of the character’s appearance is pretty interesting.
lets ignore t for now.

Remember we said 💚 has the highest precedence, then 💙 and finally  💖.  Thats why the chronology is b , i , and finally e.

Again earlier we said; for same colored heart with same number appearance, the chronology will be alphabetically. Thats why i then t for 💙.

Implementation 

We will resolve this problem step by step. But if we are greedy, we can always visit the Playground file on GitHub. BTW steps to follow:

charCount

So the very first small step is to make a char-counter. The counter will operate on a single quote at a time and will give us the total character count. Now there should be two constraints that the counter has to maintain:

  • only lowercase char
  • char count > 1

func charCount(_ quote: String) -> [Character: Int]?{
    let lowerCase = quote.components(separatedBy: CharacterSet.lowercaseLetters.inverted).joined()
    guard lowerCase.count > 1 else { return nil }

    // will continue...
    return nil
}

The first line of code is filtering the lower case character then in the second we are making sure that we at-least have multiple characters.

Now we have a lowerCase dictionary containing only lowercase characters which char count we have to return.

So for each char in lowerCase array we have to perform an operation, Either we will start the count with 1 if the char is yet not been added or increase the char count by one. Does the following ring any Bell?

for each element, of a collection, perform an action

If not, it should be map.  ie lowerCase.map({ })

Lets define a charCount dictionary, var charCount = [Character: Int](), which will hold the char counting.

By using the shorthand argument name of closure we can write


lowerCase.map({ charCount[$0] = charCount.keys.contains($0) ? charCount[$0]! + 1 :  1 })

note: shorthand if; if condition ? executeForTrue : executeForFalse

On the above we are assigning the charCount dictionary for each element, i.e character, of lowerCase. The assignment is pretty simple. If the character does not exits then just add 1 as a value for that specific character. Otherwise get the current count value of that character charCount[$0] and increment it by 1. 
just a side note: we are using the ! [force unwrapped operator] after charCount[$0] because on this case we can be certain that we will have a value here. 

Wait, one last think, we need filter out the entities, char,  which does not posses multiple count. So which HOF should we use?

Right its a simple choice, filter().  charCount.filter({ $0.value > 1 })

Finally our charCount() becomes:


func charCount(_ input: String) -> [Character: Int]?{
    let lowerCase = input.components(separatedBy: CharacterSet.lowercaseLetters.inverted).joined()
    guard lowerCase.count > 1 else { return nil }
    
    var charCount = [Character: Int]()
    
    lowerCase.map({ charCount[$0] = charCount.keys.contains($0) ? charCount[$0]! + 1 :  1 })
    
    return charCount.filter({ $0.value > 1 })
}

combinedMaxChar

Here we will combine maximum char count by combining two quotes.

If we have the same quotes then there is nothing to compare, will return nil.


guard firstQuote != secondQuote else { return nil }

Now lets count character for each of the quote by using the charCount(), we build on the last section.


let greenCharCount = charCount(firstQuote)
let blueCharCount = charCount(secondQuote)

If both the charCount is nil or count == 0 then there is no benefit of continuing the counting further.


if (greenCharCount == nil && blueCharCount == nil) || (greenCharCount?.count == 0 && blueCharCount?.count == 0){
        return nil
    }

Currently we do not have any data type which can represent the character count with type-of-heart it belongs to. Lets define an enum for Heart.


enum Heart: String{
    case equal = "💖 = "
    case blue = "💙 = "
    case green = "💚 = "
}

We will use the raw-value  at the final state for pretty-print. For more details on raw valued enum.

Ok back to our data type. So finally we can define a typealias, which can represent both the type of Heart and the count for a specific character.If interested we can always visit the typealias for more details.


typealias CombinedValue = (precedence: Heart, count: Int)

Lets use CombinedValue to update our existing charCount Array, greenCharCount and blueCharCount.

Our goal is to transform the [Character: Int] Dictionary in to a [Character:  (precedence: Heart, count: Int)] Dictionary.

Almost map() right, hmm. Incase we haven’t saw: its basically a map between values, Int to (Heart, Int). For this case we will use another HOF mapValues() which will only map the values keeping the keys same.


let greenCombine = greenCharCount?.mapValues({ CombinedValue(precedence: .green, count: $0) })
 let blueCombine = blueCharCount?.mapValues({ CombinedValue(precedence: .blue, count: $0) })

Pretty strait forward. Here $0 is the value, type Int, actually. So for each Int value we are mapping with new Instance of CombinedValue(precedence: Heart, count: Int)

The one last thing is to merge the both dictionary into a single one. So the final Dictionary will have the character as key with type-of-heart and count as value. For this purpose we will use another HOF, merging(). merging() will give us an opportunity to set a closure for common key. As a result we can customise the value baed on our requirements.


greenCombine?.merging(blueCombine!, uniquingKeysWith: {
        $0.count > $1.count ?
            $0
            : $0.count == $1.count ?
                CombinedValue(precedence: .equal, count: $0.count)
            : $1
    })

Here $0 and $1 are CombinedValue type object for greenCombine and blueCombine respectively.  And they have the same key. 
The value which has the highest precedence is selected by default. If they have the same count then a new CombinedValue is created with equal precedence.

Finally combinedMaxChar  as following:


func combinedMaxChar(_ firstQuote: String, _ secondQuote: String) -> [Character: CombinedValue]?{
    guard firstQuote != secondQuote else { return nil }
    
    let greenCharCount = charCount(firstQuote)
    let blueCharCount = charCount(secondQuote)
    
    if (greenCharCount == nil && blueCharCount == nil) || (greenCharCount?.count == 0 && blueCharCount?.count == 0){
        return nil
    }
    
    let greenCombine = greenCharCount?.mapValues({ CombinedValue(precedence: .green, count: $0) })
    let blueCombine = blueCharCount?.mapValues({ CombinedValue(precedence: .blue, count: $0) })
    
    return greenCombine?.merging(blueCombine!, uniquingKeysWith: {
        $0.count > $1.count ?
            $0
            : $0.count == $1.count ?
                CombinedValue(precedence: .equal, count: $0.count)
            : $1
    })
}

sortKeys

In this section we will sort keys based on the requirements. We will use the combined Dictionary we got from the combinedMaxChar() and will sort its key or character.

On of the sorting requirements was 💚 >  💙 > 💖 when the chart count is same. To fulfill this requirements we need to add a computed property to Heart which will return the Heart precedence. Lets call it weight.


extension Heart{
    var weight: Int{
        switch self {
        case .green:
            return 3
        case .blue:
            return 2
        default:
            return 1
        }
    }
}

Now for sorting we will use sorted() HOF. Lets discuss different sorting requirements.

  • The very first requirements is the max char count.  $0.value.count > $1.value.count   // 1. based on count.
  • For the same char count, the sorting will be based on weight of Heart.  $0.value.precedence.weight > $1.value.precedence.weight // 2. count same, so based on weight 1 > 2 > 3
  • For same count and same weight, the sorting will be based on key’s alphabetic order. $0.key < $1.key // 3. count same and weight(1,2,E) same, so based on alphabetically

func sortKeys(_ input: [Character: CombinedValue]?) -> [Character]?{
    guard let input = input, input.count > 0 else { return nil }
    return input.sorted(by: {
        $0.value.count == $1.value.count ?
            $0.value.precedence.weight == $1.value.precedence.weight ?
                $0.key < $1.key // 3. count same and weight(1,2,E) same, so based on alphabetically
                : $0.value.precedence.weight > $1.value.precedence.weight // 2. count same, so based on weight 1 > 2 > 3
            : $0.value.count > $1.value.count   // 1. based on count
    }).map({ $0.key })
}

Again for empty or nil Dictionary we will just return nil. Then we are implementing the sorting requirements. Finally we are using map() to get only the keys array or [Character]. Dictionary are not meant for sorting.

format

On the beginning of the blog we saw a fixed format for printing. So ya we need to have a formatter.

Our formatter will have two input, a combine dictionary that we got from combinedMaxChar and a sorted key array from sortKeys. And the formatter will return the desire formatter string.


func format(_ input: [Character: CombinedValue]?, with sortedKeys: [Character]?) -> String {
    guard let input = input, let sortedKeys = sortedKeys, input.count > 0, sortedKeys.count > 0 else { return "" }
    
    var combine = ""
    sortedKeys.forEach({
        guard let value = input[$0]else{return}
        
        combine += value.precedence.rawValue + "[\(value.count) times \($0)] "
        
        for _ in 1...value.count {
            combine += String($0)
        }
        
        combine += "\n"
    })
    combine.removeLast()
    print("combine:\n\(combine)")
    return combine
}

On format we will return an empty string if something is not proper.

Here we are using another HOF, forEach. We are traversing the sortedKeys array and getting the corresponding value from the input,  [Character: CombinedValue], array. After that we are constructing a String based on our desire format.  

compareQuote

So finally it wrapping time. Here on compareQuote()we will wrap everything up.


func compareQuote(_ green: String, _ blue: String) -> String {
    let combined = combinedMaxChar(green, blue)
    let sortedKey = sortKeys(combined)
    
    return format(combined, with: sortedKey)
}

Come on we don’t need any explanation for this. 😊

At the end

The corresponding code is shared on GitHub as a playground project. This  project was a part of a online code challenge. And I did implement this problem using TDD. Thats why you will see some test cases. Perhaps we will talk more about TDD on Swift on some future day. Right now you can enjoy the project.

Becoming smart part

Whenever you find a situation where you need to do some operation on a collection type, be sure to use higher order function. Smart people does that. Now how will you sharpen you higher order function, HOF, skill? Only one way and the way is same for all skills. 

Practice.

So practice more on higher order function, you will definitely become a better one. Make sure you understand closure very well. Ask question and solve them by using higher order function.

Happy talk on higher order function. Thanks.  🌊

4 thoughts on “Higher order function, HFO, Case studies”

Leave a Reply

Notifications for mobidevtalk! Cool ;) :( not cool