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.
Programming Praxis 
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""'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 55Alternative 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 28For most favoured languages try
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:
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:
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:
Prints the nth line of the triangle
# O(1) def nth_floyd(n): b = int((1+(n-1)*n) - (((n-# 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
Two solutions in Haskell.
The first one starts with the infinite list of successive integers and chops it up in increasingly larger chunks
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:
If you don’t want to print an infinite triangle, you can cut it short as follows:
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))# 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" } endAll 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
Code 👆 in Ruby.
Bash.
1 loop
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 ""; done1
2 3
4 5 6
7 8 9 10
11 12 13 14 15
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):
[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:
1
2 3
4 5 6
7 8 9 10
11 12 13 14 15
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 : footerThe 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: