current community

your communities

more stack exchange communities

Stack Exchange
tour help
Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.
up vote 3 down vote favorite

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?

share|improve this question
2  
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). –  chillworld May 9 at 5:12
add comment

2 Answers

up vote 4 down vote accepted

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.

share|improve this answer
    
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? –  Bula May 9 at 15:08
1  
OP's factorial version has an advantage of being a little bit faster (it's tail-recursive ) –  sasha.sochka May 29 at 14:49
add comment
up vote 3 down vote

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) }

share|improve this answer
    
I don't want to sound rude. Did you read my question? –  Bula May 8 at 21:59
    
I thought I did... It's true that I only answered one part: "how to improve". I did not answer "how to spot the bug", because without the stack trace or at least the exact error message (and line number?) it's a bit hard to tell what is the problem. –  janos May 8 at 22:22
    
Idiomatically instead of if (c < 0 || r < 0 || c > r) throw new IllegalArgumentException("invalid args: " + c + " " + r) you should write require(c >= 0 && r>= 7 && c <= r) –  sasha.sochka May 29 at 14:50
    
@sasha.sochka thanks, good point, corrected! –  janos May 29 at 15:07
add comment

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.