kdb programming challenge – Pascal’s Triangle

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

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]}`

kdb programming challenge – Pascal’s Triangle

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. 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…

3. 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

f:{s:enlist 0 1 0; i:1;
while [i<x; s,:enlist (0 +’: last s),0; i+:1];
-1_/:1_/: s};

5. Patrick Wu

This appears to provide decent performance:

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

\ts do[100000;f0[4]]