Maze Solver

PA 6 — Due: Fri Nov 10 11pm CT

Recall the academic integrity policy: turn in your own work and cite all sources.

The summary description of this assignment is short and sweet: Given a rectangular maze with one entrance and one exit, write a program that finds a viable path (if any).

For example, given a maze represented as a file…

SXXX
 X
   X
 XXXF

… your program should produce a path of locations:

% cabal run maze-solver -- mazes/maze-02.txt
Just [(0,0),(1,0),(2,0),(3,0),(2,0),(2,1),(2,2),(1,2),(1,3),(1,4),(2,4),(3,4)]

(No) Starter Code

The starter repository contains: a .cabal file, a mostly-empty .hs file, and a couple simple test mazes. So, this is your opportunity to model the problem and organize a solution however you see fit. Because the problem definition and likely solutions are relatively short, code style constitutes a slightly larger fraction of the grading rubric than recent assignments.

Input Format

A maze is represented as an input file, comprising a rectangular grid of the following characters:

• S: Entrance (only one)
• F: Exit (only one)
• X: Wall
• Space: Open

Your program can assume a valid input format. Do whatever you want if given an invalid maze; print a polite error message and exit gracefully, or not.

Output Format

The standard output of the program should be one line, displaying a Maybe Path through the maze. This String representation should be the result of calling show on the Maybe Path; do not implement a custom display function.

type Path = [Pos]
type Pos  = (Row, Col)
type Row  = Int
type Col  = Int

The Position (0,0) corresponds to the top-left grid cell and (n-1,m-1) to the bottom-right, where n is the number of rows and m is the number of columns.

Recommendations

Consider using Data.Set and/or Data.Map to efficiently represent boards.

Look for opportunities to use (<$>), (<*>), (>>=), guard, or any of your own helper functions.

Consider implementing an “orMaybe” function of type Maybe a -> Maybe a -> Maybe a, and look for opportunities to use foldr orMaybe Nothing. (This pattern is not captured by Monad but is captured by MonadPlus albeit in a way we haven’t yet understood. There is a related class called Alternative that includes (<|>) and asum, which for Maybe are defined to be firstJust and foldr firstJust (<|>) Nothing, respectively.)

Do a relatively simple brute-force search (for example, “flood fill” processes neighboring cells in a fixed order). But consider that a “sequential” rather than a “parallel” approach may scale better to larger mazes with more paths to search.

For testing, you should probably implement a function that walks a path to check that it goes from start to finish without walking through walls. Speaking of tests…

Test Mazes

… you are required to add at least five new valid mazes to the mazes/ directory. Don’t forget to add them to your repository before you commit and push!

Animation (Extra Credit)

For extra credit, offer an optional command-line flag animate to animate the path rather than just displaying its coordinates.

% cabal run maze-solver -- mazes/maze-02.txt animate

You are free to design the (text-based) animation however you like. For example, you could animate steps upon key presses. Or you could implement a timed animation, in which case you’ll need some kind of timer — check out Control.Timer.Tick or Control.Concurrent.Timer. If you use additional packages, make sure to submit the updated .cabal file.

Grading

Here is an outline of the grading rubric (10 points total):

• 7.0 Correct code (tested on the sample mazes, plus more)
• 2.0 Clean code (based on the style guidelines)
• 1.0 ≥5 valid new mazes
• 0.0 Extra credit (+1.0)

Sanity Check

Once you are finished, check that you added, committed, and pushed everything to your repository before the deadline (or within an eligible late period):

https://github.com/UChicago-PL/cs223-fa23-pa-6-maze-solver-USERNAME