Reference no: EM131674

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.