- Students will practice decomposing a single complex problem, into multiple digestible parts
- Students will implement a breadth or depth-first traversal of an adjaceny matrix and discuss tradeoffs
- Students will implement a Class pattern for a custom Data Structure (Offices)
* Adjacency Matrix, Object Oriented Design, Graph traversal, Breadth-first, Depth-first
Imagine you are programming a Roomba to clean every room in an office. Your Roomba has three pre-built methods:
-
isCurrentRoomDirty() //returns Boolean if current room needs cleaning) -
cleanRoom() //cleans dirty room Roomba is currently in -
move(directionString) // consumes a string ('North', 'South', 'East', 'West') and attempts to move to next room in that direction
Create a cleanFloor() method, which traverses all the available rooms on a floor and cleans the dirty offices. You may use the above methods, as well as any custom helper functions you deem necessary.
-
What data structures will you use to represent a floor plan? How about an office? You may assume all offices are accessable through at least one door.
-
Can you travel from one room to any of it's neighboring rooms? If not, how will we represent doors versus walls?
-
Does your Roomba have a floorplan of the office stored in memory, or does it create the floorplan dynamically?
-
Does your Roomba travel along predefined paths?
-
Imagine we know the location of the CEO's office, and want that cleaned first. What changes should we make to our algorithm and office design? What if we have multiple high priority rooms in the office?
- This problem is best approached by breaking it into the following parts. Instructors may wish to give students 8-12 mins per sub-problem to solve with their partner.
- Each room of the office presents a great opportunity for Object Oriented design. We want to note the cleanliness status of each office, as well as any walls. We can also bake in a property to indicate if it is a high-priority room.
class Office {
constructor(id, wallArray, isDirty, isPriority) {
this.id = id // unique id for referencing offices
/*
using an array of Booleans indicating if there is a wall creates a shorter but more opaque
function signature
*/
this.North = wallArray[0];
this.South = wallArray[1];
this.East = wallArray[2];
this.West = wallArray[3];
this.needsCleaning = isDirty;
this.priorityOffice = isPriority
}
clean() {
this.needsCleaning = false
}
}
let nimitsOffice = new Office([true, false, false, true], true, true)
NB) If students decide that they are cleaning an 'Open Office' (where no offices have walls), they may disregard the wallArray and simplify the contructor
Once we have our office class, we can extend an Adjacency Matrix class (a 2D array)and populate them with Offices for our Floor
class Floor extends AdjacencyMatrix {
constructor([officeArray]) {
this.floorPlan = [...officeArray]
}
getOffice(x, y){
return this.floorPlan[x][y]
}
}
The nuances will change depending on how students answer the questions in 'Further Considerations'. No choice is 'right', but this creates a great opportunity to engage students in a dialogue about the different technical considerations behind each choice. For example:
- An Open Office is easier to clean than an Office with walls. If our office has walls, we probably need a helper method to determine if we can move between two offices in a given cardinal direction
- If our Roomba has a floor plan in memory, it can predefine the optimal paths to travel on, reducing repeat visits to rooms. It can further store this path for future cleanings.
- If our Roomba does not have a floor plan, it will needs to clean the office dynamically, and may potentially visit the same room multiple times. This is more succinctly implemented with a recursive, backtracking approach rather than an iterative one.
- If we have high priority office rooms, does our Roomba know those coordinates in advance? If so, we can initiate multiple depth-first searches to get to and clean those rooms, before visiting the rest of the office. If not, we need to traverse the office to find all high priority rooms first.
Once these considerations are considered, successfully implementing cleanFloor() depends on understanding the implementation and use-cases of breadth-first vs depth-first search. BFS is most useful when we want to visit all nodes on a graph (i.e, clean the entire floor), while DFS is useful when we want to find a specific node first (i.e, clean the CEO's office first)
Now, we can begin to piece together the architecture of our cleanFloor() algorithm...
function cleanFloor() {
const floorPlan = new Floor([...Offices])
const directions = ['North', 'South', 'East', 'West'];
// Map allows for object keys for checking x,y coordinate
const visited = new Map();
// BFS implementation requires Queue
const toVisit = new Queue();
let currentCoordinates = {x : 0, y : 0}
let currentOffice = floorPlan.getOffice(currentRoom);
toVisit.push(currentOffice);
while(toVisit.length) {
let currentOffice = toVisit.pop();
for(let direction of directions) {
// Update coordinates in direction to move
let nextCoords = { ...currentCoordinates };
if(direction === 'North') {
nextCoords['y'] += 1;
} else if (direction === 'South') {
nextCoords['y'] -= 1;
} else if (direction === 'West') {
nextCoords['x'] += 1;
} else {
nextCoords['x'] -= 1;
}
if(!currentOffice[direction] && !visited{nextCoords}) {
toVisit.push(floorPlan[nextCoords.x][nextCoords.y])
}
}
if(isCurrentRoomDirty()){
cleanRoom()
currrentOffice.clean()
}
visited{currentCoordinates} = true;
}
return 'All Clean!;
}
This has linear time and space complexity, where n is the number of offices.
Feel free to sketch out implementations for any of the further considerations.
Note: resources indicate differing opinions on the "optimal" solution, as various floor plans and extra criteria will always add new complexity to this project. Memoizing the floorplan/cleaning paths is a great place to start. An implementation of Dykstra's algorithm will allow us to hone in on the shortest possible paths between offices.
Further reading: https://www.sciencedirect.com/science/article/pii/S2352664516300050