4
\$\begingroup\$

I wrote a function to generate a complicated version of the pascal triangle. The generated triangle should look like that:

┌─────────┬───┬───┬────┬────┬────┬────┬────┬───┬───┐
│ (index) │ 0 │ 1 │ 2  │ 3  │ 4  │ 5  │ 6  │ 7 │ 8 │
├─────────┼───┼───┼────┼────┼────┼────┼────┼───┼───┤
│    0    │ 1 │   │    │    │    │    │    │   │   │
│    1    │ 1 │ 1 │ 1  │    │    │    │    │   │   │
│    2    │ 1 │ 2 │ 3  │ 2  │ 1  │    │    │   │   │
│    3    │ 1 │ 3 │ 6  │ 7  │ 6  │ 3  │ 1  │   │   │
│    4    │ 1 │ 4 │ 10 │ 16 │ 19 │ 13 │ 10 │ 4 │ 1 │
└─────────┴───┴───┴────┴────┴────┴────┴────┴───┴───┘

My implementation is like that

function createTriangle (n) {
// initialize the holding matrix
  let matrix = [];

// iterate over the matrix rows, and for each row construct a new array of row number + 1

  for (let row = 0; row < n; row++) { 
    matrix[row] = new Array(row+1);
// iterate over each row and check conditions

    for (let col = 0; col <= 2*row; col++) {            
      if ((col === 0 && row >= 0) || (col === 2 * row)) {
        matrix[row][col] = 1;
// first case
      } else if(col === row && col === 1){
                matrix[row][col] = 1;
// second case ;
            } else if(row > col && matrix[row][col-1]=== 1 ) {
            matrix[row][col] = 
            1 + matrix[row-1][col];
// third case
            } else if(row > col && matrix[row][col-1]!== 1 ) {
            matrix[row][col] = 
            matrix[row-1][col-2] + matrix[row-1][col-1] + matrix[row-1][col];
// fourth case
     } else if((row === col && (matrix[row][col-1] !== 1))) {
                matrix[row][col] = 
                matrix[row-1][col-2] + matrix[row-1][col-1] + matrix[row-1][col];

// fifth case   
       // if the col number is even, add only the previous 2 elements in the previous row       
            } else if(row < col && col % 2 === 0){
                matrix[row][col] = matrix[row-1][col-2] + matrix[row-1][col-1] + matrix[row-1][col];
// sixth case

      // if the col number is odd add the previous 3 elements in the previous row
            } else if(row < col && col % 2 === 1){

            matrix[row][col] = matrix[row-1][col-2] + matrix[row-1][col-1];
            }
        }
    }
  return matrix;
}


console.table(createTriangle(5))

I feel that my code is a bit confusing. In addition, there is a bug on matrix[4, 5] it should be 16,but it is 13?? Could anyone advise if there is a more refactored elegant solution? Appreciate your time and help.

Edit The algorithm should generate a matrix that have number of columns twice number of rows. The elements before the element at matrix[row][col] where col = row should be the same but reversed in a desc. order. for example, matrix[4,4] => [1,4,10,16,19,16,10,4,1]. element at matrix[4,4] 19 should be equal to 6+7+6

\$\endgroup\$
1
  • \$\begingroup\$ Please do not update the code in your question to incorporate feedback from answers, doing so goes against the Question + Answer style of Code Review. This is not a forum where you should keep the most updated version in your question. Please see what you may and may not do after receiving answers. The changes you made were explicitly mentioned in an answer, so you can't make them in this post. \$\endgroup\$
    – Mast
    Oct 27, 2019 at 20:03

2 Answers 2

4
\$\begingroup\$

You are not properly calculating the pascal triangle. Here is my solution, in this code I take advantage of the function .splice() to modify the content of every row. You know that the outter elements of each row are 1s and in between you make the calculations of the sum of the top "root elements", and just like that you get the Pascal's Triangle.

function pascalTriangle(level) {
  let matrix = [[1]];

  for (let row = 1; row < level; row++) {
    matrix.push([1, 1]);
    for (let col = 1; col < row; col++) {
      matrix[row].splice(col, 0, matrix[row - 1][col - 1] + matrix[row - 1][col]);
    }
  }

  return matrix;
}

console.log(pascalTriangle(7));

┌─────────┬───┬───┬────┬────┬────┬───┬───┐
│ (index) │ 0 │ 1 │ 2  │ 3  │ 4  │ 5 │ 6 │
├─────────┼───┼───┼────┼────┼────┼───┼───┤
│    0    │ 1 │   │    │    │    │   │   │
│    1    │ 1 │ 1 │    │    │    │   │   │
│    2    │ 1 │ 2 │ 1  │    │    │   │   │
│    3    │ 1 │ 3 │ 3  │ 1  │    │   │   │
│    4    │ 1 │ 4 │ 6  │ 4  │ 1  │   │   │
│    5    │ 1 │ 5 │ 10 │ 10 │ 5  │ 1 │   │
│    6    │ 1 │ 6 │ 15 │ 20 │ 15 │ 6 │ 1 │
└─────────┴───┴───┴────┴────┴────┴───┴───┘
\$\endgroup\$
1
  • 2
    \$\begingroup\$ Since you don't need the second 1 for calculating the inner cells, the code may become clearer if you first matrix.push([1]), then matrix[row].push(matrix[row - 1][col - 1] + matrix[row - 1][col]) in the loop and finally matrix[row].push(1). Thereby you avoid the splice function and the extra 0 in that function call. It's also more efficient since the last 1 does not have to be moved in the array so often. Sure, the code would become one line longer, but it uses fewer incredients and only appends, which in my view is easier to understand. \$\endgroup\$ Oct 27, 2019 at 7:32
2
\$\begingroup\$

Pascals Triangle?

The output of your code is not Pascals triangle (even if the bug? is ignored).

As you only present one example with the statement "The generated triangle should look like that:", that contains what you state is a bug (erroneous? 13)

What the rules defining the correct result are is anyone's guess. I will address your code as is and ignore the bug or not bug.

Style and logic

  • Don't add comments that state the obvious. Eg // first case, // second case and so on.
  • Don't add comments that are just an alternative representation of the code Eg // if the col number is even, add only the previous 2 elements in the previous row. This just add another line of maintainable content, which can be dangerous because if you change the code there is nothing forcing you to change the comment. Even worse than redundant comments are comments that are in conflict with the actual logic

  • Use const for variables that do not change. Eg let matrix = []; can be const matrix = []

  • Don't repeat code.

    • You calculate row - 1 (and the like) many times
    • You index matrix[row] and matrix[row-1] many times
  • You are repeating logic. Eg the second last statement else if (j < i && i % 2 === 0) { is followed by else if (j < i && i % 2 === 1) { but you know that i % 2 === 1 as the previous statement determined its value.

  • Don't calculate known data. Eg the very last else if statement can just be a else because you must add to the array each iteration, the last statement MUST pass.

There is no advantage using let in for loops when performance is a concern. Try to favor function scoped variables and declare them at the top of the function.

Rewrite (cleanup)

The snippets below is the same logic you used, just cleaned up using the points above

function createTriangle(n) {
    var i, j;
    const matrix = [];
    for (j = 0; j < n; j++) {
        const prevRow = matrix[j - 1], row = []; 
        matrix.push(row);
        for (i = 0; i <= 2 * j; i++) {
            if ((i === 0 && j >= 0 || i === 2 * j) || (i === j && i === 1)) {
                row[i] = 1;
            } else {
                const r1 = row[i - 1], pr = prevRow[i], pr12 = prevRow[i - 1] + prevRow[i - 2];
                if (j > i && r1 === 1) {
                    row[i] = 1 + pr;
                } else if (j > i && r1 !== 1) {
                    row[i] = pr + pr12;
                } else if (j === i && r1 !== 1) {
                    row[i] = pr + pr12;
                } else if (j < i && i % 2 === 0) {
                    row[i] = pr + pr12;
                } else {
                    row[i] = pr12;
                }
            }
        }
    }
    return matrix;
}

Or

function createTriangle(n) {
    var i, j, row;
    const matrix = [];
    for (j = 0; j < n; j++) {
        const prevRow = row; 
        matrix.push(row = []);
        for (i = 0; i <= 2 * j; i++) {
            if ((i === 0 && j >= 0 || i === 2 * j) || (i === j && i === 1)) {
                row[i] = 1;
            } else {
                const r1 = row[i - 1], pr = prevRow[i], pr12 = prevRow[i - 1] + prevRow[i - 2];
                if (j > i && r1 === 1) { row[i] = 1 + pr }
                else if (j > i && r1 !== 1) { row[i] = pr + pr12 }
                else if (j === i && r1 !== 1) { row[i] = pr + pr12 }
                else if (j < i && i % 2 === 0) { row[i] = pr + pr12 }
                else { row[i] = pr12 }
            }
        }
    }
    return matrix;
}

Pascals triangle example

As an example pascals triangle can be calculated as follows. I would assume that the rules you use are similar and thus it is likely that your triangle can be calculated using a modification of this method that does not require indexing into the previous row.

function pascalsTriangle(rows) {
    var i, j, row, p, result = [[1]];
    for (i = 1; i <= rows; i++) {
        result.push(row = [p = 1]);
        for (j = 1; j <= i; j++) { row.push(p = p * (i - j + 1) / j) }
    }
    return result;
}
\$\endgroup\$
1
  • \$\begingroup\$ Thanks @Bilndman67 your feedback were really helpful. I agree with you that this is not a pascal isosceles triangle with the number of cols = number of the rows. It should instead have the number of col = twice the number of col. Also, there is a pattern the numbers after matrix[row][col] where (row=col) is the same numbers but reversed in a desc order (1,3,6,7,6,3,1). This problem I am trying to solve is from the Introduction to algorithms-A creative approach textbook - p(32, 2.11) \$\endgroup\$ Oct 27, 2019 at 16:22

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.