3
\$\begingroup\$

I have created a function which returns the number that corresponds to the given row and column from the pascal triangle. I have used the formula for this:

n! / r! * (r-n)!

The code:

def pascal(c: Int, r: Int): Int = {

    def factorial(number: Int): Int = {

      def loop(adder: Int, num: Int): Int = {
        if( num == 0) adder
        else loop(adder * num, num - 1)

      }

      loop(1,number)
    }


    factorial(r) / (factorial(c) * factorial(r-c));
}

I received 180 points out of 190 for this function because it returns an arithmetic exception for a given case (they don't give me the case). How could I improve this code and how can I make it better? Most importantly, how can I spot the bug?

\$\endgroup\$
1
  • 2
    \$\begingroup\$ I'm voting against closure cause his code is working(one small case not), and asking for improvement. (also how to spot the bug but not asking to fix the bug). \$\endgroup\$ Commented May 9, 2014 at 5:12

3 Answers 3

Reset to default
5
\$\begingroup\$

The code appears to be correct, though the explanatory formula you posted is wrong.

Your factorial function is more complex than it needs to be. Furthermore, adder is a poor variable name, since the result is multiplicative rather than additive. The traditional recursive definition is:

def factorial(n: Int): Int = {
    if (n == 0) 1
    else n * factorial(n - 1)
}

The main problem with your approach is that you work with large numbers in both the numerator and the denominator. If your program is generally working, then your problem is probably arithmetic overflow. An Int would only handle values up to 231 - 1 correctly.

Therefore, your best bet is to use an entirely different way to construct Pascal's Triangle, as suggested by @janos.

\$\endgroup\$
2
  • \$\begingroup\$ you are right. If I insert large numbers division by 0 occurs. Now implementing a whole new algorithm I guess would do the trick. However couldn't I just work with long? and then return an int? \$\endgroup\$ Commented May 9, 2014 at 15:08
  • 1
    \$\begingroup\$ OP's factorial version has an advantage of being a little bit faster (it's tail-recursive ) \$\endgroup\$ Commented May 29, 2014 at 14:49
3
\$\begingroup\$

There is a simpler solution. Consider this logic:

  • if it's the first column, the value is always 1
  • if it's the last column, the value is always 1. (You can check this based on the row!)
  • otherwise, it's the sum of the value in the previous row previous column + previous row same column

Spoiler alert:

def pascal(c: Int, r: Int): Int = { require(!(c < 0 || r < 0 || c > r), "c, r must be both positive and c <= r") if (c == 0) 1 else if (c == r) 1 else pascal(c - 1, r - 1) + pascal(c, r - 1) }

\$\endgroup\$
0
1
\$\begingroup\$

This is an inefficient way to compute ʳCₙ:

    factorial(r) / (factorial(c) * factorial(r-c));

There's a large amount of cancellation here: r!/c! can be computed as the product r·(r-1)·(r-2)·…·(c+1). Observe also that r·(r-1) must be a multiple of 2, and r·(r-1)·(r-2) a multiple of 3, and so on. So we can divide by (r-c)! as we go, iteratively.

I'll show that in Python, as my Scala is non-existent:

#!/usr/bin/python3

def combinatorial(r, n):
    """Return the number of ways r items can be chosen from n
    >>> combinatorial(1, 1)
    1
    >>> combinatorial(1, 2)
    2
    >>> combinatorial(2, 2)
    1
    >>> combinatorial(2, 3)
    3
    >>> combinatorial(2, 5)
    10
    >>> combinatorial(3, 5)
    10
    >>> combinatorial(2, 100)
    4950
    >>> combinatorial(995, 1000)
    8250291250200
    """
    if r < 0 or r > n:
        raise ValueError # or perhaps return 0, as there are no ways
    if r > n - r:
       # C(n, n-r) == C(n, r)
       # so swap to minimise multiplications
       r = n - r
    result = 1
    for i in range(r):
        result = result * (n - i) // (i + 1)
    return result

if __name__ == '__main__':
    import doctest
    doctest.testmod()
\$\endgroup\$
1
  • \$\begingroup\$ Yay, doctest FTW! \$\endgroup\$ Commented Aug 19, 2023 at 14:50

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.