Triangle Roll-Up

September 23, 2014

It’s best to solve problems like this by composing small, general-purpose functions which can often be reused for other, similar problems. Although our Standard Prelude doesn’t have it, but-last is a common function on lists, returning all elements of a list except the last:

(define (but-last xs) (reverse (cdr (reverse xs))))

Another general-purpose function, pair-wise, applies an operator f on each pair of elements of a list, returning a new list with one less element than the input:

(define (pair-wise f xs) (map f (but-last xs) (cdr xs)))

Then, our roll-up procedure is recursive, with output produced after the recursive call so the last recursive call produces the first output:

(define (roll-up xs)
  (when (pair? xs)
    (roll-up (pair-wise + xs))
    (display xs) (newline)))

It always seems to work that way: with a suitable set of primitives, you build the language to meet the current task, so that the task itself becomes trivial. All the other solutions at http://www.careercup.com/question?id=5668983114039296, where this exercise came from, use some complicated-looking set of nested loops; by contrast, our solution is a simple recursion with nary a loop in sight, easy to read and trivial to write. Here’s what it looks like in action:

> (roll-up '(4 7 3 6 7))
(81)
(40 41)
(21 19 22)
(11 10 9 13)
(4 7 3 6 7)

You can run the program at http://programmingpraxis.codepad.org/uNQ5qsvJ. We’ll add but-last to the Standard Prelude the next time we revise it.

Advertisements

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++) {
                    newList.add(liste.get(i) + liste.get(i + 1));
                    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];

  9. Arshad Khan said

    I had attached the link for my code:
    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

    @Claire: See: https://programmingpraxis.com/contents/howto-posting-source-code/

    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]).
    
    sum_adj([]) -> [];
    sum_adj([_]) -> [];
    sum_adj([A, B | _] = Row) -> [A+B | sum_adj(tl(Row))].
    
    rollup([]) -> ok;
    rollup(L) ->
        rollup(sum_adj(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;
    }

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: