Combining Sequencing and Nesting

Learning Objectives

At the end of this sub-unit, students should

know how to combine sequencing and nesting.

Combination

Now that we have learnt how to integrate subproblems using sequencing and nesting, we can look at how they can be used to gether to solve even more complex problems. Since we have sequencing and nesting, we will provide a convenient notation to indicate our design.

Say we have two codes: Code1 and Code2. To indicate that we are doing sequencing, we will use the + notation. So Code1 + Code2 means that we perform Code1 followed by Code2. On the other hand, to indicate that we are doing nesting, we will use the parentheses. So Code1 ( Code2 ) means that we inside the code for Code1, we will nest Code2.

With this, we can scribble our design as long as the meaning of the scribble is clear to us. We can see this in the two problems we solved before.

Narcissistic Number: Count_Digit + Sum_K_Power
Unique Prime Divisor: Enumerate ( Prime )

Now we have a simple notation to combine the two integration technique.

Pymarid

Printing Pyramid

Problem Description

The pyramid pattern is given below for \(n\) from 1 to 4.

n = 1
1
*
n = 2
1 2
* ***
n = 3
1 2 3
* *** *****
n = 4
1 2 3 4
* *** ***** *******

Task

Write the function print_pyramid(n) to print a pyramid with n rows.

Assumptions

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

By looking at the high-level problem, we can decompose the problem as follows.

Enumerate the rows.
- Construct a row and print the row.

However, if look closer, constructing the row can be further decomposed into smaller problems. For a given n, at row number i, the row can be described as follows.

Row01

In the image, we represent the whitespace (i.e., ' ') as the hex symbol (i.e., '#'). With this idea, we can expand the decomposition as follows.

Enumerate the rows.
- Append the whitespace (i.e., ' ') into the row.
- Append the star (i.e., '*') into the row.
- Print the row.

In our notation, we can write this as: Enumerate ( Whitespace + Star + Print ). A naïve solution is as follows.

Pyramid

def print_pyramid(n):
  i = 1
  while i <= n:
    row = ''
    # Append whitespace
    j = 1
    while j <= n - i:
      row = row + ' '
      j = j + 1
    # Append star
    j = 1
    while j <= 2 * i - 1:
      row = row + '*'
      j = j + 1
    # Print
    print(row)
    i = i + 1

Fortunately, we have learnt about wishful thinking. We can simplify this into functions. But what functions should we write? At a glance, we might need to write a function to append whitespace and another function to append star.

Append Whitespace

def append_whitespace(i):
  row, j = '', 1
  while j <= n - i:
    row = row + ' '
    j = j + 1
  return row

Append Star

def append_star(i):
  row, j = '', 1
  while j <= 2 * i - 1:
    row = row + '*'
    j = j + 1
  return row

Considering the two codes side by side, we can notice that the two codes are almost identical. The differences are highlighted. By using generalization, we can make one function that can solve both.

We generalize n - i and 2 * i - 1 into a variable called num.
We generalize ' ' and '*' into a variable called char.

def append_char(num, char):
  row, j = '', 1
  while j <= num:
    row = row + char
    j = j + 1
  return row

Using this, we can simplify the code to print the pyramid.

Pyramid

def print_pyramid(n):
  i = 1
  while i <= n:
    row = ''
    row = row + append_char(n - i    , ' ')
    row = row + append_char(2 * i - 1, '*')
    print(row)
    i = i + 1

Diamond

Now we can extend the problem further.

Printing Diamond

Problem Description

The diamond pattern is given below for \(n\) from 1 to 4.

n = 1
1
*
n = 2
1 2 3
* *** *
n = 3
1 2 3 4 5
* *** ***** *** *

n = 4

   *
  ***
 *****
*******
 *****
  ***
   *

Task

Write the function print_diamond(n) to print a pyramid with 2 * n - 1 rows.

Assumptions

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

First, notice how the top n rows is really just the pyramid problem.

n = 1
1
*
n = 2
1 2 3
* *** *
n = 3
1 2 3 4 5
* *** ***** *** *

n = 4

   *
  ***
 *****
*******
 *****
  ***
   *

This was solved via decomposition and integration as follows.

Enumerate n rows.
- Append the whitespace (i.e., ' ') into the row.
- Append the star (i.e., '*') into the row.
- Print the row.

We are still missing n - 1 rows, so the full decomposition can be as shown below.

Enumerate n rows as i from 1 up to n.
- Append n - i whitespace (i.e., ' ') into the row.
- Append 2 * i - 1 star (i.e., '*') into the row.
- Print the row.
Enumerate n - 1 rows as i from n - 1 down to 1.
- Append n - i whitespace (i.e., ' ') into the row.
- Append 2 * i - 1 star (i.e., '*') into the row.
- Print the row.

This can be expressed with additional details given in square brackets as follows.

Enumerate[1, n] ( Whitespace[n-i] + Star[2i-1] + Print ) + Enumerate[n-1, 1] ( Whitespace[n-i] + Star[2i-1] + Print )

If you are doing your own design and you are clear with your own design, you may even just write it simply as (Enumerate ( Whitespace + Star + Print)) * 2. But of course, with simpler design, it may only be clear to you and not other people. Often, that is what matters because we expect a correct code instead of just a scribble.

Back to the problem at hand. We can write the long code but since we already have append_char, we can simplify the solution as follows.

Print Diamond

def print_diamond(n):
  i = 1
  while i <= n:
    row = ''
    row = row + append_char(n - i    , ' ')
    row = row + append_char(2 * i - 1, '*')
    print(row)
    i = i + 1
  i = n - 1
  while i > 0:
    row = ''
    row = row + append_char(n - i    , ' ')
    row = row + append_char(2 * i - 1, '*')
    print(row)
    i = i - 1

Once our repertoire of problems have increased or we have improved our problem solving skills, we may even convert Line 2 to Line 8 into a call to print_pyramid.

Print Diamond

def print_diamond(n):
  print_pyramid(n)
  i = n - 1
  while i > 0:
    row = ''
    row = row + append_char(n - i    , ' ')
    row = row + append_char(2 * i - 1, '*')
    print(row)
    i = i - 1

The remaining problem is to print the inverted pyramid. We can call this inverted pyramid by inverting the letters into dimaryp. So we need a code to print a dimaryp. This is simply the remaining part.

Print Dimaryp

def print_dimaryp(n):
  """
  Print (n - 1) rows of inverted pyramid
  """
  i = n - 1
  while i > 0:
    row = ''
    row = row + append_char(n - i    , ' ')
    row = row + append_char(2 * i - 1, '*')
    print(row)
    i = i - 1

We put the documentation to remind us that it is printing only n - 1 rows even when the input is n. So now, the code is very straightforward.

Print Diamond

def print_diamond(n):
  print_pyramid(n)
  print_dimaryp(n)

In terms of the decomposition, we can represent it as: Pyramid + Dimaryp. But this is actually hiding the complexities. So the design depends on how comfortable we have at decomposition.