2022.05.22 06:36 AM
Now here’s a task that cries out for a simple solution: put a border round a matrix. My matrix is boolean and represents a QR code (yes, we’ll come to that) but it’s the same problem as, say, putting a 1px border on an image.
So let’s examine it as wrapping a char matrix in spaces. We’ll use 3 4#"ABCDEGHIJKL"
.
Our first strategy is to manipulate indexes, which is often an efficient approach in q. We make a larger blank matrix for the result and write the original matrix in the right place.
Start with the shape of the matrix; that is, count the rows and columns. (Shape is a concept that q did not inherit from its ancestor APL, but is easy enough to calculate.) We use the Zen monks for a point-free expression.
q)show M:3 4#"ABCDEFGHIJKL"
"ABCD"
"EFGH"
"IJKL"
q)count each 1 first\M / shape of M
3 4
So the result shape is 5 6, and here is our blank template:
q){n:2+count each 1 first\x; n#" "}M
" "
" "
" "
" "
" "
For the last move we could use Amend Each .'
to map each item of M
to a row-column pair in the result. But it should be more efficient to raze M
and use Amend At @
to map all its items to the vector prd[n]#" "
and then reshape it. Something like
q){n:2+s:count each 1 first\x; n#@[prd[n]#" "; ??? ;:;raze x]}M
" "
" ABCD "
" EFGH "
" IJKL "
" "
Above, ???
is some expression that returns the target indices for the items of M
. Let’s start with an easy expression – wrong, but easy. We’ll write the items of M
into the first positions of the result.
q){n:2+s:count each 1 first\x; n#@[prd[n]#" ";til prd s;:;raze x]}M
"ABCDEF"
"GHIJKL"
" "
" "
" "
Next we come to an often-overlooked overload of vs
and sv
: they encode and decode different (and variable) arithmetic bases. English pounds have 100 pennies (once known as New Pence) but once had 240, of which 12 made a shilling; and 20 shillings a pound.
q)240*4.50 / £4.50 in old pence
1080f
q)100 20 12 vs 240*4.50 / £4.50 was £4 10s 0d.
4 10 0f
q)%[;240]100 20 12 sv 4 10 0 / £4/10/- in decimal coinage
4.5
q)%[;240]100 20 12 sv 4 17 6 / not every sterling amount has an exact equivalent
4.875
We can use vs
and sv
to convert between row-col pairs and equivalent vector indices.
q){n:2+s:count each 1 first\x; n#@[prd[n]#" ";n sv flip 1 1+/:s vs/:til prd s;:;raze x]}M
" "
" ABCD "
" EFGH "
" IJKL "
" "
The above has a certain elegance in that it is probably efficient for a large matrix, but it does seem a lot of code for a simple task. If our matrices are small, perhaps we can see a simpler way?
Join ,
looks like an obvious candidate. (And it will lead us to something about flip
we might not have known; but we’ll come to that.) We have to apply it to each of four sides, but we have decided we don’t necessarily need the fastest expression for this.
Looks straightforward: Join for top and bottom, Join Each for the sides.
q),[;" "] " ",'" ",M,'" "
" "
" ABCD "
" EFGH "
" IJKL "
" "
Ah, not quite that straightforward. Joining an atom doesn’t use scalar extension the same way Join Each does. We could count the first row…
q){row:enlist(count first x)#" ";" ",'(row,x,row),'" "}M
" "
" ABCD "
" EFGH "
" IJKL "
" "
Better, but the refactoring itch remains.
The simplest operation is the Join Each, which exploits scalar extension.
When I flour an unbaked loaf, I don’t daub flour over it, I roll it in the flour.
q)reverse flip ,'[" "] M
"DHL"
"CGK"
"BFJ"
"AEI"
" "
q)reverse flip ,'[" "] reverse flip ,'[" "] M
"LKJI "
"HGFE "
"DCBA "
" "
q)4{reverse flip ,'[" "] x}/M
" "
" ABCD "
" EFGH "
" IJKL "
" "
I don’t need the (admittedly tiny) overhead of a lambda to apply a series of unaries. I can use a composition.
q)4(reverse flip ,'[" "]@)/M
" "
" ABCD "
" EFGH "
" IJKL "
" "
Now here’s a surprise: we don’t need the Each.
q)4(reverse flip ,[" "]@)/M
" "
" ABCD "
" EFGH "
" IJKL "
" "
How does that work? It turns out that flip
uses scalar extension. The items of its argument must conform; that is, they must be same-length lists – or atoms. But the result will have same-length lists.
q)flip M
"AEI"
"BFJ"
"CGK"
"DHL"
q)flip M,enlist "XYZ" / must conform!
'length
[0] flip M,enlist "XYZ"
^
q)flip M,"X"
"AEIX"
"BFJX"
"CGKX"
"DHLX"
q)
Loaf floured! And the QR code? Watch this space.
2022.05.23 10:02 AM
Brilliant post @SJT
Make sure to check out QR-Quick-Response-quite-reasonable-quirkily-rectangular and give the challenges a go!
EMEA
Tel: +44 (0)28 3025 2242
AMERICAS
Tel: +1 (212) 447 6700
APAC
Tel: +61 (0)2 9236 5700
KX. All Rights Reserved.
KX and kdb+ are registered trademarks of KX Systems, Inc., a subsidiary of FD Technologies plc.