Exploration

Learning Objectives

At the end of this sub-unit, students should

• know how to apply exploration to problem solving.

Exploration vs Connecting-the-Dots

In connecting-the-dots, the relationships are between consecutive inputs. Unfortunately, in some cases, consecutive inputs are unrelated. But there may be relationships between inputs that are further apart. Since the relationships are between inputs that are further apart, we need to finds these "related" or "relevant" inputs¹.

So previously in connecting-the-dots, it is sufficient to find the connecting formula for the output. However, for exploration, we need to also find connecting formula for the related inputs. To differentiate them, we call the connecting formula for the related inputs as relation formula.

Steps

1. Start with series of consecutive relevant inputs.
   • If the input is already given in the problem description, we can use that.
   • Alternatively, we can try to come up with our own series relevant of inputs in the first step.
2. Assume outputs from smaller inputs can be used in the computation of the output for the larger inputs.
   • This is one of the important feature of connecting-the-dots.
3. Find the relationship between outputs from consecutive relevant inputs.
   • The relationship can be simple arithmetic or other more complicated formula based on the operations that can be done on the given data type.
   • We simply have to arrive at the connecting formula that connects the outputs from consecutive relevant inputs.
4. Find the operation to transform an input to its relevant inputs.
   • This is the relation formula and will based on the operation that can be done on the given data type.

It is best to illustrate this with examples.

Counting Digit

While we have had this problem as an exercise, we leave the answer blank because we want to explain how to arrive at the solution in more details here.

Counting Digit

Problem Description

Given a positive integer \(n\), we want to find the number of digits of \(n\).

Task

Write the function count_digit(n) to compute and return the number of digits of n. There is a special case we need to consider for simplicity. The number of digit of 0 is considered to be 0 digit.

Assumptions

• n is a non-negative integer (i.e., n >= 0).

Restrictions

• You are NOT allowed to convert to other data types.
  • You must work only on integer.
  • Otherwise, it is simply len(str(n)).

First, notice that consecutive inputs are not necessarily related. For instance, there are only one digit in both n = 1 and n = 2. In some rare instances, consecutive inputs are related such as between n = 99 and n = 100. So we cannot simply rely on consecutive inputs. We need to find our own way of grouping inputs that are relevant together. To find these relevant inputs, we need to explore the possible space of inputs.

Let us take some arbitrary value of 2134. It is a nice number with four different digits and it satisfies the requirement for non-negative integer. We know that there are 4 digits in 2134. Visually, we can represent this as shown below.

So to find relevant inputs, we need to find some other numbers, related to 2134 in some way such that the output is also connected to 4. As 2134 is an integer, the operation must be related to integers. We will first try some simple operations like - and //.

Should we try + or *? There are some reason why we should not try it. But the main one is related to the boundary case. In this case, we know the lower boundary which is 0. This is also the simplest number we know the number of digit of which is 0 digit. As such, our operations should bring us closer to 0. Neither + nor * will bring us closer to 0 if we only consider positive integer.

So let us consider some operations using - and //. We need to consider its effect on the output as well as whether it will bring the input argument to 0. You can test your understanding and see which one of these operations is the correct operation to use.

- 1- 2000// 10// 5// 2

The output does not change, so it is not a good candidate.

This time it goes into negative, so it is not a good candidate.

This is correct and related to the fact that our number system uses base 10.

Although initially looks promising, it eventually fails after some steps.

The output does not change, so it is not a good candidate.

---

As the examples above have shown, the candidate operation may look promising for several steps before eventually failing. Additionally, we should try it out for other values to really be sure that the operation is correct. We will use a table to illustrate this.

n	// 10	// 10	// 10	// 10	// 10	// 10	// 10
1	0
12	1	0
123	12	1	0
1234	123	12	1	0
12345	1234	123	12	1	0
123456	12345	1234	123	12	1	0
1234567	123456	12345	1234	123	12	1	0

Luckily for us, the relation formula is a simple operation. Similar to connecting formula, we will write this as re-assignment to the original variable.

n = n // 10

The next formula to find is the connecting formula. In this case, we need to look at the output since we have figure out the relation formula. Because exploration is an extension to connecting-the-dots, we can use the technique from connecting-the-dots. We will play puzzle with the specific value of 2134 before extending this to the arbitrary value of n.

n	count_digit(n)	prev ans + value
2	1	0 + 1 = 1
21	2	1 + 1 = 2
213	3	2 + 1 = 3
2134	4	3 + 1 = 4
\(\vdots\)
n	?	\(p + 1\)

So the connecting formula is given below.

p = p + 1

With a little variable renaming, we can arrive at the following code.

Counting Digit

def count_digit(n):
  res = 0          # we use res instead of p
  while n > 0:     # we stop at 0
    res = res + 1  # connecting formula: p = p + 1
    n = n // 10    # relation formula
  return res

