2
\$\begingroup\$

I wanted to take on the challenge of the classic Robot Path's problem but solve it using Pascal's triangle. The approach was generate pascal's triangle, then grab the middle element from the row. I saw the following pattern:

//where combos are on pascal's triangle:
// 1x1 grid on the 1st line ===> 1
// 2x2 grid on 3rd line==> 2
// 3x3 grid on 5th line ===> 6
// 4x4 grid on 7th line ===> 20
// 5x5 grid on the 9th line ===> 70
// 6 x6 on the 11th line ===> 252

and so made my getPaths() function accordingly: var tri = pascal(n * 2);

function getPaths(n) {

  if (n === 1) {
    return 1;
  }

  if (n === 0) {
    return 0;
  } else {
    var oddElement = (n + (n - 2));
    var mid = Math.floor(tri[oddElement].length / 2);
    // console.log(oddElement);
    return tri[oddElement][mid];
  }

}

Below is the entire function. what could I have done better?

    //Using pascal's triangle to get all unique paths on a board, where only moves are down and to the right:

//generate Pascal's triangle.
function pascal(n) {
  function pascalHelper(n, arr) {
    if (n < 2) {
      return arr;
    }
    var prevTier = arr[arr.length - 1];
    var currTier = [1];
    for (var i = 1; i < prevTier.length; i++) {
      currTier[i] = prevTier[i] + prevTier[i - 1];
    }
    currTier.push(1);
    arr.push(currTier);
    return pascalHelper(n - 1, arr);
  }
  return pascalHelper(n, [
    [1]
  ]);
}


function getPaths(n) {
var tri = pascal(n * 2);
  if (n === 1) {
    return 1;
  }

  if (n === 0) {
    return 0;
  } else {
    var oddElement = (n + (n - 2));
    var mid = Math.floor(tri[oddElement].length / 2);
    // console.log(oddElement);
    return tri[oddElement][mid];
  }

}
//observed pattern: triangle has to be twice as long as the number of paths.
console.log(getPaths(7));
//where combos are on pascal's triangle:
// 1x1 grid on the 1st line ===> 1
// 2x2 grid on 3rd line==> 2
// 3x3 grid on 5th line ===> 6
// 4x4 grid on 7th line ===> 20
// 5x5 grid on the 9th line ===> 70
// 6 x6 on the 11th line ===> 252
\$\endgroup\$

1 Answer 1

2
\$\begingroup\$

You can collapse the two base cases (n === 1 and n === 0) in getPaths() into one n < 2 condition, which then also matches the base case used in pascal().

Also Pascal's triangle only needs to be calculated if n is more than 1, so the call to pascal() can be put into the else-clause rather than at the beginning of the function.

function getPaths(n) {
    if (n < 2) {
        return n;
    } else {
        var tri = pascal(n * 2);
        var oddElement = (n + (n - 2));
        var mid = Math.floor(tri[oddElement].length / 2);
        // console.log(oddElement);
        return tri[oddElement][mid];
    }
}
\$\endgroup\$

Your Answer

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

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