Alrighty the DISPLAY Pascal’s Triangle Challenge

[Duthomhas]

So, a common challenge is to generate Pascal’s triangle for some N rows.
Easy-peasy.

What you usually see is something like one of the following wonky outputs:

1 2 3 4 5 6 7 8

1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 1 6 15 20 15 6 1 1 7 21 35 35 21 7 1

1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 1 6 15 20 15 6 1 1 7 21 35 35 21 7 1

I consider those jarring to read. I’d like to see things lined up a bit more... nicely:

1 2 3 4 5 6 7 8

1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 1 6 15 20 15 6 1 1 7 21 35 35 21 7 1

1 1 1 1 2 1 1 3 3 1

That’s so much better on the eyes.

Your challenge, should you choose to accept it, is to generate and properly display Pascal’s triangle for some command-line argument input number of lines N in [0,32]. Your program should be 50 lines or fewer.

[lastchance]

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
using INT = unsigned long long;

int numDigits( INT n ){ return n < 10 ? 1 : 1 + numDigits( n / 10 ); }

void space( int n ){ while( n-- ) cout << ' '; }

double lognCr( int n, int r )
{
   if ( n == 0 || n == r || r == 0 ) return 0.0;
   double result = 0.0;
   for ( int i = 0; i < r; i++ ) result += log10( ( n - i ) / ( 1.0 + i ) );
   return result;
}

void cell( INT n, int width )
{
   int length = numDigits( n );
   int pre = ( width - length ) / 2;
   int post = width - length - pre;
   space( pre );
   cout << n;
   space( post);
}

void printPascal( int N, bool narrow )
{
   int width = floor( lognCr( N, N / 2 ) ) + 1.1;
   int gap = narrow ? 2 + width % 2 : width;
   vector<INT> row, old;
   for ( int r = 0; r <= N; r++ )
   {
      old = row;
      for ( int i = 1; i < r; i++ ) row[i] = old[i] + old[i-1];
      row.push_back( 1 );
      space( ( N - r ) * ( width + gap ) / 2 );
      for ( INT I : row ) { cell( I, width );   space( gap ); }
      cout << '\n';
   }
}

int main()
{
   int N;
   cout << "Enter N (row 0 is apex): ";   cin >> N;
   printPascal( N, false );
}

Enter N (row 0 is apex): 10
                               1    
                            1     1    
                         1     2     1    
                      1     3     3     1    
                   1     4     6     4     1    
                1     5    10    10     5     1    
             1     6    15    20    15     6     1    
          1     7    21    35    35    21     7     1    
       1     8    28    56    70    56    28     8     1    
    1     9    36    84    126   126   84    36     9     1    
 1    10    45    120   210   252   210   120   45    10     1  

[Duthomhas]

Very nice! A clear, succinct, algorithm.

You managed your spacing differently than I did. You did catch on to the need to determine the width of the bottom, center element and the mathematical properties to compute it. Your method of computation is unique as well.

A well-organized solution! Also, frist → bonus points!


I should note that the input N is the number of rows, so an input of 0 should print nothing, 1 should print the top row, 2 the second, etc. Sorry the challenge didn’t express that clearly enough.

_{^{Also, I adjusted the challenge to accept any reasonable method of input, like I should have to begin with.}}


I’ll wait a little longer before posting my solution as well.

[mbozzi]

#include <deque>
#include <iomanip>
#include <iostream>
#include <string>

using row_t = std::deque<int>;
using pascal_triangle_t = std::deque<row_t>;

row_t pascal_next_row(row_t const& row) {
  row_t row_shr = row; row_shr.push_front(0);
  row_t row_shl = row; row_shl.push_back(0);
  row_t new_row;

  for (unsigned i = 0; i < row_shr.size(); ++i)
    new_row.push_back(row_shr[i] + row_shl[i]);

  return new_row;
}

pascal_triangle_t pascal(int n_rows) {
  pascal_triangle_t result(n_rows, row_t{1});

  for (unsigned i = 1; i < result.size(); ++i)
    result[i] = pascal_next_row(result[i - 1]);
  
  return result;
}

static std::string spaces(int n)
{ return std::string(n , ' '); }

int main() {
  int n_rows; std::cin >> n_rows;

  pascal_triangle_t const ptri = pascal(n_rows);
  int const width = std::to_string(ptri.back()[n_rows / 2]).size();

  for (int i = 0; i < n_rows; ++i) {
    std::cout << spaces(width * (n_rows - i - 1));
    for (auto const& elt: ptri[i])
      std::cout << std::left << std::setw(width) << elt << spaces(width);
    std::cout << '\n';
  }
}

$ echo 10 | ./pascal-triangle.out
                           1     
                        1     1     
                     1     2     1     
                  1     3     3     1     
               1     4     6     4     1     
            1     5     10    10    5     1     
         1     6     15    20    15    6     1     
      1     7     21    35    35    21    7     1     
   1     8     28    56    70    56    28    8     1     
1     9     36    84    126   126   84    36    9     1

[lastchance]

#include <iostream>
#include <vector>
using namespace std;
using INT = unsigned long long;

int numDigits( INT n ){ return n < 10 ? 1 : 1 + numDigits( n / 10 ); }

void space( int n ){ while( n-- ) cout << ' '; }

void printPascal( int N, bool narrow, bool left )
{
   vector<vector<INT>> triangle;
   for ( int r = 0; r <= N; r++ )
   {
      triangle.push_back( vector<INT>( r + 1, 1 ) );
      for ( int j = 1; j < r; j++ ) triangle[r][j] = triangle[r-1][j] + triangle[r-1][j-1];
   }

   int width = numDigits( triangle[N][N/2] );
   int gap = narrow ? 2 + width % 2 : width;
   for ( int r = 0; r <= N; r++ )
   {
      space( ( N - r ) * ( width + gap ) / 2 );
      for ( INT I : triangle[r] )
      {
         int length = numDigits( I );
         int pre = left ? 0 : ( width - length ) / 2;
         space( pre );
         cout << I;
         space( gap + width - length - pre );
      }
      cout << '\n';
   }
}

int main()
{
   int N;
   cout << "Enter N (row 0 is apex): ";   cin >> N;
   printPascal( N, false, false );
}

Enter N (row 0 is apex): 10
                               1    
                            1     1    
                         1     2     1    
                      1     3     3     1    
                   1     4     6     4     1    
                1     5    10    10     5     1    
             1     6    15    20    15     6     1    
          1     7    21    35    35    21     7     1    
       1     8    28    56    70    56    28     8     1    
    1     9    36    84    126   126   84    36     9     1    
 1    10    45    120   210   252   210   120   45    10     1  

If the top line corresponds to N=1 then change the penultimate line to
if ( N > 0 ) printPascal( N - 1, false, false );

Setting the second argument sent to printPascal to true will make the gaps smaller for large N.

Setting the third argument sent to printPascal to true will left-align each column, but will cause a gradual swing to the right down a column as the numbers get larger. (Edited to allow this, but not turned on by default)

[Duthomhas]

@mbozzi
Very nice and very clean.
Interesting method for generating the next row.

@lastchance
I like this version even better than your first.

[Duthomhas]

Well, it has been a couple of days. Here’s my version.

#include <algorithm>
#include <cctype>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <string>
#include <vector>

std::vector <unsigned> & next_pascal( std::vector <unsigned> & ns )
{
  ns.emplace_back( 1 );
  if (ns.size() > 2)
    std::adjacent_difference(
      ns.rbegin() + 1, ns.rend(),
      ns.rbegin(),
      []( auto a, auto b ) { return a + b; }
    );
  return ns;
}

unsigned n_choose_k( unsigned n, unsigned k )
{
  if (k == 0) return 1;
  return (n * n_choose_k( n-1, k-1 )) / k;
}

int main( int argc, char** argv ) try
{
  // n ← number of rows
  unsigned n = std::stoul( argv[ std::max( 1, argc - 1 ) ] );
  if (!n) return 0;

  // w ← width of each field to print
  unsigned w = std::floor( std::log10( n_choose_k( n-1, (n-1)/2 ) ) ) + 1;
  w += std::toupper( *argv[ 1 ] ) == 'N' ? (1 + !(w % 2)) : w;

  // xs ← each subsequent row of Pascal's triangle
  std::vector <unsigned> xs;
  while (n--)
  {
    std::cout << std::string( w / 2 * n, ' ' );
    for (auto x : next_pascal( xs ))
      std::cout << std::left << std::setw( w ) << x;
    std::cout << "\n";
  }
}
catch (...) { }

$ pascal narrow 10
                  1
                1   1
              1   2   1
            1   3   3   1
          1   4   6   4   1
        1   5   10  10  5   1
      1   6   15  20  15  6   1
    1   7   21  35  35  21  7   1
  1   8   28  56  70  56  28  8   1
1   9   36  84  126 126 84  36  9   1

$ pascal wide 10
                           1
                        1     1
                     1     2     1
                  1     3     3     1
               1     4     6     4     1
            1     5     10    10    5     1
         1     6     15    20    15    6     1
      1     7     21    35    35    21    7     1
   1     8     28    56    70    56    28    8     1
1     9     36    84    126   126   84    36    9     1

The difference between "wide" and "narrow" is that "narrow" will reduce the spacing between elements to as few as one character if possible.

───────────────

In the interest in not scrunching the code up too much I left out a couple of my favorite non-essential parts. They are:

Display usage info for incorrect invocation:

catch (...) {
  std::string s { argv[ 0 ] };
  s = s.substr( s.find_last_of( "\\" ) + 1 );
  std::cerr << "usage:\n  " << s << " [wide] N\n  " << s << " narrow N\n"
               "Prints N rows of Pascal's triangle.\n";
}

Don’t print extra spaces at EOL:

    unsigned count = 0;
    for (auto x : next_pascal( xs ))
      std::cout << std::setw( count++ ? w : 1 ) << x;

Kudos to lastchance and mbozzi for being awesome. PM me and I’ll send you something.

Further submissions are still welcome, of course. Until the thread archives, at least.

[lastchance]

Ah, that is indeed neat. A 'simple' problem with a surprising amount of scope for different answers - even in just generating the elements of a familiar triangle. Having the 'narrow' option definitely helps when N reaches 32.

I guess what is 'neat and tidy' is a bit subjective: my children and I always used to reach opposing conclusions as to whether their bedrooms were 'tidy'. Having some options in coding (as in family life) gives scope to keep everybody happy.

Happy Christmas and New Year!

[rabster]

Wish I hadn't just seen this yesterday.

#include <iostream>
#include <string>
#include <vector>
struct Settings {
	enum class Alignment : uint8_t { LEFT, CENTER, RIGHT };
	Alignment mode = Alignment::CENTER;
	bool narrow = false;
	bool reverse = false;
	char padding = ' ';
	Settings& setPadding(char value) { padding = value; return *this; }
	Settings& setNarrow(bool value) { narrow = value; return *this; }
	Settings& setMode(Alignment value) { mode = value; return *this; }
	Settings& setReverse(bool value) { reverse = value; return *this; }
};
std::size_t digitCount(std::size_t n) { return std::to_string(n).length(); }
std::vector<std::size_t> getPascalRow(std::size_t row) {
	std::vector<std::size_t> rowData;
	rowData.reserve(row);

	double next = 1;
	for (std::size_t index = row + 1; index--;) {
		rowData.push_back(static_cast<std::size_t>(next));
		next = std::round((next / static_cast<double>(row - index + 1)) * static_cast<double>(index));
	}
	return rowData;
}
void pascalsTriangle(std::size_t rows, const Settings& settings = Settings()) {
	std::vector<std::vector<std::size_t>> pascalRows(rows + 1);
	for (std::size_t index = 0; index <= rows; ++index) { pascalRows[index] = getPascalRow(index); }
	const std::size_t width = digitCount(pascalRows.back().at(rows / 2));
	const std::size_t padding = settings.narrow ? 1 + !(width % 2) : width;
	const std::string spacing(width, settings.padding);
	for (std::size_t rI = 0; rI <= rows; ++rI) {
		const std::size_t fixedIndex = settings.reverse ? rows - rI : rI;
		std::cout << std::string((rows - fixedIndex) * (settings.narrow ? (width + padding) / 2 : width), settings.padding);
		for (std::size_t index = 0, size = pascalRows[fixedIndex].size(); index != size; ++index) {
			const std::size_t value = pascalRows[fixedIndex][index];
			const std::size_t digits = digitCount(value);
			if (settings.mode == Settings::Alignment::CENTER) {
				const std::size_t pairs = (digits - 1) / 2;
				const std::size_t nextPair = (index+1 < size ? (digitCount(pascalRows[fixedIndex][index + 1])-1) / 2 : pairs);
				const std::size_t digitSpacing = nextPair > pairs ? width - (nextPair-pairs) : (nextPair < pairs ? width + (pairs-nextPair) : width);
				std::cout << value << std::string(digitSpacing + padding- digits,settings.padding);
			}
			else if (settings.mode == Settings::Alignment::LEFT) {
				std::cout << value << std::string((width + padding) - digits, settings.padding);
			}
			else {
				std::cout << std::string(width + padding - digits, settings.padding) << value;
			}
		}
		std::cout << std::endl;
	}
}
int main() {
	std::size_t rows;
	std::cin >> rows;
	Settings settings;
	pascalsTriangle(rows, settings.setMode(Settings::Alignment::CENTER).setNarrow(false).setReverse(true).setPadding(' '));
}

Just to give credit, I used your narrowing method @Duthomhas since there isn't a better one to come up with.

[lastchance]

Hi @duthomas,
A rather pretty variant of this is to work out Pascal's triangle in MODULAR ARITHMETIC, printing solid for non-zero, blank for 0 (ie those original numbers that are divisible by the base).

It produces beautiful fractals (BASE=2 gives the Sierpinski gasket).

#include <iostream>
#include <vector>
#include <string>
using namespace std;

void pascal( int N, int BASE )
{
  vector<vector<int>> T;
  for ( int r = 0; r <= N; r++ )
  {
    T.push_back( vector<int>(r+1,1) );
    for ( int j = 1; j < r; j++ ) T[r][j] = ( T[r-1][j] + T[r-1][j-1] ) % BASE;
  }
  for ( int r = 0; r <= N; r++ )
  {
    cout << string( N - r, ' ' );
    for ( int i : T[r] ) cout << ( i ? "* " : "  " );
    cout << '\n';
  }
}

int main()
{
  int N, BASE;
  cout << "N:    ";   cin >> N;
  cout << "BASE: ";   cin >> BASE;
  pascal( N, BASE );
}

N:    31
BASE: 2
                               * 
                              * * 
                             *   * 
                            * * * * 
                           *       * 
                          * *     * * 
                         *   *   *   * 
                        * * * * * * * * 
                       *               * 
                      * *             * * 
                     *   *           *   * 
                    * * * *         * * * * 
                   *       *       *       * 
                  * *     * *     * *     * * 
                 *   *   *   *   *   *   *   * 
                * * * * * * * * * * * * * * * * 
               *                               * 
              * *                             * * 
             *   *                           *   * 
            * * * *                         * * * * 
           *       *                       *       * 
          * *     * *                     * *     * * 
         *   *   *   *                   *   *   *   * 
        * * * * * * * *                 * * * * * * * * 
       *               *               *               * 
      * *             * *             * *             * * 
     *   *           *   *           *   *           *   * 
    * * * *         * * * *         * * * *         * * * * 
   *       *       *       *       *       *       *       * 
  * *     * *     * *     * *     * *     * *     * *     * * 
 *   *   *   *   *   *   *   *   *   *   *   *   *   *   *   * 
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 

N: 49
BASE: 5
                                                 *
                                                * * 
                                               * * * 
                                              * * * * 
                                             * * * * * 
                                            *         * 
                                           * *       * * 
                                          * * *     * * * 
                                         * * * *   * * * * 
                                        * * * * * * * * * * 
                                       *         *         * 
                                      * *       * *       * * 
                                     * * *     * * *     * * * 
                                    * * * *   * * * *   * * * * 
                                   * * * * * * * * * * * * * * * 
                                  *         *         *         * 
                                 * *       * *       * *       * * 
                                * * *     * * *     * * *     * * * 
                               * * * *   * * * *   * * * *   * * * * 
                              * * * * * * * * * * * * * * * * * * * * 
                             *         *         *         *         * 
                            * *       * *       * *       * *       * * 
                           * * *     * * *     * * *     * * *     * * * 
                          * * * *   * * * *   * * * *   * * * *   * * * * 
                         * * * * * * * * * * * * * * * * * * * * * * * * * 
                        *                                                 * 
                       * *                                               * * 
                      * * *                                             * * * 
                     * * * *                                           * * * * 
                    * * * * *                                         * * * * * 
                   *         *                                       *         * 
                  * *       * *                                     * *       * * 
                 * * *     * * *                                   * * *     * * * 
                * * * *   * * * *                                 * * * *   * * * * 
               * * * * * * * * * *                               * * * * * * * * * * 
              *         *         *                             *         *         * 
             * *       * *       * *                           * *       * *       * * 
            * * *     * * *     * * *                         * * *     * * *     * * * 
           * * * *   * * * *   * * * *                       * * * *   * * * *   * * * * 
          * * * * * * * * * * * * * * *                     * * * * * * * * * * * * * * * 
         *         *         *         *                   *         *         *         * 
        * *       * *       * *       * *                 * *       * *       * *       * * 
       * * *     * * *     * * *     * * *               * * *     * * *     * * *     * * * 
      * * * *   * * * *   * * * *   * * * *             * * * *   * * * *   * * * *   * * * * 
     * * * * * * * * * * * * * * * * * * * *           * * * * * * * * * * * * * * * * * * * * 
    *         *         *         *         *         *         *         *         *         * 
   * *       * *       * *       * *       * *       * *       * *       * *       * *       * * 
  * * *     * * *     * * *     * * *     * * *     * * *     * * *     * * *     * * *     * * * 
 * * * *   * * * *   * * * *   * * * *   * * * *   * * * *   * * * *   * * * *   * * * *   * * * * 
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *

[Duthomhas]

+1. That’s pretty awesome!

[lastchance]

Have to admit that the idea (but not the code) came from Alex Bellos's book "Alex’s Adventures in Numberland" (which my family gave me for Christmas). There's also some brilliant sequences in there ... which will do for next year's challenge.