6D: Design, Debugging and Donuts

This lesson has some suggestions on how to make designing and debugging your programs easier. The longer that you do programming, the better you will become at avoiding and fixing mistakes, but here we'll try to give you some very general and useful advice. We'll explain the following techniques:

  • build one part at a time
  • solve some examples by hand
  • plan your code before you start writing it
  • write the code
  • test the examples that you have solved by hand
  • test additional examples including “borderline” and random cases

This magic formula won't solve everything automatically, but it can save you headaches and reduce the number of problems you deal with later on.

When you run into a problem, some strategies to help debug it are using diagnostic print statements (we'll do this later in the lesson), using the visualizer, reading your code carefully, and writing good tests. If you run Python at home, you can use breakpoint and step tools to gain better insight into what goes wrong.

An algorithm means a series of instructions. While a computer program needs to be written in a specific language like Python or JavaScript to work, the word algorithm means step-by-step instructions that can be written in English or expressed in a diagram. For example, a recipe for donuts is an algorithm, where "measure out 3 cups of flour" is one step, and "let the dough rise for 2 hours" is another step. We'll develop a simple algorithm in this lesson. Then we'll implement the algorithm, which means converting it to a working computer program.

The Problem: Donut Calculator

Tim Horton's, a chain of coffee stores in Canada, sells timbits, which are tasty donut spheres:

Photo: looking_and_learning, flickr

You have to organize several parties in the next few weeks, and you'll be ordering a different number of timbits for each party. So, you would like to make a program to calculate the price of an arbitrary number of timbits, in order to plan your budget. At your local branch, these are the prices:

Number Price
1 $0.20
10 (small box) $1.99
20 (medium box) $3.39
40 (large box) $6.19

Build one part at a time

Eventually, you'd like to make a program where the input is the number P of people at the party and the output is the cost to feed that many people including tax. At the highest level, there are three components to this program:

  1. calculate, for P people, what is the number T of timbits you should buy?
  2. calculate the price to buy exactly T timbits
  3. calculate the tax and overall cost.

However, you can work on these three parts one at a time. In fact, we recommend that you build one part at a time, testing and fixing each part before you proceed to work on the next part, because the larger your program is, the harder it is to find and fix each bug. It's easier to develop and test the three parts separately, before combining them into a single program. For the rest of this lesson, we will focus on step 2: calculate the price to buy exactly T timbits.

Solve some examples by hand

In order to be able to tell the computer to do something, you need to be able to do it yourself. Let's work through an example ourselves: what's the price to buy exactly 45 timbits? Looking at the list of sizes, we can buy one large box (40), which will cost $6.19. That leaves 45 – 40 = 5 more timbits that we need to buy individually, which is an additional cost of 5 * $0.20 = $1.00. The total cost will be $6.19 + $1.00 = $7.19.

Plan your code before you start writing it

What if we wanted to buy 4 or 456 timbits instead of 45? In general, we should buy as many big boxes as possible, then take a medium box and/or a small box if needed, and individual timbits to get the right total.

Is this algorithm really optimal? Yes! You can see that buying two medium boxes (2*$3.39 = $6.78) is a bad idea since we can get 2*20=40 timbits in a single large box more cheaply. Similar comparisons of individual/small and small/medium can be used to prove the algorithm gives the cheapest price to buy an exact number of timbits. If the prices/sizes were different, we might have to be more careful.

We said that you should plan your code before you start writing it. You can:

  • give a short step-by-step description of the algorithm in English instead of Python
  • use a diagram or flowchart to show the steps
  • focus on the main ideas instead of the details, for now.

In our example, we'll give an English description. We're not showing you a flowchart for this particular program, since it would just flow from step 1 to step 2 and so forth in a straight line. Programs with looping, like we'll see later, benefit more from flowcharts.

Algorithm to calculate the price of any number of timbits

  1. get the input number of timbits
  2. keep track of the total cost, starting from zero
  3. buy as many large boxes as you can
    1. calculate the number of timbits still needed
    2. update the total price
  4. buy a medium box if you can and repeat steps A. and B.
  5. buy a small box if you can and repeat steps A. and B.
  6. buy individual timbits and repeat step B.
  7. output the total cost

We call this a pseudocode description of the algorithm, since it is a series of step-by-step instructions, but not in any real programming language.

Write the code

Reiterating the first piece of advice, build one part at a time, you can also think of writing a separate chunk of code for each step from 1 to 7. Additionally, here is one thing that we need to think about for all of the steps: what variables will we use? what will their names, types, and initial values be?

Let's use timbitsLeft to represent the number of timbits we still have to buy, and let's use totalCost to represent the total cost so far. We don't need to tell Python the types in advance, but we can plan for ourselves that timbitsLeft will be an int, while totalCost will be a float variable measuring the total cost in dollars. (So one cent is 0.01). We'll need some additional temporary variables in each step, that we'll deal with only when needed.

Steps 1 and 2 can be written with one line of code each:

timbitsLeft = int(input()) # step 1: get the input
totalCost = 0              # step 2: initialize the total cost
For Step 3, we need to calculate the maximum number of big boxes that we can buy. How exactly can we do this? Since a big box contains 40 timbits, the number bigBoxes should be the integer quotient of timbitsLeft divided by 40. Keeping track of the division, cost, and subtracting, we have the following code fragment:

# step 3: buy as many large boxes as you can
bigBoxes = timbitsLeft / 40
totalCost = totalCost + bigBoxes * 6.19    # update the total price
timbitsLeft = timbitsLeft - 40 * bigBoxes  # calculate timbits still needed
Actually, it turns out that we have already made a mistake. The best way to catch mistakes is to be testing your code early and testing your code often! Let's optimistically say that we tested the partial code at this point. We'll just add a couple of print statements to observe its behaviour so far. (Instead of using print statements, you can also use the visualizer to check each step.)

Testing the code so far on the input 45, using print statements to help debug.

This is not working like we want! What is the problem? Where is the first line where what we meant is different from what happened? Try to locate it before opening the next paragraph. Remember, we solved this example by hand earlier.

Click to read the explanation
The culprit is the line bigBoxes = timbitsLeft / 40, since bigBoxes is coming out as 1.125, whereas we intended it to be equal to 1. You can't buy a fraction of a box. One possible workaround, that you will see in lesson 7A, is to use // for integer division instead of / which does decimal division. Another solution, based on what we saw in Lesson 4, is to convert timbitsLeft / 40 to an int which will delete the fractional part. We'll use that approach instead: the line becomes bigBoxes = int(timbitsLeft / 40).

Steps 4 and 5 are similar to step 3. Alternatively, since you will buy at most one medium box and at most one small box, we can use an if statement:

if timbitsLeft >= 20: # step 4, can we buy a medium box?
  totalCost = totalCost + 3.39
  timbitsLeft = timbitsLeft - 20
if timbitsLeft >= 10: # step 5, can we buy a small box?
  totalCost = totalCost + 1.99
  timbitsLeft = timbitsLeft - 20
To finish, we need to pay 20 cents for each of the last needed timbits and output the answer.

totalCost = totalCost + timbitsLeft * 20 # step 6
print(totalCost)                         # step 7

Test the examples that you have solved by hand

Here's the overall program. The first thing that we'll do is test it to see if it works on the input 45 that we solved by hand.

What is the price of 45 timbits?
You may enter input for the program in the box below.

There must be a bug, since we're paying over 100 dollars for just 45 timbits! Your final job is to find and eliminate this bug, and another bug hidden in the code. It will be tested in the next section.

Just so you know, there is a funny thing that happens with Tim Horton's pricing, which is not a bug: it can be cheaper to buy exactly T+1 timbits than to buy exactly T timbits. For example, buying exactly 19 timbits costs $3.79, but buying exactly 20 timbits costs only $3.39. Regardless, we will stick with the problem of buying exactly T timbits as cheaply as possible, for which the algorithm explained previously is correct. So your program really should output 3.79 when the input is 19.

Test additional examples

In Computer Science Circles, we try to do intelligent automated testing of your code in order to make sure that you have solved the problem correctly. But in a real programming setting, it is up to you to test your own code thoroughly. Here are a few useful guidelines for testing.

  • You can check that every line of code of your program is functioning correctly. In the timbit problem, using the input 10 will check whether we are correctly handling small boxes. Similarly, inputs 20 and 40 will check that medium and large boxes are handled correctly. Finally, you should check that we are handling individual timbits correctly (e.g., with the input 1).
    • This can help to check that values like $3.39 and $1.99 were typed in correctly.
  • Be sure to check "borderline" cases which push your program to the limits. For example, the minimum possible input to this program is 0, since you can't have negative timbits. Our program has no maximum input, but you might want to try values like 39 and 41 which are close to the border of just barely buying one large box.
    • This can help to check that you didn't accidentally type > when you should have typed >= instead.
  • In some cases you can automatically check every input, or check a large number of random inputs to see if your program is functioning correctly. We use random inputs a lot in the CS Circles internal tests. Use import random at the start of your program, then for example random.randint(10, 100) will generate a random integer between 10 and 100.

Can you find both bugs and pass all of the tests? Give it a shot!

Some calculations introduce very small errors in Python:
Example: Rounding Error
It's surprising that the code above doesn't give exactly 0.35! It has to do with how Python stores information. Don't worry about such tiny errors: the grader ignores them. We'll say more in lesson 7B.

Coding Exercise: Timbits
Fix the bugs and pass all of the tests!
You may enter input for the program in the box below.

Hungry yet? You are ready to continue to the next lesson!

While 10 timbits make a box, 8 timbits make one timbyte. Photo: thisisbrianfisher, flickr