Maze solving: Difference between revisions
→{{header|Haskell}}: Adjusted some names to side-step the wiki formatting issue
No edit summary |
(→{{header|Haskell}}: Adjusted some names to side-step the wiki formatting issue) |
||
Line 1,608:
<lang haskell>#!/usr/bin/runhaskell
import Data.Maybe (fromMaybe)
-- given two points, returns the average of them
average :: (Int, Int) -> (Int, Int) -> (Int, Int)
average (x, y) (
-- given a maze and a tuple of position and wall position, returns
Line 1,630:
-- given a maze and a position, draw a '*' at that position in the maze
draw :: [String] -> (Int, Int) -> [String]
draw maze (x, y) =
in substitute maze y $ substitute row x '*'
-- given a maze, a previous position, and a list of tuples of potential
-- new positions and their wall positions, returns the solved maze, or
-- None if it cannot be solved
tryMoves ::
-> [((Int, Int), (Int, Int))]
-> Maybe [String]
tryMoves _ _ [] = Nothing
tryMoves maze prevPos ((newPos, wallPos):more) =
case
-- given a maze, a new position, and a previous position, returns
-- the solved maze, or None if it cannot be solved
-- (assumes goal is upper-left corner of maze)
let newPositions = [(x, y - 2), (x + 4, y), (x, y + 2), (x - 4, y)]
notPrev
wallPositions = map (average pos)
zipped = zip
legalMoves = filter (notBlocked maze) zipped
in tryMoves maze pos legalMoves
Line 1,660 ⟶ 1,664:
-- (starts at lower right corner and goes to upper left corner)
solve :: [String] -> Maybe [String]
solve maze =
where
where startx = length (head maze) - 3▼
▲ start = (startx, starty)
start = (startx, starty)
-- takes unsolved maze on standard input, prints solved maze on standard output
main =
in interact main_
</lang>
{{out}}
<pre>
+---+---+---+---+---+---+---+---+---+---+---+
|