Write the constructor function makestk

Assignment Help Programming Languages
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.

 

X

 

 

X

C

X

 

 

X

 

 

 

 

 

 

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):

806_aq.png

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.

Reference no: EM131674

Questions Cloud

Describing variables, stating assumptions, illustrating mode : Show all work by describing variables, stating assumptions, illustrating model and showing output solution to the problem.
Risk and return : Investing in the stock market and Risk-free investment and inflation
The total number of slots available in the zone : The total number of slots available in the zone, the total number of bicycles in the zone at the beginning of the period
Encipher a message using a keyword : The first program will encipher a message using a keyword and second program will decipher a message using a keyword.
Write the constructor function makestk : Write the constructor function makestk, predicate function emptystk and mutator functions pushstk and popstk
Bourne shell and design suitable functions : Bourne shell and design suitable functions
Net salvage value : Evaluate Net Salvage Value
Mergers and acquisitions : Track record of mergers and acquisitions
Present and defend the budget : Given a description of a new business, new product, service or project develop, present and defend the budget.

Reviews

Write a Review

 

Programming Languages Questions & Answers

  Write a haskell program to calculates a balanced partition

Write a program in Haskell which calculates a balanced partition of N items where each item has a value between 0 and K such that the difference b/w the sum of the values of first partition,

  Create an application to run in the amazon ec2 service

In this project you will create an application to run in the Amazon EC2 service and you will also create a client that can run on local machine and access your application.

  Explain the process to develop a web page locally

Explain the process to develop a Web page locally

  Write functions

These 14 questions covers java class, Array, link list , generic class.

  Programming assignment

If the user wants to read the input from a file, then the output will also go into a different file . If the user wants to read the input interactively, then the output will go to the screen .

  Write a prolog program using swi proglog

Write a Prolog program using swi proglog

  Create a custom application using eclipse

Create a custom Application Using Eclipse Android Development

  Create a application using the mvc architecture

create a application using the MVC architecture. No scripting elements are allowed in JSP pages.

  Develops bespoke solutions for the rubber industry

Develops bespoke solutions for the rubber industry

  Design a program that models the worms behavior

Design a program that models the worm's behavior.

  Writing a class

Build a class for a type called Fraction

  Design a program that assigns seats on an airplane

Write a program that allows an instructor to keep a grade book and also design and implement a program that assigns seats on an airplane.

Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd