Task

For a maze generated by this task, write a function
that finds (and displays) the shortest path between two cells.



Note that because these mazes are generated by the Depth-first search algorithm, they contain no circular paths,
and a simple depth-first tree search can be used.




enum errors: Error {
    //Occurs when a start or end position is given that is outside of bounds
    case IndexOutsideMazeBoundary
}
///Used to solve any maze generated by the swift implementation of maze generator at:
///https://www.rosettacode.org/wiki/Maze_generation#Swift
class MazeSolver {
    ///your starting index position in the maze
    var startPos: (Int, Int)
    /// the end index position you are trying to reach within the maze
    var endPos: (Int, Int)
    /// a maze of [[INT]] where each value is between 1 and 14.
    /// each number representing a
    var maze: [[Int]]
    var visitedSpaces: [(Int, Int)]
    
    init(maze: [[Int]]) {
        self.startPos = (0, 0)
        self.endPos = (0, 0)
        /// a maze that consists of a array of ints from 1-14 organized to
        /// create a maze like structure.
        /// Each number represents where the walls and paths will be
        /// ex. 2 only has a path south and 12 has paths E or W
        self.maze = maze
        /// spaces each branch has visited to stop from searching previously explored
        /// areas of the maze
        self.visitedSpaces = []
    }

    /// determine if the user has previously visited the given location within the maze
    func visited(position: (Int, Int)) -> Bool {
        return visitedSpaces.contains(where: {$0 == position})
    }
    
    /// used to translate the mazes number scheme to a list of directions available
    ///  for each number. DirectionDiff for N would be  (0, -1) for example
    func getDirections(positionValue: Int) -> [(Int, Int)] {
        
        switch positionValue {
        case 1:
            return [Direction.north.diff]
        case 2:
            return [Direction.south.diff]
        case 3:
            return [Direction.north.diff, Direction.south.diff]
        case 4:
            return [Direction.east.diff]
        case 5:
            return [Direction.north.diff, Direction.east.diff]
        case 6:
            return [Direction.south.diff, Direction.east.diff]
        case 7:
            return [Direction.north.diff, Direction.east.diff, Direction.south.diff]
        case 8:
            return [Direction.west.diff]
        case 9:
            return [Direction.north.diff, Direction.west.diff]
        case 10:
            return [Direction.west.diff, Direction.south.diff]
        case 11:
            return [Direction.north.diff, Direction.south.diff, Direction.west.diff]
        case 12:
            return [Direction.west.diff, Direction.east.diff]
        case 13:
            return [Direction.north.diff, Direction.east.diff, Direction.west.diff]
        case 14:
            return [Direction.east.diff, Direction.south.diff, Direction.west.diff]
        default:
            return []
        }
    }
    
    /// calculate and return all paths branching from the current position that haven't been explored yet
    func availablePaths(currentPosition: (Int, Int), lastPos: (Int, Int)) -> [(Int, Int)] {
        /// all available paths to be returned
        var paths: [(Int, Int)] = []
        /// the maze contents at the given position (ie the maze number)
        let positionValue = maze[currentPosition.0][ currentPosition.1]
        /// used to build the new path positions and check them before they
        /// are added to paths
        var workingPos: (Int, Int)
        
        // is the maze at a dead end and not our first position
        if ([1, 2, 4, 8].contains(positionValue) && currentPosition != lastPos) {
            return []
        }
        
        /// the directions available based on the maze contents of our
        /// current position
        let directions: [(Int, Int)] = getDirections(positionValue: positionValue)
        
        /// build the paths
        for pos in directions {
            workingPos = (currentPosition.0 + pos.0, currentPosition.1 + pos.1)
            
            if (currentPosition == lastPos || (workingPos != lastPos && !visited(position: workingPos))) {
                paths.append(workingPos)
            }
        }
        
        return paths
    }
    
    /// prints a model of the maze with
    /// O representing the start point
    /// X representing the end point
    /// * representing traveled space
    /// NOTE: starting pos and end pos represent indexes and thus start at 0
    func solveAndDisplay(startPos: (Int, Int), endPos: (Int, Int)) throws {
        if (startPos.0 >= maze.count || startPos.1 >= maze[0].count) {
            throw errors.IndexOutsideMazeBoundary
        }
        
        /// the position you are beginning at in the maze
        self.startPos = startPos
        /// the position you wish to get to within the maze
        self.endPos = endPos
        /// spaces each branch has visited to stop from searching previously explored
        /// areas of the maze
        self.visitedSpaces = []
        
        self.displaySolvedMaze(finalPath: solveMaze(startpos: startPos, pathSoFar: [])!)
        
    }
    
