The easiest way to solve the maze without volatility

Question

After exploring some of the Scala and the benefits of FP, I reassess some of my previous CS assignments to better understand FP. However, I received one task that seems inappropriate for implementation using FP (or at least a trivial translation).

When solving a simple two-dimensional maze, you need to remember which nodes were visited. However, without a general state, how can each recursive call find out which nodes have considered other recursive calls? I could pass the labyrinth as a parameter for each recursive call and return a new labyrinth containing the places visited, but it is too computationally intensive to copy the entire labyrinth of each recursive call. Is a more advanced approach required to implement an immutable solution for mazes?

Answer 1

You can pass a collection containing the visited nodes (or their identifiers / names if the nodes themselves are comparable for equality in your setup). Adding elements to an immutable set usually takes O(log n) , so it checks to see if the element is in the set. So much cheaper than copying a maze.

Answer 2

You may have noticed that my previous answer has been deleted. Although I was angry, suggesting only that “the computer display is in red, all the dead ends and the green path connecting the input to the output”, at the same time it was a metaphor for what I understand from the functional paradigm - a kind of comprehensive predetermined certainty. Given my limited understanding and knowledge, I worked on an example in Haskell that avoids a recursive depth search, computational paths for a 4x5 maze, given an array in which each cell in the maze (i.e., each element of the array) contains only cell indices, to which he can connect; and -1 to enter, -2 to exit. (You can see the outline of the maze at the top of the code section.) I know more experienced programmers could do much more and better. Please let me know if this sounds like the spirit of this question (and thanks, Andrey, for an interesting task / direction).

  {-MAZ E-} [E]=[ ]=[ ]=[ ] | [ ]=[ ]=[ ]=[ ] | | [ ] [ ]=[ ] [ ] | | | [ ] [ ]=[ ]=[ ] | | [ ]=[ ]=[ ]=[E] import Data.List import Data.Maybe --Each element in the maze lists the indexes of connected cells, '-1' for entrance, '-2' for exit maze = [[-1,1], [0,2,5], [1,3], [2], [5], [4,6,1,9], [5,7], [6,11], [12], [5,13,10], [9], [7,15], [8,16], [14,9,17], [13,15], [14,11], [12,17], [13,16,18], [17,19], [18,-2]] maze' = [[-1,1], [0,2], [1,3], [2,7], [8,5], [4,6], [5,7], [3,6], [4,9], [8,10], [9,11], [10,15], [16,13], [12,14], [13,15], [11,14], [12,17], [16,18], [17,19], [18,-2]] index a = fromJust $ elemIndex a maze indexes a = map (index) a areConnected index_a index_b = elem index_a (maze !! index_b) isStart a --(a :: cell) | elem (-1) a = True | otherwise = False isEnd a --(a :: cell) | elem (-2) a = True | otherwise = False hasStart a --(a :: [cell]) | isStart (head a) = True | otherwise = False hasEnd a --(a :: [cell]) | isEnd (last a) = True | otherwise = False isSequenced (w:x:xs) (y:z:zs) --includes possibility of overlap since we do not know how many cells comprise the solution | areConnected (index $ last xs) (index y) || last xs == y || let (b:c:cs) = reverse (w:x:xs) in [c,b] == [y,z] = True | otherwise = False removeBacktracks (x:xs) | (x:xs) == [] = [] | xs == [] = [x] | x == head xs = removeBacktracks xs | length xs > 1 && x == let (y:ys) = xs in head ys = removeBacktracks (tail xs) | otherwise = x : removeBacktracks xs --list dead ends dead_ends = filter (\x -> length x==1 && find (==(-1)) x == Nothing) maze dead_ends_indexes = map (index) dead_ends connectedToDeadEnd (x:xs) | x `elem` dead_ends_indexes = True | not (x `elem` dead_ends_indexes) && xs == [] = False | otherwise = connectedToDeadEnd xs --list first from dead ends first_from_dead_ends = filter (\x -> length x==2 && find (==(-1)) x == Nothing && connectedToDeadEnd x) maze --create sequences filtered = [l | l <- maze, not (elem l dead_ends) && not (elem l first_from_dead_ends)] sequences_3 = [[a,b,c] | a <- filtered, not (isEnd a), b <- filtered, not (isEnd b || isStart b), areConnected (index a) (index b), c <- filtered, not (isStart c), a /= c, areConnected (index b) (index c)] sequences_4 = [a ++ [b] | a <- sequences_3, not (hasEnd a), b <- filtered, last a /= b, areConnected (index $last a) (index b)] paths = take 1 [indexes $ concat [a, b, c, d, e] | a <- sequences, hasStart a, b <- sequences, not (hasStart b || hasEnd b), isSequenced ab, c <- sequences, b /= c, not (hasStart c || hasEnd c), isSequenced bc, d <- sequences, c /= d, not (hasStart d || hasEnd d), isSequenced cd, e <- sequences, hasEnd e, isSequenced de] where sequences | length filtered < 16 = sequences_3 | otherwise = sequences_4 path = removeBacktracks $ head paths main = print path --outputs: [0,1,5,9,13,17,18,19]