Matt Doherty

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.

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!

[/showhide]

Share this: