Ask Question, Ask an Expert


Ask Programming Language Expert

Consider the space for a maze as being a large grid of cells with each cell holding four 'walls'. Starting with a random cell, the computer randomly chooses a neighboring cell. The computer removes the walls between two cells and adds the initially, randomly chosen cell to a stack. Once a cell has at least one wall removed, it is considered to have been visited. The computer continues this procedure. Any cell that has no unvisited neighbors’ is considered a dead-end. When at a dead-end the computer backtracks through the path by popping the stack till it reaches a cell with at least one unvisited neighbor, and continues the path generation by visiting this new, unvisited cell. This process continues till every cell has been visited. This depth-first search approach is captured in the subsequent algorithm:

1. Randomly choose an initial cell

2. While there are neighboring cells with all four walls intact

i. Randomly select one of the unvisited neighbors’
ii. Push the selected cell to the stack
iii. Remove the wall between the current cell and the chosen cell

3. Pop a cell from the stack and make it the current cell

4. Repeat from step 2 until all cells have been visited
Follow the instructions below to prepare the program that will create a representation of a maze by using the depth-first search algorithm.

1. Make the following ADTs.

(a) prepare constructor function makestk, predicate function emptystk and mutator functions pushstk and popstk:

i. makestk returns a new stack in 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)

iii. pushstk accept 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 eradicates the element at position 0 of the given stack.

e.g. >>> popstk(cellstk)
('cell', (0, 0), ['t', 'b', 'r', 'l'])
>>> cellstk
('stack', [])

(b) prepare a constructor function called makecell, accessor functions getx, gety and getwalls, and mutator functions removetw, removebw, removerw, removelw.

i. make cell accept 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:

The list represents the four walls of the cell: top, bottom, left and right.

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 (correspondingly) of a given cell.

e.g. >>> getx(cell0)

iii. getwalls returns the list of walls that are intact for the given cell

e.g. >>> getwalls(cell0)
['t', 'b', 'r', 'l']

iv.  remove 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. prepare 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 must 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 should discover its neighbouring cells i.e. those with which it shares a wall. In the diagram given below, the cells with an x are the neighbours of the cell c. prepare the function getneighbours that admitted a cell, the width and height of the grid, and returns all
neighbours of the given cell.

942_cell layout.jpg
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 capable to remove common walls between two cells. prepare 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 want to know, given a cell, which of its neighbours has all of its walls intact. prepare the function wallsintact that accepts the grid and a list of neighbouring cells and returns those whose four walls are integral.

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. Lastly, prepare function createmaze which accepts a width and height as the dimension for a maze and returns the maze represented as a list of cells. Use depth-first algorithm,

ADTs and functions you created in steps 1-5 above (Hint: Keep track of number of cells visited)

>>> 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'])]

1087_maze correct path.jpg
Represents maze and correct path(S=start, E=end):

Programming Language, Programming

  • Category:- Programming Language
  • Reference No.:- M91627

Have any Question? 

Related Questions in Programming Language

Programming lab assignment set awhat to submitcomplete

Programming Lab Assignment (Set A) What to Submit Complete Problem Solving Steps 1 - 3 (check plan, data analysis, initial algorithm, and refinement algorithm) for the following programs. 1. (Name: lab1a-1.cpp) Write a p ...

Add a swift class file to the project that illustrates and

Add a SWIFT class file to the project that illustrates and contains the following: • The class name is 'Calculator' • Has public variables of the type float called numerator, denominator and total. • Has a method called ...

Shell programmingyou have created the directory structure

Shell Programming You have created the directory structure and some base files to be used by the Web server and Web site. For the Web site to be created in a production environment, you need to package your commands in a ...


Computer Science Program- Write all of the following: main program: Call a function to open an input file. Call a function to read 3 integers in from the input file. Call a function that will find 3 normalized doubles, g ...

Assignmentcase problem1 - online trivia found on pages

Assignment: Case Problem1 - Online Trivia found on pages 794-795 of your textbook. Complete the web pages and upload them to your 000WebHost account. After uploading the files make sure to update your index.html page to ...

Write a program that calculates several possible tips to

Write a program that calculates several possible tips to give to a waiter at a restaurant. Ask the user to enter the total cost of the meal and then calculate a tip at 10%, 12.5%, 15%, 17.5%, and 20%. Write the original ...

Pair programming phase 1talent agency user stories1 user

Pair Programming Phase 1 Talent Agency User Stories 1. User Story 1 As a head office administrator I want to be able to produce formatted output of all the information about our talent agencies so that I can easily incor ...

Assignmentthis assignment will be marked out of 100 and

Assignment This assignment will be marked out of 100 and carries 30% of the overall module weighting. Your .java files and report for this part must be uploaded to WebLearn and submitted by 3pm on Wednesday 27th April 20 ...

Programming assignment 1 grocery storethis assignment

Programming Assignment #1: Grocery Store This assignment attempts to serve as a refresher for concepts that I hope you learned in CS 122. In this assignment, you will be building a simple storefront for a small grocery s ...

Csis program homeworkwrite a program where the user will

CSIS program homework Write a program where the user will enter a number between 1 and 50 representing a state. The program should display the full name of that state. Assume the states are in alphabetical order, that is ...

  • 4,153,160 Questions Asked
  • 13,132 Experts
  • 2,558,936 Questions Answered

Ask Experts for help!!

Looking for Assignment Help?

Start excelling in your Courses, Get help with Assignment

Write us your full requirement for evaluation and you will receive response within 20 minutes turnaround time.

Ask Now Help with Problems, Get a Best Answer

A cola-dispensing machine is set to dispense 9 ounces of

A cola-dispensing machine is set to dispense 9 ounces of cola per cup, with a standard deviation of 1.0 ounce. The manuf

What is marketingbullwhat is marketing think back to your

What is Marketing? • "What is marketing"? Think back to your impressions before you started this class versus how you

Question -your client david smith runs a small it

QUESTION - Your client, David Smith runs a small IT consulting business specialising in computer software and techno

Inspection of a random sample of 22 aircraft showed that 15

Inspection of a random sample of 22 aircraft showed that 15 needed repairs to fix a wiring problem that might compromise

Effective hrmquestionhow can an effective hrm system help

Effective HRM Question How can an effective HRM system help facilitate the achievement of an organization's strate