Problem Solving 101¶

Inventing languages to help¶

Our natural language is not very good for precision, so, we build simpler languages to express our instructions. You are familiar with one such language, the language of mathematics - all those equations!

Let’s try building our own language for something fun!

Controlling a robot¶

This is a simple robot designed to help teach beginners about programming. Here is the robot’s home page: Finch Robot

How do we program this beast to move around¶

We will start off with a very simple language I invented for this course!

Note

This robot can be programmed using a number of programming languages, but we will not worry about for now. The robot has small motors attached to wheels on each side of the body. These motors can make the wheels move forward or backward. By making the motors spin at different speeds on each side, we can make the robot turn. There are a number of other gadgets inside the robot that let it speak, figure out if it is tipping, and even sense when someone is nearby. Not bad for $99.

The real programming languages that we are supposed to use for this critter are a bit too complex for us, so I have stripped it down and created a different language of my own to play with. The robot language I have invented is very simple. Here it is:

Robot commands¶

PAUSE( n ) - delay (the program) for n milliseconds (1/1000 second)

LEFT_MOTOR( n ) - set the speed for the left motor to n (see below)

RIGHT_MOTOR( n ) - same for right motor

REPEAT n TIMES { <sequence> }

IF <condition> THEN { <sequence> }

STOP - set both servo’s speed to zero

BEEP - sound a tone from the speaker

Note

Each command makes the robot do some very simple task. Once we understand what the robot can do, we are ready to try to write down a set of instructions to make it perform some task we have in mind. The trick in doing this is to put yourself in the position of the robot and think about what would happen if you activated each instruction, then try it with groups of instructions, and so on. You need to develop the ability to visualize what will happen when your program runs. That takes practice, and experimenting with the programming.

Detail, Details¶

What are those n, <condition> and <sequence> things?

The n thing is just a whole number

In the REPEAT command it it the number of times to repeat

In the motor commands it is a number between 0 and 255

We will explain this later

More Detail¶

The <condition> is some notation we will use to ask questions

We will explain this in a moment

The <sequence> is just a series of statements

Any legal statements can be used

Note

We clearly need more information here, but it is easy enough to figure out. (With a bit of study, of course).

Supposed we need to create a program that will cause our robot to follow a simple pattern on the floor, like a square.

Stating the problem¶

Here is the problem we were given:

Write a simple program that makes the robot run through a square path. The size of the square is determined by how long it takes the robot to run through its program. Make the total time for each leg around 5 seconds. Think how this might be done.

Where do we begin?

Analysis of the problem¶

Start by examining the problem statement in detail.

Do we have all the information we need

If not, who do we go to to get additional details?

By itself, the problem statement is terribly weak. We have no idea how to make the robot do its thing! However, we were given a simple language that we can use to start!

Do we know enough?¶

Do we have enough information now? Not really! There are still a few things we need to know.

How fast do the robot’s wheels turn when we drive them forward?

How long does it take to process each instruction?

Note

We can figure this all out by experimenting with the robot, which sounds like a good plan at the moment, since I do not know the real answers to these questions myself - and I built the darn thing! So, What next?

Plan the Algorithm¶

What is an algorithm anyway?

Just a fancy term for the set of steps that will solve our problem!

We pay attention to algorithms for a simple reason: we tend to see the same problems over and over.

We seem to solve very similar small problems as part of bigger problems all the time. Remember that I said good programmers are lazy? What I really mean is that they keep track of the algorithms they have written in the past, and REUSE those algorithms over again when it make sense! Better yet, they examine algorithms written by other folks and choose good ones to include in their programs. In this way, we get our problems solved quicker. And, if the algorithms are fully tested and known to be correct, we feel better that our program is correct as well.

Creating the algorithm¶

We need to break down hard chunks of the problem into smaller pieces!

We start with a general concept of what we want the robot to do then, we create a written set of commands for the robot We hope the scheme will really do the job!

Decomposition¶

Let’s break it down.

We want the robot to move in a square path.

We also want it to take about five seconds to complete one leg.

Hmmm, how do I do that?

A square has four sides (duh!), so I need to do something to make the robot go forward, then turn 90 degrees four times in a row. I probably want to stop the robot when I am done. So, perhaps a first cut at my algorithm looks like this:

First cut - leg 1¶

Start the robot moving forward.

Wait 5 seconds (does the robot keep moving?)

stop the robot

First cut - leg 2¶

turn 90 degrees left (or right)

start the robot moving forward

wait 5 seconds

stop the robot

First cut - leg 3¶

turn 90 degrees left (or right)

start the robot moving forward

wait 5 seconds

stop the robot

First cut - leg 4¶

turn 90 degrees left (or right)

start the robot moving forward

wait 5 seconds

stop the robot

Reviewing the algorithm¶

Notice that this set of steps is just written in English, not code. (We are ‘’thinking’’ here, using pseudo code.)

What is the final state of the robot in this scheme?

Are we supposed to have leave the robot pointed in the same direction?

We were not told to do so, so this might be fine.

However it might be a good idea to ask!

It is a fact of life that those who give us problems to solve rarely give us complete definitions of what we are to do - we go back to them over and over until we know exactly what we are to do.

Let’s say we are supposed to leave the robot in the same state it was in when it started.

The State of a System¶

What in the world is the state of a system or the state of a floor-crawling robot, anyway?

You know the answer!

Is it moving or stopped?

Is it right-side-up or up-side-down?

Where is it physically?

Anything you need to define to describe accurately how the robot is configured at the moment. If you think about it, we are writing down a set of commands that will alter the state of the robot moment by moment as we move it through it’s paces. You could write down a bunch of mathematical formulas to describe the state of the robot at any moment in time. This is exactly what you learn to do in many engineering, math, and physics classes!

Our robot begins on the floor at some physical location (we could measure this with a tape measure - but we could also just mark the spot with chalk). Our robot begins in a stopped state - it isn’t moving. Somehow, we will make it start our program. (I will turn on the switch that applies power to the beast.) It will then follow our set of instructions until it stops - or crashes into something!

Why do we care about the state?¶

Because you often need to keep track of the state of your system. Your program will change the state of the system as it runs. As a result, you constantly consult that state as needed to make decisions as to what to do next!

In this robot problem, we need to keep track of time and the direction we are facing, as well as the number of times we have turned to complete our task.

Back to our Algorithm¶

Look back at our algorithm. Do you see a pattern in the steps there? I see the same pattern written down four times. We are doing a simple task multiple times, and it makes sense to use some kind of construct that lets us do the same thing over and over without writing these steps down multiple times!

Remember the looping structure? We should probably use one here.

With this in mind, let’s rewrite our algorithm:

Repeat four times

Start the robot moving forward

Wait five seconds

Stop the robot

Turn left 90 degrees

Notice that we use indentation to show that we are repeating a sequence of actions a number of times.

Will this algorithm solve our problem?

Manually walk the algorithm through¶

To feel comfortable that we have a solution, we need to check it out. At this point, we think it through by visualizing our robot sitting on the floor and not moving. We then follow our algorithm and see what happens, all the while mentally verifying that the robot is moving correctly! What will happen here?

Looks like we will do the following stuff four times

We make the robot start moving forward

We start a timer and let it run for 5 seconds

we direct the robot to stop - it will have moved some distance

We cause the robot to turn 90 degrees to the left

Hopefully, when this is finished the robot is still stopped

We are done with this leg of the square

All four passes will move the robot in a straight line for 5 seconds and cause the robot to turn left when it gets to the end of the line. Will this leave the robot pointing in the right direction? Let’s see! If we start off with the robot facing North, we get this:

Move North 5 seconds, turn to face West

Move West 5 seconds, turn to face South

Move South 5 seconds, turn to face East

Move East five seconds, turn to face North

With any luck, each leg was the same length, and from what we know of geometry, we end up in the same spot where we started, facing the same direction. So, it looks like we have a good first cut on our algorithm!

Programming Style¶

Notice something important here. In the algorithm presented above, I used one of the standard programming structures (actually, two) and nested a sequence of steps inside a loop. When I did so, I showed this nesting by indenting the sequence to be repeated. This is exactly how professional programmers write their programs in most programming languages - and you should do this as well.

Code the algorithm in our programming language¶

Now that we have a good feeling that we know what to do, we can try to recast our algorithm in our programming language.

In our simple robot language, we have two statements that allow us to nest other statements inside them. These are the FOR and the IF statements. Both of those statements have curly braces as part of them and they include a <sequence> inside those braces. Where this term is shown, we can place any sequence of statements inside the braces. Here is a (dumb) fragment of code in the robot language that demonstrates how you should use indenting to arrange your code, and might be a solution to our problem:

1)  PAUSE ( 1000 )
2)  FOR my_counter = 0 to 50 {
3)     BEEP
4)     PAUSE ( 500 )
5)     IF my_counter == 3 {
6)         LEFT_SERVO( 650 )
7)         RIGHT_SERVO( 850 )
8)         PAUSE ( 500 )
9)     }
10) }
11) STOP

You should notice something important here! We have placed the IF statement inside the FOR* statement. Both of these statements allow a sequence of any other statements to be nested inside. In this situation, we indent further as seen in the example above. Personally, I use four spaces for each level of indentation, and I have taught my editor (gVim) to automatically place four spaces into my programs any time I hit the tab key. Furthermore, my editor is smart enough to automatically un-indent when I get to the end of a statement that allows nested statements inside it. (Unfortunately, my editor does not know this silly robot language, but I could teach it that language if I wanted to!)

Now, this code does not totally solve our problem (you get to do something like that as part of this week’s lab project), but we will assume it does for the present discussion. What next?

Checking your algorithm¶

What exactly does this code do, anyway? We could put it in the robot, but we are still thinking the problem through, so let’s do it manually! We will assume the robot is initially stopped and sitting on the floor.

Statement 1 - line 1¶

We start the program and process the first statement. That statement is PAUSE ( 1000 ), which we are told simply delays for 1000 milliseconds - or one second.

What delays? The robot? The program? Actually, both! Since we do not know any better, let’s assume that our program is so fast we do not need to worry about the time it takes to process each instruction, we can assume it happens instantly!

So, we start off by going to sleep for one second! Boring!

Statement 2 - line 2¶

The next statement is a FOR loop (you will see this in many languages. It differs from our simple structured loop in one important way. It uses a counter and loops as many times as it takes to step that counter from the first counter value to the second counter value. In our program, we seem to be starting a loop that will repeat exactly 51 times (why 51?).

Back to that style issue again, since we are now working on a loop, we will indent the code we want to repeat and un-indent when we get to the end of that code. Notice how I have displayed this. There are other ways to do this (for instance, place the open curly brace on the next line by itself) but I like this form because it keeps my programs shorter, and I can trace my finger down the page to find the end of the loop. It will appear where I find a close curly brace at the same indent level as the FOR that started this loop (on line 10).

What Are we repeating? The stuff from lines 3 to 9!

Statement 3 - line 3¶

This one is easy, we BEEP to say we are here!

Statement 4 - line 4¶

Now we pause for 500 milliseconds, or one half second.

Statement 5 - line 5¶

Here we have another standard structure, the If decision structure. In this case, we must evaluate a condition, which is just a question of a sort, that has a True or False answer. If the answer is True, we will process the statements inside the curly braces (again). If the answer is False, in this statement, we do nothing but move on to the next statement in the sequence we are processing at the moment (the one inside our outer loop!).

Hmmm, the question here is Is my_counter equal to 3? If it is, we have work to do, otherwise we move on to line 10 (which is the end of the outer loop. If the answer is True we move to the next statement:

Statement 6 - line 6¶

Here, we start the robot motor on the left side and set the speed to some value. From our description of the statement, we see that the value we have chosen makes the motor start up moving full speed backward!

Statement 7 - line 7¶

This statement starts up the right motor going full speed forward! Yikes, what will the robot do? Looking at the poor beast, we see that it will spin in place (approximately) moving counter-clockwise. If we allowed this to continue for some time, we would be turning the robot around to the left - hmmm, that sounds useful!

Statement 8 - line 8¶

Here we do pause for one half second again, maybe we turned 90 degrees, maybe not, we will have to see.

Statement 9 - line 11¶

What happens on lines 9 and 10? Nothing much! Those lines are part of the statements previously described! When we hit line 9, we see the end of the IF statement. If we skipped the sequence inside the IF, we simply picked up processing the sequence inside the FOR at this point. However the next line is another curly brace, so we end this pass through that loop at this point.

The program actually does something when it gets to the close curly brace for the FOR statement on line 10. This statement maintains a counter that it increments each time through the loop. It does this increment at the end of the loop (it sets it to the first value before it actually starts). When it finishes the increment action, it checks to see if the new value for the counter exceeds the final value specified by the programmer. If not, we go back and repeat the code inside the loop once more. If so, we fall out of the loop and move on to the next statement at the save level as the FOR loop, which is on line 11.

On statement 9 (line 11), we simply stop the robot. And we are done.

Is this description correct? Think about it. We started the robot spinning to the left on lines 6 and 7, then we waited long enough to turn the robot for one half a second. What happened next?

Well, we press on with our code, which loops back and beeps again. Hmmm, did we stop the motors yet? We then wait a bit and see what value the counter has now. Only when the counter is three do we get inside the IF statement, every other time we skip past it and loop again.

Sounds like I will hear 51 beeps, each about a half second apart. At beep three (or is it four?), the robot will start spinning to the left, and keep on spinning until we get done with all this beeping! Then it will stop - and be very dizzy!

If at first you don’t succeed¶

This situation is all too common. We thought we had a good piece of code, but until we really thought about it, or actually tested it, we do not know for sure. We next need to go back and continue with these same several steps until we get it right!

Then we are done!¶

This is a real problem, one that I give to another class of mine. It is a good one to help you learn to visualize what is happening. But, I think you will agree that playing with some of the programs we will use this term, is more satisfying. You will get to play around and really see what is happening, not just imagine what is happening. Believe me, though, in that real world of programming, using your mind and imagination is going to happen far more often that anything else.

Problem Solving 101¶

Inventing languages to help¶

Controlling a robot¶

How do we program this beast to move around¶

Robot commands¶

Detail, Details¶

More Detail¶

Stating the problem¶

Analysis of the problem¶

Do we know enough?¶

Plan the Algorithm¶

Creating the algorithm¶

Decomposition¶

First cut - leg 1¶

First cut - leg 2¶

First cut - leg 3¶

First cut - leg 4¶

Reviewing the algorithm¶

The State of a System¶

Why do we care about the state?¶

Back to our Algorithm¶

Manually walk the algorithm through¶

Programming Style¶

Code the algorithm in our programming language¶

Checking your algorithm¶

Statement 1 - line 1¶

Statement 2 - line 2¶

Statement 3 - line 3¶

Statement 4 - line 4¶

Statement 5 - line 5¶

Statement 6 - line 6¶

Statement 7 - line 7¶

Statement 8 - line 8¶

Statement 9 - line 11¶

If at first you don’t succeed¶

Then we are done!¶

Page contents

Previous page

Next page

This Page