Recognising problem types

Why this matters

Most programming problems arrive as a sentence. A shop owner asks which stall is cheapest. A teacher asks how many students passed. An interview asks whether a name appears in a list. Before you can write any code, you have to know what kind of answer the sentence wants, because the answer decides the shape of the loop you will write.

If you pick the wrong shape, the code looks fine and still gives the wrong result. A loop that stops at the first match gives the wrong answer to a question that asks for every match. A counter that starts at the wrong value gives the wrong total. Naming the type first prevents this, and it takes less than a minute.

This lesson teaches four types that cover a large share of beginner problems. You will learn to read the question, decide which type it is, and write down the first step. Reading unfamiliar code is covered in the lesson before this one, and the trace method is covered in the lesson on trace tables.

The idea: ask what the answer looks like

Forget the story in the question for a moment. Look only at the answer the question wants.

• If the answer is yes or no, or where something is, the problem is a search.
• If the answer is a single number that counts things, the problem is a count.
• If the answer is a new list of things, the problem is a build.
• If the answer is one item that is best by some rule, the problem is a pick-best.

These four are the types this lesson uses. Each one has a standard loop, and each one has a first step that you can write before any other line. The table shows the questions to ask.

The word loop means a block of steps that runs once for each item. The word item means one thing in a collection, such as one name in a list or one price in a table. A counter is a number that goes up by one each time something happens. A list is an ordered collection of items. The best-so-far is a variable that holds the best candidate you have seen up to the current step.

The four types, one at a time

Search

A search asks whether something is in a collection, or where it is. "Is the name Ravi on the attendance list?" is a search. So is "Which position is the score 38 at?"

The first step is to decide what counts as a match. This sounds too obvious to write down, but it is where many searches go wrong. Does Ravi match ravi? Does a match need the whole name, or only the first letter? Write the rule in one sentence before you write any loop.

Then start at the first item and look at each one in turn. The moment you find a match, you can stop, because a search needs only one match. If you reach the end without one, the answer is "no" or a value that means "not found".

Here is a search that returns a position. It uses -1 for "not found", which is a common convention because positions start at 0, so -1 cannot be a real position.

def find_position(items, target):
    for position in range(len(items)):
        if items[position] == target:
            return position
    return -1
 
scores = [55, 72, 38, 90]
print(find_position(scores, 38))
print(find_position(scores, 100))

Output:

2
-1

The value 38 is at position 2, because positions start at 0. The value 100 is not in the list, so the function returns -1. Notice that the function returns as soon as it finds a match. That is correct for a search, and it is the reason a search loop is often shorter than the other three.

Count

A count asks how many things meet a rule. "How many orders were over 500 rupees?" is a count. "How many students passed?" is a count.

The first step is to set a counter to 0 before the loop starts. The counter is the answer you are building, so it must exist before the first item is checked. A counter that is never set produces an error, which is covered in the mistakes section.

Then go through each item. For each item that meets the rule, add 1 to the counter. Each item is looked at once, and the counter is read once at the end.

def count_over(amounts, limit):
    total = 0
    for amount in amounts:
        if amount > limit:
            total = total + 1
    return total
 
print(count_over([420, 510, 999, 75, 1200], 500))

Output:

3

Three amounts are over 500: 510, 999 and 1200. The function returns 3, which is a single number, as a count should.

Build

A build asks for a new collection made from some of the items. "Make a list of every student who passed" is a build. "List all the pairs of stalls with a total under 40" is a build too, although it is harder, and the second worked example shows it.

The first step is to make an empty list before the loop. The list is the answer you are building, and each matching item is added to it, so it must exist first.

Then go through the items. Each time an item meets the rule, add it to the list. At the end, return the list.

def names_passing(scores, pass_mark):
    passed = []
    for name in scores:
        if scores[name] >= pass_mark:
            passed.append(name)
    return passed
 
print(names_passing({"Asha": 72, "Ravi": 38, "Meena": 55}, 40))

Output:

['Asha', 'Meena']

The function returns a list, not a number. The difference between a count and a build is the type of the answer. A count gives one number. A build gives a collection. If the question says "how many", think count. If it says "which" or "list all", think build, unless it asks for a single item, in which case think pick-best.

Pick-best

A pick-best asks for one item that is best by some rule. "Which stall sells the cheapest samosa?" is a pick-best. "Which student has the highest score?" is a pick-best.

The first step has two parts. You decide what "better" means, such as lower price or higher score. You also decide what the best-so-far starts as. There are two common choices. One is to start with nothing, using None in Python, and treat the first item as the first candidate. The other is to start with the first item in the collection. Either works, as long as you handle the starting case on purpose.

Then go through the items. For each one, compare it with the best-so-far. If it is better, it becomes the new best-so-far. At the end, return the best-so-far.

def cheapest_stall(prices):
    best_name = None
    best_price = None
    for stall in prices:
        if best_price is None or prices[stall] < best_price:
            best_name = stall
            best_price = prices[stall]
    return best_name, best_price
 
print(cheapest_stall({"Stall A": 22, "Stall B": 18, "Stall C": 25}))

Output:

('Stall B', 18)

The function returns two values at once, the name and the price, in a form called a tuple, which is a fixed group of values in order. The name is the answer to "which", and the price is kept so the caller can see the number as well. A pick-best often needs both.

The starting check, best_price is None, matters. Without it, the first stall would be compared with a value that does not exist. The check makes the first item always become the first candidate, and that is the reason the rule for "better" can stay simple.

Worked examples, with more parts

Real questions often mix two types. The method is to split the question into parts, name the type of each part, and then join them. Each part has its own first step.

Example 1: which student has the most passing scores

A teacher has a list of papers for each student and asks: which student has the most passing scores, where a pass is 40 or more?

Split the question. The phrase "how many passing scores" is a count, once for each student. The phrase "which student has the most" is a pick-best, across the students. So there are two loops. The inner loop is a count, and the outer loop is a pick-best that uses the count's result.

papers = {
    "Asha": [72, 38, 55, 91],
    "Ravi": [40, 41, 39],
    "Meena": [60, 65, 70],
}
 
def passes(scores, mark):
    count = 0
    for s in scores:
        if s >= mark:
            count = count + 1
    return count
 
best_student = None
best_count = -1
for student in papers:
    n = passes(papers[student], 40)
    print(student, n)
    if n > best_count:
        best_student = student
        best_count = n
print(best_student, best_count)

Output:

Asha 3
Ravi 2
Meena 3
Asha 3

Asha and Meena both have three passing scores. The output says Asha, because the rule n > best_count only replaces the best when the new value is strictly bigger. The tie rule is a decision, and it should be made in the first step, not discovered afterwards. If the teacher wanted both names, the answer would be a build of the names with the top count, which is a different question. The exercises ask you to make that change.

The starting value of best_count is -1, not 0, because a student could have zero passes and still needs to be picked when nobody has any. If the start value were 0, then a student with no passing scores would never replace it. When every student has zero passes, the program would return None instead of a name.

Example 2: which pairs of stalls are cheap enough

A shopper has four stalls with prices. The shopper wants every pair of stalls whose combined price is under 40, and wants to know which of those pairs is the cheapest in total.

The question has three parts. The phrase "every pair" is a build, because the answer is a list of pairs. The phrase "under 40" is the rule for keeping an item. The phrase "which pair is the cheapest" is a pick-best over the list. So the first step is to make an empty list of pairs, and the second step, after the build finishes, is to start a pick-best over that list.

Making every pair needs two nested loops. The inner loop starts one position after the outer loop, so that a pair is never made of the same stall twice, and so that (A, B) and (B, A) are not both listed.

prices = {"Stall A": 22, "Stall B": 18, "Stall C": 25, "Stall D": 9}
names = list(prices)
 
pairs = []
for i in range(len(names)):
    for j in range(i + 1, len(names)):
        total = prices[names[i]] + prices[names[j]]
        if total < 40:
            pairs.append((names[i], names[j], total))
print(pairs)
 
best = None
for pair in pairs:
    if best is None or pair[2] < best[2]:
        best = pair
print(best)

Output:

[('Stall A', 'Stall D', 31), ('Stall B', 'Stall D', 27), ('Stall C', 'Stall D', 34)]
('Stall B', 'Stall D', 27)

The build comes first and produces three pairs. The pick-best comes second and works on the list the build made. The answer is the pair of stalls B and D, with a total of 27. Stall A and stall B together cost 40, which is not under 40, so the pair is not in the list. That check is what the rule "under 40" means, and it is worth stating in plain words before writing the condition.

Example 3: how many stalls cost less than the cheapest Sunday stall

A list of stalls and their prices is given. A second list names the stalls that are open on Sunday. The question is how many stalls, of all of them, cost less than the cheapest Sunday stall.

This question mixes two types. First, a pick-best over the Sunday stalls gives the cheapest Sunday price. Second, a count over all the stalls gives the answer, using that price as the limit. The first step is the pick-best, because the count depends on its result. The order matters, and the first step tells you what the second step needs.

prices = {"Stall A": 22, "Stall B": 18, "Stall C": 25, "Stall D": 9, "Stall E": 12}
sunday = ["Stall B", "Stall C", "Stall E"]
 
cheapest_sunday = None
for name in sunday:
    if cheapest_sunday is None or prices[name] < cheapest_sunday:
        cheapest_sunday = prices[name]
print("cheapest Sunday price:", cheapest_sunday)
 
count = 0
for name in prices:
    if prices[name] < cheapest_sunday:
        count = count + 1
print("stalls cheaper:", count)

Output:

cheapest Sunday price: 12
stalls cheaper: 1

The cheapest Sunday stall is Stall E at 12. Only Stall D at 9 is cheaper than 12. Stall E is not counted, because the question says "less than", and 12 is not less than 12. The count is 1.

This is the point where the wording matters. Replacing < with <= changes the answer, because the rule would then include Stall E itself. Written as a separate check, a count of stalls at or below 12 gives 2. The question's words decide which comparison to use, so write the words down before choosing the symbol.

Common mistakes

Setting the counter inside the loop. A count written as count = 0 inside the loop resets the counter on every pass. The result is always 0 or 1, depending on the last item. Set the counter once, before the loop.

Forgetting to set the counter at all. Using a counter that was never set gives an error. In Python, this program:

orders = [420, 510]
for amount in orders:
    if amount > 500:
        big = big + 1
print(big)

produces this output, where the folder part of the file path is shortened to ...:

Traceback (most recent call last):
  File ".../count_mistake.py", line 4, in <module>
    big = big + 1
          ^^^
NameError: name 'big' is not defined. Did you mean: 'bin'?

The first step of a count, setting the counter to 0, prevents this error. The message says the name does not exist yet, and the fix is to write the setting line before the loop.

Making the new list inside the loop. The build version of this mistake is the same kind of error. A passed = [] line inside the loop empties the list on every pass, so only the last matching item survives. This code:

scores = {"Asha": 72, "Ravi": 38, "Meena": 55}
passed = []
for name in scores:
    passed = []
    if scores[name] >= 40:
        passed.append(name)
print("reset inside loop:", passed)

prints reset inside loop: ['Meena'], which is not the list of both passing students. The fix is to make the list once, before the loop.

Returning from a search too early. A search can stop at the first match, but it must not stop at the first non-match. This code is a common mistake:

def is_present(names, target):
    for name in names:
        if name != target:
            return False
        return True

The first name is Asha, which is not Meena, so the function returns False before it has checked the other names. Running is_present(["Asha", "Ravi", "Meena"], "Meena") prints False, although Meena is in the list. The return False belongs after the loop, so that every name is checked first.

Starting the best value at zero. A pick-best that starts at 0 assumes no candidate is below 0. With prices, that means nothing is ever cheaper than 0, so no stall is chosen. Running this code:

prices = {"Stall A": 22, "Stall B": 18, "Stall C": 25}
best_name = None
best_price = 0
for stall in prices:
    if prices[stall] < best_price:
        best_name = stall
        best_price = prices[stall]
print("start at zero:", best_name, best_price)

prints start at zero: None 0. The start value must be a value that the first real candidate can replace, such as None with a check, or the first item in the list.

Mixing up count and build. A count returns a number. A build returns a list. If the question asks "how many", and the code returns the list, the caller gets a list where a number was expected. A quick check is to read the question's last word before writing the function's return line. "How many" returns a number. "Which" or "list" returns a collection or a single item.

Practice

Exercise 1. For each question, name the type: search, count, build or pick-best. Then write the first step in one sentence.

a. Is the word "exam" in the list of announcements?

b. How many of the 40 tickets were sold before noon?

c. List the names of every member who has paid.

d. Which of the three delivery routes is the shortest?

Show the answer

a. Search. The first step is to decide what counts as a match, such as the same letters with or without capitals, and to start at the first announcement.

b. Count. The first step is to set a counter to 0 before the loop.

c. Build. The first step is to make an empty list of names before the loop.

d. Pick-best. The first step is to decide that a shorter distance is better, and to set the best-so-far to nothing before the loop.

Exercise 2. The question is: "Which student has the highest total score across all tests?" Name each part of the question and its type. Then say what the answer's shape is, and why the question can be solved with one pass through the students.

Show the answer

The question has two parts. The phrase "highest total score" needs the total of each student, which is a sum over that student's tests. The phrase "which student" is a pick-best across students. The answer is one name, so the outer loop is a pick-best. The total for each student is computed inside the outer loop. The question can be solved in one pass over the students, because each total is needed only once, at the moment it is compared with the best so far.

Exercise 3. The program below is meant to count the numbers in a list that are even. Find the mistake, and say what it prints for [2, 3, 4].

def count_even(values):
    for value in values:
        count = 0
        if value % 2 == 0:
            count = count + 1
    return count
 
print(count_even([2, 3, 4]))

Show the answer

The counter is set inside the loop, so it resets to 0 on every pass. The program prints 1, because only the last item, 4, is counted after the final reset. The fix is to move count = 0 above the loop, so the counter is set once. With that fix, the function prints 2.

Exercise 4. Change Example 1 so that it returns every student tied for the most passing scores, not only the first one. Show the output for the same data, and say which step of the first-step rule you changed.

Show the answer

The tie rule changes from "replace only when strictly bigger" to a build. Keep a list of the best students. When a higher count appears, replace the list with that student. When a count equals the best, add the student to the list. The starting value is an empty list, and the starting count is -1. The output for the same data is ['Asha', 'Meena'] 3. The change is in the first step of the pick-best: the best-so-far is now a list of names, not one name.

Exercise 5. In Example 3, the program counts stalls cheaper than 12 and prints 1. Suppose the question changed to "how many stalls cost no more than the cheapest Sunday stall". Which symbol changes, and what does the program print?

Show the answer

"No more than" means "at most", so the comparison becomes <=. The program then counts Stall D at 9 and Stall E at 12, and prints 2. The only line that changes is the comparison inside the count loop. The pick-best above it stays the same, because the cheapest Sunday price is still 12.

Exercise 6. A friend says that a pick-best and a search are the same, because both stop when they find something. Explain the difference in your own words, with one example of each.

Show the answer

A search stops at the first match, because it needs only one item that meets a rule, such as the position of 38 in a list. A pick-best must check every item, because the best item can be the last one, such as the cheapest stall in a list that is not sorted. A search answers "is it there", and a pick-best answers "which one is best". Both use a loop, but a pick-best cannot stop early unless the best possible value has been reached. Any two examples that show this difference are correct.

Summary

• Read the answer the question wants, not the story. A yes, no or position is a search. A number is a count. A new list is a build. One best item is a pick-best.
• Name the type before writing any loop, and write its first step in one sentence.
• A count sets its counter to 0 before the loop, and a build makes an empty list before the loop.
• A pick-best decides what "better" means and what the best-so-far starts as.
• Split questions with two parts into two loops, and name the type of each part.
• The words of the question decide the comparison symbol, such as "less than" against "no more than".