Floyd’s Triangle

May 22, 2018

I noticed the other day this list of the Top 75 Programming Interview Questions. I’m not sure of the origin of the list, and it does have a Java feel to it, but I was happy to see that we’ve covered almost all the questions on the list. One of the questions we missed is Number 57:

Write a program to print Floyd’s Triangle.

I wasn’t familiar with Floyd’s Triangle, so I had to peek at the solution. Floyd’s Triangle lists the numbers in order, in lines of increasing length, so a Floyd’s Triangle of size 5 looks like this:

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

Your task is to write two programs that print Floyd’s Triangle; you must write two different programs that use two fundamentally different methods. 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.

Advertisements

Pages: 1 2

14 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

  14. Jared said

    Haskell. Infinite list generator the first:

    floyd :: [[Int]]
    floyd = loop 1 [1..] where
      loop n input =
        let header = take n input
            footer = loop (succ n) (drop n input)
        in  header : footer
    

    The second, using an unfold:

    import Data.List as L (unfoldr)
    
    floyd :: [[Int]]
    floyd = L.unfoldr alg (1, 0) where
      alg (m, n) =
        let lbound = m
            ubound = lbound + n
            range  = [lbound..ubound]
        in  Just (range, (succ ubound, succ n))
    

    Either can then be pretty-printed to an arbitrary number of rows as follows:

    render :: Show a => [a] -> String
    render input = case input of
      []    -> ""
      [h]   -> show h
      (h:t) -> show h ++ " " ++ render t
    
    main :: IO ()
    main = mapM_ (putStrLn . render) (take 5 floyd)
    

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: