kdb programming challenge - self similarity

A self similar object is one that is exactly or approximately similar to a part of itself (i.e. the whole has the same shape as one or more of the parts). Self similarity is a central property of fractals. Many objects in the real world, such as coastlines, are statistically self-similar: parts of them show the same statistical properties at many scales.

Outside of the real world, many mathematical objects show perfect self-similarity. A pretty cool example of this self-similarity in two dimensions is a Koch snowflake, which is both self-similar and symmetrical; it can be continually magnified by a factor of 3 without changing shape.

You are becoming sleepy, very sleepy…

So the challenge this time around is to write a function which tests for one-dimensional self-similarity in a list. The function should take a list and a “magnification” and return a bool indicating if the list is self-similar or not. For example here’s a sequence called Gould’s sequence:

1 2 2 4 2 4 4 8 2 4 4 8 4 8 8 16 2 4 4 8 4 8 8 16 4 8 8 16 8 16 16 32 2 4 ...

If we drop every other number the list remains the same i.e. it’s self similar with magnification of 2:

1 2 2 4 2 4 4 8 2 4 4 8 4 8 8 16 2 4 4 8 4 8 8 16 4 8 8 16 8 16 16 32 2 4 ...
1 2 2 4 2 4 4 8 2 4 4 8 4 8 8 16 2 ...

q)f[2;1 2 2 4 2 4 4 8 2 4 4 8 4 8 8 16 2 4 4 8 4 8 8 16 4 8 8 16 8 16 16 32 2 4]
1b

On the other hand it’s not self similar if magnification is 3:

q)f[3;1 2 2 4 2 4 4 8 2 4 4 8 4 8 8 16 2 4 4 8 4 8 8 16 4 8 8 16 8 16 16 32 2 4]
0b

Let’s see what you can get!

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

Once again there’s more than one nice way to solve this problem, so here’s two alternatives. The first is perhaps the most straightforward way: we index into the list at intervals of the magnification – 0, 2, 4 if the factor is 2 – and compare to the original list:

{#[l;y]~y@x*til l:count[y]div x}

Another very nice technique is to take advantage of the # operator to force the list into 2 dimensional arrays, then select out rows and columns for comparison:

f:{#[0N,x;y][;0]~#[x,0N;y]0}

In my opinion this solution is a particularly concise and elegant example of q code: an elegant and efficient solution in only 26 characters! Can anyone beat that? As always post your solutions below.

Until next time!