Pascal's triangle
You are encouraged to solve this task according to the task description, using any language you may know.
Pascal's triangle is an interesting math concept. Its first few rows look like this:
1 1 1 1 2 1 1 3 3 1
where each element of each row is either 1 or the sum of the two elements right above it. For example, the next row would be 1 (since the first element of each row doesn't have two elements above it), 4 (1 + 3), 6 (3 + 3), 4 (3 + 1), and 1 (since the last element of each row doesn't have two elements above it). Each row n (starting with row 0 at the top) shows the coefficients of the binomial expansion of (x + y)n.
Write a function that prints out the first n rows of the triangle (with f(1) yielding the row consisting of only the element 1). This can be done either by summing elements from the previous rows or using a binary coefficient or combination function. Behavior for n <= 0 does not need to be uniform, but should be noted.
Ada
<ada> -- Pascals triangle
with Ada.Integer_Text_Io; use Ada.Integer_Text_Io; with Ada.Text_Io; use Ada.Text_Io;
procedure Pascals_Triangle is
type Row is array(Positive range <>) of Integer;
type Row_Access is access Row;
type Triangle is array(Positive range <>) of Row_Access;
function General_Triangle(Depth : Positive) return Triangle is
Result : Triangle(1..Depth);
begin
for I in Result'range loop
Result(I) := new Row(1..I);
for J in 1..I loop
if J = Result(I)'First or else J = Result(I)'Last then
Result(I)(J) := 1;
else
Result(I)(J) := Result(I - 1)(J - 1) + Result(I - 1)(J);
end if;
end loop;
end loop;
return Result;
end General_Triangle;
procedure Print(Item : Triangle) is
begin
for I in Item'range loop
for J in 1..I loop
Put(Item => Item(I)(J), Width => 3);
end loop;
New_Line;
end loop;
end Print;
begin
Print(General_Triangle(7));
end Pascals_Triangle; </ada>
BASIC
Summing from Previous Rows
This implementation uses an array to store one row of the triangle. DIM initializes the array values to zero. For first row, "1" is then stored in the array. To calculate values for next row, the value in cell (i-1) is added to each cell (i). This summing is done from right to left so that it can be done on-place, without using a tmp buffer. Because of symmetry, the values can be displayed from left to right.
Space for max 5 digit numbers is reserved when formatting the display. The maximum size of triangle is 100 rows, but in practice it is limited by screen space. If the user enters value less than 1, the first row is still always displayed.
<freebasic>DIM i AS Integer DIM row AS Integer DIM nrows AS Integer DIM values(100) AS Integer
INPUT "Number of rows: "; nrows values(1) = 1 PRINT TAB((nrows)*3);" 1" FOR row = 2 TO nrows
PRINT TAB((nrows-row)*3+1);
FOR i = row TO 1 STEP -1
values(i) = values(i) + values(i-1)
PRINT USING "##### "; values(i);
NEXT i
PRINT
NEXT row</freebasic>
Using binary coefficients
This implementation does not need an array to store values for each row, but the calculation is slightly more complex.
If the user enters value less than 1, nothing is displayed. <freebasic>DIM c AS Integer DIM i AS Integer DIM row AS Integer DIM nrows AS Integer
INPUT "Number of rows: "; nrows FOR row = 0 TO nrows-1
c = 1 PRINT TAB((nrows-row)*3); FOR i = 0 TO row
PRINT USING "##### "; c;
c = c * (row - i) / (i+1) NEXT i PRINT
NEXT row</freebasic>
Note: Unlike most Basic implementations, FreeBASIC requires that all variables have been declared before use (but this can be changed with compiler options).
Clojure
For n < 1, prints nothing, always returns nil. Copied from the Common Lisp implementation below, but with local functions and explicit tail-call-optimized recursion (recur).
(defn pascal [n]
(let [newrow (fn newrow [lst ret]
(if lst
(recur (rest lst)
(conj ret (+ (first lst) (or (second lst) 0))))
ret))
genrow (fn genrow [n lst]
(when (< 0 n)
(do (println lst)
(recur (dec n) (conj (newrow lst []) 1)))))]
(genrow n [1])))
(pascal 4)
Common Lisp
To evaluate, call (pascal n). For n < 1, it simply returns nil.
(defun pascal (n)
(genrow n '(1)))
(defun genrow (n l)
(if (< 0 n)
(progn
(print l)
(genrow (- n 1) (cons 1 (newrow l))))))
(defun newrow (l)
(if (> 2 (length l))
'(1)
(cons (+ (car l) (cadr l)) (newrow (cdr l)))))
D
There is similarity between Pascal's triangle and Sierpinski triangle. Their difference are the initial line and the operation that act on the line element to produce next line. The following is a generic pascal's triangle implementation for positive number of lines output (n). <d>import std.stdio, std.string, std.format : fmx = format ;
string Pascal(alias dg, T, T initValue)(int n) {
string output ;
void append(T[] l) {
output ~= repeat(" ", (n - l.length + 1)*2) ;
foreach(e; l) output ~= fmx("%4s", fmx("%4s",e)) ;
output ~= "\n" ;
}
if(n > 0) {
T[][] lines = initValue ;
append(lines[0]) ;
for(int i = 1 ; i < n ; i++) {
lines ~= lines[i-1] ~ initValue ; // length + 1
for(int j = 1 ; j < lines[i-1].length ; j++)
lines[i][j] = dg(lines[i-1][j], lines[i-1][j-1]) ;
append(lines[i]) ;
}
}
return output ;
}
string delegate(int n) GenericPascal(alias dg, T, T initValue)(){
mixin Pascal!(dg, T, initValue) ; return &Pascal ;
}
char xor(char a, char b) { return a == b ? '_' : '*' ; }
void main() {
auto pascal = GenericPascal!((int a, int b) { return a + b; }, int , 1 ) ;
auto sierpinski = GenericPascal!(xor, char, '*') ;
foreach(i ; [1,5,9]) writef(pascal(i)) ; // an order 4 sierpinski triangle is a 2^4 lines generic pascal triangle with xor operation foreach(i ; [16]) writef(sierpinski(i)) ;
}</d>
Forth
: init ( n -- )
here swap cells erase 1 here ! ;
: .line ( n -- )
cr here swap 0 do dup @ . cell+ loop drop ;
: next ( n -- )
here swap 1- cells here + do
i @ i cell+ +!
-1 cells +loop ;
: pascal ( n -- )
dup init 1 .line
1 ?do i next i 1+ .line loop ;
Fortran
Prints nothing for n<=0. Output formatting breaks down for n>20
PROGRAM Pascals_Triangle
CALL Print_Triangle(8)
END PROGRAM Pascals_Triangle
SUBROUTINE Print_Triangle(n)
IMPLICIT NONE
INTEGER, INTENT(IN) :: n
INTEGER :: c, i, j, k, spaces
DO i = 0, n-1
c = 1
spaces = 3 * (n - 1 - i)
DO j = 1, spaces
WRITE(*,"(A)", ADVANCE="NO") " "
END DO
DO k = 0, i
WRITE(*,"(I6)", ADVANCE="NO") c
c = c * (i - k) / (k + 1)
END DO
WRITE(*,*)
END DO
END SUBROUTINE Print_Triangle
Haskell
An approach using the "think in whole lists" principle: Each row in the triangle can be calculated from the previous row by adding a shifted version of itself to it, keeping the ones at the ends. The Prelude function zipWith can be used to add two lists, but it won't keep the old values when one list is shorter. So we need a similar function
zapWith :: (a -> a -> a) -> [a] -> [a] -> [a] zapWith f xs [] = xs zapWith f [] ys = ys zapWith f (x:xs) (y:ys) = f x y : zapWith f xs ys
Now we can shift a list and add it to itself, extending it by keeping the ends:
extendWith f [] = [] extendWith f xs@(x:ys) = x : zapWith f xs ys
And for the whole (infinite) triangle, we just iterate this operation, starting with the first row:
pascal = iterate (extendWith (+)) [1]
For the first n rows, we just take the first n elements from this list, as in
*Main> take 6 pascal [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1],[1,5,10,10,5,1]]
A shorter approach, plagiarized from [1]
-- generate next row from current row nextRow row = zipWith (+) ([0] ++ row) (row ++ [0]) -- returns the first n rows pascal = iterate nextRow [1]
J
solution
!/~@i. N
explanation
Of course, the triangle itself is simply the table of number-of-combinations, for the first N non-negative integers.
That is, C(n,k) for all n,k ∈ [0 .. n). J's notation for C(n,k) is k ! n (mnemonic: combinations are closely related to factorials, which are denoted by ! in math).
So, for example, the number of ways to choose a poker hand (5 cards from the deck of 52):
5!52 2598960
So ! is the mathematical choose function. What of /~@i.? Well, you can think of /~ as "table of" and @i. "the first N non-negative integers (i.e. 0 .. N-1)".
So, for example, here's the multiplication table you had to memorize in first grade:
*/~@i. 10 0 0 0 0 0 0 0 0 0 0 0 1 2 3 4 5 6 7 8 9 0 2 4 6 8 10 12 14 16 18 0 3 6 9 12 15 18 21 24 27 0 4 8 12 16 20 24 28 32 36 0 5 10 15 20 25 30 35 40 45 0 6 12 18 24 30 36 42 48 54 0 7 14 21 28 35 42 49 56 63 0 8 16 24 32 40 48 56 64 72 0 9 18 27 36 45 54 63 72 81
and here's the addition table for 0 to 4
+/~@i. 4 0 1 2 3 1 2 3 4 2 3 4 5 3 4 5 6
Similarly, !/~@i. is the number-of-combinations table, or the "choose" table:
!/~@i. 5 1 1 1 1 1 0 1 2 3 4 0 0 1 3 6 0 0 0 1 4 0 0 0 0 1
Of course, to format it nicely, you need to do a little more work:
([:'0'&=`(,:&' ')} -@|. |."_1 [: ":@|: !/~)@i. 5
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
(I won't bother explaining the formatting.)
Java
Summing from Previous Rows
<java>import java.util.ArrayList; ...//class definition, etc. public static void genPyrN(int rows){ if(rows < 0) return; //save the last row here ArrayList<Integer> last = new ArrayList<Integer>(); last.add(1); System.out.println(last); for(int i= 1;i <= rows;++i){ //work on the next row ArrayList<Integer> thisRow= new ArrayList<Integer>(); thisRow.add(1); //beginning for(int j= 1;j < i;++j){//loop the number of elements in this row //sum from the last row thisRow.add(last.get(j - 1) + last.get(j)); } thisRow.add(1); //end last= thisRow;//save this row System.out.println(thisRow); } }</java>
OCaml
<ocaml>(* generate next row from current row *) let next_row row =
List.map2 (+) ([0] @ row) (row @ [0])
(* returns the first n rows *) let pascal n =
let rec loop i row = if i = n then [] else row :: loop (i+1) (next_row row) in loop 0 [1]</ocaml>
Perl
<perl>sub pascal
- Prints out $n rows of Pascal's triangle. It returns undef for
- failure and 1 for success.
{my $n = shift;
$n < 1 and return undef;
print "1\n";
$n == 1 and return 1;
my @last = (1);
foreach my $row (1 .. $n - 1)
{my @this = map {$last[$_] + $last[$_ + 1]} 0 .. $row - 2;
@last = (1, @this, 1);
print join(' ', @last), "\n";}
return 1;}</perl>
Python
<python>def pascal(n):
"""Prints out n rows of Pascal's triangle.
It returns False for failure and True for success."""
if n < 1: return False
print 1
if n == 1: return True
last = [1]
for row in range(1, n):
this = [last[i] + last[i + 1] for i in range(row - 1)]
last = [1] + this + [1]
print " ".join(map(str, last))
return True</python>
RapidQ
Summing from Previous Rows
The main difference to BASIC implementation is the output formatting. RapidQ does not support PRINT USING. Instead, function FORMAT$() is used. TAB() is not supported, so SPACE$() was used instead.
Another difference is that in RapidQ, DIM does not clear array values to zero. But if dimensioning is done with DEF..., you can give the initial values in curly braces. If less values are given than there are elements in the array, the remaining positions are initialized to zero. RapidQ does not require simple variables to be declared before use.
DEFINT values(100) = {0,1}
INPUT "Number of rows: "; nrows
PRINT SPACE$((nrows)*3);" 1"
FOR row = 2 TO nrows
PRINT SPACE$((nrows-row)*3+1);
FOR i = row TO 1 STEP -1
values(i) = values(i) + values(i-1)
PRINT FORMAT$("%5d ", values(i));
NEXT i
PRINT
NEXT row
Using binary coefficients
INPUT "Number of rows: "; nrows
FOR row = 0 TO nrows-1
c = 1
PRINT SPACE$((nrows-row)*3);
FOR i = 0 TO row
PRINT FORMAT$("%5d ", c);
c = c * (row - i) / (i+1)
NEXT i
PRINT
NEXT row
Ruby
def pascal(n = 1)
return if n < 1
# set up a new array of arrays with the first value p = 1 # for n - 1 number of times, (n - 1).times do |i|
# inject a new array starting with [1]
p << p[i].inject([1]) do |result, elem|
# if we've reached the end, tack on a 1.
# else, tack on current elem + previous elem
if p[i].length == result.length
result << 1
else
result << elem + p[i][result.length]
end
end
end
# and return the triangle.
p
end