Sum of Digit

We can take this idea of exploration further and solve a different but related problem.

Sum of Digit

Problem Description

Given a positive integer \(n\), we want to find the sum of the digits of \(n\).

Task

Write the function digit_sum(n) to compute and return the sum of the digits of n.

Assumptions

• n is a non-negative integer (i.e., n >= 0).

Restrictions

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

Since we have already solved the count of digit problem, we can look at how it is related to the sum of digit problem. Using the same relevant inputs as before, we can compare the two problems. The difference is highlighted.

n	count_digit(n)	Operation	digit_sum(n)	Operation
2	1	0 + 1 = 1	1	0 + 2 = 2
21	2	1 + 1 = 2	2	2 + 1 = 3
213	3	2 + 1 = 3	3	3 + 3 = 6
2134	4	3 + 1 = 4	4	6 + 4 = 10
\(\vdots\)
n	?	\(p + 1\)	?	\(p + (n \% 10)\)

So the difference is only in connecting formula. We simply replace + 1 with + (n % 10) and we can solve the sum of digit problem. The expression (n % 10) comes about because we have to extract the last digit of \(n\). The code is given below.

Sum of Digit

def digit_sum(n):
  res = 0                 # we use res instead of p
  while n > 0:            # we stop at 0
    res = res + (n % 10)  # connecting formula: p = p + (n % 10)
    n = n // 10           # relation formula
  return res

Alternative

For the same of completeness of the discussion, we will show that there is not just a single solution to a problem. Here we will show an alternative for the counting digit problem and an alternative for the sum of digit problem.

Guess-and-Check

By switching our way of thinking, we can actually use guess-and-check for the counting digit problem. This may not be obvious so let us explain this a little bit further. What we need for our guess-and-check is to find a representative number for each number of digits. The representative number we will be using is the number of 0s to the right of the leftmost digit 1.

Number of Digits	Representative Number
0	1
1	10
2	100
3	1000
4	10000
\(\vdots\)

Using the representative number, we can check if a particular number n is bounded by two consecutive representative numbers. So if n is in the range of \(1000 \leq n < 10000\). then we know n has exactly 3 digits. To use this in a guess-and-check, we simply guess the number of digits one by one and compare against the representative number. Try to work out the entire steps from design to solution based on this understanding of the problem. Hopefully you will arrive at a similar code as below.

Counting Digit

def count_digit(n):
  guess, bound = 0, 1
  while n > bound:
    guess = guess + 1
    bound = bound * 10
  return guess

Unfortunately, guessing for sum of digit is probably more difficult than this because there is no representative number for a particular sum. Which is why we have the different alternative shown below. However, it might be instructive to see how the operation on this alternative count_digit relates to the original count_digit. The main connection is that we are using the inverse of // 10 operation which is * 10.

Different Exploration

The second alternative is an alternative to the sum of digit problem and it can be obtained via a more complicated exploration. Recap that during our design phase, we came up with a simple relation formula n = n // 10. However, there are some seemingly useful potential alternative.

Consider the alternative of n = n - 2000. This operation removes the leftmost digit instead of the rightmost digit like in the n = n // 10 operation. So the idea is this, why not abstract this idea of removing the leftmost digit into a function? We know how to abstract the operation of removing the rightmost digit into a function.

def remove_rightmost(n):
  return n // 10

How do we create a function to remove the leftmost digit? That requires us to know the number of digit and digit_sum is a simple modification from count_digit so this is --in a way-- cheating. So this current technique cannot be used to count the number of digits because we are invoking count_digit. Luckily, we have an alternative for count_digit already.

But let us not be afraid and assume we will simply call the function count_digit, maybe we have the function in our notes and we simply copy the function to be used. After all, that is the use of a function.

The idea is then simply to do the following sequence of operations for a given number n.

def remove_leftmost(n):
  ctx = count_digit(n)   # number of digit
  exp = 10 ** (ctx - 1)  # to get the digits except leftmost
  sub = n % exp          # all digits except leftmost
  return sub

The other thing we need to do is to extract the leftmost digit like how we extracted the rightmost digit using n % 10. Again, by using abstraction into a function we can write the following function. We use the fact that % and // operators are related. This is like % 10 and // 10 we used before but we cannot just use the constant 10.

def extract_leftmost(n):
  ctx = count_digit(n)       # number of digit
  exp = 10 ** (ctx - 1)      # to be used as denominator
  dgt = n // exp             # only leftmost digit
  return dgt

So now, we can rewrite our solution as follows.

Sum of Digit

def digit_sum(n):
  res = 0
  while n > 0:
    res = res + extract_leftmost(n)
    n = remove_leftmost(n)
  return res

But of course, the functions remove_leftmost, extract_leftmost, and count_digit are doing the heavy lifting. So this solution is much more complicated than what it looks like.

---

1. These inputs are relevant exactly because they are related. ↩