.png)
Pascal Triangle in scala without variable definition
Pascal Triangle is one of problem mention by HackerRank in Functional Programming Domain. The main problem is implementing this without any val and var in Scala.
Problem Statement
For a given integer
K, print the first K rows of Pascal's Triangle. Print each row with values separated by spaces. The value at nthrow and rth column of the triangle is equal to n! / (r! * (n-r)!) where indexing start from 0. These values are the binomial coefficients.
The Pascal Triangle
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
....
Input Format
A Single Integer, K.
A Single Integer, K.
Constraints
2 <= K <=10
And, you need to accomplish this without directly defining any local variables. For example,var and val have been blocked in Scala; def and defn are blocked in Clojure.
Output Format
The first K rows of the Pascal Triangle.
Sample Input
4
Sample Output
1
1 1
1 2 1
1 3 3 1
Copyright (c) 2015 HackerRank.
Solution
My approach to this problem is by using the first two line of pascal triangle~List(1) and List(1,1)~ to generate next line of pascal triangle~List(1,2,1).~Using List(1,1) and List(1,2,1) to generate List(1,3,3,1),
Using List(1,2,1) and List(1,3,3,1) to generate List(1,4,6,4,1), and so on.
I also use x to keep track of the input. Yeah, it needs exact number to know when to stop.
So, here is the basic function. f will first print all integer in l1 with space between each integer. If x is zero, then the recursive will stop. If x is not zero, decrease the value of zero, change the position of l1 with l2, then we generate next item.
def f(x:Int, l1:List[Int], l2:List[Int]):List[Int]={
println(l1 mkString " ")
if(x==0) l1
else f(x-1, l2, List(1):::next(l2, List()):::List(1))
}
To generate the next List from the previous List, we can use normal addition between first element(arr.head) and second element(arr.tail.head). The process will repeat itself until size of array reaches 1. Then the result will be appended with 1 in front of function next() and 1 in the rear.
def next(arr:List[Int], result:List[Int]):List[Int]={
if(arr.size<=1) result
else next(arr.tail, result:::List(arr.head+arr.tail.head))
}
To sum up, this is the full code
object Solution {
def next(arr:List[Int], result:List[Int]):List[Int]={
if(arr.size<=1) result
else next(arr.tail, result:::List(arr.head+arr.tail.head))
}
def f(x:Int, l1:List[Int], l2:List[Int]):List[Int]={
println(l1 mkString " ")
if(x==0) l1
else f(x-1, l2, List(1):::next(l2, List()):::List(1))
}
def main(args: Array[String]) {
f(readInt()-1, List(1), List(1,1))
}
}
0 comments: