Skip to content

Programming Pattern

Learning Objectives

At the end of this sub-unit, students should

  • know how to generalize a solution into programming patterns.
  • know how to use programming patterns to solve problems.

Generalization

By now, we have already solved a number of problems. What we need to do is to compare some of the solutions and try to find the common pattern between some of the solutions. When comparing two solutions, we keep the parts that are the same and convert the parts that are different into blanks. Let us compare counting digit and sum of digit. We highlight the lines that contains the difference except for the function name.

Counting Digit 
1
2
3
4
5
6
def count_digit(n):
  res = 0
  while n > 0:
    res = res + 1
    n = n // 10
  return res
Generalized Digit 
1
2
3
4
5
6
def generalized_digit(n):
  res = 0
  while n > 0:
    res = res + ░░░░░░░░
    n = n // 10
  return res
Sum of Digit 
1
2
3
4
5
6
def digit_sum(n):
  res = 0
  while n > 0:
    res = res + (n % 10)
    n = n // 10
  return res

So this is good, with this, we can solve the following problems by filling in the blanks appropriately. You can try finding the appropriate blanks1 as an exercise.

  • Sum of the square of the digits.
  • Sum of the cubes of the digits.
  • Sum of even digits.
  • Sum of odd digits.

Can we have a better generalization? Let us now compare the generalized digit above with factorial so that we can now solve at least three problems using a single pattern.

Factorial 
1
2
3
4
5
6
def factorial(n):
  res = 1
  while n >= 1:
    res = res * n
    n = n - 1
  return res
Accumulator Integer 
1
2
3
4
5
6
def accumulator_int(n):
  res = ░░░░░░░░░
  while ░░░░n░░░░:
    res = res ░░░░░░░░░░
    n = n ░░░░░░░
  return res
Generalized Digit 
1
2
3
4
5
6
def generalized_digit(n):
  res = 0
  while n > 0:
    res = res + ░░░░░░░░
    n = n // 10
  return res

We use ░░░░n░░░░ to indicate that n should be used within this blank so that we do not just use an arbitrary condition like while True. So now, we have one possible patterns called accumulator. Since this accumulator is intended for integer, we will name it as accumulator (int). There may be another accumulator for other data types.

What about other patterns? That is up to you to decide. We can, for instance, try to generalize the prime checking function into a pattern that simply enumerate the potential divisor.

Prime Checking 
1
2
3
4
5
6
7
def is_prime(n):
  i = 2
  while i < n:
    if n % i == 0:
      return False
    i = i + 1
  return True
Enumerator Integer 
1
2
3
4
5
6
7
def enumerator_int(n):
  i = ░░░
  while ░░░░n░░░░:       # use n
    ░░░░░░░░░i░░░░░░░░░░  # use i
    ░░░░░░░░░░░░░░░░░░░░
    i = i + 1
  return ░░░░░░░░░

Comparing Patterns

Now that we have at least 3 patterns, we can try to compare them. Some of the comparison we want to make is to figure out which pattern is more general. We say that the less general one is more specific. It can be the case that two patterns are incomparable in a sense that none is more general. First, we will take a look at accumulator compared to generalized digit.

  • Accumulator Integer

    1
2
3
4
5
6
    def accumulator_int(n):
  res = ░░░░░░░░░
  while ░░░░n░░░░:
    res = res ░░░░░░░░░░
    n = n ░░░░░░░
  return res

  • Generalized Digit

    1
2
3
4
5
6
    def generalized_digit(n):
  res = 0
  while n > 0:
    res = res + ░░░░░░░░
    n = n // 10
  return res

One way to compare patterns is to look at the kinds of problems they can solve. In this case, accumulator_int is more general than generalized_digit. accumulator_int can solve whatever generalized_digit can solve and a few more like computing factorial which cannot be done by generalized_digit.

What about comparison between accumulator and enumerator?

  • Accumulator Integer

    1
2
3
4
5
6
    def accumulator_int(n):
  res = ░░░░░░░░░
  while ░░░░n░░░░:
    res = res ░░░░░░░░░░
    n = n ░░░░░░░
  return res

  • Enumerator Integer

    1
2
3
4
5
6
7
    def enumerator_int(n):
  i = ░░░
  while ░░░░n░░░░:       # use n
    ░░░░░░░░░i░░░░░░░░░░  # use i
    ░░░░░░░░░░░░░░░░░░░░
    i = i + 1
  return ░░░░░░░░░

In this case, it is not exactly clear. By looking at the problems they can solve, we know that enumerator_int can solve the prime checking problem which accumulator_int cannot solve. On the other hand, we may not have enough information to use enumerator_int to solve factorial. The variable i is used for iteration, so there is no counterpart for res. So these two are incomparable.

Hierarchy

Given that we can compare the patterns based on how specific/general they are, we can also arrange the patterns in a hierarchy. The details is left up to you but one way to arrange the patterns in a hierarchy is to put the more general pattern on top of the more specific patterns. Usually, the more specific pattern is easier to use than the more general ones. Creating a border around them is also a good way to categorize them as represented below.

Pattern01

In this hierarchy, "Generalized Digits" is more general than "Sum of Digit" but more specific than "Accumulator Integer". Additionally, we can also see based on our hierarchy that "Accumulator Integer" and "Enumerator Integer" are incomparable but both are more specific than "Iteration". The code for these patterns are also left as an exercise. In the case of "For-Loop", we will learn this construct only when we are dealing with sequence.

There are some potential work to be done while building this hierarchical pattern bank as shown above. For instance, if we encounter a gap in the pattern, then we may want to invent some pattern that is in between the two patterns. Consider the case of "While-Loop" and "Guess-and-Check Arbitrary". If we feel that there should be an intermediate pattern, then we try to think of a problem that it can solve, and create the pattern.

In the end, all of these are personal notes. It should be catered to individual needs. Each one of us would have a different way of thinking and so would come to a different conclusion on what constitutes an "easy to use" pattern. Since the task of the programming pattern in the pattern bank is to help you solve future problem, then it is imperative that the categorization is done by you for your need.

Furthermore, this is a continuous exercise. So when you encounter a new problem, you may want to do both of these.

  • Find a pattern that can be used to solve the problem.
    • Since our pattern is hierarchical, we can search from the bottom of the hierarchy.
    • Once you have accumulated proficiency in problem solving, you may no longer need to compare one by one and may quickly identify the necessary pattern.
  • Abstract the solution into more patterns.
    • This can then be used to solve more future problems.
    • So the more problems you solve → the more patterns you have → the more future problems you can solve and the more patterns you can accumulate.

We will show how we can use these some of these patterns to solve some problems.

Sum of Digit at Even Index

Sum of Even Index

Problem Description

Given a \(k\) digit integer \(d_{k-1}d_{k-2}{\cdots}d_1d_0\), we want to sum only the digits at even index. So we want to sum \(d_0 + d_2 + d_4 + \cdots\). Whether \(d_{k-1}\) is included or not depends on whether it is even or odd.

Task

Write the function sum_even_index(n) to compute and return the sum of the digits of n that are at even index. The index is computed from the rightmost digit with the index of this digit being 0.

Assumptions

  • n is a positive integer (i.e., n > 0).

Restrictions

  • You are NOT allowed to convert to other data types.
    • You must work only on integer.

At this point, we can use all the previous technique and come up with a separate solution but we want to highlight the use of programming pattern. So we rephrase the question as follows.

Which pattern can best be used to solve this problem?

Think about a similar problems that you have solved2. Which of those problems is the closest? Looking at the problem more closely, we can see that it is similar to the sum of digit problem.

Now, what is the programming pattern that is close to sum of digit in the hierarchy? We can consider using accumulator integer to try to solve this. At this point, we can simply write down the code for accumulator integer as shown below.

1
2
3
4
5
6
def accumulator_int(n):
  res = ░░░░░░░░░
  while ░░░░n░░░░:
    res = res ░░░░░░░░░░
    n = n ░░░░░░░
  return res

So this will be our template to solve the problem. We still to figure out the blanks. What kind of changes is needed to adapt this pattern to solve our problem? There are two ways to do this.

  1. We need to keep a flag on whether we are at even or odd index.
  2. We need to remove two digits instead of one digit in each iteration.

In both cases, we can guarantee that we perform an actual work only if we are at even index. The first is by using the flag and the second is by ensuring that the rightmost index will always be an even index.

1
2
3
4
5
6
7
8
def sum_even_index(n):
  res, is_even = 0, True
  while n > 0:
    if is_even:
      res = res + (n % 10)
    n = n // 10
    is_even = not is_even  # flip-flop between True/False
  return res

1
2
3
4
5
6
def sum_even_index(n):
  res = 0
  while n > 0:
    res = res + (n % 10)
    n = n // 100  # remove two digits
  return res

As a bonus, we can also find the sum of digits at odd index by removing the rightmost digit.

1
2
def sum_odd_index(n):
  return sum_even_index(n % 10)

ISBN-10

ISBN-10

Problem Description

The final character of a ten-digit International Standard Book Number is a check digit computed so that multiplying each digit by its position in the number (counting from the right) and taking the sum of these products modulo 11 is 0. The digit the farthest to the right (which is multiplied by 1) is the check digit, chosen to make the sum correct. It may need to have the value 10, which is represented as the letter X. For example, take the ISBN 0-201-53082-1. The sum of product is:

\[ 0 \times 10 + 2 \times 9 + 0 \times 8 + 1 \times 7 + 5 \times 6 + 3 \times 5 + 0 \times 4 + 8 \times 3 + 2 \times 2 + 1 \times 1 = 99 \]

Since 99 is multiples of 11 (i.e., \(99 \equiv 0 \ (\text{mod} \ 11)\)), then the ISBN is valid.

Task

Write the function isbn10(n) to check if n is a valid ISBN-10 number. If it is valid, the function returns True. Otherwise, it returns False.

Assumptions

  • n is a positive integer (i.e., n > 0).
  • n can have any number of digits including more than 10 digits.

Restrictions

  • You are NOT allowed to convert to other data types.
    • You must work only on integer.

To use programming pattern technique of problem solving, we need to try to match the problem into a problem that we have solved before. In the understanding the problem step, we can try to analyze the problem in more details. We may then figure out that in the summation above, we have two series.

  1. A series of running number that corresponds to the right operand of each term in the summation.
    \(\_ \times 10 + \_ \times 9 + \_ \times 8 + \_ \times 7 + \_ \times 6 + \_ \times 5 + \_ \times 4 + \_ \times 3 + \_ \times 2 + \_ \times 1\)

  2. A series of digits from n that corresponds to the left operand of each term in the summation.
    \(0 \times \_ + 2 \times \_ + 0 \times \_ + 1 \times \_ + 5 \times \_ + 3 \times \_ + 0 \times \_ + 8 \times \_ + 2 \times \_ + 1 \times \_\)

Can we generate these two series independently?

Problem #1: Right Operands

Consider the problem of generating the right operand.

  • What is the similar problem?
    • Counting digit because this is a running number that corresponds to the position of the digit.
  • What is the programming pattern?
    • Accumulator integer.

Extract the pattern.

1
2
3
4
5
6
def accumulator_int(n):
  res = ░░░░░░░░░
  while ░░░░n░░░░:
    res = res ░░░░░░░░░░
    n = n ░░░░░░░
  return res

Then we rename this into isbn10_R(n).

1
2
3
4
5
6
def isbn10_R(n):
  res = 0
  while n > 0:
    res = res + 1
    n = n // 10
  return res

Problem #2: Left Operands

Now we look at the left operand and go through the entire process again.

  • What is the similar problem?
    • Sum of digit because we are extracting the digit.
  • What is the programming pattern?
    • Accumulator integer.

Similarly, we rename this into isbn10_L(n).

1
2
3
4
5
6
def isbn10_L(n):
  res = 0
  while n > 0:
    res = res + (n % 10)
    n = n // 10
  return res

The Remaining Problem

Once we have an idea on how to solve the two problems above, the next step is to think about the remaining problem. That is the problem that we have yet to solve. We have the left operand and we have the right operand. What is left is to multiply them together.

Consider the code for isbn10_L(n) above3. This is where we extract each digit. The extraction is done on Line 4 in the expression (n % 10). But this needs to be multiplied with something first before it can be used in the summation. We will modify this a little.

1
2
3
4
5
6
def isbn10_L(n):
  res = 0
  while n > 0:
    res = res + (n % 10) * ???
    n = n // 10
  return res

How do we get the value for ???. Now we consider isbn10_R(n), the answer can be found here. During the computation of isbn10_R(n), we have all the right operands in the correct order stored inside the variable res. So we need to combined the two code together via an interleaving. Unfortunately, we cannot really combine them as it is because the same variable res is used differently. The variable n is fine as it is used in the same way in both codes.

So we rename the all occurrences of variable res in isbn10_R(n) into idx. This gives us the following code.

1
2
3
4
5
6
def isbn10_R(n):
  idx = 0
  while n > 0:
    idx = idx + 1
    n = n // 10
  return idx

Now we put both codes side by side and extract the common code. Then we interleave the two codes in the blank space we have already created to accommodate both codes. Next, we fill in the missing value for ???. The answer should be quite obvious, we need to use idx in place of ???. Finally, we need to decide if we need to return idx or res. This answer should hopefully also be obvious.

Left Operand

1
2
3
4
5
6
7
8
def isbn10_L(n):

  res = 0
  while n > 0:

    res = res + (n % 10) * ???
    n = n // 10
  return res

Common Code

1
2
3
4
5
6
7
8
def isbn10(n):


  while n > 0:


    n = n // 10
  return ░░░

Right Operand

1
2
3
4
5
6
7
8
def isbn10_R(n):
  idx = 0

  while n > 0:
    idx = idx + 1

    n = n // 10
  return idx

Left Operand

1
2
3
4
5
6
7
8
def isbn10_L(n):

  res = 0
  while n > 0:

    res = res + (n % 10) * ???
    n = n // 10
  return res

Common Code

1
2
3
4
5
6
7
8
def isbn10(n):
  idx = 0
  res = 0
  while n > 0:
    idx = idx + 1
    res = res + (n % 10) * ???
    n = n // 10
  return ░░░

Right Operand

1
2
3
4
5
6
7
8
def isbn10_R(n):
  idx = 0

  while n > 0:
    idx = idx + 1

    n = n // 10
  return idx

Left Operand

1
2
3
4
5
6
7
8
def isbn10_L(n):

  res = 0
  while n > 0:

    res = res + (n % 10) * ???
    n = n // 10
  return res

Common Code

1
2
3
4
5
6
7
8
def isbn10(n):
  idx = 0
  res = 0
  while n > 0:
    idx = idx + 1
    res = res + (n % 10) * idx
    n = n // 10
  return ░░░

Right Operand

1
2
3
4
5
6
7
8
def isbn10_R(n):
  idx = 0

  while n > 0:
    idx = idx + 1

    n = n // 10
  return idx

Left Operand

1
2
3
4
5
6
7
8
def isbn10_L(n):

  res = 0
  while n > 0:

    res = res + (n % 10) * ???
    n = n // 10
  return res

Common Code

1
2
3
4
5
6
7
8
def isbn10(n):
  idx = 0
  res = 0
  while n > 0:
    idx = idx + 1
    res = res + (n % 10) * idx
    n = n // 10
  return res

Right Operand

1
2
3
4
5
6
7
8
def isbn10_R(n):
  idx = 0

  while n > 0:
    idx = idx + 1

    n = n // 10
  return idx

A word of caution, the order of the interleaving matter. Try changing the order and put idx after res and you will see that the code will not work. Fortunately, there is no need to record this interleaved pattern into your pattern bank. We will discuss ways to keep our pattern bank simple by looking at more advanced problem solving technique called divide-and-conquer.

  1. square: (n % 10) ** 2 ; cube: (n % 10) ** 3 ; even: (1 - (n % 2)) * (n % 10) ; odd: (n % 2) * (n % 10). ↩

  2. The more you solve, the more similar problems you can use as a sample. ↩

  3. This analysis below can be done by considering isbn10_R(n) first, so the choice to consider isbn10_L(n) is an arbitrary decision. ↩