How Many Ways To Find A Way?
04 Nov 2015

Recently I had to explain recursive functions to my students. One of the examples was the recursive formula for Binomial Coefficients which can be visualized as Pascal's triangle. Looking for a real world problem that can be solved by using Pascal's triangle I found the shortest grid path problem. Since I'm currently trying to get familiar with programming in Swift, I thought to myself, why not coding something in Swift that computes these paths?

The task is as follows: Supposed there is a city having a rectangular grid of streets. A person needs to travel from one point (or intersection) A to a different point B. How many shortest ways do exist between A and B? One can imagine that this is a repeating tour and the person wants to vary the routes from time to time.

The streets should run strictly rectangular, so all direct routes without detours have the same length. To simplify the problem and without loss of generality, I assume the destination to be at point (0, 0). Furthermore the start at some point (x, y) should have non-negative integer coordinates. One step along a route brings the person to an adjacent point that is closer to (0, 0), i.e. that is either at (x-1, y) or at (x, y-1).

The following grid shows a possible route from point (5, 3) to the destination at (0, 0):

The analogy to Pascal's triangle now is: If there are two possibilities to choose the next point, either by going parallel to the x-axis or by going parallel to the y-axis, then the number of different routes from the current point is the sum of the numbers of routes from each of these two adjacent points.

In the following code I also want to compute these routes, not only their number.

Let me start with the representation of a route. A route can be expressed as a simple linked list of steps. Each step goes either to the left (by reducing x) or downwards (by reducing y). It seems to be a good idea to use an enum to represent this as a recursive data structure:

indirect enum Route {
    case Left(Route)
    case Down(Route)
    case End
}

The enum must be indirect because it is recursive. It is either a step Left followed by a Route, a step Down followed by a Route, or it is the End of the route (this case could also have been named Empty to represent the empty route), i.e. the person has reached the destination at the coordinates (0, 0).

The next step is to add a function findRoutesFrom that returns an array of possible Routes. There are three cases to consider: I have arrived (both coordinates are 0), I have reached one of the axes (one of the coordinates is 0, so there is only one possibility for the next step), or I am somewhere else and have two possible routes to consider. Using the pattern matching approach for pairs I get the following:

indirect enum Route {
    case Left(Route)
    case Down(Route)
    case End

    static func findRoutesFrom(x: Int, _ y: Int) -> [Route] {
        switch (x, y) {
        case (0, 0):
            return [.End]
        case (0, _):
            return findRoutesFrom(x, y - 1).map({ .Down($0) })
        case (_, 0):
            return findRoutesFrom(x - 1, y).map({ .Left($0) })
        default:
            return findRoutesFrom(x, y - 1).map({ .Down($0) })
                + findRoutesFrom(x - 1, y).map({ .Left($0) })
        }
    }
}

In case I am not at the destination (0, 0) yet, I have to determine the routes from an adjacent point and add the chosen step to each of them (this is what the map({ .Down($0) }) is doing). Note, that the routes found in the previous step are neither altered nor copied. Instead a new Route is created using the previous route as its associated value.

What I don't like much here are the duplicate expressions for constructing the new Left and Down routes. Normally I would extract them into variables, however, I must not compute them in the (0, 0) case. Lazy values from Scala might be useful. Unfortunately, Swift allows lazy variables only as members in class or struct, but not as local variables. But there's a solution: I can wrap the expression in local closures and invoke them if needed:

indirect enum Route {
    case Left(Route)
    case Down(Route)
    case End

    static func findRoutesFrom(x: Int, _ y: Int) -> [Route] {
        let downRoutes = {
            findRoutesFrom(x, y - 1).map({ Route.Down($0) })
        }
        let leftRoutes = {
            findRoutesFrom(x - 1, y).map({ Route.Left($0) })
        }
        switch (x, y) {
        case (0, 0):
            return [.End]
        case (0, _):
            return downRoutes()
        case (_, 0):
            return leftRoutes()
        default:
            return downRoutes() + leftRoutes()
        }
    }
}

This function works already quite well. At least for positive values of x and y. Alright, let me extend the switch by adding another case to be on the safe side. For negative values the function always returns an empty array. There are no routes in these cases, so that makes perfect sense:

case _ where x < 0 || y < 0:
    return []

Wait. If this case is allowed then there's no need to deal with the special cases where either x or y is already 0. I always can try to find routes in both directions and in the worst case I get an empty array for one of these directions. That makes the code a lot simpler again:

indirect enum Route {
    case Left(Route)
    case Down(Route)
    case End

    static func findRoutesFrom(x: Int, _ y: Int) -> [Route] {
        switch (x, y) {
        case _ where x < 0 || y < 0:
            return []
        case (0, 0):
            return [.End]
        default:
            return findRoutesFrom(x, y - 1).map({ .Down($0) })
                + findRoutesFrom(x - 1, y).map({ .Left($0) })
        }
    }
}

That's it! However, one thing has still room for improvement: the result I get is not really readable. For example invoking

print(Route.findRoutesFrom(3, 1))

produces this output

[Route.Down(Route.Left(Route.Left(Route.Left(Route.End)))),
Route.Left(Route.Down(Route.Left(Route.Left(Route.End)))),
Route.Left(Route.Left(Route.Down(Route.Left(Route.End)))),
Route.Left(Route.Left(Route.Left(Route.Down(Route.End))))]

The way to create a pretty string representation is to make the enum Route to be CustomStringConvertible. I just have to add the protocol and a proper description property. Since the enum is recursive, the description implementation is recursive as well:

indirect enum Route : CustomStringConvertible {
    case End
    case Down(Route)
    case Left(Route)

    var description: String {
        switch self {
        case .End: return ""
        case .Down(let route): return "⬇\(route)"
        case .Left(let route): return "⬅\(route)"
        }
    }

    // ... static func findRoutesFrom() as above
}

OK, now the output is much better

[⬇⬅⬅⬅, ⬅⬇⬅⬅, ⬅⬅⬇⬅, ⬅⬅⬅⬇]

Finally, let's try to find all routes starting at (5, 3) as illustrated above. Since this results in 56 routes I print the result in rows of 4 columns:

let routes = Route.findRoutesFrom(5, 3)
print("Found \(routes.count) routes")
for i in 0 ..< routes.count / 4 {
    print(routes[i * 4 ..< (i + 1) * 4])
}
if routes.count % 4 != 0 {
    print(routes.suffix(routes.count % 4))
}

This code outputs

Found 56 routes
[⬇⬇⬇⬅⬅⬅⬅⬅, ⬇⬇⬅⬇⬅⬅⬅⬅, ⬇⬇⬅⬅⬇⬅⬅⬅, ⬇⬇⬅⬅⬅⬇⬅⬅]
[⬇⬇⬅⬅⬅⬅⬇⬅, ⬇⬇⬅⬅⬅⬅⬅⬇, ⬇⬅⬇⬇⬅⬅⬅⬅, ⬇⬅⬇⬅⬇⬅⬅⬅]
[⬇⬅⬇⬅⬅⬇⬅⬅, ⬇⬅⬇⬅⬅⬅⬇⬅, ⬇⬅⬇⬅⬅⬅⬅⬇, ⬇⬅⬅⬇⬇⬅⬅⬅]
[⬇⬅⬅⬇⬅⬇⬅⬅, ⬇⬅⬅⬇⬅⬅⬇⬅, ⬇⬅⬅⬇⬅⬅⬅⬇, ⬇⬅⬅⬅⬇⬇⬅⬅]
[⬇⬅⬅⬅⬇⬅⬇⬅, ⬇⬅⬅⬅⬇⬅⬅⬇, ⬇⬅⬅⬅⬅⬇⬇⬅, ⬇⬅⬅⬅⬅⬇⬅⬇]
[⬇⬅⬅⬅⬅⬅⬇⬇, ⬅⬇⬇⬇⬅⬅⬅⬅, ⬅⬇⬇⬅⬇⬅⬅⬅, ⬅⬇⬇⬅⬅⬇⬅⬅]
[⬅⬇⬇⬅⬅⬅⬇⬅, ⬅⬇⬇⬅⬅⬅⬅⬇, ⬅⬇⬅⬇⬇⬅⬅⬅, ⬅⬇⬅⬇⬅⬇⬅⬅]
[⬅⬇⬅⬇⬅⬅⬇⬅, ⬅⬇⬅⬇⬅⬅⬅⬇, ⬅⬇⬅⬅⬇⬇⬅⬅, ⬅⬇⬅⬅⬇⬅⬇⬅]
[⬅⬇⬅⬅⬇⬅⬅⬇, ⬅⬇⬅⬅⬅⬇⬇⬅, ⬅⬇⬅⬅⬅⬇⬅⬇, ⬅⬇⬅⬅⬅⬅⬇⬇]
[⬅⬅⬇⬇⬇⬅⬅⬅, ⬅⬅⬇⬇⬅⬇⬅⬅, ⬅⬅⬇⬇⬅⬅⬇⬅, ⬅⬅⬇⬇⬅⬅⬅⬇]
[⬅⬅⬇⬅⬇⬇⬅⬅, ⬅⬅⬇⬅⬇⬅⬇⬅, ⬅⬅⬇⬅⬇⬅⬅⬇, ⬅⬅⬇⬅⬅⬇⬇⬅]
[⬅⬅⬇⬅⬅⬇⬅⬇, ⬅⬅⬇⬅⬅⬅⬇⬇, ⬅⬅⬅⬇⬇⬇⬅⬅, ⬅⬅⬅⬇⬇⬅⬇⬅]
[⬅⬅⬅⬇⬇⬅⬅⬇, ⬅⬅⬅⬇⬅⬇⬇⬅, ⬅⬅⬅⬇⬅⬇⬅⬇, ⬅⬅⬅⬇⬅⬅⬇⬇]
[⬅⬅⬅⬅⬇⬇⬇⬅, ⬅⬅⬅⬅⬇⬇⬅⬇, ⬅⬅⬅⬅⬇⬅⬇⬇, ⬅⬅⬅⬅⬅⬇⬇⬇]

Quite a lot of possible routes for this rather short distance. Who would have thought?

Back to Pascal's triangle: the number 56 happens to be in the triangle when traversing it downwards starting at the top by taking in any order 5 steps right and 3 steps left (or 3 right and 5 left). It can also be computed using the factorial formula:

The full Swift code can be found in this gist.

Update 05 Nov 2015 In order to create that table like output with 4 columns I was looking for a simple way to slice an array. I ended up with these somewhat ugly for and if statements. However, wouldn't it be nice to have a function on the Array type that creates an array of slices?

By using Swift's extension mechanism this is quite simple to achieve. Violà, here it is: the slicesOf extension function:

extension Array {
    func slicesOf(size: Int) -> [ArraySlice<Array.Element>] {
        var slices = [ArraySlice<Array.Element>]()
        slices.reserveCapacity(self.count / size + 1)
        for var i = 0; i < self.count; i += size {
            slices.append(self[i ..< min(i + size, self.count)])
        }
        return slices;
    }
}

With this the above output can be produced shorter and more concise:

for slice in routes.slicesOf(4) {
    print(slice)
}

I'm interested in your feedback. Send me a mail or ping me on twitter.