Half of a Square
excerpt: This covers the basic building blocks, Problem Reduction and Count Down by Counting Up. tags: problem-reduction count-down-by-counting-up head-recursion tail-recursion nested-for-loops using-equation-for-upper-bound
Write a program to print a triangle as shown below:
#####
####
###
##
#
First task is to print 5 pound symbols:
|
|
This is problem reduction in action. A naive approach to print the triangle:
def triangle
5.times do
print '#'
end
puts
4.times do
print '#'
end
puts
3.times do
print '#'
end
puts
2.times do
print '#'
end
puts
1.times do
print '#'
end
end
We can refactor the code to remove duplication by using a variable. The value decrements from 5 to 1. The initial value of the variable is 5 and the last value is 1.
|
|
Alternative Approach
Find the relationship between the number of pounds to print and the row number. The first row must print 5, second row must print 4 and so on. We can print the pounds in a for loop.
|
|
We can now print the number of pounds for each row using the relationship between the number of pounds and the row:
|
|
This approach results in lot less code than the previous approach. For a detailed explanation of how the relationship is derived, read the chapter 2 of Think Like a Programmer book.
The code can be rewritten as shown below to make it easy to write in other languages.
|
|
The inner for loop reduces the number of pounds to print gradually as the row value increases. This is the building block Count Down by Counting Up in action.
A square can be printed by the code:
|
|
How can we print the upside down view of the previous problem?
*
* *
* * *
* * * *
* * * * *
The inner loop will start from one and stop at the end index provided by the outer loop.
|
|
The numbers can be printed instead of * as follows:
|
|
This prints:
1
12
123
1234
12345
Sideways Triangle
Iterative Implementation
#
##
###
####
###
##
#
The key to solving this problem is to find an expression to vary the upper bound for the inner for loop.
|
|
Recursive Implementation
The tail and head recursion can be combined to print the sideways triangle:
|
|
The counting down will print a hourglass shape.
|
|
Building Blocks
- Problem Reduction
- Count Down by Counting Up
- Head Recursion
- Tail Recursion
- Nested for Loops
- Using Equation for Upper Bound