{-|
Module      : Mazelib.Solve
Description : A module for solving mazes generated by Mazelib.Generate
Copyright   : (c) Kevin Vicente, 2023
License     : GPL-3
Maintainer  : kvicente@fastmail.com
Stability   : experimental
Portability : portable
-}

module Mazelib.Solve 
    (
      SolutionMethod(..)
    , Path
    , Maze
    , Exits 
    , mazeToString
    , solveMaze
    , cleanPath
    ) where 


import qualified System.Random as Rand
import Data.Maybe (fromMaybe)
import Data.List (elemIndices)
import Mazelib.Common

-- | Various methods for solving a 2D maze
data SolutionMethod = 
    -- | This is a relatively simple random walk through the maze until we
    -- reach the exit
    RandomWalker |
    -- | Almost identical to the random walk except we don't revisit the last
    -- visited cell
    RecursiveBacktracker

-- | A function to remove cells that are not on the path from the start to the 
-- end of the maze -- a natural byproduct of some solution methods.
cleanPath :: Path -> Path
cleanPath path = 
    let removeSlice cell cells =
            case elemIndices cell cells of
                [] -> cells
                indices -> drop (maximum indices + 1) cells
        recursivelyRemove index cells = 
            if index >= length cells then 
                cells 
            else let 
                i = index + 1
                before = take i cells 
                after = drop i cells
            in recursivelyRemove i $
                before ++ removeSlice (cells !! index) after
    in recursivelyRemove 0 path

solveRandomWalker :: (Int, Int) -> Maze -> Exits -> Rand.StdGen -> Path -> Path
solveRandomWalker current maze exits gen path =
    let neighbors = getNeighbors current maze False False 1
        (next, gen') = chooseRand gen neighbors
    in if snd exits `elem` neighbors then
        path ++ [snd exits]
    else case next of 
        Just n -> solveRandomWalker n maze exits gen' (path ++ [n])
        Nothing -> path

solveRecursiveBacktracker ::
    (Int, Int)  ->
    Maze        ->
    Exits       ->
    Rand.StdGen ->
    Path        ->
    Path
solveRecursiveBacktracker current maze exits gen path =
    let neighbors = getNeighbors current maze False False 1
        -- Don't revisit the previous cell.
        filtered = filter (\ n -> n /= last (init path)) neighbors
        (next, gen') = chooseRand gen 
            (if null filtered then neighbors else filtered)
    in if snd exits `elem` neighbors  then
        path ++ [snd exits]
    else case next of 
        Just n -> solveRecursiveBacktracker n maze exits gen' (path ++ [n])
        Nothing -> path


-- | The function used to compute the solution to a maze in the form of a path 
solveMaze ::
    SolutionMethod    -> -- ^ The desired solution method
    Maze              -> -- ^ A maze generated by generateMaze
    Exits             -> -- ^ The associated entrance and exit
    Maybe Rand.StdGen -> -- ^ Possibly an RNG, or Nothing to use the default
    Path                 -- ^ The resulting path without reduction
solveMaze method maze (start, end) mgen =
    let gen = fromMaybe (Rand.mkStdGen 0) mgen
        replacedStart = replace start maze False
        replacedEnd = replace end replacedStart False
    in case method of 
        RandomWalker -> 
            solveRandomWalker start replacedEnd (start, end) gen [start]
        RecursiveBacktracker -> let
            neighbors = getNeighbors start maze False False 1 
            (next, gen') = chooseRand gen neighbors
            neighbor = fromMaybe start next
            in solveRecursiveBacktracker neighbor replacedEnd (start, end) gen'
                [start, neighbor]