Tips for golfing in J

Question

GolfScript gets its own way far too often and I feel that a repository of handy hints for golfing in J might help in the fight against the evil empire. What tips do you have for making this already terse language shorter?

For those wanting to learn J, the obvious place to begin is the jsoftware site and particularly the vocabulary, the Learning J guide and the J for C programmers guide.

Answer 1

There are a number of subtleties to squeezing out the last few characters in J. For the following, assume that each capital letters is a primitive verb (i.e. I am removing the spaces that would otherwise be required to delimit names).

• When you have a train going, and you need to apply a function atop another partway through, ([:FLGR) and (LF@:GR) have the same number of characters, but (LF@GR) saves one. If the frame of G is greater than or equal to the monad rank of F, this is a valid transformation. Notably, all trains have infinite rank, as do , ,. ,: ~. /: \: [ ] and most uses of # and |..

• If you have to pick strings out of a list, and these strings have no spaces, use >i{ab`cd`ef. It's dirty, but it saves characters for each new string you have to deal with, unless you're just pulling single characters, and even then the charlist has to be length 4 to be shorter. What's happening is that undefined names are treated as references to verbs, and when you take the gerunds of those verbs you get a boxed string of the name. Any names that are already defined as having type noun, adverb, or conjunction cannot be used in this fashion, because those names get resolved before ` can have at them.

• If you're lucky enough to have an expression to work with and not just a tacit verb, it's almost always worth it to assign any bits you reuse to variables, be they nouns, verbs, or adverbs. The parens will sometimes pay themselves back by fitting right into where you had spaces before, and most such definitions are worth it if they're reused even once more.

• Conjunctions like (FGH)^:(u`v`w) can be rewritten u`v`w(FGH^:). This works for any length of train, even 1, though you only save anything if this trick removes parens from the right argument. This trick only works when you preload the left operand. (Have no idea what just happened? Look up 'tacit adverbs', and study the Parsing and Execution section of the J Dictionary.)

• Don't use a.&i., use u:! {&a. and 3&u: are equivalent on length, though, and the former might be more useful in a conjunction (depending on the conjunction).

• Things like (2%~F) and (F%2:) are equivalent in length. This is useful because sometimes, depending on what the rest of your train looks like, you can restructure it with @ tricks as written in the first point, to save some desperate characters. (And of course, if F is ] and the train is a monad, using %&2 saves a char, duh.)

• Hook-like trains with ] or [ as the leftmost verb, e.g. (]FGH).

  • ] lets you break up a dyadic application and use the right argument only. (Swap to left with (]FGH)~, at a penalty of at least 1 character, maybe more.) Saves a char over (FGH)@], and is very handy in gerunds!
  • [ in a hook applied monadically allows you to do something for the side effects on the right side, then return the argument again. Most common usage is with 1!:2, possibly with formatting junk.

• I/O sucks. Speed up the process by making loops out of everything you can. 1!:1 has rank 0, and both of 1!:2 3 have rank _ 0, for example, so utilise this by making arrays of 1s and run 1!:1 directly over them. Note that ". also has rank 1, so you can usually just put that directly after 1!:1, too, and not have to attach it via @ or rank shenanigans.

• It's not easy to find places to put this, but :: can be useful.

  • ::]^:_ is a particularly powerful combination, for example, that lets you do something dangerous until you can't do it anymore. (Subject to the usual ^:_-as-a-loop caveats.)

  • This also lets you use { on lists that don't have the desired index, because it throws a domain error when that happens. Useful to e.g. take the head of a list only if it exists (try using ::] to return the empty list, or ::_1: to return an error code, and so on).

• ]`($:@u)@.v can usually be made shorter than u^:v^:_, especially on definitions of u and v that can be played around with. A similar case holds for the conditional-like u^:(1-v) vs. ]`u@.v. Consider your options, especially when you have lots of named verbs floating about. It's also a little more flexible, but remember, if using $:, there is a recursion depth that it's easy to bump up against. (Usually something like 1800 iterations?)

Answer 2

The most important thing when golfing in J is to not only understand the problem, but to reduce the problem to a series of array transformations. You need to understand this way of thinking to have any success with J code.

For example, a recent challenge asked to solve the largest subarray problem. The stock algorithm to solve this problem is Kadane's algorithm has the following informal description:

Go through the array and at each position and find the sum of the largest subarray ending here, which is the maximum of 0 or the value at the current index plus the sum of the largest subarray ending at the previous position. Compute the maximum of these subarrays as you go to find the largest subarray in the entire array.

A translation into imperative code is straightforward:

1. let A be the input array.
2. h ← m ← i ← 0.
3. if i ≥ len(A) return m.
4. h ← max(0, h + A[i]).
5. m ← max(m, h).
6. i ← i + 1.
7. goto 3.

This algorithms seems complicated for J at a glance as there is an explicit loop that doesn't look like a reduction at first. If you realize what the algorithm is doing you can untangle the individual steps and see that it actually performs two simple array operations:

1. Scan through the array to compute the lengths of the largest subarrays ending at each index.
2. Reduce these lengths with the max function to find the maximum.

Now these two steps are very easy to implement in J. Here is a translation:

1. (0 >. +)/\. y , 0 – This step operates from the other end of the array to better fit J's paradigm. 0 >. + is tacit for 0 >. x + y.
2. >./ y

Put together, we get a very terse implementation of the algorithm:

>./ (0 >. +)/\. y , 0

If you learn this way of approaching the implementation of algorithms, your solutions will be as terse as this code.

Here are some tricks I accumulated over time. This list will be expanded as I get more knowledge in J golfing.

• Learn the dictionary. It contains a lot of really obscure verbs that don't make any sense until you see how useful they are. For instance, monadic = is strange at first but is very useful in ASCII art challenges.
• Use dyadic & in tacit contexts when you want a power conjunction. The vocabulary suggests u@[&0 as a tacit replacement to 4 : 'u^:x y and so do I.
• In many cases you can avoid a [: or @: in a sequence like u@v by choosing a variant of u that has a left argument. For instance, to drop the first item of the result of v, use 1}.v instead of [:}.v if }.@v isn't possible for some reason.
• ] v is often shorter than v@] if you want to use monadic v in a dyadic context. This comes in useful especially when v is a long train of verbs.
• Sometimes you can write m (n v w) y instead of (n v m&w) y. This may make it possible to avoid spaces and parentheses.
• #\ instead of >:@i.@#.
• u &. v is useful when v has an obverse. When not, you might want to use [: vinv u & v or u & (v :. vinv) instead.
• Understand rank and how to use it. Try to fiddle around with the rank conjunction until you get something that fits. It helps understanding how rank influences your code.
• ^:_ is extremely useful for algorithms where you want to reach convergence, like a flood-fill or simulations.
• Know your standard library. It contains very useful functions that save you tons of characters.
• The copulæ =. and =: can be embedded anywhere in a phrase. Use this to make one-liners where tacit notation isn't enough.
• Use monadic , instead of multiple reductions when reducing multi-dimensional arrays.
• Understand what phrases are supported by special code when the challenge imposes runtime boundaries. Some useful things operate in O(n) instead of O(n²) counter-intuitively.
• Boxes are useful for trees.

Answer 3

Be wary of using loops.

While J has looping structures (for. do. end., while. do. end. and variations), if you find yourself using them there's a possibility that your algorithm is not playing to J's golfing strengths and that there are character savings to be made.

^: the power conjunction is your friend. To execute a verb x times:

verb^:x

If you need the result of each iteration in a list:

verb^:(i.x)

You can also use ^: to execute a verb conditionally:

  +:^:(3<])"0[ 1 2 3 4 5 6
1 2 3 8 10 12

Double +: if ^: the item is greater than 3 3<] (the "0 changes the rank of the verb so it works an item at a time).

Answer 4

Input

1!:1[1 will take one line of input terminated by pressing the enter key.

1!:1[3 will take a number of lines of input (terminated by Ctrl-D on my Mac, Ctrl-C on Windows).

If you're trying to input numbers, using ". will evaluate the string and return a list of numbers ready to be manipulated. If you're taking in one number but need to operate on the digits individually, ".,. (thanks to Jan Dvorak's comment for this) or "."0 will split the string into separate digits:

   "."0[1!:1[1
12345
1 2 3 4 5

   ".,.1!:1[1
12345
1 2 3 4 5

If you're reading in strings, the shortest way to get a boxed list of separate strings is to use ;:. This works best for space separated strings:

   ;:1!:1[1
hello world
┌─────┬─────┐
│hello│world│
└─────┴─────┘

Answer 5

Using iteration to compute sequences

Typically, solving an OEIS sequence challenge will require using one of the formulas given on its page. Some of these adapt well for J, and others not so much. Recursive formulas are straight-forward, however, iteration might not be simple. A pattern I've begun to use is

(s(]f)^:[~]) n
          ]  Gets n
 s           The first value in the sequence
         ~   Commute the argument order, n is LHS and s is RHS
        [    Gets n
      ^:     Nest n times with an initial argument s
  (]f)         Compute f s
             Returns (f^n) s

where s is the first value in the sequence, f is a verb that will compute the next term given the previous term, and n is the zero-based index of the term you want to compute. This method relies on the fact that when computing the power of a dyad, the LHS is bound to the dyad to form a new monad, and that monad is nested on the initial value. The dyad given to the power adverb is a hook where (]f) is given the index n on the LHS and the value of a term in the sequence s. The hook will apply f on s as a monad, and then ignore n to return the result of f s.

Standard library

Sometimes, you might find that J will have support for a verb in its standard library. For example, most of the bitwise integer operations are bound to names which are shorter than using the primitive call.

AND =: (17 b.) NB. it is actually '$:/ :(17 b.)'

Date and time builtins are also available.

Ranges

If you have a set of values [a, b, c] and you want to form a range based on their product like [0, 1, 2, ..., a*b*c-1], the typical approach would be to find their product and then form a range which might be [:i.*/ which costs 6 bytes. A shorter way is ,@i. for 4 bytes since i. can form multidimensional arrays while still counting up, and flattening it will produce an equivalent range.

Printing continuously

A tacit way to print a value and continue to use it without an explicit loop is ([echo) for a monadic case. echo is a verb in the standard library that prints its contents to stdout in the same format used in the interpreter. The hook then passes the same input value out using the left [ verb.

Base 10 digits of an integer

The standard way of acquiring the base 10 digits of an integer is 10#.inv] which costs 8 bytes, too much! An alternative is to convert it to a string and parse it at rank 0 "."0@": which saves a byte, but an even better way is ,.&.": which saves another byte making the final cost 6 bytes instead of 8.

Answer 6

Some (fairly) common tricks I've seen

I'm sharing a few things that have come in handy for me. Basically all of these are tips I've received myself, but I don't have credits for most.

Sum of a rank one array

Instead of using +/@:(FGH) use (1#.FGH). This means debase to base 1, which effectively means summing an array. Although it's longer than +/, it doesn't require a cap or composition, which often makes it much shorter than using +/.

Counting trailing truths

If you have a boolean list and you want to count the number of trailing truths, use #.~. See here. The APL answer provides a good explanation for how this works. Granted, this has only been helpful to me twice but I figured I'd share it anyways.

Under (&.)

Not a specific trick, but just a general suggestion: the adverb &.-under often leads to elegant and (more importantly) short solutions. Keep it in mind when you're golfing.

Often times it's useful for binary and other base conversion challenges, e.g. this code which removes the most significant bit from a number: }.&.#: (convert to list of binary digits, remove the first digit, then undo the conversion to a list of binary digits and convert back to decimal). The straightforward solution is two more bytes: #.@}.@#:.

Under is also helpful for challenges where you need to work with decimal digits, since you can use u&.":. For example, the short way miles gives to split to decimal digits uses under: ,.&.":.

A final example is finding the magnitude of a vector: +/&.:*:, note that you need to collect all of the results from *:-square with &.:-under since *:-square is rank zero.

Answer 7

Consider using explicit definition instead of writing a tacit verb; sure the 3 :' and ' cost 5 bytes, but you can save a lot of @, @: and [: that way.

Answer 8

Shorter ways to mess with ranks

Sometimes, you'll have code like <"0 i.3 3, where you want to apply a verb v at rank r. However, if you use a noun (like 0), you'll often have to include a space. To avoid this, you can use another verb u of equivalent rank and use u"v instead. For example, since + has rank 0 0 0, we can use <"+ instead of <"0.

Here is a table of all verbs and their ranks (obtainable by using v b. 0):

0 0 0     > + * - % ^ | ! ? <. <: >. >: +. +: *. *: %: ^. j. o. q: r.
0 _ _     -. -: E. i: p:
1 0 1     p..
1 0 _     { A.
1 1 0     p.
1 1 1     #.
1 1 _     C.
1 _ _     ;: ". i. I.
2 _ 2     %.
_ 0 0     = < ~. ~: {: }: ?. L.
_ 1 0     #:
_ 1 _     $ # |. |: {. }. ": {::
_ _ _     , ; [ ] _: $. $: ,. ,: /: \: [: e. s: u: x: 0:

To use this table, find the desired rank r on the left hand side, then choose an appropriate verb v from the right hand side. E.g., if I need to vectorize a verb v at depth 2 _ 2, then I find that rank on the left and choose %. from the right. Then I use v"%. instead of v"2 _ 2.

Answer 9

Getting numbers from 0 to 4

If there’s a restriction on using numbers in your code:

0 %_: one divided by infinity.
1 #_: how many infinities?
2 #_ _: two infinities.
3 verb: there’s a built-in.
4 dyad: another built-in.

Getting numbers from 10 to 35

Base-inifinity literals: 11:_bb, 26:_bq etc.

Answer 10

Tacit programming

Basics

Dyadic verb

x (F G H) y == (x F y) G (x H y)
x (F G) y == x F (G y)
x ([: G H) y == G (x H y)  NB. G is called monadically

NB. Verbs are grouped from the right by units of 3.
NB. For the following, think like G, I, K are replaced by the results of (x G y) etc.
NB. and then the sentence is run as usual.
x (F G H I J K) y == x (F (G H (I J K))) y
                  == x F ((x G y) H ((x I y) J (x K y)))

NB. Using conjunctions for dyadic verb
x F@G y == F (x G y)  NB. Atop; Same as x ([: F G) y; Consider as golfing alternatives
x F&G y == (G x) F (G y)  NB. Compose; G is applied monadically to both arguments

Monadic verb

(F G H) y == (F y) G (H y)
(G H) y == y G (H y)  NB. Note that this is different from APL
([: G H) y == G (H y)
(F G H I J K) y == (F (G H (I J K))) y
                == y F ((G y) H ((I y) J (K y)))
F@G y == F (G y)

Misc

x&F y == x F y
F&y x == x F y
y F~ x == x F y
F~ y == y F y

Tricks

(F x) G (H y)

Tacit solution: (G~F)~H; depending on the actual verbs, consider rearranging the left and right arguments to remove ~.

x ((G~F)~H) y
x (G~F)~ (H y)
(H y) (G~F) x
(H y) G~ (F x)
(F x) G (H y)

Monadic-Dyadic replacements

>:y == 1+y
<:y == 1-~y or _1+y
+:y == 2*y
-.y == 1-y
-:y == 2%~y
*:y == 2^~y
#.y == 2#.y
#.inv y == 2#.inv y  NB. #: doesn't work this way
{.y == 0{y
{:y == _1{y
}.y == 1}.y
+/y == 1#.y

Answer 11

strings library: golfing tips

The strings library is vastly helpful for doing anything with string manipulation. Sure, it takes include'strings' (which is very costly, considering J), but you may at times reap the benefits.

stringreplace

Find yourself using string replace? Observe that A stringreplace B is the same as B rplc A.

In fact, this is how rplc is implemented:

   rplc
 stringreplace~

cuts

The verb cuts provides thus:

cut y at x (conjunction)
string (verb cuts n) text
  n=_1  up to but not including string
  n= 1  up to and including string
  n=_2  after but not including string
  n= 2  after and including string

So it's really slicing a string.

Answer 12

& is your friend, use it wisely

v is a verb, n is a noun, x and y are left and right arguments, respectively.

Monad &: Introduce ~ inside adverb/conjunction chain

An adverb/conjunction chain evaluates from the left. So something like _2&+/\&.> won't work because it parses like (_2&+)/\&.> while we want _2&(+/\)&.>. In this case, swapping the left/right of +/\ can save a byte, as in +/\~&_2&.> because this one parses as ((+/\)~)&_2&.>. To see why this works:

+/\~&_2 y
is equivalent to
y +/\~ _2
is equivalent to
_2 +/\ y
is equivalent to
_2&(+/\) y

Dyad &: Repeat x times

Did you know that if you give a left argument x to &, the function applies it x times to y? Quite a few challenges ask you to do certain operation x times. It is mainly achievable in two ways:

• Use the power operator ^: without right operand

If the operation is v, then v^: becomes an adverb train that, when given a left operand, becomes a monadic verb. So v is applied to y, x times.

x(v^:)y
is equivalent to
(v^:x)y

• Use the dyadic & as the outermost conjunction

To use this, you need to identify a constant n and a dyadic verb u, so that either n u y or y u n is equivalent to v. Then you can write n&u or u&n to solve the entire task. This form is most effective when the choice of the constant is obvious, e.g. 3 in 3 u: (convert chars to ASCII values).

Also, u&n is slightly preferred over n&u when the outermost structure of u is a conjunction or adverb (in which case n&u should be n&(u); you can do u~&n instead).

Note that you can place the dyadic & anywhere in a train to achieve repeating arbitrary function to arbitrary argument, in the similar sense to dynamic ^:.