A Journey to Conforming to Sequence… and Collection

So quite a while ago I started working on a 15-puzzle implementation for tvOS.

I had a lot of fun doing that over a few days but then had some hiccups trying to port it to iOS and kind of left it there. You know, your standard side project. (or at least my standard side project…)

Fast forward to a few weeks ago and with this still in the back of my mind, I wanted to challenge myself to write a solver for this puzzle.

It sounded like an interesting problem to solve (pun intended) and would give me the opportunity to learn about well, writing a solver, as well as diving into algorithms, optimization, math, etc… the possibilities are endless!

I started looking into ways to go about solving this puzzle — it is really interesting to see this pretty much 180 degree change from you solving the puzzle versus solving it with an algorithm. Long story short, I watched a few videos (which I highly recommend you watching, if you are interested in algorithms!) and was hooked.

Writing a solver

I did not only want to write a solver that, given input A, would return me output B, but rather give me all its steps towards B. That is what this post will dive into.

Imagine the following code:

struct Board {
    // some implementation
    func solve() {
      // convert "a" to "b" here
    }
}

This is the “simple” approach of converting input A to output B. But we need more. The solve() function should return a solution, including its steps:

func solve() -> Solution<Board> {
    // return the solution somehow
}

This all made sense in my mind. Actually, I wrote this pseudocode after I put the code down and went to bed, where my brain continued thinking about it.

The next day, I started working on the Solution type:

struct Solution<Problem> {
    struct Step<T> {
        let step: T
    }
    
    let steps: [Step<Problem>]
    
    var input: Step<Problem> {
        steps.first! // safe, as steps will guaranteed to be larger than 0.
    }
    
    var output: Step<Problem> {
        steps.last! // safe, as steps will guaranteed to be larger than 0.
    }
    
    init(steps: [Step<Problem>]) {
        precondition(steps.count > 0, "Solution must contain at least one step.")
        self.steps = steps
    }
    
    init(steps: Step<Problem>...) {
        self.init(steps: steps)
    }
}

As you can see, Solution is generic over Problem. Now I am not quite sure yet if I like that name, but with Xcode’s ability to refactor it later (🙃), I am sure I will be fine. (well actually, refactoring does not work in Playgrounds, where I am experimenting with this. 🤷‍♂️)

⚠️ If you are using Playgrounds on macOS, use a macOS Playground rather than an iOS Playground if you can get away with it; an iOS Playground will be a lot slower as it will use a simulator under the hood. ⚠️

That being said, we got a first implementation going! It is still awful to explain to the type checker¹, but check it out:

let solution = Solution<Int>(
    steps: Solution.Step(step: 1), Solution.Step(step: 2), Solution.Step(step: 3)
)

print(solution.input) // Step<Int>(step: 1)
print(solution.output) // Step<Int>(step: 3)

And the steps look like this:

print(solution.steps) // [__lldb_expr_46.Solution<Swift.Int>.Step<Swift.Int>(step: 1), __lldb_expr_46.Solution<Swift.Int>.Step<Swift.Int>(step: 2), __lldb_expr_46.Solution<Swift.Int>.Step<Swift.Int>(step: 3)]

Yikes. Although… that was not the point I wanted to make. What I want to be able to do (and yes, I am actually going to talk about the post’s topic now!), is to look at all steps of my solution.

Simple, you say? Indeed!

for step in solution.steps {
    print(step)
}

// Step<Int>(step: 1)
// Step<Int>(step: 2)
// Step<Int>(step: 3)

But would it not be marvelous if we can do this more magically, like so:

for step in solution {
    print(step)
}

Yes. Yes it would. Enter Sequence.

Conforming to `Sequence`, part I

So “all” we have to do here, is to make sure that our Solution conforms to the Sequence protocol. Like the Array already does.

So let us look at the documentation.

Conforming to the Sequence Protocol

Making your own custom types conform to Sequence enables many useful operations, like for-in looping and the contains method, without much effort. To add Sequence conformance to your own custom type, add a makeIterator() method that returns an iterator.

Alternatively, if your type can act as its own iterator, implementing the requirements of the IteratorProtocol protocol and declaring conformance to both Sequence and IteratorProtocol are sufficient.

Well then. I do not know about you, but I was still a bit stuck at this point. It does feel like Solution will act as its own iterator. But how do I create this “iterator”?

