Generating an L-system matrix by block replacement

Suppose you are given a 2x2 “start” matrix like this one:

11

10

and a second 2x2 matrix like this one:

00

00

Create the next larger matrix by replacing every 1 in the start matrix with a copy of itself, and every 0 with the other matrix. In this case, you’d get

1111

1010

1100

1000

Make the same replacements to get larger and larger matrices (i.e. replace 1’s with the start matrix, 0’s with the other matrix.). Is there a clean way to do this in Q/kdb? I’ve written solutions in other programming languages, but they all involve multiple functions, most of which contain nested do-loops.

======================

The example given above produces a version of the Sierpinski Triangle. If you use

00

01

for the second matrix, you get a Hadamard matrix:

1111

1010

1100

1001 

This is quite a fun problem to solve :D This is what I have:

/ Sierpinski Triangle

q){raze@‘raze flip@’((2#count y)#0;y)x}[(1 1;1 0)]/[1;(1 1;1 0)]

1 1 1 1

1 0 1 0

1 1 0 0

1 0 0 0

q){raze@‘raze flip@’((2#count y)#0;y)x}[(1 1;1 0)]/[3;(1 1;1 0)]

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0

1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0

1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0

1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0

1 0 1 0 0 0 0 0 1 0 1 0 0 0 0 0

1 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0

1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0

1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0

1 0 1 0 1 0 1 0 0 0 0 0 0 0 0 0

1 1 0 0 1 1 0 0 0 0 0 0 0 0 0 0

1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0

1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0

1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0

1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0

1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0


/ Hadamard matrix

q){raze@‘raze flip@’(1-y;y)x}[(1 1;1 0)]/[1;(1 1;1 0)]

1 1 1 1

1 0 1 0

1 1 0 0

1 0 0 1

q){raze@‘raze flip@’(1-y;y)x}[(1 1;1 0)]/[3;(1 1;1 0)]

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0

1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0

1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1

1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0

1 0 1 0 0 1 0 1 1 0 1 0 0 1 0 1

1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1

1 0 0 1 0 1 1 0 1 0 0 1 0 1 1 0

1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0

1 0 1 0 1 0 1 0 0 1 0 1 0 1 0 1

1 1 0 0 1 1 0 0 0 0 1 1 0 0 1 1

1 0 0 1 1 0 0 1 0 1 1 0 0 1 1 0

1 1 1 1 0 0 0 0 0 0 0 0 1 1 1 1

1 0 1 0 0 1 0 1 0 1 0 1 1 0 1 0

1 1 0 0 0 0 1 1 0 0 1 1 1 1 0 0

1 0 0 1 0 1 1 0 0 1 1 0 1 0 0 1

q)f:{raze each raze flip each (y;x)@/:z}

q)x:(1 1;1 0)
q)y:(0 0;0 0)
q)2 f[x;y]/x
1 1 1 1 1 1 1 1
1 0 1 0 1 0 1 0
1 1 0 0 1 1 0 0
1 0 0 0 1 0 0 0
1 1 1 1 0 0 0 0
1 0 1 0 0 0 0 0
1 1 0 0 0 0 0 0
1 0 0 0 0 0 0 0
q)y:(0 0;0 1)
q)2 f[x;y]/x
1 1 1 1 1 1 1 1
1 0 1 0 1 0 1 0
1 1 0 0 1 1 0 0
1 0 0 1 1 0 0 1
1 1 1 1 0 0 0 0
1 0 1 0 0 1 0 1
1 1 0 0 0 0 1 1
1 0 0 1 0 1 1 0

Nick and WooiKent:

I was sure there was a Q-ish solution to this problem, but I didn’t know where to start. Both of yours look like Q-gods solutions to me (a Q newbie). Thanks for figuring this problem out!

-Stu S.

======

this is a beauty

dont think you need the @/: 

g:{raze each raze flip each(y;x)z}

  Attila

Hi Attila,

It really is a beauty! I’m astonished at the compactness of the code a skilled Q programmer can produce.

-Stu

====

----- Original Message -----
From: Attila Vrabecz <attila.vrabecz@gmail.com>
To: [kdb+] [kdb+] <personal-kdbplus@googlegroups.com>
Sent: Thu, 15 Jan 2015 14:57:44 -0000 (UTC)
Subject: Re: [personal kdb+] Generating an L-system matrix by block replacement

this is a beauty

dont think you need the @/: 

g:{raze each raze flip each(y;x)z}

  Attila

and in k it’s only

k:{,/‘,/+:’(y;x)z}

  Attila

In the next programming language Arthur Whitney creates, it will probably be only 3 characters long!

-Stu

====

----- Original Message -----
From: Attila Vrabecz <attila.vrabecz@gmail.com>
To: [kdb+] [kdb+] <personal-kdbplus@googlegroups.com>
Sent: Thu, 15 Jan 2015 15:52:26 -0000 (UTC)
Subject: Re: [personal kdb+] Generating an L-system matrix by block replacement

and in k it’s only

k:{,/‘,/+:’(y;x)z}

  Attila

I don’t understand the 2 f[x;y]/x part, can somebody explain to me?
what is the / means here, and why the 2 in front?

Thanks in advance.

The / in this instance is the ‘over’ operator. More information on how it works can be found here:

http://code.kx.com/wiki/Reference/Slash#over

In this case the 2 will control the dimensions of the generated matrix as it is using the infix version
of the iterate form (try changing this!). If you leave the 2 off, then the function will get stuck in a loop.

– 
Mark Rooney
Financial Software Developer
AQUAQ Analytics

On Tuesday, 20 January 2015 14:38:46 UTC, Hao Deng wrote:

I don’t understand the 2 f[x;y]/x part, can somebody explain to me?
what is the / means here, and why the 2 in front?

Thanks in advance.

As mark says, it’s the infix (verb) form of over.

For example:

/starting with the number 2, double it 3 times

q){2*x}/[3;2]
16

/can also be written

q)3 {2*x}/2
16

Terry