Pascal's Pyramid and Higher Dimensions - Code Golf Stack Exchange most recent 30 from codegolf.stackexchange.com 2019-07-16T12:40:57Z https://codegolf.stackexchange.com/feeds/question/2741 http://www.creativecommons.org/licenses/by-sa/3.0/rdf https://codegolf.stackexchange.com/q/2741 6 Pascal's Pyramid and Higher Dimensions mellamokb https://codegolf.stackexchange.com/users/879 2011-06-03T19:26:57Z 2017-04-07T09:43:14Z <p>Pascal's Triangle is a familiar mathematical construct with many interesting properties. It is constructed by starting with a 1 on top, and generating the numbers in the next row from the sum of the number to the left and right in the row above (with implied 0's around the boundary):</p> <pre><code> 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 </code></pre> <p>The Triangle can be expanded into N dimensions by using the same rules. For example, the 3-D Pascal's Triangle would be a pyramid with each row being a cross-section of the pyramid, i.e., a triangle. Each triangle's entry is generated by adding the three numbers in the "row" above forming a triangle directly above that entry. An example of the first four "rows" is shown below:</p> <pre><code>1 1 1 1 1 2 2 1 2 1 1 3 3 3 6 3 1 3 3 1 </code></pre> <p>The 4-D Pascal's Triangle would have a 3-D Pascal's Triangle for the cross section, and so forth.</p> <p>Your task is to write a program that takes as input the dimension of the Pascal's Triange, and a row index to display. The row index starts at 0, so row 0 is <code>1</code> for every dimension. Your program should abide by the following specifications:</p> <ul> <li>Take input N = dimension number, R = row number (0-based). The input can be either command-line arguments or from stdin. N >= 2, R >= 0</li> <li>Output the R'th row in the N-dimensional Pascal's Triangle, by displaying each row or triangle on a separate line as in the above example.</li> <li>The format can vary as long as it is 'triangle-like' and obvious where each row and entry in the row belongs with respect to other rows.</li> </ul> <p>Here is some sample output (I believe these are correct):</p> <pre><code>&gt;./pascal 2 5 1 5 10 10 5 1 &gt;./pascal 3 4 1 4 4 6 12 6 4 12 12 4 1 4 6 4 1 &gt;./pascal 4 3 1 3 3 3 3 6 6 3 6 3 1 3 3 3 6 3 1 3 3 1 &gt;./pascal 5 2 1 2 2 2 2 1 2 2 2 1 2 2 1 2 1 </code></pre> <p>Bonus: What is the significance of each "row" in an N-dimensional Pascal's triangle? I can think of at least three interesting facts.</p> https://codegolf.stackexchange.com/questions/2741/-/2742#2742 5 Answer by Howard for Pascal's Pyramid and Higher Dimensions Howard https://codegolf.stackexchange.com/users/1490 2011-06-04T08:51:33Z 2017-04-07T09:43:14Z <h2>Ruby, 181</h2> <pre class="lang-ruby prettyprint-override"><code>def P(a)a.min&lt;0?0:a.max&lt;1?1:(b=a*1;t=k=0;b.map{b[k]-=1;k+=1;t+=P(b)};t)end def d(n,a)print n&gt;1?((0..a[-1]).map{|i|d(n-1,a+[i])};"\n"):"#{P(a)} "end d(ARGV.to_i,[ARGV.to_i]) </code></pre> <p>The first approach using the following recursive formula</p> <pre class="lang-ruby prettyprint-override"><code>P(...,-1,...) = 0 P(0,0,...,0) = 1 P(a,b,c,....) = P(a-1,b,c,...) + P(a-1,b-1,c,...) + P(a-1,b-1,c-1,...) + ... </code></pre> <p>and then printing row <code>P(R,...)</code>.</p> <p>The output is triangle-like - for <code>pascal 4 2</code> it looks like</p> <pre class="lang-ruby prettyprint-override"><code>1 3 3 3 3 6 6 3 6 3 1 3 3 3 6 3 1 3 3 1 </code></pre>