Number and alphabet patterns in Python

Why this matters

The star patterns in the last lesson taught the method. The shape of the picture told you how many symbols to print. In this lesson the symbol changes. Each cell may show a number, a letter, or a value worked out from the cells around it. That is closer to real programming, where a loop often does more than print the same character again and again.

Interviewers use number and letter patterns to test whether you understand a counter. A counter is a variable that changes on every pass of a loop, and a program can print it. If you can say what a counter holds on each pass, you can predict most number patterns. The most famous example, Pascal's triangle, is a table of values in which each new value is built from values already computed. That idea appears in many later topics.

You will write several complete programs in this lesson. You will also meet the list of lists, which is Python's way to store a table in memory. Trace each program slowly. The same tracing skill is what every later topic needs.

The idea: the shape stays, the symbol changes

Every pattern in the previous lesson had one symbol, a star. A number or letter pattern keeps the same shape, but each cell now needs a value. There are three questions to ask for every cell:

1. Which row am I on? That is the outer counter, usually i.
2. Which position am I in within the row? That is the inner counter, usually j.
3. What value belongs in this cell? The answer might be i, j, a counter that keeps growing, a letter, or a value computed from earlier cells.

Here is a small example that shows how much one variable changes the result. Both programs use the same loops. Only the value printed is different. The first prints the row counter i:

For each row i, the inner loop prints i once for each position. Row 1 prints 1. Row 2 prints 22, because i is 2 and it is printed twice. Row 3 prints 333. The output is 1, then 22, then 333.

The second program prints the position counter j instead:

Now row 2 prints 1 and then 2, which is 12. Row 3 prints 123. The output is 1, then 12, then 123. The loops are nearly the same, and the only difference is which counter is printed. Decide which counter you want to see before you write the print line.

Worked example 1: a number triangle

The first program prints a triangle in which each row repeats its own row number. Row 1 shows 1, row 2 shows 22, row 3 shows 333, and so on. The row number is the value, and the inner loop decides how many copies of it appear.

Type 4 in the Input box when you run this program saved as a file.

n = int(input())
for i in range(1, n + 1):
    for _ in range(i):
        print(i, end="")
    print()

The output for 4 is:

1
22
333
4444

Trace row 3 slowly. The outer loop sets i to 3. The inner loop runs three times. Each pass prints the current value of i, which is 3. It does not print the position. So the row number is printed, and the inner loop only decides how many copies appear.

The planning table for this pattern has a column for the value. Row i has i copies of the value i. A common confusion is to think the inner counter must be printed. It does not have to be, and in this pattern it should not be.

Worked example 2: Floyd's triangle and a counter that never resets

Floyd's triangle is a number triangle with a different rule. It writes the numbers 1, 2, 3, and so on, in order, reading the triangle row by row. The first row holds 1. The second row holds 2 and 3. The third row holds 4, 5 and 6. Each row is one number longer than the row before it, and the numbers never start again at 1.

row 1:  1
row 2:  2  3
row 3:  4  5  6
row 4:  7  8  9 10

The rule contains a trap. The value in a cell depends on how many values were printed before it, not on the row number alone. So the program needs a third variable, a counter that goes up every time a number is printed. The counter must be created before the outer loop starts, so it keeps its value from one row to the next.

Type 4 in the Input box when you run this program saved as a file.

n = int(input())
next_value = 1
for i in range(1, n + 1):
    for j in range(1, i + 1):
        if j > 1:
            print(" ", end="")
        print(next_value, end="")
        next_value += 1
    print()

The output for 4 is:

1
2 3
4 5 6
7 8 9 10

The variable next_value is created before the outer loop, so it keeps its value between rows. The line next_value += 1 adds one, which is a short way to write next_value = next_value + 1.

If next_value is created inside the outer loop, every row starts again at 1. The next program shows that mistake on purpose. Its output has a trailing space at the end of each line.

The output is:

1 
1 2 
1 2 3 

The inner check if j > 1 in the correct program prints a space before every number except the first in each row. That gives single spaces between values with no space at the end of the line. Python also has a method that joins a list of values with spaces. It is shown with Pascal's triangle below.

Trace row 3 in the correct program. Before row 3 starts, next_value holds 4, because rows 1 and 2 printed 1, 2 and 3. The inner loop prints 4, then a space and 5, then a space and 6. Then next_value holds 7, which starts row 4.

Letters and character codes

A letter is a single character. Python has no separate character type. A letter is a string of length 1, such as "A".

Every character has a number code. The function ord gives the code of a character, and the function chr gives the character for a code. For example, ord("A") is 65, and chr(65) is "A". The codes for uppercase letters go from 65 for "A" to 90 for "Z". Lowercase letters start at 97.

This is why letter patterns can use arithmetic. Add 2 to the code of "A" and you get the code of "C". Convert the number back with chr.

Run this example. It prints the code of "A", then the code two places on, then that letter, then the letter after "A".

The output is:

65
67
C
B

A common mistake is to add a number to a letter without ord. The expression "A" + 2 does not give "C", and Python refuses to run it. This program makes the mistake:

ch = "H"
print(ch + 1)

Python prints this message:

TypeError: can only concatenate str (not "int") to str

The message says that + joins two strings, and that a number is not a string. Use ord to get the code, add the number, and use chr to get the letter back.

If you know Java, note that Python has no char type. A letter is a one-character string, so ord and chr move between a letter and its code.

Worked example 3: an alphabet triangle

The alphabet triangle prints the first letters of the alphabet, one more letter in each row. Row 1 is A. Row 2 is AB. Row 3 is ABC. The shape is the same triangle as in the star lesson, but the symbol is a letter that depends on its position.

The planning table has a column for the letter count and a column for the last letter. Row i has i letters. The last letter is the one at position i counting from A as 1. With row 4, the last letter is D, because A is 1, B is 2, C is 3 and D is 4.

Type 4 in the Input box when you run this program saved as a file.

n = int(input())
for i in range(1, n + 1):
    for k in range(i):
        print(chr(ord("A") + k), end="")
    print()

The output for 4 is:

A
AB
ABC
ABCD

The inner loop counts k from 0 up to i minus 1. For k equal to 0, ord("A") + 0 is 65, and chr(65) is "A". Each pass prints the next letter. The loop does not need a letter counter, because the letter is computed from k.

Python can also read a string by position, and that gives a shorter version. A string such as letters[:i] is the first i characters of the string. The part before the colon is the start, which is empty here, so it means the beginning. The part after the colon is where to stop, and the stop position is not included.

letters = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
n = int(input())
for i in range(1, n + 1):
    print(letters[:i])

The output for 4 is the same as before. Positions in a Python string start at 0, so letters[0] is "A" and letters[3] is "D".

Worked example 4: Pascal's triangle

Pascal's triangle is the most famous number pattern in mathematics, and it is a favourite interview question. It has one row for each number of items, starting at the top with a single 1. Each new number is the sum of the two numbers directly above it, and the first and last number of every row are 1. Here is the start of the triangle, with the rows numbered from 0 at the top:

row 0:          1
row 1:        1   1
row 2:      1   2   1
row 3:    1   3   3   1
row 4:  1   4   6   4   1

Each interior number is the sum of the two above it. For example, row 2's middle 2 comes from the 1 and the 1 above it in row 1, which add to 2. Row 3's 3 comes from 1 and 2, which add to 3. Row 4's 6 comes from the 3 and 3 above it.

The values have a meaning too. The number in row i at position j counts the ways to choose j items from i items when the order does not matter. You do not need that meaning to print the triangle, but it helps when you check the values. For example, choosing 2 items from 4 gives 6 ways, which is row 4's middle value.

