kdb programming challenge – Pascal’s Triangle

Matt Doherty kdb+ 9 Comments

Hello and welcome to the hotly anticipated inaugural post of the AquaQ Analytics q programming challenge blog! Hopefully our humble website can handle the inevitable onslaught of puzzle-solving traffic.

In this blog we will try to keep you entertained with a series of interesting computational or mathematical problems, and their solutions in kdb+/q. The solutions will be initially hidden for those of you who want to have a go at solving the problems before seeing our answer. The solution we give for each problem will be the one we thought was the most elegant/pretty; as with any programming problem there are many different solutions, none of which are the single ‘right’ answer!

Puzzle 1 – Pascal’s Triangle

Pascal's Triangle

Given an input n, generate the first n rows of Pascal’s triangle. You may assume that n is an integer inclusively between 1 and 25. There must be a line break between each row and a space between each number, but aside from that, you may format it however you like. The solution should be a monadic function of the form:

f:{[x]}

 

Matt Dohertykdb programming challenge – Pascal’s Triangle

Comments 9

  1. Jamie Grant

    Quick and dirty way of formatting the result as a triangle by centre aligning each line:

    {(neg floor .5*m-c)rotate'(m:max[c:count each x])$'x}" "sv/: string (),/:f 12
    

    And messier still, try to straighten the side of the triangle by normalising the width of each integer:

    {(neg floor .5*m-c)rotate'(m:max[c:count each x])$'x}" "sv/: {(max count each raze x)$''x:string x} (),/:f 14
    
  2. Pingback: Q programming challenge, Pascal’s triangle

  3. Steven Taylor

    Nice. I came up with this prior to clicking on “show answer”

    p:{[i]r:(,)a:(,)1;do[i-:1;r,:a:{((+’:)x),1}a];:r}

    the scan version works better though. Maybe it looks a little cleaner if expressed this way?

    f:{-1_x{(+’:)x,0}\1}

    1. WooiKent Lee

      imo, it does look cleaner, but I’m just thinking “iterate n-1 times is better than iterate n times and drop the last result” as less resources will be used. Yet,I suppose for this small problem, it doesn’t really matter…

  4. Jose Cambronero

    Just discovered your guys blog, good addition! Below my solution (without pretty print)

    pascal:{(,[;1] ( +’: ) @)\ [x;1]}

    fyi, the text box seems to mess up q code, so had to add unwanted spaces in the above

  5. Patrick Wu

    This appears to provide decent performance:

    f0:{{(+)’:[x], 1}[x-1;1]}
    f0[4]

    \ts do[100000;f0[4]]

Leave a Reply

Your email address will not be published. Required fields are marked *

To create code blocks or other preformatted text, indent by four spaces:

    This will be displayed in a monospaced font. The first four 
    spaces will be stripped off, but all other whitespace
    will be preserved.
    
    Markdown is turned off in code blocks:
     [This is not a link](http://example.com)

To create not a block, but an inline code span, use backticks:

Here is some inline `code`.

For more help see http://daringfireball.net/projects/markdown/syntax