DPBO – Final Exam (Programming): Isosceles Triangle of Numbers (Problem B1)

This is the third post for the series. For other posts in the series, see:

• 1st part: Longest Common Substring (Problem A1)
• 2nd part: Generic Bubble Sort (Problem A2 and C2)

The following describes the problem:

Make a program to print out numbers in triangular patterns according to the output examples. The program will accept a positive integer not larger than 20 as a command-line parameter. Output examples are given below. Note that no space is printed before the last row of the triangle.

Output examples:

[sourcecode gutter="false" toolbar="false"]
> java DisplayTriangleOfNumbers 1
1
> java DisplayTriangleOfNumbers 3
1
212
32223
> java DisplayTriangleOfNumbers 7
1
2 1 2
3 2 2 2 3
4 3 4 4 4 3 4
5 4 6 8 8 8 6 4 5
6 5 81216161612 8 5 6
7 6101624323232241610 6 7
[/sourcecode]
Here is the solution:
[sourcecode language="java" light="true"]
/**
* This class is a solution for problem B1 in DPBO programming exam.
* The problem task:  print out numbers in a triangular form, depending
* on the input parameter given as a command-line argument.
*/
public class DisplayTriangleOfNumbers {
public static void main(String[] args) {
int input = Integer.parseInt(args[0]);
cetak(input);
}
/**
* Static method that prints out the numbers in a triangular form
* whose size depends on the input integer.
*
* To clarify the aim of this method, the following are some examples of expected outputs.
*
* Size = 1:
<pre> 1</pre>
* Size = 3:
<pre> 1
212
32223</pre>
* Size = 7:
<pre> 1
2 1 2
3 2 2 2 3
4 3 4 4 4 3 4
5 4 6 8 8 8 6 4 5
6 5 81216161612 8 5 6
7 6101624323232241610 6 7</pre>
*
*
Assume that n[i,j] is the jth element of the ith row where i and j starts from 0.
* Closer inspection leads to the following relations:
<pre> n[i][0] = i+1 for all i</pre>
n[i][j] = n[i-1][j-1] + n[i-2][j-2] + ... + n[i-j][0] for 0 < j <= i
n[i][j] = n[i][2i-j] for i < j <= 2i
*
Let size = N. With this relation in mind, we employ one two dimensional integer arrays with N rows
* and (i+1) column for the ith row (i starts from 0). It's not necessary to store explicitly every element
* of the triangle in the array because of symmetry as induced by the third equation above.
*
In order to print the array contents into a smooth isosceles triangle, care must be taken in implementing
* the pretty printing. In particular, we have to make sure that each number is printed in such a way the width
* for printing each of them is equal to the width of the cell with maximum number of digits (except the leftmost
* number on the last row). Number of spaces printed before printing each row must also be calculated according
* to abovementioned width.
*
* @param b size parameter of the triangle, <code> 1<=b<=20</code>.
*/
public static void cetak(int b) {
// the main 2-dimensional array to store the numbers (its number of rows is b)
int nums[][] = new int[b][];
// auxiliary 2-dimensional array to store the sum of numbers obtained so far so that
// we don't have to loop to compute n[i][j] = n[i-1][j-1] + n[i-2][j-2] + ... + n[i-j][0]
int sums[][] = new int[b][];
// The main loop filling the array according to:
// n[i][0] = i+1 for all i
// n[i][j] = n[i-1][j-1] + n[i-2][j-2] + ... + n[i-j][0] for 0 < j <= i
for (int i=0; i < b; i++) {
nums[i] = new int[i+1];
sums[i] = new int[i+1];
sums[i][0] = nums[i][0] = i+1;
for (int j=1; j<=i; j++) {
nums[i][j] = sums[i-1][j-1];
sums[i][j] = sums[i-1][j-1] + nums[i][j];
}
}
// This is the maximum width of all array cells, equals to
// the number of digits of nums[b-1][b-1] which is obviously the largest number in the triangle.
int maxcellwidth = String.valueOf(nums[b-1][b-1]).length();
// Pretty-printing starts here.
for (int i=0; i < b; i++) {
// Number of spaces needed before printing the first number of the ith row.
int spacenum = (b-2)-i < 0 ? 0 : ((b-2)-i)*maxcellwidth + String.valueOf(nums[b-1][0]).length();
for (int j=0; j
// To print each number, we use format method which allows us to specify the width explicitly.
for (int j=0; j<=i; j++) { String formatnum = (i == b-1 && j == 0) ? "%d" : "%" + maxcellwidth + "d"; System.out.format(formatnum, nums[i][j]); } //Similar part as above, but this is for the symmetric part. for (int j=i-1; j>=0; j--) {
String formatnum = "%" + maxcellwidth + "d";
System.out.format(formatnum, nums[i][j]);
}
System.out.println();
}
}
}
[/sourcecode]