StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>Perhaps you noticed that my earlier answer was deleted. Although I was poking fun, by suggesting only that the "computer display in red all the dead-ends and in green the path that connects the entrance to the exit," at the same time, it was a metaphor for what I understand of the functional paradigm - a kind of encompassing precomputed certainty. Given my limited understanding and knowledge, I worked on an example in Haskell that avoids a recursive depth search, computing paths for a 4x5 maze, given an array where each cell in the maze (i.e., each array element) contains only the indexes of the cells it can connect to; and -1 for the entrance, -2 for the exit. (You can see an 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 seems to fit in with the spirit of this question (and thank you, Andrew, for the interesting challenge/direction).</p> <pre><code> {-M A Z 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 a b, c <- sequences, b /= c, not (hasStart c || hasEnd c), isSequenced b c, d <- sequences, c /= d, not (hasStart d || hasEnd d), isSequenced c d, e <- sequences, hasEnd e, isSequenced d e] 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] </code></pre>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload