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

[image type=”thumbnail” src=”7060″ alt=”Pascal’s Triangle” link=”true” href=”http://en.wikipedia.org/wiki/Pascal’s_triangle” target=”blank”]

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

[showhide type=”post” more_text=”Show Solution” less_text=”Solution” hidden=”yes”]

f:{{prior[+]x,0}\[x-1;1]}

Breaking this solution own a bit; we start with the number 1 at the top of the pyramid, pass this into our inner function, which adds 0 to the end and applies the projected function prior[+] to it, adding each number to it’s predecessor:

q)prior[+] 1 0
1 1

If we repeat this process it’s give us the next row etc.:

q)prior[+] 1 1 0
1 2 1

We then use the scan adverb to pass the result of this function back in as the argument, x-1 times:

q)f:{{prior[+]x,0}\[x-1;1]}
q)f 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

For those who are interested there is also an even more compact (and less readable!) version of this solution, courtesy of Qidioms:

f:{{0+':x,0}\[x-1;1]}

[/showhide]