Floyd's triangle: Difference between revisions

From Rosetta Code
Content added Content deleted
(added a quite simple Rexx solution)
Line 626: Line 626:
**********************************************************************/
**********************************************************************/
Parse Arg rowcount
Parse Arg rowcount
col=0 /* last line of triangle */
col=0
ll=''
ll='' /* last line of triangle */
Do j=rowcount*(rowcount-1)/2+1 to rowcount*(rowcount+1)/2
Do j=rowcount*(rowcount-1)/2+1 to rowcount*(rowcount+1)/2
col=col+1 /* column number */
col=col+1 /* column number */
Line 644: Line 644:
Say ll /* output last line */
Say ll /* output last line */
</lang>
</lang>

=={{header|Scala}}==
=={{header|Scala}}==
<lang scala>def floydstriangle( n:Int ) {
<lang scala>def floydstriangle( n:Int ) {

Revision as of 11:48, 12 July 2012

Task
Floyd's triangle
You are encouraged to solve this task according to the task description, using any language you may know.

Floyd's triangle lists the natural numbers in a right triangle aligned to the left where

  • the first row is just 1
  • successive rows start towards the left with the next number followed by successive naturals listing one more number than the line above.

The first few lines of a Floyd triangle looks like this: 

 1
 2  3
 4  5  6
 7  8  9 10
11 12 13 14 15

The task is to:

  1. Write a program to generate and display here the first n lines of a Floyd triangle.
    (Use n=5 and n=14 rows).
  2. Ensure that when displayed in a monospace font, the numbers line up in vertical columns as shown and that only one space separates numbers of the last row.

Ada

<lang Ada>with Ada.Text_IO, Ada.Integer_Text_IO, Ada.Command_Line;

procedure Floyd_Triangle is 

  Rows:    constant Positive := Integer'Value(Ada.Command_Line.Argument(1));
  Current:          Positive := 1;
  Width:            array(1 .. Rows) of Positive;

begin 

  -- compute the width for the different columns
  for I in Width'Range loop
     Width(I) := Integer'Image(I + (Rows * (Rows-1))/2)'Length;
  end loop;
  
  -- output the triangle
  for Line in 1 .. Rows loop
     for Column in 1 .. Line loop
       Ada.Integer_Text_IO.Put(Current, Width => Width(Column));
       Current := Current + 1;
     end loop;
     Ada.Text_IO.New_Line;
  end loop;

end Floyd_Triangle;</lang>

Output:
> ./floyd_triangle 5
  1
  2  3
  4  5  6
  7  8  9 10
 11 12 13 14 15


> ./floyd_triangle 14
  1
  2  3
  4  5  6
  7  8  9 10
 11 12 13 14 15
 16 17 18 19 20 21
 22 23 24 25 26 27 28
 29 30 31 32 33 34 35 36
 37 38 39 40 41 42 43 44  45
 46 47 48 49 50 51 52 53  54  55
 56 57 58 59 60 61 62 63  64  65  66
 67 68 69 70 71 72 73 74  75  76  77  78
 79 80 81 82 83 84 85 86  87  88  89  90  91
 92 93 94 95 96 97 98 99 100 101 102 103 104 105

C

<lang c>#include <stdio.h>

void t(int n) { int i, j, c, len;

i = n * (n - 1) / 2; for (len = c = 1; c < i; c *= 10, len++); c -= i; // c is the col where width changes

  1. define SPEED_MATTERS 0
  2. if SPEED_MATTERS // in case we really, really wanted to print huge triangles often

char tmp[32], s[4096], *p;

sprintf(tmp, "%*d", len, 0);

inline void inc_numstr(void) { int k = len;

redo: if (!k--) return;

if (tmp[k] == '9') { tmp[k] = '0'; goto redo; }

if (++tmp[k] == '!') tmp[k] = '1'; }

for (p = s, i = 1; i <= n; i++) { for (j = 1; j <= i; j++) { inc_numstr(); __builtin_memcpy(p, tmp + 1 - (j >= c), len - (j < c)); p += len - (j < c);

*(p++) = (i - j)? ' ' : '\n';

if (p - s + len >= 4096) { fwrite(s, 1, p - s, stdout); p = s; } } }

fwrite(s, 1, p - s, stdout);

  1. else // NO_IT_DOESN'T

int num; for (num = i = 1; i <= n; i++) for (j = 1; j <= i; j++) printf("%*d%c", len - (j < c), num++, i - j ? ' ':'\n');

  1. endif

}

int main(void) { t(5), t(14);

// maybe not // t(10000); return 0; }</lang> Output identical to D's.

D

<lang d>import std.stdio, std.conv;

void floyd(in uint n) { 

   immutable llc = n * (n - 1) / 2 + 1; // lower left corner
   foreach (r; 0 .. n) {
       foreach (c; 0 .. r + 1) {
           immutable nc = text(llc + c).length.text();
           writef("%" ~ nc ~ (c == r ? "d" : "d "),
                  r * (r + 1) / 2 + c + 1);
       }
       writeln();
   }

}

void main() { 

   floyd(5);
   floyd(14);

}</lang>

Output:
 1
 2  3
 4  5  6
 7  8  9 10
11 12 13 14 15
 1
 2  3
 4  5  6
 7  8  9 10
11 12 13 14 15
16 17 18 19 20 21
22 23 24 25 26 27 28
29 30 31 32 33 34 35 36
37 38 39 40 41 42 43 44  45
46 47 48 49 50 51 52 53  54  55
56 57 58 59 60 61 62 63  64  65  66
67 68 69 70 71 72 73 74  75  76  77  78
79 80 81 82 83 84 85 86  87  88  89  90  91
92 93 94 95 96 97 98 99 100 101 102 103 104 105

Go

<lang go>package main

import "fmt"

func main() { 

   floyd(5)
   floyd(14)

}

func floyd(n int) { 

   fmt.Printf("Floyd %d:\n", n)
   lowerLeftCorner := n*(n-1)/2 + 1
   lastInColumn := lowerLeftCorner
   lastInRow := 1
   for i, row := 1, 1; row <= n; i++ {
       w := len(fmt.Sprint(lastInColumn))
       if i < lastInRow {
           fmt.Printf("%*d ", w, i)
           lastInColumn++
       } else {
           fmt.Printf("%*d\n", w, i)
           row++
           lastInRow += row
           lastInColumn = lowerLeftCorner
       }
   }

}</lang>

Output:
Floyd 5:
 1
 2  3
 4  5  6
 7  8  9 10
11 12 13 14 15
Floyd 14:
 1
 2  3
 4  5  6
 7  8  9 10
11 12 13 14 15
16 17 18 19 20 21
22 23 24 25 26 27 28
29 30 31 32 33 34 35 36
37 38 39 40 41 42 43 44  45
46 47 48 49 50 51 52 53  54  55
56 57 58 59 60 61 62 63  64  65  66
67 68 69 70 71 72 73 74  75  76  77  78
79 80 81 82 83 84 85 86  87  88  89  90  91
92 93 94 95 96 97 98 99 100 101 102 103 104 105

Haskell

Program <lang haskell>import Data.List import Control.Monad import Control.Arrow

alignR :: Int -> Integer -> String alignR n = (\s -> replicate (n - length s) ' ' ++ s). show

floydTriangle = liftM2 (zipWith (liftM2 (.) enumFromTo ((pred.). (+)))) (scanl (+) 1) id [1..]

formatFT n = mapM_ (putStrLn. unwords. zipWith alignR ws) t where 

 t = take n floydTriangle
 ws = map (length. show) $ last t</lang>

Output: <lang haskell>*Main> formatFT 5 

1
2  3
4  5  6
7  8  9 10

11 12 13 14 15

  • Main> formatFT 14
1
2  3
4  5  6
7  8  9 10

11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105</lang>

J

Note: require 'strings' does nothing in J7, but is harmless (strings is already incorporated in J7).

<lang J>require 'strings' floyd=: [: rplc&(' 0';' ')"1@":@(* ($ $ +/\@,)) >:/~@:i.</lang>

Note, the parenthesis around ($ $ +/\@,) is optional, and only included for emphasis.

Example use:

<lang J> floyd 5 

1            
2  3         
4  5  6      
7  8  9 10

11 12 13 14 15 

  floyd 14
1                                             
2  3                                          
4  5  6                                       
7  8  9 10

11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105</lang>

How it works:

First, we create a square lower triangular matrix with our argument as the length of one side. We have 1s along the diagonal and the lower triangle, and 0s for the upper triangle.

Second, we create a running sum of these values (treating rows as being adjacent horizontally for this purpose). Then, we multiply this result by our lower triangular matrix (forcing the upper triangle to be 0s).

Then, we format the matrix as text (which gives us the required vertical alignment), and in each row we replace each space followed by a zero with two spaces.

Efficiency note: In a measurement of time used: in floyd 100, 80% the time here goes into the string manipulations -- sequential additions and multiplications are cheap. In floyd 1000 this jumps to 98% of the time. Here's a faster version (about 3x on floyd 1000) courtesy of Aai of the J forums:

<lang J>floyd=: [: ({.~ i.&1@E.~&' 0')"1@":@(* ($ $ +/\@,)) >:/~@:i.</lang>

Java

<lang java> public class Floyd { public static void main(String[] args){ System.out.println("5 rows:"); printTriangle(5); System.out.println("14 rows:"); printTriangle(14); }

private static void printTriangle(int n){ for(int rowNum = 1, printMe = 1, numsPrinted = 0; rowNum <= n; printMe++){ int cols = (int)Math.ceil(Math.log10(n*(n-1)/2 + numsPrinted + 2)); System.out.printf("%"+cols+"d ", printMe); if(++numsPrinted == rowNum){ System.out.println(); rowNum++; numsPrinted = 0; } } } }</lang> Output: 

5 rows:
 1 
 2  3 
 4  5  6 
 7  8  9 10 
11 12 13 14 15 
14 rows:
 1 
 2  3 
 4  5  6 
 7  8  9 10 
11 12 13 14 15 
16 17 18 19 20 21 
22 23 24 25 26 27 28 
29 30 31 32 33 34 35 36 
37 38 39 40 41 42 43 44  45 
46 47 48 49 50 51 52 53  54  55 
56 57 58 59 60 61 62 63  64  65  66 
67 68 69 70 71 72 73 74  75  76  77  78 
79 80 81 82 83 84 85 86  87  88  89  90  91 
92 93 94 95 96 97 98 99 100 101 102 103 104 105

Pascal

Works with: Free_Pascal

<lang pascal>Program FloydDemo (input, output);

function digits(number: integer): integer; 

 begin
   digits := trunc(ln(number) / ln(10)) + 1;
 end;

procedure floyd1 (numberOfLines: integer); { variant with repeat .. until loop } 

 var
   i, j, numbersInLine, startOfLastlLine: integer;

 begin
   startOfLastlLine := (numberOfLines - 1) * numberOfLines div 2 + 1;
   i := 1;
   j := 1;
   numbersInLine := 1;
   repeat
     repeat
       write(i: digits(startOfLastlLine - 1 + j), ' ');
       inc(i);

inc(j); 

     until (j > numbersInLine);
     writeln;
     j := 1;
     inc(numbersInLine);
   until (numbersInLine > numberOfLines);
 end;

procedure floyd2 (numberOfLines: integer); { Variant with for .. do loop } 

 var
   i, j, numbersInLine, startOfLastlLine: integer;

 begin
   startOfLastlLine := (numberOfLines - 1) * numberOfLines div 2 + 1;
   i := 1;
   for numbersInLine := 1 to numberOfLines do
   begin
     for j := 1 to numbersInLine do
     begin
       write(i: digits(startOfLastlLine - 1 + j), ' ');
       inc(i);
     end;
     writeln;
   end;
 end;

begin 

 writeln ('*** Floyd 5 ***');
 floyd1(5);
 writeln;
 writeln ('*** Floyd 14 ***');
 floyd2(14);

end.</lang> Output: 

% ./Floyd
*** Floyd 5 ***
 1 
 2  3 
 4  5  6 
 7  8  9 10 
11 12 13 14 15 

*** Floyd 14 ***
 1 
 2  3 
 4  5  6 
 7  8  9 10 
11 12 13 14 15 
16 17 18 19 20 21 
22 23 24 25 26 27 28 
29 30 31 32 33 34 35 36 
37 38 39 40 41 42 43 44  45 
46 47 48 49 50 51 52 53  54  55 
56 57 58 59 60 61 62 63  64  65  66 
67 68 69 70 71 72 73 74  75  76  77  78 
79 80 81 82 83 84 85 86  87  88  89  90  91 
92 93 94 95 96 97 98 99 100 101 102 103 104 105

Perl 6

<lang perl6>sub chunk(@flat is copy, *@size) { 

   gather for @size -> $s { take [@flat.shift xx $s] }

}

constant @floyd = chunk 1..*, 1..*;

sub say-floyd($n) { 

   my @fmt = @floyd[$n-1].map: {"%{.chars}s"}

   for @floyd[^$n] -> @i {
       say join ' ', (@i Z @fmt).map: -> $i, $f { $i.fmt($f) }
   }

}

say-floyd 5; say-floyd 14;</lang>

Output:
 1 
 2  3 
 4  5  6 
 7  8  9 10 
11 12 13 14 15 
 1 
 2  3 
 4  5  6 
 7  8  9 10 
11 12 13 14 15 
16 17 18 19 20 21 
22 23 24 25 26 27 28 
29 30 31 32 33 34 35 36 
37 38 39 40 41 42 43 44  45 
46 47 48 49 50 51 52 53  54  55 
56 57 58 59 60 61 62 63  64  65  66 
67 68 69 70 71 72 73 74  75  76  77  78 
79 80 81 82 83 84 85 86  87  88  89  90  91 
92 93 94 95 96 97 98 99 100 101 102 103 104 105

PicoLisp

Calculate widths relative to lower left corner

<lang PicoLisp>(de floyd (N) 

  (let LLC (/ (* N (dec N)) 2)
     (for R N
        (for C R
           (prin
              (align
                 (length (+ LLC C))
                 (+ C (/ (* R (dec R)) 2)) ) )
           (if (= C R) (prinl) (space)) ) ) ) )</lang>

Pre-calculate all rows, and take format from last one

<lang PicoLisp>(de floyd (N) 

  (let
     (Rows
        (make
           (for ((I . L) (range 1 (/ (* N (inc N)) 2))  L)
              (link (cut I 'L)) ) )
        Fmt (mapcar length (last Rows)) )
     (map inc (cdr Fmt))
     (for R Rows
        (apply tab R Fmt) ) ) )</lang>

Output in both cases: 

: (floyd 5)
 1
 2  3
 4  5  6
 7  8  9 10
11 12 13 14 15

: (floyd 14)
 1
 2  3
 4  5  6
 7  8  9 10
11 12 13 14 15
16 17 18 19 20 21
22 23 24 25 26 27 28
29 30 31 32 33 34 35 36
37 38 39 40 41 42 43 44  45
46 47 48 49 50 51 52 53  54  55
56 57 58 59 60 61 62 63  64  65  66
67 68 69 70 71 72 73 74  75  76  77  78
79 80 81 82 83 84 85 86  87  88  89  90  91
92 93 94 95 96 97 98 99 100 101 102 103 104 105

PL/I

<lang PL/I> (fofl, size): floyd: procedure options (main); /* Floyd's Triangle. Wiki 12 July 2012 */ 

  declare (i, m, n) fixed (10), (j, k, w, nr) fixed binary;

  put list ('How many rows do you want?');
  get list (nr);   /* the number of rows   */
  n = nr*(nr+1)/2; /* the total number of values */

  j,k = 1; m = n - nr + 1;
  do i = 1 to n;
     put edit (i) ( x(1), f(length(trim(m))) );
     if k > 1 then do; k = k - 1; m = m + 1; end;
     else do; k,j = j + 1; m = n - nr + 1; put skip; end;
  end;

end floyd; </lang> 


How many rows do you want?
  1
  2  3
  4  5  6
  7  8  9 10
 11 12 13 14 15

How many rows do you want? 
  1
  2  3
  4  5  6
  7  8  9 10
 11 12 13 14 15
 16 17 18 19 20 21
 22 23 24 25 26 27 28
 29 30 31 32 33 34 35 36
 37 38 39 40 41 42 43 44  45
 46 47 48 49 50 51 52 53  54  55
 56 57 58 59 60 61 62 63  64  65  66
 67 68 69 70 71 72 73 74  75  76  77  78
 79 80 81 82 83 84 85 86  87  88  89  90  91
 92 93 94 95 96 97 98 99 100 101 102 103 104 105

Final row for n=45:
 991 992 993 994 995 996 997 998 999 1000 1001 1002 1003 1004 1005 1006 1007 1008 1009 1010 1011 1012 1013 1014 1015 1016 1017 1018 1019 1020 1021 1022 1023 1024 1025 1026 1027 1028 1029 1030 1031 1032 1033 1034 1035

Python

<lang python>>>> def floyd(rowcount=5): rows = 1 while len(rows) < rowcount: n = rows[-1][-1] + 1 rows.append(list(range(n, n + len(rows[-1]) + 1))) return rows

>>> floyd() [[1], [2, 3], [4, 5, 6], [7, 8, 9, 10], [11, 12, 13, 14, 15]] >>> def pfloyd(rows=[[1], [2, 3], [4, 5, 6], [7, 8, 9, 10]]): colspace = [len(str(n)) for n in rows[-1]] for row in rows: print( ' '.join('%*i' % space_n for space_n in zip(colspace, row)))


>>> pfloyd() 1 2 3 4 5 6 7 8 9 10 >>> pfloyd(floyd(5)) 

1
2  3
4  5  6
7  8  9 10

11 12 13 14 15 >>> pfloyd(floyd(14)) 

1
2  3
4  5  6
7  8  9 10

11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 >>> </lang>

Alternately (using the mathematical formula for each row directly): <lang python>def floyd(rowcount=5): return [list(range(i*(i-1)/2+1, i*(i+1)/2+1)) 

               for i in range(1, rowcount+1)]</lang>

REXX

<lang rexx> /* REXX ***************************************************************

  • Parse Arg rowcount
  • 12.07.2012 Walter Pachl - translated from Python
                                                                                                                                            • /

Parse Arg rowcount col=0 ll= /* last line of triangle */ Do j=rowcount*(rowcount-1)/2+1 to rowcount*(rowcount+1)/2 

 col=col+1                         /* column number                 */ 
 ll=ll j                           /* build last line               */ 
 len.col=length(j)                 /* remember length of column     */ 
 End

Do i=1 To rowcount-1 /* now do and output the rest */ 

 ol=                                                                 
 col=0                                                                 
 Do j=i*(i-1)/2+1 to i*(i+1)/2     /* elements of line i            */ 
   col=col+1                                                           
   ol=ol right(j,len.col)          /* element in proper length      */ 
   end                                                                 
 Say ol                            /* output ith line               */ 
 end

Say ll /* output last line */ </lang>

Scala

<lang scala>def floydstriangle( n:Int ) { 

 val s = (1 to n)
 val t = s map {i => (s take(i-1) sum) + 1}
 
 (s zip t) foreach { n => 
   var m = n._2; 

   for( i <- 0 until n._1 ) {
     val w = (t.last + i).toString.length + 1  // Column width from last row
     print("           " + m takeRight w )
     m+=1
   }

   print("\n")
 }

}

// Test floydstriangle(5) floydstriangle(14)</lang>

Output:
  1
  2  3
  4  5  6
  7  8  9 10
 11 12 13 14 15

  1
  2  3
  4  5  6
  7  8  9 10
 11 12 13 14 15
 16 17 18 19 20 21
 22 23 24 25 26 27 28
 29 30 31 32 33 34 35 36
 37 38 39 40 41 42 43 44  45
 46 47 48 49 50 51 52 53  54  55
 56 57 58 59 60 61 62 63  64  65  66
 67 68 69 70 71 72 73 74  75  76  77  78
 79 80 81 82 83 84 85 86  87  88  89  90  91
 92 93 94 95 96 97 98 99 100 101 102 103 104 105

Tcl

<lang tcl>proc floydTriangle n { 

   # Compute the column widths
   for {set i [expr {$n*($n-1)/2+1}]} {$i <= $n*($n+1)/2} {incr i} {

lappend w [string length $i] 

   }
   # Print the triangle
   for {set i 0; set j 1} {$j <= $n} {incr j} {

for {set p -1; set k 0} {$k < $j} {incr k} { puts -nonewline [format "%*d " [lindex $w [incr p]] [incr i]] } puts "" 

   }

}

  1. Demonstration

puts "Floyd 5:" floydTriangle 5 puts "Floyd 14:" floydTriangle 14</lang>

Output:
Floyd 5:
 1 
 2  3 
 4  5  6 
 7  8  9 10 
11 12 13 14 15 
Floyd 14:
 1 
 2  3 
 4  5  6 
 7  8  9 10 
11 12 13 14 15 
16 17 18 19 20 21 
22 23 24 25 26 27 28 
29 30 31 32 33 34 35 36 
37 38 39 40 41 42 43 44  45 
46 47 48 49 50 51 52 53  54  55 
56 57 58 59 60 61 62 63  64  65  66 
67 68 69 70 71 72 73 74  75  76  77  78 
79 80 81 82 83 84 85 86  87  88  89  90  91 
92 93 94 95 96 97 98 99 100 101 102 103 104 105
Retrieved from "https://rosettacode.org/wiki/Floyd%27s_triangle?oldid=215789"