    /// recursively solves our maze
    private func solveMaze(startpos: (Int, Int), pathSoFar: [(Int, Int)]) -> [(Int, Int)]? {
        /// marks our current position in the maze
        var currentPos: (Int, Int) = startpos
        /// saves the spaces visited on this current branch
        var currVisitedSpaces : [(Int, Int)] = [startpos]
        /// the final path (or the path so far if the end pos has not been reached)
        /// from the start position to the end position
        var finalPath: [(Int, Int)] = pathSoFar
        
        /// all possible paths from our current position that have not been explored
        var possiblePaths: [(Int, Int)] = availablePaths(currentPosition: startpos, lastPos: pathSoFar.last ?? startpos)
                
        // move through the maze until you come to a position that has been explored, the end position, or a dead end (the 
        // possible paths array is empty)
        while (!possiblePaths.isEmpty) {
            // found the final path
            guard (currentPos != self.endPos) else {
                finalPath.append(contentsOf: currVisitedSpaces)
                return finalPath
            }
            // multiple valid paths from current position found
            // recursively call new branches for each valid path
            if (possiblePaths.count > 1) {
                visitedSpaces.append(contentsOf: currVisitedSpaces)
                finalPath.append(contentsOf: currVisitedSpaces)
                // for each valid path recursively call each path
                // and if it contains the final path
                // ie it found the endpoint, return that path
                for pos in possiblePaths {
                    let path = solveMaze(startpos: pos, pathSoFar: finalPath)
                    
                    if (path != nil) {
                        return path
                    }
                }
                // otherwise this branch and it's sub-branches
                // are dead-ends so kill this branch
                return nil
            }
            // continue moving along the only path available
            else {
                // update current path to our only available next
                // position
                currentPos = possiblePaths[0]
                
                // calculate the available paths from our new
                // current position
                possiblePaths = availablePaths(currentPosition: currentPos, lastPos: currVisitedSpaces.last ?? currentPos)
                // update the visited spaces for this branch
                currVisitedSpaces.append(currentPos)
            }
        }
        
        // if our new current position is the endpos return our final path
        if (currentPos == self.endPos) {
            finalPath.append(contentsOf: currVisitedSpaces)
            return finalPath
        }
        else {
            return nil
        }
    }
    
    // Reference: https://www.rosettacode.org/wiki/Maze_generation#Swift
    // adapts the display method used in the swift implementation of the maze generator we used for this app to display the maze 
    // solved
    func displaySolvedMaze(finalPath: [(Int, Int)]) {
        /// all cells are 3 wide in the x axis
        let cellWidth = 3
        for j in 0..<y {
            // Draw top edge
            // if mark corner with +, add either (cell width) spaces or - to the topedge var dependin on if it is a wall or not
            var topEdge = ""
            for i in 0..<x {
                topEdge += "+"
                topEdge += String(repeating: (maze[i][j] & Direction.north.rawValue) == 0 ? "-" : " ", count: cellWidth)
            }
            topEdge += "+"
            print(topEdge)

            // Draw left edge
            //through the center of the cell if is a wall add |  if not a space
            // then if it is travelled add " * " otherwise just 3 spaces then
            //cap it with a | at the end for the right most wall
            var leftEdge = ""
            for i in 0..<x {
                leftEdge += (maze[i][j] & Direction.west.rawValue) == 0 ? "|" : " "
                
                if (finalPath.first! == (i, j)) {
                    leftEdge += " O "
                }
                else if (finalPath.last! == (i, j)) {
                    leftEdge += " X "
                }
                else {
                    if (finalPath.contains(where: {$0 == (i, j)})) {
                        leftEdge += " * "
                    }
                    else {
                        leftEdge += String(repeating: " ", count: cellWidth)
                    }
                }
            }
            leftEdge += "|"
            print(leftEdge)
        }

        // Draw bottom edge
        // adds + on corners and _ everywhere else
        var bottomEdge = ""
        for _ in 0..<x {
            bottomEdge += "+"
            bottomEdge += String(repeating: "-", count: cellWidth)
        }
        bottomEdge += "+"
        print(bottomEdge)
    }

}
