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.

Pages: 1 2

Posted by programmingpraxis
Filed in Exercises
14 Comments »

14 Responses to “Floyd’s Triangle”

  1. James Curtis-Smith said
    May 22, 2018 at 9:54 AM

    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
    May 22, 2018 at 12:58 PM

    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
    May 22, 2018 at 1:37 PM

    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
    May 22, 2018 at 10:25 PM

    For most favoured languages try 

    https://rosettacode.org/wiki/Floyd%27s_triangle
  5. Daniel said
    May 23, 2018 at 12:27 AM

    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. Sochima Biereagu, KodeJuice said
    May 24, 2018 at 2:49 PM

    Prints the nth line of the triangle

    # O(1)

def nth_floyd(n):
    b = int((1+(n-1)*n) - (((n-
  7. Sochima Biereagu, KodeJuice said
    May 24, 2018 at 2:54 PM 
    # 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
    May 24, 2018 at 3:37 PM

    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
    May 25, 2018 at 5:13 AM

    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
    May 25, 2018 at 11:50 AM 
    
# 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
    May 25, 2018 at 11:53 AM

    Code 👆 in Ruby.

  12. sbocq said
    May 29, 2018 at 9:08 PM

    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
    May 29, 2018 at 9:17 PM

    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
    July 8, 2018 at 7:31 PM

    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 comment