[SOLVED] Create a small script

danielbmartin · 11-20-2014, 08:54 PM

Quote:

Originally Posted by grail

... see if you use your solution for Pascal's Triangle instead

Creating a cosmetically appealing display of Pascal's Triangle is difficult. I resorted to using a "pseudo-hexadecimal" numbering system such that a=10, ..., f=15, g=16, ..., z=35. This permits values up to 35 to be expressed as a single character.

This code ...

Code:

# Formula for calculating any element in Pascal's Triangle:
#
#          rownum!            where rownum is the number of the row ...
#  -----------------------     and elnum is the element number in that row
#   elnum!(rownum-elnum)!
#
nrows=8   # nrows = number of rows in the output file.
awk -v nrows=$nrows 'BEGIN{F[0]=1
  alphabet="123456789abcdefghijklmnopqrstuvwxyz"
  blankline="                "
  for (rownum=1;rownum<=nrows;rownum++)   # Build a table of 
    {F[rownum]=rownum*F[(rownum-1)]}      #  factorials in array F
  for (rownum=0;rownum<nrows;rownum++)    # Execute formula
    {outline=substr(blankline,1,nrows-rownum)
     for (elnum=0;elnum<=rownum;elnum++)
       outline=outline" "  \
         substr(alphabet,F[rownum]/(F[elnum]*F[rownum-elnum]),1)
   print outline}}' >$OutFile

... produced this result ...

Code:

         1
        1 1
       1 2 1
      1 3 3 1
     1 4 6 4 1
    1 5 a a 5 1
   1 6 f k f 6 1
  1 7 l z z l 7 1

Daniel B. Martin

grail · 11-21-2014, 12:57 AM

Agreed Daniel that formatting is a little crappy

However, ignoring our formatting issue, here is the same but with bash (your factorial mileage will of course depend on your computer

)

Code:

#!/usr/bin/env bash

factorial()
{
  local l_start_num

  l_start_num=$1

  if (( l_start_num == 1 || l_start_num == 0 ))
  then
    echo 1
  else
    echo $(( l_start_num * $(factorial $((--l_start_num))) ))
  fi
}

n=$1

printf "%$((n + 1))d\n" 1

for ((i = 1; i <= n; i++))
do
  for ((j = 0; j <= i; j++))
  do
    (( num = $(factorial $i) / ($(factorial $j) * $(factorial $((i - j)))) ))
    (( wspace = (j == 0)?(n - i + 1):$((${#num} + 1)) ))

    printf "%${wspace}d" $num
  done
  echo
done

danielbmartin · 11-21-2014, 08:29 AM

Quote:

Originally Posted by grail

Agreed Daniel that formatting is a little crappy

I improved my awk solution to eliminate the use of "pseudohexidecimal" number representation.
The output formatting was improved (but not perfected) by left-padding the individual values with blanks.
This awk ...

Code:

# Formula for calculating any element in Pascal's Triangle:
#
#          rownum!            where rownum is the number of the row ...
#  -----------------------     and elnum is the element number in that row
#   elnum!(rownum-elnum)!
#
nrows=16   # nrows = number of rows in the output file.
awk -v nrows=$nrows 'BEGIN{F[0]=1
  blankline="                                        "
  for (rownum=1;rownum<=nrows;rownum++)   # Build a table of 
    {F[rownum]=rownum*F[(rownum-1)]}      #  factorials in array F
  for (rownum=0;rownum<nrows;rownum++)    # Execute formula
    {outline=substr(blankline,1,2*(nrows-rownum-1))
     for (elnum=0;elnum<=rownum;elnum++)
       {value=F[rownum]/(F[elnum]*F[rownum-elnum])
       value=substr(blankline,1,5-length(value)) value   # Pad with blanks
     outline=outline value}
   print outline}}' >$OutFile

... produced this result ...

Code:

                                   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
            1   11   55  165  330  462  462  330  165   55   11    1
          1   12   66  220  495  792  924  792  495  220   66   12    1
        1   13   78  286  715 1287 1716 1716 1287  715  286   78   13    1
      1   14   91  364 1001 2002 3003 3432 3003 2002 1001  364   91   14    1
    1   15  105  455 1365 3003 5005 6435 6435 5005 3003 1365  455  105   15    1

The awk program runs noticeably faster than the bash. The bash version recalculates the same factorials over and over again, and does that computation with a recursive routine. The awk version makes a table of factorials and then uses it multiple times.

Daniel B. Martin

grail · 11-21-2014, 10:43 AM

Well the same pre-storage in bash does indeed increase the speed:

Code:

#!/usr/bin/env bash

n=$1
F=( 1 )

for (( i = 1; i <= n ; i++ ))
do
  F+=( $(( ${F[i-1]} * i )) )
done

for (( k = 0; k <= n; k++))
do
  for (( j = 0; j <= k; j++ ))
  do
    (( out = ${F[k]} / ( ${F[j]} * ${F[k-j]} ) ))
    (( wspace = 2 * ((j == 0)?(n - k + 1):(${#out} + ((${#out} == 1)?1:0))) ))

    printf "%${wspace}d" $out
  done
  echo
done

I improved the formatting a little but it still gets messy