Tips for golfing in K

17

1

K is a programming language in the APL family designed by Arthur Whitney. While the official interpreter is closed-source and commercial, a trial version with a workspace limit of 32 bits of addressing space (which shouldn't pose problems for code golf) can be found at the Kx Systems website. This version bundled as part of the kdb+ database is colloquially known as "K4". There are also open-source K implementations available, including Kona, which is based on K3, and my own interpreter called oK, which is based on K5 and has a browser based REPL.

Kx Systems has a wiki with K4/kdb+/Q information, and the Kona GitHub page also has an excellent collection of reference materials. I have begun writing a manual for oK/k5 which may be a useful reference.

Like J and APL, K is a very terse and powerful language, and can often make a good showing in code golf. Please share tips, tricks and idioms you discover, and if you haven't tried K before consider giving it a spin! Post one tip per answer, please!

JohnE

Posted 2015-05-22T23:29:28.277

Reputation: 4 632

Answers

5

Calling a Dyad

Assuming you had a dyadic (2-argument) function f:

f: {x+2*y}

You would ordinarily call it like so:

f[3;47]

You can save a character by instead currying in the first argument and then applying the resulting partial function to the second argument by juxtaposition:

f[3]47

The same naturally works for array indexing:

  z: (12 17 98;90 91 92)
(12 17 98
 90 91 92)

  z[1;2]
92

  z[1]2
92

JohnE

Posted 2015-05-22T23:29:28.277

Reputation: 4 632

5

Printing newlines

If your output must have a newline, you may be tempted to do this:

`0:whatever,"\n"

Don't. K2 (and likely other versions) has a neat feature where you can print a list of lines:

  `0:("abc";"def")
abc
def

So, if you need to append a newline to the output, just do:

`0:,whatever

kirbyfan64sos

Posted 2015-05-22T23:29:28.277

Reputation: 8 730

3

Ranges

Normally if you want to create a vector of sequential numbers you use !:

  !5
0 1 2 3 4

If you want to create a range that starts at a number other than zero, you'd then add an offset to the resulting vector:

  10+!5
10 11 12 13 14

There are a few unusual approaches which could work better for a particular situation. For example, if your base and offset are already members of a list, you could use "where" twice:

  &10 5
0 0 0 0 0 0 0 0 0 0 1 1 1 1 1
  &&10 5
10 11 12 13 14

For slower-growing sequences, consider combining "where" with "take":

  5#2
2 2 2 2 2
  &5#2
0 0 1 1 2 2 3 3 4 4

If you want to create a range of multiples, you could multiply the result of ! or you could scan (\) a list of copies of the step size:

  2*!5
0 2 4 6 8
  +\5#2
2 4 6 8 10

If you're trying to avoid parentheses, the former is better if the length of the sequence is variable and the step size is fixed, while the latter is better if the step size is what tends to vary. Picking the right variation can save 1 or 2 characters. The off-by-one difference could also work in your favor.

JohnE

Posted 2015-05-22T23:29:28.277

Reputation: 4 632

2

Each Right

Occasionally you may find yourself writing (or arriving at by simplification) a parenthesized expression applied via each-monad:

  (2#)'3 4 5
(3 3
 4 4
 5 5)

It is one character shorter to convert this pattern into an application of each-right:

  2#/:3 4 5
(3 3
 4 4
 5 5)

JohnE

Posted 2015-05-22T23:29:28.277

Reputation: 4 632

2

Casts from strings are expensive. Just use eval. This:

0.0$a

can become just this:

. a

In K5, it's a byte shorter:

.a

kirbyfan64sos

Posted 2015-05-22T23:29:28.277

Reputation: 8 730

1

Cyclic Permutations

Dyadic ! in K3/K4 is "rotate":

  2!"abcd"
"cdab"
  -1!"abcd"
"dabc"

When "scan" (\) is provided with a monadic verb, it acts as a fixed-point operator. In K, fixed point operators repeatedly apply their verb to a value until the initial value is revisited or the value stops changing. Combining rotate with fixed-point scan provides a very convenient way of computing a set of cyclic permutations of a list:

  ![1]\1 2 4 8
(1 2 4 8
 2 4 8 1
 4 8 1 2
 8 1 2 4)

You can either curry ! via brackets or parenthesize to create the verb train (1!):

![1]\
(1!)\

(Note that 1!\ has an entirely different behavior!) Each of these is equivalent in length but the former may be more desirable if the rotation stride is something other than 1; in this case the brackets delimit a parenthesized subexpression "for free".

As an example, here is a short program which tests via brute force whether a string x contains the substring y (cyclically!):

{|/(y~(#y)#)'![1]\x}

K5 users beware! K5 has changed the meaning of dyadic !, so this technique isn't so easy. It will work as expected in Kona.

JohnE

Posted 2015-05-22T23:29:28.277

Reputation: 4 632

1

Avoid Conditionals

K has a conditional construct (:[) which is equivalent to a Lisp-style cond:

:[cond1;result1; cond2;result2; cond3;result3; default]

You can have as many conditions as you like, and if none match the default value is returned.

Sometimes (as in recursive programs or programs that otherwise rely on a sequence of side effects), there's no getting around using one of these. However, in situations where you can afford to do a bit of extra work, you can often replace a "cond" with list indexing.

Consider the infamous fizzbuzz program. Written in a conventional imperative programming style, we might go with:

{:[~x!15;"FizzBuzz";~x!3;"Fizz";~x!5;"Buzz";x]}'1+!100

There's quite a bit of repetition here in the divisibility tests. A different approach recognizes that there are 4 cases (a number, divisibility by only 3, divisibility by only 5, divisibility by 3 and 5) and attempts to directly compute an index which chooses one of these cases from a list:

{(x;"Fizz";"Buzz";"FizzBuzz")@+/1 2*~x!/:3 5}'1+!100

Two characters shorter, and a better use of the language. Knowing that list literals are evaluated right to left, we also gain some additional golfing opportunities for combining reused subexpressions. We couldn't have easily done this in the cond-based version, since the string cases aren't evaluated at all if they aren't selected:

{(x;4#t;4_ t;t:"FizzBuzz")@+/1 2*~x!/:3 5}'1+!100

Now we've saved 5 characters overall. Incidentally, this particular example works out even nicer in k5, since we have the "pack" overload for / to handle the step of multiplying by a vector of coefficients and summing:

{(x;4_t;4#t;t:"FizzBuzz")@2 2/~3 5!\:x}'1+!100

Also note that the behavior of "find" (?), which produces an index past the end of the key list if the item is not found, is specifically designed to support handling a "default" case in this kind of indexing. Consider this fragment to convert vowels to uppercase:

{("AEIOU",x)"aeiou"?x}'

Versus one of:

{t:"aeiou"?x;:[t<5;"AEIOU"t;x]}'
{:[~4<t:"aeiou"?x;"AEIOU"t;x]}'

(I know which I'd rather read, too!)

JohnE

Posted 2015-05-22T23:29:28.277

Reputation: 4 632