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