KeyTimeValues Coding Challenge

KeyTimeValues.swift

let keyTimeValues: [TimeInterval: Float] = [
    0.4: 0.0,
    0.45: 1.0,
    0.475: 1.0,
    0.5: 1.0,
    0.525: 1.0,
    0.55: 0.0,
    0.575: 1.0,
    0.6: 1.0,
    0.65: 1.0,
    0.7: 0.0
]

/// The challenge:
/// The keys represent animation key times, the values represent values. Some key times repeat the same value of the previous keytime.
/// How would you reduce the above dictionary in such way that the values do not repeat themselves
/// more than once?
/// For example, this group:
///     0.45: 1.0,
///     0.475: 1.0,
///     0.5: 1.0,
///     0.525: 1.0,
///
/// The keytime 0.475 and 0.5 don't change the value and are, therefore, redundant in key frame animations.
///
/// Expected outcome:
let expectedOutcome: [TimeInterval: Float] = [
    0.4: 0.0,
    0.45: 1.0,
    0.525: 1.0,
    0.55: 0.0,
    0.575: 1.0,
    0.65: 1.0,
    0.7: 0.0
]

This should work...

let keyTimeValues: [TimeInterval: Float] = [
  0.4: 0.0,
  0.45: 1.0,
  0.475: 1.0,
  0.5: 1.0,
  0.525: 1.0,
  0.55: 0.0,
  0.575: 1.0,
  0.6: 1.0,
  0.65: 1.0,
  0.7: 0.0
]

let expectedOutcome: [TimeInterval: Float] = [
  0.4: 0.0,
  0.45: 1.0,
  0.525: 1.0,
  0.55: 0.0,
  0.575: 1.0,
  0.65: 1.0,
  0.7: 0.0
]

var lastValue: Float? = nil
var reducedKeyTimeValues: [TimeInterval: Float] = [:]
var currentKey: TimeInterval? = nil

for key in keyTimeValues.keys.sorted() {
  if let last = lastValue, keyTimeValues[key] == last {
    // If value is the same as last one, update the key
    currentKey = key
    continue
  }
  if let value = keyTimeValues[key] {
    // If value has changed, store the last key of the previous value
    if let lastKey = currentKey, let lastVal = lastValue {
      reducedKeyTimeValues[lastKey] = lastVal
    }
    // Then store the first key of the new value
    reducedKeyTimeValues[key] = value
    lastValue = value
    currentKey = key
  }
}

// Finally add the last key if it's a repeating value
if let lastKey = currentKey, let lastVal = lastValue {
  reducedKeyTimeValues[lastKey] = lastVal
}

if reducedKeyTimeValues == expectedOutcome {
  print("Job done!")
} else {
  print("Oops, wasn't expecting that!")
}

@KieranConlon nice one! That's close to what I came up with:

extension [Dictionary<TimeInterval, Float>.Element] {
    func reduceDuplicateValues() -> Self {
        var previousSameValueElement: Dictionary<TimeInterval, Float>.Element?
        var lastStoredElement: Dictionary<TimeInterval, Float>.Element?

        return reduce([]) { partialResult, element in
            var partialResult = partialResult

            if element.value != lastStoredElement?.value {
                /// Since we have a new value, we need to check whether we should close the last chain.
                /// We only have to if the previous element isn't equal to the last stored one.
                if let previousSameValue = previousSameValueElement, let lastStoredElement, previousSameValue != lastStoredElement {
                    partialResult.append(previousSameValue)
                    previousSameValueElement = nil
                }

                /// We have a new value which we should always add right away
                partialResult.append(element)

                /// We save the last stored element so we can compare the next value
                lastStoredElement = element
            } else {
                /// The value is similar to the last value
                /// Let's overwrite the previous element but we don't add it yet
                previousSameValueElement = element
            }

            return partialResult
        }
    }
}

Assuming the input would be:

let sortedKeyValues = keyTimeValues.sorted(by: { $0.key < $1.key }).reduceDuplicateValues()

My attempt:

extension [TimeInterval: Float] {
    func filter(allowedValueRepetition: UInt) -> Self {
        var includedKeys = [TimeInterval]()
        let sortedKeys = self.keys.sorted()
        var previous: (value: Float, count: UInt)?

        for key in sortedKeys {
            guard let value = self[key] else { continue }

            if value != previous?.value {
                includedKeys.append(key)
                previous = (value, 1)
                continue
            }

            if let prev = previous, value == prev.value {
                if prev.count < allowedValueRepetition {
                    includedKeys.append(key)
                } else {
                    includedKeys[includedKeys.count - 1] = key
                }
                previous!.count += 1
                continue
            }
        }

        return self.filter { includedKeys.contains($0.key) }
    }
}

Nice challenge, here's my solution:

func reduceDuplicateValues(_ keyTimeValues: [TimeInterval: Float]) -> [TimeInterval: Float] {
    var result: [TimeInterval: Float] = [:]
    let sortedKeys = keyTimeValues.keys.sorted()

    for (index, key) in sortedKeys.enumerated() {
        let currentValue = keyTimeValues[sortedKeys[index]]
        
        // If there's a value before the current, and this value is different than the current, 
        // then the current value is a useful keyframe for the animation because it introduces a new state 
        if sortedKeys.indices.contains(index - 1), keyTimeValues[sortedKeys[index - 1]] != currentValue {
            result[sortedKeys[index]] = currentValue 
        }
        
        // Else if there's a next value and this value is different than the current,
        // then the current value is a useful keyframe for the animation because it's a starting point
        // for animating to the new state
        else if sortedKeys.indices.contains(index + 1), keyTimeValues[sortedKeys[index + 1]] != currentValue {
            result[sortedKeys[index]] = currentValue
        }
        
        // If none of the previous conditions are true, then it means that
        // the current value is in one of the following cases:
        // 1. It's in the middle of 2 equal values (e.g. 1.0 [1.0] 1.0)
        // 2. It's the first value of the sequence, and it's equal to the next (e.g. [1.0] 1.0)
        // 3. It's the last value of the sequence, and it's equal to the previous (e.g. 1.0 [1.0])
        // 4. The keyTimeValues only contains 1 value or all equal values, hence no useful keyframes for an animation 
        // In all these cases the current value is not added to the result
    }

    return result
}

Using swift-collections for OrderedDictionary and swift-algorithms for adjacentPairs (which is O(1)), this should do the trick:

import Algorithms
import Collections
import Foundation

let keyTimeValues: OrderedDictionary<TimeInterval, Float> = [
    0.4: 0.0,
    0.45: 1.0,
    0.475: 1.0,
    0.5: 1.0,
    0.525: 1.0,
    0.55: 0.0,
    0.575: 1.0,
    0.6: 1.0,
    0.65: 1.0,
    0.7: 0.0
]

var reduced = OrderedDictionary<TimeInterval, Float>()

keyTimeValues.adjacentPairs().forEach { pair in
    if pair.0.value != pair.1.value {
        reduced[pair.0.key] = pair.0.value
        reduced[pair.1.key] = pair.1.value
    }
}

print(reduced)

This is my attempt :) (Twitter: BowdusBrown)

for (currentTimeInterval, currentValue) in sorted {
    
    defer {
        lastValue = currentValue
        lastTimeInterval = currentTimeInterval
    }
    
    if lastValue == nil {
        collection[currentTimeInterval] = currentValue
        continue
    }
    
    if lastValue.isNotEqual(to: currentValue) {
        collection[lastTimeInterval!] = lastValue
        collection[currentTimeInterval] = currentValue
    }
}

FYI 👆

extension Optional where Wrapped == Float {
    
    func isNotEqual(to value: Float) -> Bool {
        switch self {
        case .none:
            return true
        case .some(let unwrapped):
            return value != unwrapped
        }
    }
}

Golfed using Swift Algorithms:

import Algorithms

let keyTimeValues: [(TimeInterval, Float)] = [...]

let reduced = keyTimeValues.chunked(on: \.1).flatMap { _, chunk in
    [chunk.first, chunk.dropFirst().last].compacted()
}

(Convert to/from a dictionary as needed, but I think that was probably the incorrect choice of data structure to begin with)

Great solutions, all! Thanks a lot for joining the challenge. It's been an experiment for me and looking at the number of solutions submitted, it's definitely worth another challenge in the future.

Next time I'll make sure to provide an actual project together with a suite of tests that should succeed. Stay tuned!

Great stuff @AvdLee ! Even if it takes me ages to solve such challenges, keep those coming 🙂

Here is what I came up with:

/// Reduce repeating values if they occur more than once in a dictionary.
/// - Parameter keyTimeValues: A dictionary of key-time-value pairs.
/// - Returns: A reduced dictionary.
func reduceRepeatingValues(_ keyTimeValues: [TimeInterval : Float]) -> Dictionary<TimeInterval, Float> {
    var result: [TimeInterval : Float] = [:]
    var previousValue: Float?
    var previousKey: TimeInterval?

    for key in keyTimeValues.keys.sorted() {
        let currentValue = keyTimeValues[key]

        // If the previous value has not changed, cache the current key as previousKey and continue with the next key in the loop
        if previousValue == currentValue {
            previousKey = key
            continue
        }

        // Value has changed: unwrap (because these vars are defined as optional) and add the previous key/value pair to the result
        if let pKey = previousKey, let pValue = previousValue {
            result[pKey] = pValue
        }

        // Store the current key/value pair to the result
        result[key] = currentValue

        // Cache the current key/value pair as the new previous pair
        previousKey = key
        previousValue = currentValue
    }
    return result
}

var result = reduceRepeatingValues(keyTimeValues)
assert(result == expectedOutcome, "Oh no, I failed!")

Well done @simonberner 💪🏼

I guess I'm struggling with the example or explanation

let keyTimeValues: [TimeInterval: Float] = [
    0.4: 0.0,
    0.45: 1.0,
    0.475: 1.0,
    0.5: 1.0,
    0.525: 1.0,
    0.55: 0.0,
    0.575: 1.0,
    0.6: 1.0,
    0.65: 1.0,
    0.7: 0.0
]

/// Expected outcome:
let expectedOutcome: [TimeInterval: Float] = [
    0.4: 0.0,
    0.45: 1.0,
    0.525: 1.0,
    0.55: 0.0,
    0.575: 1.0,
    0.65: 1.0,
    0.7: 0.0
]

Why does 0.475 and 0.5 get removed but not 0.525? It's still repeating a value of 1.0.

I guess I'm missing out on something, would you mind pointing me towards that?

If you have a repeating value, then keep the first and last instance of that value.
Not sure if this colour-coded version helps; essentially remove the values within the red boxes.

@KieranConlon : Thank you !!

@AvdLee It's my solution:

let keyTimeValues: [TimeInterval: Float] = [
0.4: 0.0,
0.45: 1.0,
0.475: 1.0,
0.5: 1.0,
0.525: 1.0,
0.55: 0.0,
0.575: 1.0,
0.6: 1.0,
0.65: 1.0,
0.7: 0.0
]

extension Dictionary<TimeInterval, Float>{
    func optmizedDict() -> Dictionary<TimeInterval, Float>{
        var tempElement: Dictionary<TimeInterval, Float>.Element? = nil
        return reduce([:]) { partialResult, element in
            var partialResult = partialResult
            if element.value != tempElement?.value && tempElement != nil {
                partialResult[tempElement!.key] = tempElement!.value
                partialResult[element.key] = element.value
            }
        
            tempElement = element
            return partialResult
        }
    }
}


let result = keyTimeValues.optmizedDict().sorted{$0.0 < $1.0}

import Foundation

final class LinkedList: CustomStringConvertible {
    private final class Node {
        let timing: TimeInterval
        let value: Float
        var next: Node?

        init(timing: TimeInterval, value: Float) {
            self.timing = timing
            self.value = value
        }
    }

    private var head: Node?
    private var tail: Node?

    func append(timing: TimeInterval, value: Float) {
        let newNode = Node(timing: timing, value: value)
        if let tailNode = tail {
            if tailNode.value != newNode.value {
                tailNode.next = newNode
                tail = newNode
            }
        } else {
            head = newNode
            tail = newNode
        }
    }

    var description: String {
        var result = ""
        var current = head
        while let node = current {
            result = result.isEmpty
            ? "[timing:\(node.timing), value:\(node.value)]"
            : "\(result) → [timing:\(node.timing), value:\(node.value)]"
            current = node.next
        }
        return result
    }
}

// Example usage
let keyTimeValues: [TimeInterval: Float] = [
    0.4: 0.0,
    0.45: 1.0,
    0.475: 1.0,
    0.5: 1.0,
    0.525: 1.0,
    0.55: 0.0,
    0.575: 1.0,
    0.6: 1.0,
    0.65: 1.0,
    0.7: 0.0
]

var list = LinkedList()

keyTimeValues.sorted { $0.key < $1.key }.forEach { (key: TimeInterval, value: Float) in
    list.append(timing: key, value: value)
}