1. Create the following ADTs.
(a) Write the constructor function makestk, predicate function emptystk and mutator functions pushstk and popstk:
i. makestk returns a new stack in the form of a tagged tuple: ('stack',[]).
e.g. >>> cellstk=makestk()
>>> cellstk
('stack', [])
ii. emptystk returns True or False depending on whether the given stack is empty or not.
e.g. >>> emptystk(cellstk)
True
iii. pushstk accepts a stack and an element, and adds the element to the stack at position 0 (see part (b) below for the creation of cell0).
e.g. >>> pushstk(cellstk,cell0)
>>> cellstk
('stack', [('cell', (0, 0), ['t', 'b', 'r', 'l'])])
iv. popstk removes the element at position 0 of the given stack.
e.g. >>> popstk(cellstk)
('cell', (0, 0), ['t', 'b', 'r', 'l'])
>>> cellstk
('stack', [])
(b) Write a constructor function called makecell, accessor functions getx, gety and getwalls, and mutator functions removetw, removebw, removerw, removelw.
i. makecell accepts a tuple which consists of the x and y co-ordinate of the cell being created. It returns a cell in the form of a tagged tuple:
('cell',(x,y),['t','b','r','l']).
The list represents the four walls of the cell: top, bottom, right and left.
e.g. >>> cell0=makecell((0,0))
>>> cell0
('cell', (0, 0), ['t', 'b', 'r', 'l'])
ii. getx and gety return the x and y co-ordinates (respectively) of a given cell.
e.g. >>> getx(cell0)
0
iii. getwalls returns the list of walls that are intact for a given cell
e.g. >>> getwalls(cell0)
['t', 'b', 'r', 'l']
iv. remove?w removes the associated wall from the list of walls of a given cell.
e.g. >>> removetw(cell0)
>>> cell0
('cell', (0, 0), ['b', 'r', 'l'])
2. Write the function makegrid. This function accepts a width and height and creates a grid/matrix of cells. The width gives the number of columns and the height the number of rows of the grid that should be created.
e.g. >>> makegrid(4,5)
[('cell', (0, 0), ['t', 'b', 'r', 'l']), ('cell', (0, 1),
['t', 'b', 'r', 'l']), ('cell', (0, 2), ['t', 'b', 'r', 'l']),
('cell', (0, 3), ['t', 'b', 'r', 'l']), ('cell', (0, 4), ['t',
'b', 'r', 'l']), ('cell', (1, 0),['t', 'b', 'r', 'l']),
('cell', (1, 1), ['t', 'b', 'r', 'l']), ('cell', (1, 2), ['t',
'b', 'r', 'l']), ('cell',(1, 3), ['t', 'b', 'r', 'l']),
('cell', (1, 4), ['t', 'b', 'r', 'l']), ('cell', (2, 0), ['t',
'b', 'r', 'l']), ('cell', (2, 1), ['t', 'b', 'r', 'l']),
('cell', (2, 2), ['t', 'b', 'r', 'l']), ('cell', (2, 3), ['t',
'b','r', 'l']), ('cell', (2, 4), ['t', 'b', 'r', 'l']),
('cell', (3, 0), ['t', 'b', 'r', 'l']), ('cell', (3, 1),['t',
'b', 'r', 'l']), ('cell', (3, 2), ['t', 'b', 'r', 'l']),
('cell', (3, 3), ['t', 'b', 'r', 'l']), ('cell',(3, 4), ['t',
'b', 'r', 'l'])]
3. Given a cell, we must determine its neighbouring cells i.e. those with which it shares a wall. In the diagram below, the cells with an x are the neighbours of the cell c. Write the function getneighbours that accepts a cell, the width and height of the grid, and returns all neighbours of the given cell.
e.g. >>> getneighbours(cell0,4,5)
[('cell', (0, 1), ['t', 'b', 'r', 'l']), ('cell', (1, 0), ['t', 'b', 'r', 'l'])]
4. We must also be able to remove common walls between two cells. Write the function removewalls that accepts two cells and removes the wall that is common between the two (hint: any cell will have at most, one wall in common with another).
e.g. >>> cell1=makecell((0,1))
>>> removewalls(cell0,cell1)
>>> cell0
('cell', (0, 0), ['t', 'r', 'l'])
>>> cell1
('cell', (0, 1), ['b', 'r', 'l'])
5. We also need to know, given a cell, which of its neighbours has all of its walls intact. Write the function wallsintact that accepts the grid and a list of neighbouring cells and returns those whose four walls are intact.
e.g. >>> intact=wallsintact(grid,neighbours)
>>> intact
[('cell', (2, 3), ['t', 'b', 'r', 'l']), ('cell', (3, 2), ['t', 'b', 'r', 'l']), ('cell', (3, 4), ['t', 'b', 'r', 'l'])]
6. Finally, write the function createmaze that accepts a width and height as the dimension for a maze and returns the maze represented as a list of cells. Use the depth-first algorithm, ADTs and functions you created in steps 1-5 above (Hint: Keep track of the number of cells visited)
e.g.
>>> createmaze(4,5)
[('cell', (0, 0), ['t', 'r', 'l']), ('cell', (0, 1), ['b', 'l']), ('cell', (0, 2), ['t', 'l']), ('cell', (0, 3), ['r', 'l']), ('cell', (0, 4), ['b', 'l']), ('cell', (1, 0), ['t', 'r', 'l']), ('cell', (1, 1), []), ('cell', (1, 2), ['r']), ('cell', (1, 3), ['b', 'r', 'l']), ('cell', (1, 4), ['t', 'b']), ('cell', (2, 0), ['t', 'l']), ('cell', (2, 1), []), ('cell', (2, 2), ['b', 'r', 'l']), ('cell', (2, 3), ['t', 'r', 'l']), ('cell', (2, 4), ['b']), ('cell', (3, 0), ['t', 'b', 'r']), ('cell', (3, 1), ['t', 'b', 'r']), ('cell', (3, 2), ['t', 'r', 'l']), ('cell', (3, 3), ['r', 'l']), ('cell', (3, 4), ['b', 'r'])]
Represents the maze and correct path(S=start, E=end):
N.B. throughout this assignment, no absractions are to be violated. If you do so, marks will be deducted. Whenever possible, use list comprehensions, and higher-order functions in your code.