Return to Answer

replaced http://codegolf.stackexchange.com/ with https://codegolf.stackexchange.com/

edited Apr 13, 2017 at 12:39

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

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:

added 19 characters in body

Source Link

edited Mar 1, 2015 at 11:40

FUZxxl

edited Mar 1, 2015 at 11:40

FUZxxl

10.2k
1
41
82

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

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.

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

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 , 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.

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

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.

Source Link

answered Feb 24, 2015 at 14:57

FUZxxl

answered Feb 24, 2015 at 14:57

FUZxxl

10.2k
1
41
82

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:

let A be the input array.
h ← m ← i ← 0.
if i ≥ len(A) return m.
h ← max(0, h + A[i]).
m ← max(m, h).
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:

Scan through the array to compute the lengths of the largest subarrays ending at each index.
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:

(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.
>./ 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 , 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.