Welcome to Maze’s documentation!

Table of Contents

• Welcome to Maze’s documentation!
  • Constants
  • Data Structure Definitions
    • Maze
    • Example
• Functions (Internal)
  • bit-test
  • bit-set
  • bit-clear
  • get-wall
  • set-wall
  • walls-up
  • get-border
  • set-border
  • all-walls-up?
• Functions (Interfaces)
  • get-solution
  • set-solution
  • swap-2d
  • reset-2d
  • get-2d
  • get-direction
  • show-maze
• Functions (Your Work)
  • solve-maze-dfs
  • solve-maze-bfs

Constants

Variable Name	Value
empty-node	0
test-maze	A 2-d vector of maze
reverse-function	Key-Value combination of opposite directions.

Data Structure Definitions

Maze

Mazes are defined as 2-D vector.

The top-left(north-westmost) corner has the coordinate of [0 0]. (i.e. (get-in maze [0 0])). First index is the row number, and the second is column. (i.e. The tile right below the top-left corner would be (get-in maze [1 0]))

Up is north, left is west and so on.

Each element in the vector contains a node, represented as an integer. Each bit of the integer carries information about the maze, described as below.

Bit	Meaning (if this bit is set to 1)
0	There’s a wall to the north of the current node.
1	There’s a wall to the east of the current node.
2	There’s a wall to the south of the current node.
3	There’s a wall to the west of the current node.
4	North side of this node is the border of the maze.
5	East side of this node is the border of the maze.
6	South side of this node is the border of the maze.
7	West side of this node is the border of the maze.
8	Solution path goes north on this node
9	Solution path goes east on this node.
10	Solution path goes south on this node.
11	Solution path goes west on this node.

Bits 0-7 are about the maze, which will be generated by the maze generator. Bits 8-11 are about the solution, with should be calculated by your program.

Other bits are unused, but can be unused to store information at your discretion.

Example

Here’s an example of how this maze-saving mechanism works.

+-+-+-+-+-+-+-+-+-+-+
|A  | |       |     |
+-+ + + +-+ +-+ + +-+
| | | | | | |   |   |
+ + + + + + + +-+-+ +
| | | | | |       | |
+ + + + + +-+-+-+ + +
| | | |     |   | | |
+ + + +-+ +-+ + + + +
| | |     |   | | | |
+ + +-+ +-+ +-+ +-+ +
| |   |   | |    B  |
+ +-+ +-+ + +-+-+-+ +
| |   | | |   |   | |
+ + +-+ + +-+ + +-+ +
| |   |   | | |     |
+ +-+ + +-+ + + +-+-+
|   | |     | | |   |
+ + + +-+-+-+ + +-+ +
| |           |     |
+-+-+-+-+-+-+-+-+-+-+

For the cell labeled A, it have borders to its north and west, and walls to its north, west and east. Therefore, the value here would be binary 1001 1101, which converts to a decimal value of 157.

For the cell labeled B, it have walls to its north and south. Therefore, the value here would be binary 0000 0101, which converts to a decimal value of 5.

In practice, you may or may not have to deal with the bits directly. Functions are provided to manipulate them.

Functions (Internal)

These functions are provided for generating maze, testing, etc. You may or may not make use of these functions.

bit-test

(defn bit-test [a b])

Intepret the input number in its binary representation, then test a given bit.

Input

• a: The number to be tested.
• b: The bit to read.

Output True or false.

Example

(bit-test 5 0) => True
(bit-test 5 1) => False

bit-set

(defn bit-set [a b])

Intepret the input number in its binary representation, then set a given bit and return the number.

Input

• a: The number to be changed.
• b: The bit to set.

Output The modified number.

Example

(bit-set 5 0) => 5
(bit-set 5 1) => 7

bit-clear

(defn bit-clear [a b])

Intepret the input number in its binary representation, then clear a given bit and return the number.

Input

• a: The number to be changed.
• b: The bit to clear (set to 0).

Output The modified number.

Example

(bit-clear 5 0) => 4
(bit-clear 5 1) => 5

get-wall

(defn get-wall [node dir])

Check if there’s a wall in the given direction.

Input

• node: The integer content of the node. i.e. 157 for [0 0] of the given test maze.
• dir: Direction. One of :n :s :w :e, for north, south, west and east respectively.

Output True or False.

set-wall

(defn set-wall [node dir up])

Add or remove a wall at the given direction.

Input

• node: The integer content of the node. i.e. 157 for [0 0] of the given test maze.
• dir: Direction. One of :n :s :w :e, for north, south, west and east respectively.
• up: If true, a wall will be set at the given direction. If false, the wall in such direction will be removed.

Output The modified integer content for the node.

walls-up

(defn walls-up [node])

Add walls to all four directions of the given node. Will not change border or solution bits.

Input

• node: The integer content of the node. i.e. 157 for [0 0]

Output The modified integer content for the node.

get-border

(defn get-border [node dir])

Check if there’s a border in the given direction. Similar to get-wall.

Input

• node: The integer content of the node. i.e. 157 for [0 0] of the given test maze.
• dir: Direction. One of :n :s :w :e, for north, south, west and east respectively.

Output True or False.

set-border

(defn set-wall [node dir up])

Add or remove a border at the given direction. Similar to set-wall.

Input

• node: The integer content of the node. i.e. 157 for [0 0] of the given test maze.
• dir: Direction. One of :n :s :w :e, for north, south, west and east respectively.
• up: If true, a wall border be set at the given direction. If false, the border in such direction will be removed.

Output The modified integer content for the node.

all-walls-up?

(defn all-walls-up? [m [r c]])

Check if the node at [r c] have all four wall set. (i.e. stranded).

This function is used for generating the maze.

Input

• m: 2-d vector representation of the maze.
• [r c]: Coordinate of the node to check, in the format of [row col]

Output True if all four walls are set.

Functions (Interfaces)

These functions are used for reading mazes and writing back solutions.

Though you can implement your own version, there’s a big chance you will make use of some of these.

get-solution

(defn get-solution [node dir])

Given the content of a node, check if the solution path goes in the given direction at this node. The return value of the function depends on what you have done to the maze. Executing it on an unsolved maze will always return false.

Input

• node: The integer content of the node. i.e. 157 for [0 0] of the given test maze.
• dir: Direction. One of :n :s :w :e, for north, south, west and east respectively.

Output True or False

set-solution

(defn set-wall [node dir up])

Given the content of a node, modify the solution bits and return the modified value.

Input

• node: The integer content of the node. i.e. 157 for [0 0] of the given test maze.
• dir: Direction. One of :n :s :w :e, for north, south, west and east respectively.
• up: If true, the solution bit is set at the given direction. If false, the solution path in such direction will be removed.

Output The modified integer content for the node.

swap-2d

(defn reset-2d [v x y f])

Modify an element in the given 2-d vector with the function f. In other languages, v[x][y]=f(v[x][y])

Input

• v: A 2-d matrix. In this context, it’s probably the maze you’re working on.
• [x y]: Coordinate in [row col] format.
• f: The function for modifying the value. Should accept an integer and return an integer.

Output The modified 2-d vector.

reset-2d

(defn reset-2d [v x y content])

Replace an element in the 2d matrix. In other languages, v[x][y]=content

Input

• v: A 2-d matrix. In this context, it’s probably the maze you’re working on.
• [x y]: Coordinate in [row col] format.
• content: The new value for the given index.

Output The modified 2-d vector.

get-2d

(defn reset-2d [v x y content])

Get an element in the 2d matrix. In other languages, return v[x][y]

Input

• v: A 2-d matrix. In this context, it’s probably the maze you’re working on.
• [x y]: Coordinate in [row col] format.

Output The content at given index.

get-direction

..code-block:: clojure

(defn get-direction [[row-a col-a] [row-b col-b]])

Get the direction from [row-a col-a] to [row-b col-b]

Input

• [row-a col-a]: The source coordicate.
• [row-b col-b]: The target coordinate.

Output Direction. One of :n :s :w :e, for north, south, west and east respectively.

Example ..code-block:: clojure

(get-direction [0 0] [1 0]) => :s (get-direction [0 0] [0 1]) => :e

show-maze

(defn show-maze [m])

Print a maze with ascii characters. Borders are double-lined, walls are single-lined, and the solution path will be indicated with *.

Functions (Your Work)

solve-maze-dfs

(defn solve-maze-dfs [maze start-loc goal-loc])

Solves a maze using the DFS algorithm. It should set the solution bits of the maze to show the path, and return the corresponding maze.

Input

• maze: The maze for you to solve.
• start-loc: Starting location, a vector in the form of [row col].
• goal-loc: Goal, a vector in the form of [row col].

Output A maze in 2-d vector representation, with the solution bits set to reflect the path.

Example Call

(solve-maze-dfs test-maze [0 0] [0 2])

solve-maze-bfs

(defn solve-maze-bfs [maze start-loc goal-loc])

Solves a maze using the BFS algorithm. It should set the solution bits of the maze to show the path, and return the corresponding maze.

In this version, goal-loc will be a set of coordicates. You shall terminate the program whenever any of the goals is reached. That goal should be the one closest to the starting location.

Input

• maze: The maze for you to solve.
• start-loc: Starting location, a vector in the form of [row col].
• goal-loc: Goal, a set of vectors in the form of #{[row1 col1] [row2 col2]}

Output A maze in 2-d vector representation, with the solution bits set to reflect the path.

Example Call

(solve-maze-bfs test-maze [0 0] #{[0 2] [1 0]})