Created
December 27, 2016 03:46
-
-
Save matnogaj/8ea873cd52e548a20655ddea9b513659 to your computer and use it in GitHub Desktop.
Shortest maze
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
//: Playground - noun: a place where people can play | |
import UIKit | |
class Step { | |
let x: Int | |
let y: Int | |
init?(_ x: Int, _ y: Int) { | |
guard x >= 0 && x < Step.maze.count else { return nil } | |
guard y >= 0 && y < Step.maze[x].count else { return nil } | |
guard Step.maze[x][y] else { return nil } | |
guard !Step.mazeVisited[x][y] else { return nil } | |
self.x = x | |
self.y = y | |
Step.mazeVisited[x][y] = true | |
} | |
static var maze: [[Bool]] = [] { | |
didSet { | |
mazeVisited = Array(repeating: Array(repeating: false, count: maze[0].count), count: maze.count) | |
} | |
} | |
static private (set) var mazeVisited: [[Bool]] = [] | |
func goLeft() -> Step? { | |
return Step(x-1, y) | |
} | |
func goRight() -> Step? { | |
return Step(x+1, y) | |
} | |
func goTop() -> Step? { | |
return Step(x, y-1) | |
} | |
func goBottom() -> Step? { | |
return Step(x, y+1) | |
} | |
} | |
// Start is in [0][0] | |
func findShortest(maze: [[Bool]], end: (x: Int, y: Int)) -> Int { | |
Step.maze = maze | |
let begin = Step(0, 0)! | |
var result: [[Step]] = [[begin]] | |
var oneProgress = true | |
while (oneProgress) { | |
var newResult: [[Step]] = [] | |
oneProgress = false // assume the end | |
for index in 0..<result.count { | |
guard !result.isEmpty else { return 0 } | |
if let last = result[index].last { | |
guard !(last.x == end.x && last.y == end.y) else { | |
newResult.append(result[index]) // add unchanged | |
continue | |
} | |
if let step = last.goLeft() { | |
oneProgress = true | |
var newRow = result[index] | |
newRow.append(step) | |
newResult.append(newRow) | |
} | |
if let step = last.goRight() { | |
oneProgress = true | |
var newRow = result[index] | |
newRow.append(step) | |
newResult.append(newRow) | |
} | |
if let step = last.goBottom() { | |
oneProgress = true | |
var newRow = result[index] | |
newRow.append(step) | |
newResult.append(newRow) | |
} | |
if let step = last.goTop() { | |
oneProgress = true | |
var newRow = result[index] | |
newRow.append(step) | |
newResult.append(newRow) | |
} | |
} | |
} | |
result = newResult | |
} | |
let counts = result.flatMap { $0.count } | |
return counts.reduce(Int.max) { min($0, $1) } | |
} | |
findShortest(maze: [[true, true], | |
[true, false]], end: (x: 1, y: 0)) | |
findShortest(maze: [[true, false, true], | |
[true, false, true], | |
[true, true, true]], end: (x: 0, y: 2)) | |
findShortest(maze: [[true, false, true, true], | |
[true, false, true, true], | |
[true, false, false, true], | |
[true, true, true, true]], end: (x: 0, y: 2)) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment