Floyd’s Triangle

May 22, 2018

Our first solution uses two nested loops; the loop on i runs from 0 to the size of the triangle, and the loop on j runs from 0 to i:

(define (floyd1 n)
  (let ((num 1))
    (do ((i 0 (+ i 1))) ((<= n i))
      (do ((j 0 (+ j 1))) ((< i j))
        (display num)
        (display (if (< j i) #\space #\newline))
        (set! num (+ num 1))))))
> (floyd1 10)
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

Our second solution has a single loop that runs from 1 to the highest number to be printed, stopping when the correct number of rows has been printed:

(define (floyd2 n)
  (let ((row 0))
    (do ((num 1 (+ num 1))) ((= row n))
      (display num)
      (if (square? (+ (* 8 num) 1))
          (begin (display #\newline)
                 (set! row (+ row 1)))
          (display #\space)))))
> (floyd2 10)
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

This version of the program identifies the last number on each row as a triangle number (the fifth triangle number, 15, is the number of balls that form a triangle with sides of length 5, like billiard balls) where n is triangular if and only if 8n + 1 is a perfect square.

You can run the program at https://ideone.com/MFK97F.

Advertisements

Pages: 1 2

13 Responses to “Floyd’s Triangle”

  1. Golfing these in perl – the first one uses map to perform two loops..; the second a single loop – until we start drawing the “n+1″st row..

    
    perl -E 'say join"\n",map{$a=$_*($_-1)/2;join" ",map{$a+$_}1..$_}1..(shift||5)'
    
    perl -E 'for($N=shift||5;$r<$N;){print!$r?"":$c?" ":"\n",++$_;($c=0,$r++)if++$c>$r}say""'
    
    
  2. mcmillhj said

    Perl6 solution using a single while loop and two variables to track state:

    #!perl6
    
    sub floyds-triangle(Int:D $max-rows --> Nil) {
      my $row-length = 1;
      my $current = 1;
      while $row-length <= $max-rows {
        say join "\t", $current ..^ $current + $row-length; # [current, current + row-length)
        
        $current += $row-length;
        $row-length++;
      }
    }
    
    floyds-triangle(10);
    # 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
    
  3. mcmillhj said

    Alternative Perl6 solution that recursively works backward from the nth triangle number:

    multi sub floyds-triangle(1 --> List) { [1 .. 1] }
    multi sub floyds-triangle(Int:D $n where * > 1 --> List) {
      my $nth-triangle-number = $n * ($n + 1) div 2;
    
      floyds-triangle2($n - 1).push: $nth-triangle-number - $n ^.. $nth-triangle-number;
    }
    
    say join "\n", floyds-triangle(7).map({ join "\t", $_.flat });
    # 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
    
  4. Milbrae said

    For most favoured languages try

    https://rosettacode.org/wiki/Floyd%27s_triangle
  5. Daniel said

    Here’s a solution in C that uses a nested loop along with a counter.

    #include <stdio.h>
    #include <stdlib.h>
    
    void print_floyd(int n) {
      int count = 1;
      for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= i; ++j) {
          if (j > 1) printf(" ");
          printf("%d", count);
          ++count;
        }
        printf("\n");
      }
    }
    
    int main(int argc, char* argv[]) {
      if (argc != 2) {
        fprintf(stderr, "Usage: %s <N>\n", argv[0]);
        return EXIT_FAILURE;
      }
      int n = abs(atoi(argv[1]));
      print_floyd(n);
      return EXIT_SUCCESS;
    }
    

    Example:

    $ ./floyd 10
    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
    

    Here’s a solution in C that uses a counter, printing a newline each time a triangular number is reached.

    #include <stdio.h>
    #include <stdlib.h>
    
    void print_floyd(int n) {
      int count = 1;
      int row = 1;
      int last = 1;
      while (1) {
        if (row > n) break;
        printf("%d", count);
        if (count == last) {
          printf("\n");
          ++row;
          last = row * (row + 1) / 2;
        } else {
          printf(" ");
        }
        ++count;
      }
    }
    
    int main(int argc, char* argv[]) {
      if (argc != 2) {
        fprintf(stderr, "Usage: %s <N>\n", argv[0]);
        return EXIT_FAILURE;
      }
      int n = abs(atoi(argv[1]));
      print_floyd(n);
      return EXIT_SUCCESS;
    }
    

    Example:

    $ ./floyd 10
    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
    

    Here’s a solution in Python 3.

    from itertools import count
    
    def print_floyd(n):
      c = count(1)
      for x in range(n):
        print(" ".join(str(next(c)) for _ in range(x+1)))
    
    print_floyd(10)
    

    Output:

    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
    
  6. Prints the nth line of the triangle

    # O(1)
    
    def nth_floyd(n):
        b = int((1+(n-1)*n) - (((n-
    
  7. # Prints the nth line of the triangle
    def nth_floyd(n):
        b = int((1+(n-1)*n) - (((n-1)/2)*(2+(n-2))))
        print(list(range(b, b+n)))
    
    for i in range(1, 10):
        nth_floyd(i)
    

    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 5

  8. Josef Svenningsson said

    Two solutions in Haskell.

    The first one starts with the infinite list of successive integers and chops it up in increasingly larger chunks

    triangle = snd $ mapAccumL ((swap .) . flip splitAt) [1..] [1..]
    

    The second solution generates increasingly long lists

    triangle2 = [ [n..n+i]
    	    | i <- [0..]
                | j <- [1..]
                , let n = j * (j-1) `div` 2 + 1
    	    ]
    

    The triangles can be printed using the following code:

    printTriangle triangle = mapM_ (putStrLn . unwords . map show) triangle
    

    If you don’t want to print an infinite triangle, you can cut it short as follows:

    printTriangle $ take 10 triangle
    
  9. samdphillips said

    Racket

    #lang racket/base
    
    ;; nested for loops
    (define (floyd n)
      (void
       (for/fold ([i 1]) ([j (in-range 1 (add1 n))])
         (define next-i
           (for/last ([k (in-range i (+ i j))])
             (printf "~a " k)
             k))
         (newline)
         (add1 next-i))))
    
    ;; recursive and a for loop
    (define (floyd2 n)
      (define (row i j k)    
        (unless (= n i)
          (for ([x (in-range j k)])
            (printf "~a " x))
          (newline)
          (row (add1 i) k (+ 2 k i))))
      (row 0 1 2))
    
  10. V said
    
    # Funtional, iterative
    # First we generate the values range for each row
    # Then converte them into strings
    def floyd_triangle1(n)
      return ''    if n < 1
      return "1\n" if n == 1
      (2..n)
        .reduce([[1]]) { |m, i| m << ((m.last.last + 1)..(m.last.last + i)) }
        .map { |x| x.to_a.join(" ") + "\n" }.join
    end
    
    # Using "for" loops
    # Doing the whole thing in one go
    def floyd_triangle2(n)
      return "" if n <= 0
      
      out = ""
      last = 0
    
      (1..n).each do |i|
        (1..i).each do |j|
          last += 1
          out << last.to_s
          out << " " if i > j
        end
        out << "\n"
      end
      out
    end
    
    # Functional. Using the triagular number formula
    # An advantage of this is that we can calculate the values of a row
    # independently. So in theory we could calculate each row in parallel
    def floyd_triangle3(n)
      return "" if n <= 0
      
      # Triangular Number. See: https://en.wikipedia.org/wiki/Triangular_number
      tn = -> (n) { (n * (n + 1) ) / 2 }
      
      (1..n)
        .map { |n| n == 1 ? (1..1) : (tn.(n) - (n-1))..tn.(n) }
        .reduce('') { |m, x| m + x.to_a.join(" ") + "\n" }
    end  
    

    All three versions produce the same output. Here an example for n = 10

    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

  11. V said

    Code 👆 in Ruby.

  12. sbocq said

    Bash.

    1 loop

    $ l=1; e=1; i=1; while (( l <= 5 )); do (( e == i )) && echo "$i" && (( e = i++ + ++l )) || echo -n "$((i++)) "; done
    

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

    2 loops

    $ i=1;for l in {1..5}; do ((e = i + l)); while (( i < e )); do echo -n "$((i++)) "; done; echo ""; done
    

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

  13. sbocq said

    Clojure/Script lazy streams

    (defn floyd
      ([] (floyd 1 [1]))
      ([l r] (lazy-seq
               (cons r (floyd (inc l) (conj (mapv (partial + l) r) (inc (+ (last r) l))))))))
    

    Test (try online at http://clojurescript.net):

    (dorun (map print (take 5 (floyd))))
    

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

    Logically equivalent imperative Bash version using arrays

    function floyd {
      a=( 1 )
      for l in $(seq 1 $1); do
        echo "${a[*]}"
        for i in $(seq 0 $l); do
          ((a[i]+=l))
        done
        (( a[l]=a[l-1]+1 ))
      done
    }
    

    Test:

    $ floyd 5
    

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

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 )

w

Connecting to %s

%d bloggers like this: