7
\$\begingroup\$

Our task was to calculate the entry of a Pascal’s triangle with a given row and column recursively. The triangle was specified in a way that the tip of the triangle is column = 0 and row = 0. That said, column 0 has always the entry 1.

My concerns are that the way I initialize the triangle as an array and filling in the entries are not so super.

class EntryOfPascalsTriangle {
    public static void main(String[] args) {
        validateInput(args);

        int row = 0;
        row = parseInteger(args[0]);

        int column = 0;
        column = parseInteger(args[1]);

        // A Pascal’s triangle expands quadratic.
        // There are never entries at a position greater column length
        if (column > row) {
            handleError("There can't be entries in a column that doesn't exist in a Pascal's triangle.");
        }

        // We know already that the first and last entries in a row are always 1
        if (column == 0 || column == row) {
            System.out.println(1);
            System.exit(0);
        }

        int pascalsTriangle[][] = initPascalsTriangle(row);

        // initPascalsTriangle() takes care of the cases `0` and `1` already …
        if (row > 1) {
            // … so we can start to fill the rows starting from 2.
            pascalsTriangle = fillPascalRows(pascalsTriangle, 2);
        }

        System.out.println(pascalsTriangle[row][column]);
    }

    /**
     * Initializes a Pascal’s triangle with all cells filled with `0`
     * except for the first and last cell in a row which are `1`
     */
    private static int[][] initPascalsTriangle(int rows) {
        int[][] pascalsTriangle = new int[rows+1][];

        // Iterate over the columns of the rows of pascalsTriangle
        for (int cell = 0; cell < pascalsTriangle.length; cell++) {
            pascalsTriangle[cell] = new int[cell+1];

            // Fill the first cell of each row with `1`
            pascalsTriangle[cell][0] = 1;

            // Also fill the last cells with `1`
            pascalsTriangle[cell][cell] = 1;
        }

        return pascalsTriangle;
    }

    /**
     * Fills in the cells of Pascal’s triangle recursively
     */
    private static int[][] fillPascalRows(int[][] pascalsTriangle, int row) {
        for (int cell = 1; cell < pascalsTriangle[row].length-1; cell++) {
            pascalsTriangle[row][cell] = pascalsTriangle[row-1][cell-1] + pascalsTriangle[row-1][cell];
        }

        if (row < pascalsTriangle.length-1) {
            fillPascalRows(pascalsTriangle, row+1);
        }

        return pascalsTriangle;
    }

    /**
     * We need to make sure that two arguments are provided
     * and fail with a helpful message if they weren’t.
     */
    private static void validateInput(String[] args) {
        if (args.length < 2) {
            handleError("Not enough arguments.");
        }

        if (args.length > 2) {
            handleError("Too many arguments.");
        }
    }

    /**
     * Small wrapper to parse strings as integers.
     */
    private static int parseInteger(String arg) {
        int result = 0;

        try {
            result = Integer.parseInt(arg);
        } catch (NumberFormatException nfe) {
            handleError("'" + arg + "' was not an integer.");
        }

        return result;
    }

    /**
     * Small wrapper to produce error messages
     */
    private static void handleError(String errorMessage) {
        String basicUsage = "Please enter the column and the row of a Pascal's triangle.";
        System.out.println(errorMessage);
        System.out.println("\n" + basicUsage);
        System.exit(1);
    }
}
\$\endgroup\$

4 Answers 4

7
\$\begingroup\$

Since this question is marked as beginner, let me compliment the neat structure and consistent style I see throughout. It's well done.

Variable, method, and class names are all meaningful, and useful.

The validation and error handling systems are uncommonly comprehensive, and again, well done.

Validation

The validation should provide more feedback to the user. Saying 'not enough arguments' is fine, but then you should also say how many are expected. Does the user have to engage on a guessing game, bouncing between too many arguments, and not enough arguments before discovering how many they need?

Pre-initializing variables

There is no need to preinitialize variables. The following:

    int row = 0;
    row = parseInteger(args[0]);

    int column = 0;
    column = parseInteger(args[1]);

can just be:

    int row = parseInteger(args[0]);
    int column = parseInteger(args[1]);

Algorithm

THis is where I see the biggest problem, and it's not because you've made a mess, but because I think you've missed the point. If the problem is: "... to calculate the entry of a Pascal’s triangle with a given row and column recursively" then that is not what you have done.

You have calculated all entries and stored them in an array, then indexed the values you need. Sure, some parts are recursive, but I expect that the point is to not have the arrays at all.

Consider the triangle:

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

The 'simple' solution is to have a method like:

public int getPascalValue(int row, int column) {
    if (column == 0 || column == row) {
        return 1;
    }
    return getPascalValue(row - 1, column - 1) + getPascalValue(row - 1, column);
}

That is a system for recursively calculating the value at a given row/column (assuming valid input).

It does a fair number or recalculations, but the point is that it solves the problem as stated.

\$\endgroup\$
2
  • \$\begingroup\$ Excellent answer. +1 for being very positive in the beginning and +1 for pointing out that the array doesn't need to be constructed at all. Oh wait, I only have one vote... \$\endgroup\$ Commented Dec 20, 2014 at 13:27
  • \$\begingroup\$ Re: Validation. I tried doing that with handleError(). I add the basicUsage string there which tells the user which arguments were expected. However, the wording is somewhat poor. If you recall my question in the 2nd Monitor yesterday, that's where I wanted to output something like java EntryOfPascalsTriangle 15 3. \$\endgroup\$ Commented Dec 20, 2014 at 14:37
