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:

1
2
3
4
5
def triangle
  5.times do
    print '#'
  end
end

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.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
def print_pound(n)
  n.times do
    print '#'
  end
  puts 
end

def triangle
  5.downto(1) do |n|
    print_pound(n)
  end  
end

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.

1
2
3
4
5
def triangle
  for row in (1..5)
    print '#'
  end
end

We can now print the number of pounds for each row using the relationship between the number of pounds and the row:

1
2
3
4
5
6
def triangle
  for row in (1..5)
    print '#' * (6 - row)
    puts
  end
end

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.

1
2
3
4
5
6
7
8
def triangle
  for row in (1..5)
    for i in (1..(6 - row))
      print '#' 
    end
    puts
  end
end

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:

1
2
3
4
5
6
7
8
def triangle
  for row in (1..5)
    for i in (1..5)
      print '#' 
    end
    puts
  end
end

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.

1
2
3
4
5
6
7
8
def triangle
  for row in (1..5)
    for i in (1..row)
      print '*' 
    end
    puts
  end
end

The numbers can be printed instead of * as follows:

1
2
3
4
5
6
7
8
def triangle
  for row in (1..5)
    for i in (1..row)
      print i 
    end
    puts
  end
end

This prints:

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.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
def triangle
  for row in (1..7)
    upper = 4 - (4 - row).abs

    for i in (1..upper)
      print '#'
    end
    puts
  end
end

Recursive Implementation

The tail and head recursion can be combined to print the sideways triangle:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
def triangle(n)
  if n == 5
    return
  end
  
  print '#' * n
  puts
  triangle(n+1)
  if n != 4
    print '#' * n
    puts
  end
end

The counting down will print a hourglass shape.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
def triangle(n)
  if n == 0
    return
  end
  
  print '#' * n
  puts
  triangle(n-1)
  print '#' * n
  puts
end

Building Blocks

Problem Reduction
Count Down by Counting Up
Head Recursion
Tail Recursion
Nested for Loops
Using Equation for Upper Bound