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> {
return steps.first! // safe, as steps will guaranteed to be larger than 0.
}

var output: Step<Problem> {
return 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 checker1, 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.

``````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 `Step`s:

``````var startIndex: Int {
return steps.startIndex
}

var endIndex: Int {
return steps.endIndex
}

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

func index(after i: Int) -> Int {
return 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.

1. 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!