## 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

### 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);
return EXIT_FAILURE;
}
int n = abs(atoi(argv));
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);
return EXIT_FAILURE;
}
int n = abs(atoi(argv));
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

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)

;; 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([]) { |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 ))
([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))))
```


[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)
```

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)
```