A table for this pattern is a list of lists. A list is a sequence of values in square brackets, and a list of lists is a list whose values are lists. The table is created with this line:

c = [[0] * n for _ in range(n)]

This makes n rows, and each row is a list of n zeros. The part [0] * n builds one row, and the part for _ in range(n) repeats it n times. Each new row is a separate list. The first row of the table is c[0], and the cell in row i at position j is c[i][j]. Positions start at 0 in Python.

The program fills the table one row at a time, from the top down. Each cell reads two cells from the row above, so those cells are already filled when they are needed.

Type 5 in the Input box when you run this program saved as a file.

n = int(input())
c = [[0] * n for _ in range(n)]
for i in range(n):
    c[i][0] = 1
    for j in range(1, i + 1):
        c[i][j] = c[i - 1][j - 1] + c[i - 1][j]
for i in range(n):
    print(" ".join(str(x) for x in c[i][: i + 1]))

The output for 5 is:

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1

The first loop sets the first value of each row to 1, and then fills the inner values from the row above. Row 0 has no inner values, so the inner loop does nothing there. The second loop prints the rows. The slice c[i][: i + 1], which works on lists as it does on strings, takes the first i + 1 values of row i, so the zeros on the right of each row are not printed. The method " ".join(...) puts a single space between the strings it is given. Each value is turned into text with str, because join works only on text.

One detail needs care. When j equals i, the code reads c[i - 1][i]. That place is past the last value printed for the row above, but it exists, because each row has n places. Its value is 0, so the sum gives the right answer. This is why each row has n places, even though the top rows use only a few of them.

Python integers have no fixed size limit. The value C(34, 17) is 2,333,606,220, which is larger than the biggest value a 32-bit integer can hold. Python keeps the exact value, and it does not wrap around. Run this program to check the value:

The output is:

2333606220

Larger tables take more memory and more time, but the numbers themselves do not overflow.

Columns of numbers with f-strings

A pattern often needs numbers to line up in columns. In Python, the way to do this is an f-string. An f-string is a string that starts with the letter f before the quotes, and it can put a value inside braces. The format {v:3d} means: print the number v as an integer in at least three places, padded with spaces on the left.

Run this example:

The output is:

  7| 12|1234

The number 7 has two spaces in front of it, because it takes three places. The number 1234 is longer than three places, so it is printed in full.

Here is Pascal's triangle with four rows, printed in aligned columns. The end="" argument keeps the values on one line, and print() ends each row.

The output is:

  1
  1  1
  1  2  1
  1  3  3  1

Planning a number pattern with a table

A planning table for a number pattern needs one more column than the star table. Add a column for the value printed in each cell, or the value the counter holds on each row. The planning steps are the same as before:

1. Draw the first three rows and write the value in each cell.
2. Look for a rule in the values. Is each value the row number? Is it a counter that keeps going? Is it the sum of two cells above?
3. Write the rule as code, and check it on the first and last row.
4. For the triangle shape, write the spaces and the cell count as in the star lesson.

For the number triangle the rule is the row number. For Floyd's triangle the rule is a counter. For Pascal's triangle the rule is the sum of the two cells above. You will meet each of these rules in the exercises. Name the rule before you write the loop, and the code follows.

What happens inside a list of lists

A cell in a list of lists is reached with two indexes, as in c[i][j]. The first index picks the row, and the second picks the position in that row. Positions start at 0.

Python checks the index every time you use it. If the index is too large, Python stops the program and prints an error. Here is a short program that asks for a position past the end of a list with five places:

a = [0] * 5
print(a[5])

Python prints this message. The list has positions 0 to 4, so position 5 does not exist.

  File "...", line 2, in <module>
    print(a[5])
          ~^^^
IndexError: list index out of range

Read it in this order. The last line names the problem: the index is out of range. The line above it shows the line of code that failed.

Python also accepts negative indexes. The index -1 means the last place in the list, -2 means the one before it, and so on. This is useful, and it is also a trap. In the Pascal program, c[i - 1] with i equal to 0 would be c[-1], which is the last row of the table. Python would not stop, and it would read a value that makes no sense for row 0. The program avoids the problem only because the inner loop does not run when i is 0.

The output is:

4

A trap with lists of lists

A tempting way to build a table is [[0] * 2] * 2. It looks like it makes two rows of two zeros. Set one value and look at the result:

The output is:

[[1, 0], [1, 0]]

Both rows changed, although only one was set. The expression * 2 puts the same list into both places, so the two rows are one list. The list comprehension used in the Pascal program, [[0] * n for _ in range(n)], creates a new row each time, so the rows are separate.

Tracing Floyd's counter step by step

Before you run a pattern that uses a counter, trace it on paper. For n equal to 3, the trace has one line for every printed value. The table records the row, the position within the row, the value printed, and the value of the counter after the print.

Read the last column as a chain. The counter starts at 1, and each print uses its current value and then moves it on by one. The chain does not break at the end of a row, because the counter is never reset. The final value, 7, is one more than the last number printed.

The trace also shows the two loops at work. A row ends when j reaches the row number i. Row 2 holds two values, and row 3 holds three. The outer counter decides how many values each row needs, and the shared counter decides which value each one gets. Keeping those two jobs apart is the main idea of this pattern.

Practise the trace before you write the code. Choose a small n, such as 3 or 4, and fill in the table with a pencil. Then write the loops and check that the output matches the last column.

Common mistakes and their real messages

Mistake 1: printing the wrong counter. A number pattern often prints j when it should print i, or the other way round. The shape is right, but the numbers are wrong. Check the print line, and ask which counter it should show. The number triangle should print 1, 22, 333. Printing j instead gives 1, 12, 123, which is a different picture.

Mistake 2: resetting a counter that must carry on. Floyd's triangle needs a counter that never resets. If you create next_value inside the outer loop, every row starts again at 1. Python prints no error. The output is simply wrong, as the example earlier in this lesson showed. The fix is to create the counter before the outer loop.

Mistake 3: adding a number to a letter. The expression "H" + 1 raises a TypeError, as shown earlier. Use ord to get the code, add the number, and use chr to get the letter back.

Mistake 4: an index past the end. Reading c[i - 1] when i is 0 can give a negative index, which Python accepts without an error. Reading an index that is too large gives IndexError: list index out of range. Keep the reads inside the loop that runs only when the read is safe.

Mistake 5: a list that shares its rows. The expression [[0] * n] * n makes one row, shared by every position. Use [[0] * n for _ in range(n)], as shown in this lesson.

Mistake 6: a range that stops one early. This program leaves out the last cell of each row, because range(1, i) stops before i:

The output is:

1
1 0
1 1 0
1 2 1 0

The right output is the Pascal table from before. Here the last cell of each row stays at 0. The fix is range(1, i + 1).

Mistake 7: forgetting the edges. Pascal's triangle has a 1 at the start and end of every row. If the first value of a row is not set to 1, every value that depends on it is wrong too. Set the first value of each row before you fill the middle of the row.

Debugging walkthrough: the Pascal values are wrong

Suppose you wrote Pascal's triangle with range(1, i) and the output is the one shown in the last mistake. The first wrong line is row 1, which shows 1 0 instead of 1 1. Walk through the steps.

Step 1: find the first wrong cell. Row 1 has the wrong value at its end, so the problem is at c[1][1]. Look at the first wrong line, not the last one, because the first error is usually the cause of the others.

Step 2: ask how that cell is filled. The rule is c[i][j] = c[i - 1][j - 1] + c[i - 1][j]. For i equal to 1 and j equal to 1, that is c[0][0] + c[0][1], which is 1 plus 0. The correct value is 1, but the cell still holds 0, so the cell was never written.

Step 3: find the reason the cell was not written. The inner loop is for j in range(1, i). For i equal to 1 this loop has no values, so the cell is skipped. The loop stops one place early. Changing it to range(1, i + 1) writes the last cell of each row.

Step 4: run the program again and check the last value of every row. Each edge must be 1, and every middle value must equal the sum of the two above it.

The same idea works for any table of values. Find the first wrong cell, read the rule that fills it, and check the inputs the rule uses. Usually one of those inputs is wrong, or a loop does not reach the cell.

Variations and edge cases

Test every number pattern at n equal to 1 first. The number triangle prints a single 1. Floyd's triangle prints a single 1. Pascal's triangle prints a single 1, which is the top of the triangle. The alphabet triangle prints a single A. A program that gets n equal to 1 wrong usually has an off-by-one error in the outer range.

Test n equal to 0 next. Every loop over range(n) or range(1, n + 1) runs zero times, so the program prints nothing. For the Pascal program, the list has zero rows, and no row is printed. That is the right output for zero rows, and the program does not crash.

The alphabet pattern has its own edge case. The letters run out after Z, which has the code 90. The code 91 is [. A loop that counts up from ord("A") keeps going past Z and prints [ and then other symbols. Run this program to see it:

The output is:

ABCDEFGHIJKLMNOPQRSTUVWXYZ
[

Slicing stops at the end of the string, so letters[:27] gives the 26 letters and no error. A careful program checks that n is at most 26 before it starts. The conditionals module teaches that check.

Pascal's triangle has a property that makes a good check. The sum of all the numbers in row i is 2 raised to the power i. Row 4 has 1 plus 4 plus 6 plus 4 plus 1, which is 16, and 2 to the power 4 is also 16. This program prints the sums for six rows, using sum, which adds up the values in a list:

The output is:

1
2
4
8
16
32

Each sum is a power of 2. If a row fails this check, one of its values is wrong.

Interview questions and real uses

Pascal's triangle appears in interviews because it has many questions hidden inside it. An interviewer may ask you to print the first n rows, to find the value at a given row and column, to check that every row sums to a power of 2, or to find the row that contains a given number. Each question is a small variation on the table you have just built.

A strong answer to "print the first n rows" follows the planning method. "I will build a table of n rows. Each row starts and ends with 1. Every other value is the sum of the two values above it. I will fill the table from the top down, so every value I need already exists. The time is proportional to the number of cells, which is about n squared over two." That answer names the rule, the order of work and the cost. Interviewers also value a note about the size of the numbers, because it shows you know how the numbers grow.

Number patterns also appear in real programs. A table of prices with a running total, a list of invoice numbers that continue from one batch to the next, and a calendar that counts days across months all use the same idea as Floyd's counter. The value depends on what came before, and the variable that carries it across rows is the one you must keep alive.

Practice

Try each exercise before you open its answer. The first four use the Input box, and some use fixed numbers. Write the program, trace a small n by hand, and then run it.

Exercise 1. Print the number triangle for n equal to 5, where row i repeats the row number i exactly i times. Check that row 5 has five 5s.

Show the answer

The output is 1, then 22, then 333, then 4444, then 55555, one row on each line. Use the number triangle from worked example 1 with n equal to 5.

Exercise 2. Print the number staircase: row i shows the numbers 1 up to i, separated by single spaces, with no space at the end of a line. For n equal to 4 the rows are 1, 1 2, 1 2 3, 1 2 3 4.

Show the answer

Print j in the inner loop, which runs from 1 to i, and use the if j > 1 check to print the separating space. The output for 4 has four lines, and the last line has no trailing space.

n = int(input())
for i in range(1, n + 1):
    for j in range(1, i + 1):
        if j > 1:
            print(" ", end="")
        print(j, end="")
    print()

Exercise 3. Print Floyd's triangle for n equal to 6. Work out on paper which value starts row 6 before you write any code.

Show the answer

Rows 1 to 5 hold 15 values in total, 1 plus 2 plus 3 plus 4 plus 5. So row 6 starts at 16. Use the Floyd program from worked example 2 with the input 6. The last line is 16 17 18 19 20 21.

Exercise 4. Print the alphabet triangle for n equal to 6, where row i shows the letters from A up to the ith letter. Then print the inverted version, where row 1 shows six letters, row 2 shows five, and so on down to A on the last row.

Show the answer

The rising version is worked example 3 with the input 6. The inverted version prints letters[: n - i + 1] on each row, so row 1 is the first six letters, and the last row is A. The output of the inverted version is:

ABCDEF
ABCDE
ABCD
ABC
AB
A

Exercise 5. Print the letters of the alphabet from A to Z on one line, using a loop over the characters of a string. Then print every second letter, A, C, E, and so on, up to Y.

Show the answer

The string letters can be used directly in a for loop, and each pass gives one character. For every second letter, use a range with a step of 2, and turn each number into a letter with ord and chr. The last letter printed is Y, because Y is 24 places after A, which is even.

The output is:

ABCDEFGHIJKLMNOPQRSTUVWXYZ
ACEGIKMOQSUWY

Exercise 6. Build Pascal's triangle for n equal to 10 and print only the last row. Predict the last row before you run the program. Check that its values add up to 512.

Show the answer

The last row of the 10-row table is row 9. It is 1 9 36 84 126 126 84 36 9 1, and the sum is 512, which is 2 to the power 9. Build the full table, and then print row n - 1.

n = int(input())
c = [[0] * n for _ in range(n)]
for i in range(n):
    c[i][0] = 1
    for j in range(1, i + 1):
        c[i][j] = c[i - 1][j - 1] + c[i - 1][j]
print(" ".join(str(x) for x in c[n - 1][:n]))
print(sum(c[n - 1]))

Exercise 7. The following code should print the letter after H, which is I. It prints an error instead. Find the bug and fix it.

ch = "H"
print(ch + 1)

Show the answer

The expression ch + 1 adds a number to a string, which Python does not allow. The message is TypeError: can only concatenate str (not "int") to str. Use ord to get the code of H, add 1, and use chr to turn the result back into a letter. The fixed line is print(chr(ord(ch) + 1)), and it prints I.

Exercise 8. Find the bug. A program prints Pascal's triangle with the inner loop written as for j in range(1, i):. Its output for n equal to 4 is shown below. What is wrong, and what is the fix?

1
1 0
1 1 0
1 2 1 0

Show the answer

The loop stops one place early. range(1, i) does not include i, so the last cell of each row is never written and stays at 0. The first wrong line is row 1, which shows 1 0 instead of 1 1. Change the inner loop to for j in range(1, i + 1):. Then every row ends with a 1, as the table in this lesson shows.

Exercise 9. Print the sums of the rows of Pascal's triangle for rows 0 to 5. Predict the sums first. Then check that each sum is a power of 2.

Show the answer

The sums are 1, 2, 4, 8, 16 and 32, which are 2 to the power 0, 1, 2, 3, 4 and 5. The program is the one from the variations section, with a table of six rows. The output has one sum on each line.

Exercise 10. Print Pascal's triangle for n equal to 4, with each number in a field three places wide, so the numbers line up in columns. Predict how many spaces appear before the single 1 in the first row.

Show the answer

Each value takes three places, so the single 1 in row 0 has two spaces in front of it. The format {v:3d} in an f-string pads each number to three places on the left. The output is the same as the aligned example earlier in this lesson:

  1
  1  1
  1  2  1
  1  3  3  1

Summary

Decide the value of each cell before you write its loop. Python lists and strings start counting at 0, and a negative index does not raise an error, so check the indexes you read. Python integers have no fixed size limit, so a table of large numbers stays exact.

The next lesson moves from numbers and letters to pyramids. There the spaces and the stars both change, so the planning table has to track two things at once.