## Triangle Roll-Up

### September 23, 2014

We have a simple little exercise today: Given a list, write a triangle showing successive sets of sums of the pair-wise elements of the list. For instance, given the input 4, 7, 3, 6, 7, your program should write this output:

81
40 41
21 19 22
11 10 9 13
4 7 3 6 7

The original list is at the bottom of the triangle. The next row up has pair-wise sums of the elements of the list: 4 + 7 = 11, 7 + 3 = 10, 3 + 6 = 9, and 6 + 7 = 13. The next row up has pair-wise sums of those list elements: 11 + 10 = 21, 10 + 9 = 19, and 9 + 13 = 22. The next-to-top row has only two sums: 21 + 19 = 40 and 19 + 22 = 41. And finally the top row is the sum of those two numbers: 40 + 41 = 81.

Your task is to write a program to print the triangle roll-up of an input list. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

### 19 Responses to “Triangle Roll-Up”

1. A bit messy…!

```while( @ARGV ) {
unshift @res,"@ARGV";
\$i    = shift @ARGV;
@ARGV = map {\$t=\$i+\$_;\$i=\$_;\$t} @ARGV;
}
print join "\n", @res,q();
```
2. Rutger said

In python:

```def triangle(x):
if len(x) > 0:
triangle([x[i]+x[i+1] for i in range(len(x)-1)])
print ' '.join(map(str,x))
# e.g.
triangle([4,7,3,6,7])
```
3. Andras said

Java

```public static void main(String[] args) {
printList(newArrayList(4, 7, 3, 6, 7));
}

private static void printList(List<Integer> liste) {
String line = "";
if (liste.size() > 1) {
List<Integer> newList = newArrayList();
for (int i = 0; i < liste.size() - 1; i++) {
line += liste.get(i) + " ";
}
printList(newList);
}
System.out.println(line + liste.get(liste.size() - 1));
}
```
4. matthew said

We can do this without using any extra memory by constructing each row in the right hand part of the original array:

```4 7 3 6 7
4 11 10 9 13
4 11 21 19 22
4 11 21 40 41
4 11 21 40 81
```

The final array is the left hand column of the triangle. We can then reverse the process and print out each row on the way, so they come out in the correct order. I can’t see a very neat way of doing this with lists (since we need to iterate in both directions).

```#include <iostream>
int main()
{
const int N = 5;
int a[N] = { 4,7,3,6,7 };
for (int i = 1; i <= N; i++) {
for (int j = N-1; j >= i; j--) {
a[j] += a[j-1];
}
}
for (int i = N; i >= 1; i--) {
for (int j = i; j <= N-1; j++) {
a[j] -= a[j-1];
}
for (int j = i-1; j < N; j++) {
std::cout << a[j] << " ";
}
std::cout << "\n";
}
}
```
5. svenningsson said

A solution in Haskell, split up into two function. One to generate the triangle and another to print it.

```trianglify [] = []
trianglify [x] = [[x]]
trianglify xs = xs : trianglify (zipWith (+) xs (tail xs))

printTriangle = putStrLn . unlines . map (unwords . map show) . reverse
```
6. Mike said

Prints the numbers using a fixed field width so the triangle looks nice.

```def triangle(x):
stack = []
row = x
width = 0
while row:
width = max(width, max(len(str(n)) for n in row))
stack.append(row)
row = [row[i-1]+row[i] for i in range(1, len(row))]
while stack:
print(*["{:{}}".format(n, width) for n in stack.pop()])
```

Example:

```>>> triangle([1,2,3,4,5])
48
20 28
8 12 16
3  5  7  9
1  2  3  4  5
```
7. Here is a php program for this solution

<?php
\$inputArray = array_slice(\$argv, 1);

//\$inputArray = array(4,7,3,6,7);
\$size = count(\$inputArray);
\$output = array();
\$newsize=\$size;
for(\$k = 0; \$k 0)
{
if(\$k == 0)
\$sum = \$inputArray[\$i-1];
else
\$sum = \$inputArray[\$i-1]+\$inputArray[\$i];
if(\$sum 0; \$i–)
echo “\n”.\$output[\$i];
?>

8. ``` \$inputArray = array_slice(\$argv, 1);```

``` ```

```//\$inputArray = array(4,7,3,6,7); \$size = count(\$inputArray); \$output = array(); \$newsize=\$size; for(\$k = 0; \$k 0) { if(\$k == 0) \$sum = \$inputArray[\$i-1]; else \$sum = \$inputArray[\$i-1]+\$inputArray[\$i]; if(\$sum 0; \$i--) echo "\n".\$output[\$i]; ```

It will take max 5 input number, you can change inside the code by changing the value of MAX_ARRAY_SIZE.

10. Axio said

A bit lazy for printing…

``````
process [] l = (mapM_ print) l
process [x] l = process [] ([x]:l)
process l1 l = process (treat l1) (l1:l)
where
treat (a:b:r) = (a+b):(treat (b:r))
treat _ = []
```
```

P!

11. Claire said

#include
using namespace std;

void TriangleRollup(int a[],int n)
{
int k = n-1;
for(int i = 1; i<=n;i++)
{
for( int j = 0; j<k; j++)
{
a[j]+=a[j+1];
cout<<a[j]<<" ";
}
k–;
cout<<endl;
}

for( int i=0; i<n;i++)
{

for( int j = 0; j<=i;j++)
{
cout<<a[j]<<" ";
}
cout<=0;j–)
{
a[j] -= a[j+1];
}
}

}
int main(int argc, char ** argv)
{
int N;
cout<>N;
//int a[N] = {4,7,3,6,7};
int array[N];
int i = 0;
while( i >array[i++];
}

TriangleRollup(array,N);
return 0;
}

12. Claire said

int main(int argc, char ** argv)
{
int N;
cout<>N;
//int a[N] = {4,7,3,6,7};
int array[N];
int i = 0;
while( i >array[i++];
}

TriangleRollup(array,N);
return 0;
}

13. Claire said

Why is some of the code missing when I pasted my code here ?

14. matthew said

Easiest thing is to wrap in ‘

`' and '`

‘ lines.

15. matthew said

Gaa, that was screwed by formatter as well, I meant, easiest thing is to use the ‘sourcecode’ directive as described in that page.

16. anil said

\$input = array(6,10,11,12);
\$output = \$input;
\$triangleList = array();
array_push(\$triangleList, implode(“,”, \$input));
while(count(\$output) >= 1){
\$newList = array();
for(\$i = 1; \$i = 0; \$i–){
echo \$triangleList[\$i].””;
}

17. David said

In Erlang

```-module(rollup).
-export([rollup/1]).

rollup([]) -> ok;
rollup(L) ->
io:format("~w~n", [L]).
```
18. Shubhra said

Perl newbie here.

print”No. of elements?”;
\$n=;
print”enter the elements”;
for(\$i=0;\$i<\$n;\$i++){
\$arr[\$i]=;
chomp \$arr[\$i];
}
print “@arr\n”;
\$j=\$n;
\$l=\$n-1;
\$i=0;
for(\$k=0;\$k<\$l;\$k++){
for( ;\$i+1<\$n;\$j++,\$i++){
\$arr[\$j]=\$arr[\$i]+\$arr[\$i+1];
print "\$arr[\$j] ";
}
\$n=\$j;
\$i++;
print "\n";
}
\$m=1;
for(\$i=1;\$i<=\$l+1;\$i++){
for(\$j=\$j-\$m,\$k=0;\$k<\$i;\$j++,\$k++){
print "\$arr[\$j] ";
}
print "\n";
\$m+=2;
}