Prelab 6 – An aMazing Programming Problem
Note: This pre-lab should be completed before starting the first laboratory assignment for this course.
Table of Contents
The Programming Problem
The problem we will be trying to solve for the semester was originally taken from a puzzle book. Here is the problem as defined by the puzzle book.
“In the forest, you will find beehives and more importantly honeycombs. Along the path are bees. The number of bees at any given location is indicated by a number. There are a few ways your bear can travel to the forest. Your aim is to teach your bear how to make his way to the forest while encountering as few bees as possible.”
Take a few minutes and see if you can solve the puzzle. While the problem may seem trivial, we will be using this as an example to show how various programming methods can be used to develop a solution that can be implemented with the assembly language that you learned in lecture. Hopefully, later on in your engineering careers, this sequence of labs will help you realize how there are many ways to resolve a problem and that creating a program may simplify the solution.
Draw a Flowchart
Now let’s see if you can translate your path through the maze into a flowchart. We will need to break it down into the individual actions that the bear can take and make sure that it can be executed by the program. This leads to the following assumptions.
- Assume the hungry Bear is initially facing north with his knapsack. In the knapsack is a blank notepad with a pencil and eraser. (This is our explanation for how the bear keeps track of various values) The length of each step is exactly one square.
- There are certain things that the bear can do or check in the attempt to exit the maze. The bear could take a step into the next room, check to see what type of room is encountered, or decide on which way to go next.
The entire list of instructions that the bear can take are listed below. Compare it with your own list of instructions that you thought to see how close you were.
Actuators and corresponding unconditional instructions
- Take a step
- Turn left
- Turn right
- Turn around
- Count and record the number of bees in your notepad
Sensors and corresponding conditional instructions
- Did you hit a wall?
- Can your left paw touch a wall?
- Can your right paw touch a wall?
- Are you in the forest?
- Do you see any bees?
- Are you thinking of a number {not equal, less than, greater than, or equal} to 0?
- Is the number on page N of the notepad {not equal, less than, greater than, or equal} to some constant?
Notepad operations
The bear can remember 8-bit unsigned and 1-bit (binary) numbers. The bear records a number in his notepad. He can only save one number per page. You may assign a descriptive name to a page (ex. bees), simply use the page number (page1), or think of it as a variable (X). In the following example X = 0.
Pseudocode | C++ Equivalent Instructions |
---|---|
1. Erase page X. | page0 = 0; |
2. Increment the number on a page. | page0++; |
Nodes
- Start
- Stop
Tips and Tricks
- You may not need all the instructions provided.
- Although not required, you can use subroutines.
Take a few minutes to see if you can sketch-out your flowchart. If you don’t know where to start; don’t worry, in the next few sections I will step you through how to write your own flowchart.
The path through the maze can be modeled as follows. Figure 2 provides an overview of the process we will be implementing in our labs. Each block can be considered a collection of the various actions described above and will be expanded on in future labs to describe exactly what our assembly program will be doing. For example, this pre-lab will focus on defining the “Which Way” block, which determines the direction the bear should face while going through the maze.
Creating the Which Way Flowchart
First, we need to clarify what the WhichWay block will be doing. From Figure 2, we know that the bear has just entered a room in the maze and now needs to determine which direction to go. The bear will be taking another step after the Which Way block, so we only need to make sure that the bear is in the correct orientation. There are two ways the bear can decide which way to turn when entering a room. You can count how many rooms the bear has passed or identify what type of room the bear is in. We will be doing the latter for our lab. Based on this information, these are the only instructions needed for this flowchart.
- Turn left
- Turn right
- Turn around
- Did you hit a wall?
- Can your left paw touch a wall?
- Can your right paw touch a wall?
- Increment the number on a page
- Is the number on page N of the notepad {not equal, less than, greater than, or equal} to some constant?
With that in mind, we need to define a way to identify the rooms the bear enters.
Square Naming Convention
Here is a standardized naming convention to help you define the decision points in any maze. In order to provide a design example, the following maze identifies the squares (i.e., intersections) where the bear needs to make a decision for the shortest path solution.
Squares are numbered by concatenating the binary values (yes = 1, no = 0) for the answers to the following three questions (sensor inputs).
Can your left paw touch a wall? – Did you hit a wall? – Can your right paw touch a wall?
The answers to these three questions provide all the information that our bear can know about any given square. Let’s look at a few examples to see how this works. After taking the first step the bear can touch a wall with his left paw (1), has not hit a wall (0), and cannot touch a wall with its right paw (0). For our convention, this would correspond to input condition 4 = 1002. As seen in the illustration, those types of squares are labeled number 4. Assuming the bear turns right; after taking another step the bear finds himself in a hallway where his left and right paws touch a wall and he does not hit a wall. This corresponds to square 5 (1012). Although you could write a 5 in this square, for the sake of brevity, the square is left blank (your bear walks down a lot of hallways). Notice that the numbers are based on the direction the bear is facing and not a universal reference point, like facing north. This corresponds to the fact that within the maze our bear has no idea where north, or any direction for that matter, is (our bear forgot his compass). So, let’s continue to the next intersection. Here the bear’s left paw cannot touch a wall (0), he does not hit a wall (0), and his right paw can touch a wall (1). We therefore would write a 1 (0012) in this square. Continuing in this fashion all intersections are identified for our minimum solution.
Shortest Path Solution
Using the naming convention and the shortest path through the maze presented in the last section, let’s design a solution for the shortest path.
Build a Truth Table
Here are all the possible squares our bear could encounter and a short description of the situation he is facing.
For your minimum solution your bear should encounter squares 1, 3, 4, 5, and 6. Once again we did not include in our illustration situations where the bear has no choice (3 = left corner, 6 = right corner, and 5 = hallway).
Draw your Flowchart – Solution for a Fully “Deterministic” Maze
A fully deterministic maze is one where for any given intersection the bear will always (it is predetermined) take the same action. For example, for your puzzle solution, whenever the bear encounters intersection 4 he will always turn right. Fora a non-deterministic maze he may turn right one time and turn left another. If you look at our shortest solution to the maze you will discover that it is fully deterministic, and so it lends itself to this simple solution.
It is always a good idea to check your answer (or the given one) to see if it actually teaches the bear how to count bees and find the shortest path out of the maze. Once you have your flowchart, implementation in the C programming language or Assembly is fairly straightforward.
Pre-Lab Assignment
In subsequent labs, we will be working with the same bear in the same maze; however you will all be mapping out and trying to teach your bear how to follow a different path. To help everyone plot a unique path, you will need to locate your target square.
Please use the maze included at the start of this lab and “theMaze.bmp” that is linked in the Page 2 section under Deliverable for Prelab 1.
Find Your Target Square
Write down the last four digits of your student ID as two 2-digit decimal numbers. These digits will provide the coordinates (row and column) of your target square. For example, if the last four digits of your student ID were 7386, your two 2-digit numbers would be 73 and 86. Divide by 20 using long division on each number and write the remainder down. Those remainders are now your row and column numbers. In our example, 20 dives into 73 three times with a remainder of 13 and into 86 four times with a remainder of 6. Next convert both numbers into a hexadecimal number. For our example, 13 = 0x0D (where the prefix 0x signifies a number in hexadecimal) and 6 = 0x06. Your target square would therefore be in row 0x0D and column 0x06.
How to Find Your Path
Find a path through the maze such that:
- The bear goes through the target square.
- The bear must get lost at least once. Specifically, he must at some point turn-around. This is typically, but does not need to be, at a dead end.
- There are any number of paths that can take your bear through the target square, get lost, and into the forest, you now want to find the one that results in the numbers of bees encountered being closest to but not exceeding 15 (inclusive).
- Finally, the maze must be non-deterministic. This means that at some intersection along the path the bear will need to take a different action. For example, the first time he encounters a T-intersection he turns left and the second time he turns right. The good news is that, if your path meets the first three criteria, the odds are extremely high that it will be non-deterministic.
Let’s look at how you can develop a flowchart for your unique path.
Design Methodology for a Non-deterministic Maze
As previously mentioned, most maze solutions are non-deterministic. The phrase “not fully deterministic” means, while one set of input conditions in one part of the maze will determine one action (go straight), in another part of the maze the exact same conditions will require a different action (turn right). By looking at your truth-table you can recognize a “non-deterministic” path as having two or more 1’s in the same row. A quick inspection of my truth table reveals that, for the shortest path solution (Figure 4), the bear follows a fully deterministic path. Specifically, for any given intersection the bear will always take the same action. For example, if the bear’s left paw is touching a wall (1), he does not hit a wall (0), and his right right paw is not touching a wall (0), then the bear will always turn right. Following is one path example that illustrates how to solve a non-deterministic maze.
Let’s begin by looking at the sequential actions that must be taken as we encounter each intersection.
The good news is that with the exception of square number 1 all other actions are deterministic. The bad news is that only when we encounter room 1 after the second time do we start turning left. To solve this more difficult problem, we will create a binary tree that allows us to resolve all 8 squares, allowing us to then take any action needed. This binary tree can now be easily translated into C++ or Assembly.
Step-by-Step Instructions
Here are step-by-step instructions for solving your maze.
Begin by making a copy (electronic or paper) of the maze and drawing your bear’s path through the maze. When you are happy with your new path, follow the methodology previously discussed to build your truth table. Verify that your path meets the design criteria (passes through the target square while encountering the minimum number of bees and getting lost once). Remember, your target square may not be along the original solution path.
It is now time to teach your bear how to navigate the new path by writing a flow chart. To accomplish your goal you will need to apply everything you have learned so far plus add a few Notepad operations. The notepad pages (i.e., variables) are used to determine which path your bear should take when he enters an intersection in which more than one action is possible. For example, the first time he enters intersection 1 you may want the bear to go straight, while the second time he encounters intersection 1 you want him to turn left. To resolve this conflict you would record in your notepad how many times intersections 1 had been encountered and then check your notepad before taking any action.
In addition to previously stated conditions, your solution must also meet the following negative criteria.
- Your solution may not use a variable (notepad) to simply count how many steps the bear has taken in order to make a decision.
- Your solution should use a variable(s) and not the number of bees encountered to help it make a decision.
Deliverable for Pre-Lab 6
Turn in the following material on the following pages (i.e., no more, no less). All work must be typed or neatly done in ink.
All labs should represent your own work – DO NOT COPY.
Title Page (Page 0)
The title page (Page 0) includes the lab number, your name, today’s date, and the day your lab meets.
Page 1
At the top of the page provide the last four digits of your student ID and describe how you calculated your target square. Include in your discussion how the resulting path met the design requirements defined in the pre-lab. For example how many paths did you consider before choosing your final path – how close did you come to 15.
Page 2
Next, using your favorite illustration (Visio, Illustrator, or Photoshop) program or the drawing tools included with your favorite Office program (PowerPoint, Excel, and Word) mark your target square with an X and illustrate your bear’s path through the maze. Also include on this page a table of “Sensor input combinations and actions” similar to Table 2. If you do not have access to any of those programs, there is a free online website called draw.io that works just fine.
Many drawing programs allow you to import a bitmap file, in this case the maze. You can find a bitmap and vector formatted picture of the Maze here. Once imported, draw your path, typically using the line tool. Next, number your intersections (but not corners or hallways) as illustrated in Figure 5 “Nondeterministic path example.”
Page 3
Again using your favorite drawing program, draw the flowchart for programming problem.
Your flowchart should resemble the one included with the lab and only use the provided instructions. Artwork of the sample flowchart is included here.
Checklist
- Your pre-lab report includes a title page.
- Pages are in the order specified (see Deliverable)
- You do not have any extra pages
- You describe how you arrived at your path
- Maze is not copied from another student (zero points)
- Path is computer drawn.
- Maze Path meets specified requirements
- Intersections are not drawn by hand and appear as shown in the example
- Intersections are numbered
- Intersections are numbered correctly
- Truth table
- Truth table is on the same page as the maze
- Truth table is typed
- Truth table matches the maze
- Flowchart
- Flowchart matches your truth table
- Flowchart is correct