current community

your communities

more stack exchange communities

company blog
Stack Exchange Inbox Reputation and Badges
tour help
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top
up vote 2 down vote favorite

This is my attempt to implement the Pascal Triangle in C#. It is meant to calculate and return a pascal triangle of size n (which it takes is through the parameter rows).

static List<List<int>> GetPascalTriangle(int rows)
{
    List<List<int>> result = new List<List<int>>();
    for (int x = 0; x <= rows - 1; x++)
    {
        if (x == 0 || x == 1)
        {
            result.Add(Enumerable.Repeat(1, x + 1).ToList());
        }
        else
        {
            List<int> prevRow = result[x - 1];
            List<int> semiResult = new List<int>();
            semiResult.Add(1);
            for (int x1 = 0; x1 <= prevRow.Count - 2; x1++)
            {
                semiResult.Add(prevRow[x1] + prevRow[x1 + 1]);
            }
            semiResult.Add(1);
            result.Add(semiResult);
        }
    }
    return result;
}

I feel this code is a little messy. Thus I seek some opinion on it and ways to improve it.

share|improve this question
up vote 5 down vote accepted

First: The Pascal Triangle will grow very rapidly. And rows=100, your maximum value is 1.27388061294904e+28. Yes, that's right it will overflow int, uint, long, and ulong within 100 rows. Check it out on interactive pascal triangle site The only suggestion is Numerics.BigInteger where there is no upperbound.

Second: Why are you using List<List<int>>? You can use a jagged array, which is much shorter: int[][], and effectively does the same. You just need to initialize them ahead with their size

var triangle = new int[rows][];
for(int i = 0; i<rows;i++){triangle[i] = new int[i+1];}

Third: if you know the first and last element is always a 1, then the if-statement for the first 2 rows is redundant

// This part is redundant, you already check if the first/last element is 1
if (x == 0 || x == 1)
{
    result.Add(Enumerable.Repeat(1, x + 1).ToList());
}

So with all the improvements, you code would be shorter and could handle much more rows. As a bonus I removed the dependency on system.linq. It could look like this:

public static BigInteger[][] GetPascalTriangleImproved(int rows)
    {
        BigInteger[][] result = new BigInteger[rows+1][];
        for (int x = 0; x < rows; x++)
        {
            result[x] = new BigInteger[x + 1];
            result[x][0] = 1; // first element is ALWAYS 1

            for (int x1 = 1; x1 <= x; x1++)
            {
                // last element is always 1 (just like the first)
                if (x1 == x) { result[x][x] = 1; continue; }

                // in all other cases, just add the 2 digits in the upper row
                result[x][x1] = result[x - 1][x1 - 1] + result[x - 1][x1];
            }                
        }
        return result;
    }
share|improve this answer
    
Great. This was exactly what I wanted. – Fᴀʀʜᴀɴ Aɴᴀᴍ Feb 3 at 17:56
up vote 2 down vote

In addition to Malachi's suggestion,

Equivalent Conditions:

The condition x <= rows - 1 is equivalent to x < rows which is shorter and technically more efficient (though I'm fairly certain the compiler would optimize this).

Guard Statements:

A common way I clean up my code is to use guard-statements instead of if/else. They're not always possible but something like this could reduce nesting. Just be aware this doesn't work in every case (as it may make some situations more confusing) but when it does work it can make code a lot less of an eye-sore.

if (x == 0 || x == 1)
{
    result.Add(Enumerable.Repeat(1, x + 1).ToList());
    continue;
}

var prevRow = result[x - 1];
var semiResult = new List<int>();
semiResult.Add(1);
for (int y = 0; y < prevRow.Count - 1; y++)
{
    semiResult.Add(prevRow[y] + prevRow[y + 1]);
}
semiResult.Add(1);
result.Add(semiResult);

var keyword:

It isn't uncommon to make use of the var keyword. Particularly in cases where it is obvious what the variables type is. e.g. var semiResult = new List<int>(); this way you don't have to type 'List' twice.

share|improve this answer
    
Any suggestion on the implementation algorithm? – Fᴀʀʜᴀɴ Aɴᴀᴍ Feb 2 at 19:06
    
Honestly not much of an algorithm kind of guy (I lean towards architecture). So I can't say much there, I might have used arrays instead of lists since you know the number of rows from the start. – Shelby115 Feb 2 at 19:11
    
Yeah the only thing I'm seeing with your algorithm is the overhead of using a list instead of an array. – Shelby115 Feb 2 at 19:21
    
With arrays, i would need a separate counter to assign elements to. Would arrays over lists be a significant optimization? – Fᴀʀʜᴀɴ Aɴᴀᴍ Feb 2 at 19:26
    
I found this answer. And arrays do seem to be faster. I'll wait for some other opinions on the algorithm. – Fᴀʀʜᴀɴ Aɴᴀᴍ Feb 2 at 19:28
up vote 1 down vote

The iteration variable on the inside of this function that you have named x1 should be named y or at least something a little more distinguishing, it is a little confusing have x and then x1.

This line:

for (int x1 = 0; x1 <= prevRow.Count - 2; x1++)

you should change the conditional statement so it is more clear, less than or equal to 2 less than the previous rows count. make it less than the previous row count minus 1. 

for (int y = 0; y < prevRow.Count - 1; y++)

These little changes are not so much about code efficiency as they are about being able to read the code more efficiently.

if you said this out loud x1 <= prevRow.count - 2 it would be

x one less than or equal to prevRow dot count minus 2

versus y < prevRow.count - 1

y less than prevRow dot count minus 1

it is the same things but with less clutter, so it is easier to read, and if you keep in mind that less than is not an equal to, which you should know no matter what, you shouldn't have any issues.

another place where you have this is in your if statement here.

if (x == 0 || x == 1)

let's just say it like this instead

if (x < 2)
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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