I published my solution to Dave Thomas’s Transitive Dependencies programming exercise, known as a kata, to GitHub:
This exercise involves analyzing a graph data structure which contains nodes that “depend on” other nodes. A graph is represented as direct dependencies between nodes:
The objective is to find all of a node’s dependencies, both direct and indirect, like so:
An interesting complication is that a graph might contain cyclical dependencies, where a node indirectly depends upon itself. A proper solution to this problem must be able to cope with a graph like this:
If this programming challenge interests you, stop reading now and solve the puzzle for yourself! Check out the kata for more information.
My solution relies on three things:
- An instance of Swift’s Set<T> collection keeps track of which nodes have been visited.
- The higher-order function reduce accumulates nodes into a Set as they are visited.
- Recursion is used to visit dependencies from the reduce method’s combine logic.
Here’s how I solved this little puzzle:
You can download the Xcode project here.
Pingback: Dew Drop – June 9, 2016 (#2268) | Morning Dew