Well, I was lucky. The documentation continued:

Here’s a definition of a Countdown sequence that serves as its own iterator. The makeIterator() method is provided as a default implementation.

Exactly. We do not have to worry about this iterator, and have an example implementation.

struct Countdown: Sequence, IteratorProtocol {
    var count: Int
    
    mutating func next() -> Int? {
        if count == 0 {
            return nil
        } else {
            defer { count -= 1 }
            return count
        }
    }
}

let threeToGo = Countdown(count: 3)
for i in threeToGo {
    print(i)
}
// Prints "3"
// Prints "2"
// Prints "1"

Now let us implement ours.

Conforming to `Sequence`, part II

This is where the “fun” starts. Let us expand on the Solution type, and make it ready to implement Sequence as well as IteratorProtocol.

struct Solution<Problem>: Sequence, IteratorProtocol {

}

And now we use the fixit that Xcode will provide us, and implement the missing implementations, right? Right.

This is what it generates:

struct Solution<Problem>: Sequence, IteratorProtocol {
    typealias Element = <#type#>
    typealias Iterator = <#type#>
    typealias Element = <#type#>
}

Welp. I should file a JIRA for this.

At this point, I gave up on trying to figure this out myself, and came across a blog post from NatashaTheRobot that was exactly what I was looking for.

So, like in the Countdown example, let us implement next()… the only thing we will actually have to implement.

struct Solution<Problem>: Sequence, IteratorProtocol {

    private var _index: Int? = nil
    mutating func next() -> Step<Problem>? {
        // we're counting up (looping though the steps array), so begin at _index 0.
        if _index == nil { _index = 0 }
        // shadow _index so we do not have to deal with its optionality
        // this is also why the "other" index is underscored.
        var index = _index!
        if index < steps.count {
            // always move the _index forward after we can return a step
            defer { _index! += 1 }
            return steps[index]
        } else {
            // when we're done, reset the _index to nil.
            _index = nil
            return nil
        }
    }
}

Et voilà:

for step in solution {
    print(step)
}

// Step<Int>(step: 1)
// Step<Int>(step: 2)
// Step<Int>(step: 3)

Magical. 🧙‍♂️

Update: … and `Collection`

My colleague Manuele and later (my not colleague) Soroush pointed out that it might make more sense for this Solution type to conform to Collection (which itself conforms to Sequence) instead. From the documentation:

A sequence whose elements can be traversed multiple times, nondestructively, and accessed by an indexed subscript.

And yes, it would make sense to be able to traverse a solution multiple times. So, let’s implement it. First, we conform to Collection.

- struct Solution<Problem>: Sequence, IteratorProtocol {
+ struct Solution<Problem>: Collection {

And then we implement it, getting rid of a lot (read: all) of our manual work that was required to conform to Sequence.

- private var _index: Int? = nil
- mutating func next() -> Step<Problem>? {
-     // we're counting up (looping though the steps array), so begin at _index 0.
-     if _index == nil { _index = 0 }
-     // shadow _index so we do not have to deal with its optionality
-     // this is also why the "other" index is underscored.
-     var index = _index!
-     if index < steps.count {
-         // always move the _index forward after we can return a step
-         defer { _index! += 1 }
-         return steps[index]
-     } else {
-         // when we're done, reset the _index to nil.
-         _index = nil
-         return nil
-     }
- }

Where instead, we can now piggyback on our internal array of Steps:

var startIndex: Int {
    steps.startIndex
}

var endIndex: Int {
    steps.endIndex
}

subscript(i: Int) -> Step<Problem> {
    steps[i]
}

func index(after i: Int) -> Int {
    steps.index(after: i)
}

And that is it! This is so much easier to understand and gives me a lot more confidence when it comes to its validity, both from a correctness and performance point of view.

Thanks, Manuele & Soroush! 🎉

You can find the implemention of the Solution type, including the one conforming to Collection instead of Sequence, in this gist.

If you have any ideas on how to improve this the verbosity of initializing a Solution, being able to help the type checker, please let me know! ↩

Writing a solver

Conforming to Sequence, part I

Conforming to Sequence, part II

Update: … and Collection

Conforming to `Sequence`, part I

Conforming to `Sequence`, part II

Update: … and `Collection`