Search code examples
kdb+k

Except (^ or _dvl) analog in k4, 8 Queens example


I've just played with 8 Queens puzzle, and found out that it seems there is no _dvl operator (from k(v2)) in k(v4). Also I checked other k versions from ngn k impls and found ^ operator in k(v6), for example at JohnEarnest's impl:

l^a or l^l is except. Remove all instances of each of y from x.

k) 1 3 2 5 1 2 3^1 3 5
2 2

I really love SQL-style and would like to apply it in q. But is the following way idiomatic in q/k(v4) and is it a good solution? Or maybe there are shorter ways to do such list comparison/exclusion exists:

q)show s:til 8
0 1 2 3 4 5 6 7
q)s where not s in 2 4 6 /bother about this line, can it be shorter?
0 1 3 5 7

My version of q8 code is a bit longer then in nsl k2, without recursion and without conditions:

f:{raze {(x,) each (til 8) where not (til 8) in {x,(x-f),x+f:reverse 1+til count x} x} each x}
\ts:10 7 f/til 8 /248 100128
count  7 f/til 8 /92
first  7 f/til 8 /0 4 7 5 2 6 1 3

Upd: command I was looking for is except:

q)f:{raze {(x,) each (til 8) except {x,(x-f),x+f:reverse 1+til count x} x} each x}

Upd2: generalized 8 Queens solution in k(v4):

k){(x-1){,/{(x,)'(!y)@&~(!y)in{x,(x-f),x+f:|1+!#x}x}[;y]'x}[;x]/!x}8

Upd3: add 8 queens puzzle to blog


Solution

  • It is just keyword except.

    How to find it: we know idiomatic k construction @&, so just search through .q namespace for it:

    q)qfind:{([] q:k;k:.q k:key[.q] where (string value .q) like "*",x,"*")}
    q)qfind "@&"
    q      k
    -----------------------------------
    inter  k){x@&x in y}
    except k){x@&~x in y}
    xcols  k){(x,f@&~(f:cols y)in x)#y}
    
    q) (til 8) except 2 4 6
    0 1 3 5 7