5
\$\begingroup\$
class EntryOfPascalsTriangle {

Why not make it a public class? As it contains a main method.


    int row = 0;
    row = parseInteger(args[0]);

    int column = 0;
    column = parseInteger(args[1]);

Can preferably be done on the same line

    int row = parseInteger(args[0]);
    int column = parseInteger(args[1]);

    // A Pascal’s triangle expands quadratic.

Wait, what? A triangle that expands quadratic?

I guess that depends on how you look at it, but I'd say that it expands like a triangle. For each new row there is one more column.


You're never checking for negative numbers, so there are two possible exceptions:

Exception in thread "main" java.lang.NegativeArraySizeException

At this line:

int[][] pascalsTriangle = new int[rows+1][];

And

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException

here:

System.out.println(pascalsTriangle[row][column]);

You should validate row and column better.


There's no need to return one of the parameters to the method when the parameter is mutable and is being modified.

pascalsTriangle = fillPascalRows(pascalsTriangle, 2);

can be just:

fillPascalRows(pascalsTriangle, 2);

private static void fillPascalRows(int[][] pascalsTriangle, int row) {

// Iterate over the columns of the rows of pascalsTriangle
for (int cell = 0; cell < pascalsTriangle.length; cell++) {

I would name that parameter row.

private static int[][] fillPascalRows(int[][] pascalsTriangle, int row) {
    for (int cell = 1; cell < pascalsTriangle[row].length-1; cell++) {

And that one col.


Your parseInteger method can be shortened a little bit:

private static int parseInteger(String arg) {
    try {
        return Integer.parseInt(arg);
    } catch (NumberFormatException nfe) {
        handleError("'" + arg + "' was not an integer.");
        return 0;
    }
}

Overall, the setup of Pascal's Triangle looks OK. I might not have done it the exact same way (I would especially handle the edges differently), but I have no specifics to pick on there.

\$\endgroup\$
3
\$\begingroup\$

You are already doing validation of the arguments inside the validateInput() method but then you are validating the column and row again in the main() method.

You should do this validation in an overloaded validateInput() method.

private void validateInput(int column, int row){
    if (column > row) {
        handleError("There can't be entries in a column that doesn't exist in a Pascal's triangle.");
    }   
}  

Comments like // Fill the first cell of each row with1`` are only boilerplate text which you can remove, because your code is telling what is done.

\$\endgroup\$
2
\$\begingroup\$

I agree with @rolfl: you missed the point of the assignment, which is that recursion should result in a simple, elegant expression — which your code wasn't.

Granted, a purely recursive algorithm for calculating Pascal's Triangle entries is inefficient, since it would recalculate many entries twice. Therefore, memoization is called for. Here is an elegant way to write recursion with memoization. Note that the caller is spared of the details of how to access the array entries.

public class PascalsTriangle {
    private int[][] memo;

    public PascalsTriangle(int maxRow) {
        try {
            this.memo = new int[maxRow + 1][];
            for (int row = 0; row <= maxRow; row++) {
                this.memo[row] = new int[row + 1];
                this.memo[row][0] = this.memo[row][row] = 1;
            }
        } catch (NegativeArraySizeException e) {
            throw new IllegalArgumentException("Negative size: " + maxRow);
        }
    }

    public int entry(int row, int col) {
        try {
            if (this.memo[row][col] != 0) {
                return this.memo[row][col];
            } else {
                return this.memo[row][col] = this.entry(row - 1, col - 1) +
                                             this.entry(row - 1, col);
            }
        } catch (ArrayIndexOutOfBoundsException e) {
            throw new IllegalArgumentException("No such element (" + row +
                                                              ", " + col + ")");
        }
    }
}

Here is the driver. I've written it as a separate class for clarity, so that PascalsTriangle can focus on the calculation without being cluttered by validation and error handling code.

Note that the validation and error handling could be simplified by more effective use of exceptions. The philosophy is, just do what you want to do. The code that you call will tell you if you can't.

Error messages belong on System.err, so as not to contaminate valid output on System.out.

public class EntryOfPascalsTriangle {
    /** Integer.parseInt() with a customized error message */ 
    private static int parseInteger(String arg) {
        try {
            return Integer.parseInt(arg);
        } catch (NumberFormatException nfe) {
            throw new NumberFormatException("'" + arg + "' was not an integer.");
        }
    }

    /** Prints usage help and exits with status 1. */
    private static void handleError(String errorMessage) {
        System.err.println(errorMessage);

        // This should say "row and column", not "column and row", to
        // match the expected order of parameters on the command line.
        System.err.println("Please enter the row and column of a Pascal's triangle.");
        System.exit(1);
    }

    public static void main(String[] args) {
        if (args.length < 2) {
            handleError("Not enough arguments.");
        } else if (args.length > 2) {
            handleError("Too many arguments.");
        }
        try {
            int row = parseInteger(args[0]);
            int col = parseInteger(args[1]);
            System.out.println((new PascalsTriangle(row)).entry(row, col));
        } catch (IllegalArgumentException e) {
            handleError(e.getMessage());
        }
    }
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.