Shortest maze

ShortestMaze.swift

//: 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))