Problem Solving

What type of problems do computers solve?

Computers fundamentally solve problems that require decision making and repetition. In many cases, computers are used to execute instructions that eventually find solutions to hard problems. For example, one can use computers to find the result of dividing x by y or find the square root of a number x. These are among the many fundamentally numerical problems that computers are here to solve. However, as we may already know, computers do not think and do not have intrinsic intelligence. We need to tell computers what to do and how to do it. Depending on the programming language used to program a computer, our own thinking and problem-solving skills differ. With Python, we need to write down a detailed sequence of instructions for the computer to follow to come up with the results we want. Thus, the kind of problem-solving skills that we need is not limited to solving a numerical problem by pencil and paper. We also need to figure out a method to teach the computer to automatically produce the results as we would expect.

How should we think about numerical problems?

A good way to think about solving problems with computer programs is to go back in time. Imagine you live several hundred years ago with access only to a pen and a set of papers. How would you solve a numerical problem such as finding the root of a function? You need to come up with a procedure or an algorithm that you can use now and in the future to find the root of a particular function. You can write that algorithm on paper (in terms of steps required to produce the results) so that someone else who has the same goal but hasn't thought about a way to solve the problem can follow your steps and produce the results. This is the type of problem-solving skill that we would like to develop in this section. As we will see below, we can use a simple recipe for designing solutions for computers to solve problems for us.

We will summarize the simple recipe for producing programs in four steps.

Understand the problem, the available input X, and the required output Y.
Design a solution involving the use of input/output, decision-making, and repetition.
Translate your solution in the programming language you want to use.
Test your program with various inputs to ensure the required output Y is produced.

If we follow these steps correctly, we can surely improve our programming results. The programmer should follow the steps in the given order. First, we start with understanding what is required from us. This helps to avoid so many mistakes that could arise from misunderstanding the required solution. Second, we will need to imagine a solution for the problem, often thinking there was no digital computer to solve it. How would we approach the problem as humans? We can also write down some sketches of the design or write in plain natural language the steps we need to solve. It often helps to take a few example inputs and workout the output on them. Third, once we have a clear plan for our solution, we can write it down in the Python programming language (or some other language of choice). This requires mastering basic elements and tools available in the language. At this point, when a programmer tries to solve problems using computers, we'd assume the programmer is comfortable with using various language tools. Finally, when we have our code, we need to check if it works. This is what we call the testing stage. There is a lot of science in testing, but we will need to go into those details at this point. We need to ensure no compile or runtime errors and that our program works with obvious input examples.

Sum of a list of numbers

Python has a built-in function sum, which receives a sequence value and produces the sum of all values in the sequence (given that the sequence is numeric). That is, given the sequence X, the computed sum is Σxᵢ for xᵢ∈ X. If we did not have such a function, we'd be given the problem of computing the sum of all elements in a numeric sequence using repetition.

Application of Step 1: We have a sequence of numbers X that start with index 0 and end with index len(X). We would like to know what their sum is according to the formula above. We know that the sequence has at least one element and is finite, and is provided by the user on the keyboard. We are required to print the sum of X.

Application of Step 2: How would we solve this problem with pencil and paper? Imagine having the numbers written horizontally on paper. We start by writing a zero somewhere on the paper to memorize the sum. Then, we add the first number on the list to the current sum 0. Next, we check if there are more numbers to add. If so, we add the next number to the previous sum. We repeat this process until there are no more values in the list. Then, the last value of our sum is the sum of all elements in X.

Application of Step 3: We now have to write the solution in Python.

X = input().split()
X = list(map(eval,X))
s = 0 
i = 0 
n = len(X) 
while i < n: 
   s+= X[i] 
   i+=1 
print(s)

This program first takes the numbers in the form of a list from the keyboard. Next, it allocates three variables. s is used to accumulate the sum, i is used for iterating over the list X, and n is the number of values in X. Next, we set a while loop that only stops if i becomes equal to n. In each iteration, we add the current list element to the sum and increment the iterator variable by one. Once we're out of the loop, we will print the sum.

Application of Step 4: Once we're done with the Python program, we first check if it has no compile issues. Next, we run the program, provide some values to the list, and see the sum. Is the sum correct? If not, we will need to go back and check if we did not understand the problem correctly, or we had an issue with our design, or the Python program was not correct. Fix any issues, and then test again.

Finding the maximum number

Given a list of numeric values X from the user, we're asked to write a Python program to compute the maximum value in the list X.

Application of Step 1: Like the summation problem, we should ask the user to enter the keyboard's values. We know that the values are numbers, and we assume the user does not enter anything but numbers. We're required to print the maximum value among those entered by the user. Also, we're restricted from solving the problem using loops.

Application of Step 2: If we were to solve the problem using pencil and paper, we start by assuming that the user's first number is the maximum. We need to memorize one single number in each iteration until the user finishes giving us numbers. The number that we memorize is the current maximum. That is the maximum number we have seen so far. After receiving the first number, we check if the user wants to enter another number. If so, we compare the new number with the current maximum. We would replace the current maximum if the given number were greater. We continue this process until the user enters a sentinel value. Let's say the sentinel value is @. That is, when the user enters @, we will stop asking for more values.

Application of Step 3: Here's the translation of our design into Python code.

value = input('Enter a value: ')
from math import inf
m = -inf
while value.find('@') == -1:
   if value > m:
      m = value
   value = input('Enter a value: ')

print('Maximum is:',m)

Application of Step 4: This program is intentionally flawed. There is no compile error, but the maximum computed by this program will not always be correct. As a testing exercise, try to figure out the problem and modify it to produce the correct result.

The power problem

Suppose that we're given two integers n and k, and we are asked to write a program to compute nᵏ.

Application of Step 1: The problem is straight-forward. We need to receive two integers from the user and compute and print nᵏ. The problem does not mention writing a function or creating a file, nor does it say anything about the way to receive the two integers. So, we will make our own assumptions.

Application of Step 2: First, we will need to receive n and k from the user on the keyboard. Next, we need to check if the k < 0. In this case, the result would be 1/nᵐ, where m = -k. However, we will compute nᵏ, assuming k >=0. If k is 0, then we need to print 1. If n is 0, we need to print 0. We're now left with the case when neither n nor k is zeros. In this case, we need to multiple n with itself k times, which clearly needs a loop.

Application of Step 3: We now have a plan to write our Python code. We need the two variables n and k, and we need a variable to check if k < 0 and remember that, and we need a variable that remembers the result of the multiplication.

n = int(input('n: '))
k = int(input('k: '))
p = 1
negative = False
if k < 0: 
    negative = True
    k = -k 
while k >= 1:
    p*=n
    k-=1
if negative:
    p = 1/p
print(p)

In this code, the variable negative is a Boolean variable set to False, assuming k >=0. But, we will check and see if k < 0 and, in that case, set it to True. Then, we will negate k to make it positive. Next, we will execute the loop downward, starting with k down until k is 1, each time decrementing k by 1. In each iteration, we will also do p*=n. The value of p is initially 1, and it will remain 1 if k was zero (see the condition of the while loop). Finally, if negative is true, we will need to take the inverse of p, and we are done.

Application of Step 4: As usual, we will try our program with several values of n and k and see if it works. If not, we will go back and check our understanding of the problem, the validity of our design, and our code's correctness.

The long division problem

We are asked to write a program that divides x by y and computes the quotient and the remainder. Note that, for simplicity, we will make assumptions, and the program we will write is by no means complete. Here's the description of the problem that we need to understand as required by Step 1:

Given an integer N and a divisor integer D, write a Python program to produce a quotient q and a remainder r such that N=q×D+r.

Application of Step 1: The available inputs are two integers, N and D. The required outputs are two integers, q, and r. The problem is to divide N by D to produce q and r.

Application of Step 2: How should we think about solving this problem? Should we start by coding some Python? No! We will need to think about what sort of memory we need, what decisions we should make, and what needs to be repeated to solve it. The best way to design a solution is to imagine that we do not have access to any computers. How could we do this using paper and pencil?

First, we need to hold the two input numbers in memory so the computer does not forget them. For this, we will need two simple variables. Second, we need to check (decision making) if D is zero. In that case, we cannot compute q or r. Next, we would like to see if N == D. In this case, q = 1 and r = 0. After that, we need to know if N < D_. In this case, whatever the value of D, r = N and q = 0. We're now left with the case that _N > D. Assume that both N and D are nonnegative. How should we find q and r? Here, we need to find the number q such that q+1 > N. This is a perfect repetition problem. We need to start with some initial value i and increment i until i is no longer less than N. At this point, we have found both q and r.

Here's a simple example: Imagine you are given N=17 and D=3. Start with i = 1. We know that i×D < N_. So, it's safe to increment _i_. Now, with _i = 2_, we have _i×D = 6 < 17_. We can now go to _i = 3_ so that _i×D = 9 < 17_. We continue this until we have _i = 6_ and that _i×D = 18 > N. Now that we exceeded N, we know that q = 5 and r = N - q×D = 2.

Now that we have a design for our solution, we can start coding it.

Application of Step 3: To translate the design above into Python code, we will search for the language tools we have at our disposal and construct it.

def divider(N,D):
   q,r=0,0
   if D==0: 
      raise ValueError('Division by zero!')
   if N < D:
      return 0,N
   if N == D: 
      return D,0 
   i = 1
   while i*D <= N: 
      i+=1
   q=i-1
   r=N-q*D 
   return q,r

The first few lines in the program above are responsible for the cases that we discussed earlier. One noticeable language feature is the exception that we have used using the raise statement. This exception stops the program execution and displays the error message that we have specified in the string 'Divison by zero!' so we tell the user that we cannot continue because the given input is invalid. The core of the solution is in the while loop that we have introduced. This while loop iterates to find the quotation as we have defined in our solution design. Based on the quotation, we compute the remainder, and then we can return the results.

Application of Step 4: Now that we have a program, we must first check if there are no syntax errors. If none, we will provide various values for N and D and execute the function to see if it produces the desired outcome. This way of testing is called unit testing, where we test a unit of our program. It's not proof that our program works with all values for N and D, but as we do more testing, we would gain more confidence that our program works correctly or find cases where our program fails to produce the right results. In those cases, we will need to revise our design and code to fix the problems we face and redo the testing.

Converting a decimal number to a binary number

Sometimes programmers need to know the representation of a decimal number as a binary string. For example, we know that the decimal number 1 is represented as 0000 0001. Also, the decimal number 26 is represented as 0001 1010.

Problem: Given an integer value n in decimal format, write a Python program to produce a string s that represents n in binary.

Step 1: Notice that we are required to receive a number n and produce the binary string that is equal to n. This requires us to know that binary strings have a special meaning. A binary string such as 0011 can be seen as 0×2³+0×2²+1×2¹+1×2⁰.

Step 2: Solving this problem requires that we write the number n in terms of powers of 2 since binary representations are powers of 2 as we saw in the previous step. Let's take n = 26. In this case, what will be the biggest power of 2 that is less than 26? 2⁵ = 32 so it should be 2⁴ = 16. The next one is 2³ = 8. If 16 + 8 < 26, then we also add 8. But we know that 16 + 8 = 24, so we're short only 2 from 26. Thus, we have 26 = 16 + 8 + 2, which can be written in binary as: 11010. This solution requires us to write a loop that keeps finding powers of 2 less than n that in total do not exceed n.

Step 3: We're now ready to translate the solution above into code. We need two while loops here. One is to find the power of 2 below or equal n. We will have a variable v to hold that number. The next while loop will produce the binary bits as we proceed. Note that the second while loop decreases n with v, divides v by 2 to find the next power of 2, and adds ones when n is still bigger than or equal to v.

#This code is based on a code from book by Sedgewick et al. 
#Assume n >=0 and n is integer.
n = int(input())

#What is the biggest power, less than n?
v = 1
while True:
   t=v*2
   if t > n: 
      break
   v = t

#Find the binary string
s = ''
while v > 0:
   if n < v: 
      s += '0'
   else:
      s += '1'
      n -= v
   v //=2

Step 4: Try the code with a variety of numbers such as 26, 890, 0, and 14 and see if it works as you expect.