I published my solution to Dave Thomas’s Transitive Dependencies programming exercise, known as a kata, to GitHub:

https://github.com/ijoshsmith/transitive-dependencies-kata

The Challenge

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

My solution relies on three things:

1. An instance of Swift’s Set<T> collection keeps track of which nodes have been visited.
2. The higher-order function reduce accumulates nodes into a Set as they are visited.
3. 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.