HiveBrain v1.2.0
Get Started
← Back to all entries
patterncsharpMinor

Pascal Triangle implementation in C#

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
pascalimplementationtriangle

Problem

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> GetPascalTriangle(int rows)
{
    List> result = new List>();
    for (int x = 0; x  prevRow = result[x - 1];
            List semiResult = new List();
            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.

Solution

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? 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;
    }

Code Snippets

var triangle = new int[rows][];
for(int i = 0; i<rows;i++){triangle[i] = new int[i+1];}
// 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());
}
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;
    }

Context

StackExchange Code Review Q#118656, answer score: 6

Revisions (0)

No revisions yet.