A Problem-Solving Process
Mar 192018A computer programmer is somebody who converts computational problems into computational solutions. This is a “meta-problem”:
- Given a problem, write a computer program which solves it.
- Input: a problem statement.
- Output: a computer program.
A computer can’t do this — writing programs requires insight and ingenuity.(1) But there are some systematic processes we can follow when writing programs, so most of the time we don’t have to hope for a “eureka!” moment.
In this post we’ll see one systematic, effective process for writing algorithms. We’ll demonstrate this process by solving a simple problem.
1. Specify the problem
The first step is to specify the problem. Here’s the one we’ll solve:
- Problem: count how many times a value occurs in a list.
- Input: a list.
- Input: the value to be counted.
- Output: the number of occurrences, as an integer.
- Example: the value
7occurs 3 times in the list[1, 7, 2, 7, 7, 5, 9]. - Example: the value
"hello"occurs once in the list["hello", "world"]. - Example: the value
10occurs 0 times in the list[1, 3, 2, 5, 4].
This problem is simple, and an experienced programmer can solve it quickly and easily — by following a problem-solving process like the one we’re demonstrating. If you can write a solution in under 30 seconds, it’s very likely you’re following a similar process, perhaps without realising it.
Before we begin, let’s name the inputs — we’ll call the list lst, and the value to be counted will be value.
2. Split into subproblems
The next step is to split the problem into simpler subproblems. There are three parts to this problem:
- Look at each value in
lst, one by one. - Detect occurrences of
value. - Count the detected occurrences.
Now we have three problems instead of one — but each of these problems is simpler than what we started with, so we’ve made progress.
3. Select plans
These subproblems are simple enough to solve directly. Experienced programmers recognise subproblems like these, and have “plans” for what code to write. Each of these subproblems can be solved with one “plan”.
The first plan is: “do something for each value”.
This will be for x in lst:, where x takes each value from lst, one at a time.
The second plan is: “filter for what we want”.
We want to count occurrences of value, so the code is if x == value:.
The third plan is: “use a counter variable”. The counter starts at 0, and should be incremented each time we see what we’re counting. At the end of the loop, the counter will hold the correct number. The code is in three parts:
- Before the loop, set
counter = 0. - To increment the counter, do
counter += 1. - After the loop, we can
return counter.
4. Compose the plans
Next, we need to compose these plans into a solution for the entire problem.
Let’s start with the function signature.
The inputs are lst and value:
def count_occurrences(lst, value):
# ...The first plan is to “do something for each value”:
def count_occurrences(lst, value):
for x in lst:
# ...The second plan is to “filter for what we want”:
def count_occurrences(lst, value):
for x in lst:
if x == value:
# ...The third plan is to “use a counter variable”:
def count_occurrences(lst, value):
counter = 0
for x in lst:
if x == value:
counter += 1
return counterThe code is now all put together.
We return counter because after the loop, it holds the correct number of occurrences — and this is the required output.
5. Test the solution
Let’s make sure our code works; we want to check that it gives the correct outputs, and doesn’t cause unexpected errors or get stuck in an infinite loop.
Fortunately, because we already gave examples of inputs and outputs when we specified the problem, we can use these to test the code. IDLE’s interactive mode is a good way to do quick tests:
>>> count_occurrences([1, 7, 2, 7, 7, 5, 9], 7)
3
>>> count_occurrences(['hello', 'world'], 'hello')
1
>>> count_occurrences([1, 3, 2, 5, 4], 10)
0The outputs seem to be correct, so now we’re satisfied with our solution.
The problem-solving process
In this post we demonstrated a systematic process for writing algorithms:
- Specify the problem.
- Split the problem into simpler subproblems.
- Solve the subproblems:
- If you already have plans for solving them, use those plans.
- Otherwise, temporarily “forget” about the original problem, and focus on solving one subproblem at a time.(2)
- Combine the subproblem solutions into a solution to the original problem.
- Test the solution to make sure it works.
The problem we solved was simple — the solution is only a few lines of code — but still, there were three subproblems, and we composed three plans together to produce the solution.
This may seem like a lot of effort just to solve a simple problem. But experienced programmers really do follow a process like this when they write code — they just do it quickly and automatically, without having to think about it.(3) To get to this point takes practice.
Footnotes
- If it didn’t, we’d be out of a job!
- This is recursive, because we can follow the same process to solve the subproblem. The recursive nature of problem-solving is humourously illustrated in a scene from the TV show Malcolm in the Middle (video).
- Think about it like walking, writing with a pen, or typing on a keyboard — if you do it often for a long time, then you don’t need to consciously control your muscles; they’re automatic processes.
If you’re proficient with a language then you probably don’t consciously think about how to spell most words, or what order to say them in; if you do a lot of mental arithmetic, you don’t need to count on your fingers.
Comments