This may come as a surprise, but I will today write about a programming language for which no Free Software implementation exists, the J programming language. J does not stand for the J dirty word (Java), but is the full name of the language.

I first heard about J while solving some problems on the Project Euler challenge. One of the problems to be solved was “given that C(n,p) is the number of ways to take p items amongst m items, find the number of C(n,p) greater than one million for n between 1 and 100 inclusive.”

This was a very easy problem. I coded my solution using Python and, out of curiosity, looked at how other people did it. I saw someone mentionning its J solution:

+/1e6<,!/~>:i.100

Wow, 17 characters! As I was in disbelief, I gave it a try and installed a copy of J on my GNU/Linux laptop. I cut and pasted the expression, and it gave me 4075, the expected solution. Let me describe how it works.

First of all, expressions are evaluated from right to left.

i.100

will generate a list of all integers from 0 to 99 (the 100 first non-negative integers). Then, the increment operator is used, so the part

>:i.100

leads to the list of numbers from 1 to 100. The rank of the increment operator is zero, which means that it operates on individual items, not on lists. Since we give it a list as argument, each member of the list will be incremented, and give the new 1 to 100 list.

The C(n,p) operator in J is written as

p ! n

However, we want to apply it for every p and n in 1 to 100. The tilde (~) modifier means that we want the left argument of the ! function to be the same as the right argument. The slash (/) modifier means that we want to build a table. Without it, the ! operator would be applied to the first item of the left argument and the first item of the right argument, then to the second item of the left argument and the second item of the right argument and so on. Here, it is applied to every combination of its left and right arguments, meaning that the result is a 100x100 table:

!/~>:i.100

Now, the coma (,) transforms the 100x100 table into a 10000 elements flat list:

,!/~>:i.100

Now, we want to select all the elements greater than one million. For that, we will compare each element to 1e6 (one million in scientific notation). Since the left argument is a plain number and the right argument is a list (the 10000 long list we obtained), the result will be a 10000 items list containing either 0 (false) or 1 (true):

1e6<,!/~>:i.100

Ok, so we now have a 10000 items list containing 0 (smaller than one million) or one (greater than one million). To find out the number of ones, we only have to sum up the items. Using the plus (+) operator and the slash (/) modifier, an addition will be inserted between every item of the list:

+/1e6<,!/~>:i.100

That’s it.

To the computer literate people, it looks a lot like APL without the special characters and the need for a special keyboard. No surprise, J and APL have both been designed by Kenneth E. Iverson.

J is very efficient while working on large sets of data. Its table operator and its rank analysis almost entirely obviates the need for explicit loops. For example, if you want to multiply the 100 first prime numbers, you can use the p: operator which returns the n-th prime number (starting with 0, which returns 2, 1 returns 3, 2 returns 5, 3 returns 7 and so on):

*/p:i.100x

The x modifier stands for extended (read unlimited) integer precision. You want to know what the solution is? Install your copy of J and try it yourself.

blog comments powered by Disqus