Half of a Square
excerpt: This covers the basic building blocks, Problem Reduction and Count Down by Counting Up. tags: problemreduction countdownbycountingup headrecursion tailrecursion nestedforloops usingequationforupperbound
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