Skip to content

Instantly share code, notes, and snippets.

@obecker
Last active November 5, 2015 11:37
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save obecker/af06c46051b59a21240f to your computer and use it in GitHub Desktop.
Save obecker/af06c46051b59a21240f to your computer and use it in GitHub Desktop.
Solving the shortest grid path problem in Swift
indirect enum Route : CustomStringConvertible {
case End
case Down(Route)
case Left(Route)
var description: String {
switch self {
case .End: return ""
case .Down(let way): return "⬇︎\(way)"
case .Left(let way): return "⬅︎\(way)"
}
}
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) }
}
}
}
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))
}
@obecker
Copy link
Author

obecker commented Nov 4, 2015

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment