Today I stumbled upon an interesting task.

Create an algorithm that compress string with repeated symbols. 

"aaaaabbbbbbbbcd" -> "a5b8c1d1"
"abcaaaaaaaaaaaaaaaaaabbc" -> "a1b1c1a18b2c1"

if compressed string longer than original ("ab" -> "a1b1") return string without changes

I'm not strong in programming and can't really move an inch with this task. I tried to use Array and map but it's all not working. How can i start? Should i try with functions like map, filter, reduce or create func and implement logic inside? Any help will be appreciated !

CodePudding user response：

Form a counter and compare the current character to the next on each iteration. Only print when current character differs from next.

// Pseudo code
s = "aaaaabbbbbbbbcd"

count = 1

while (s not at end) 
  c = *s
  advance s
  if c same as next
    increment count
  else 
    print c and count
    count = 1
end loop

CodePudding user response：

You can use reduce(into:_) to do so:

The logic is to keep an array (ie ordered), with letter, and its number of following occurence. You iterate over the String, and check last entry. Increment its value, or append it to the array. Then, you iterate over the reduce output, and create the final string.

func compressing(str: String) -> String {
    let reduced = str.reduce(into: [(Character, Int)]()) { result, current in
        guard var last = result.last else {
            result.append((current, 1))
            return
        }
        if last.0 == current {
            last = (current, last.1   1)
            result[result.count - 1] = last
        } else {
            result.append((current, 1))
        }
    }
    print(reduced)
    let output = reduced.map { String($0.0)   "\($0.1)" }.joined()
    if output.count > str.count {
        return str
    } else {
        return output
    }
}

To test it:

let values: [(String, String)] = [("aaaaabbbbbbbbcd", "a5b8c1d1"),
                                  ("abcaaaaaaaaaaaaaaaaaabbc", "a1b1c1a18b2c1"),
                                  ("a111", "a113"),
                                  ("aaaaaaaaaaaaa", "a13")]

values.forEach {
    let result = compressing(str: $0.0)
    print("\(result) \(result == $0.1 ? "=" : "!")= \($0.1)")
}

Output:

[("a", 5), ("b", 8), ("c", 1), ("d", 1)]
a5b8c1d1 == a5b8c1d1
[("a", 1), ("b", 1), ("c", 1), ("a", 18), ("b", 2), ("c", 1)]
a1b1c1a18b2c1 == a1b1c1a18b2c1
[("a", 1), ("1", 3)]
a113 == a113
[("a", 13)]
a13 == a13

CodePudding user response：

Do it the simplest way possible: with a loop. No need to know fancy stuff like map and reduce for now, no need for intermediate data structures either.

Just iterate all characters and employ the logic in the loop (compare to previous character, count repetitions, etc...).
Then you may encounter special cases like for the first and last iteration and handle them appropriately.

Also you can't get faster than this, because you do only one iteration.

import Foundation

extension String {

    func compressed() -> String {
        
        var result = ""
        var counter = 1
        var storedChar: Character? = nil
        for (i, currentChar) in self.enumerated() {
            
            if storedChar == nil { // special case: first char
                
                storedChar = currentChar
            } else if storedChar == currentChar {
                
                counter  = 1
            } else {
                
                result  = String(storedChar!)   String(counter)
                storedChar = currentChar
                counter = 1
            }

            if i == self.count-1 { // special case: last char
                
                result  = String(storedChar!)   String(counter)
            }
        }

        if result.count >= self.count {

            return self 
        }

        return result
    }
}


"aaaaabbbbbbbbcd".compressed() == "a5b8c1d1"
"abcaaaaaaaaaaaaaaaaaabbc".compressed() == "a1b1c1a18b2c1"
"ab".compressed() == "ab"