At Work and Play with J: Year’s Digits for 1996
Vector 12:4, page 123
Transcribed from the printed issue; not yet reviewed. Read it in the PDF of the issue, page 123
This problem is a variation of an old one that originated as a Fortran puzzle in the MIT alumni magazine, adapted for use with J. Here it is:
Create a character table T, having 101 rows, each row representing a J expression, according to the following rules:
(a) The result of executing row i must be the atom i, and
(b) The characters ‘1’, ‘9’, ‘9’, and ‘6’ must appear in that order in each row, and no other digits may be present. (In the Fortran puzzle, the digits could appear in any order.)
Expressed in J, (a) each row
must satisfy the requirement that
for i an item of i.101 (and thus an atom), and (b)
There are two additional requirements, suggested by Roger Hui:
(c) Character constants are not permitted. If they were then all solutions would need no more than two tokens. For example 7 could be represented by #'1 9 9 6'.
(d) J allows ‘b’ form constants, in which a decimal integer base appears to the left of ‘b’ and the digits to the right of ‘b’ may include not only the digits 0 through 9 but also the letters a through z, representing digits 10 through 35. For example, the octal representation of 63 is 8b77 and the hexadecimal representation of 255 is 16bff and the decimal number 100 can be written as 1buzz. The b form of constants is allowed, but the digits a through z are excluded, as well as 0 2 3 4 5 7 8. If a through z were not excluded almost all solutions would be one token long.
Here are some examples of invalid rows. The reason each example is unacceptable is given directly after it.
19+6+9 |
The digits are not in the prescribed order. |
1+96+1 |
The digits are not 1996. |
3*19[96 |
It contains a ‘3’. |
1{.99 6 |
It yields a list result, not an atom. |
#' 1996' |
It uses a character constant. |
1bzp996 |
It uses the digits z and p. |
As a valid example, row 19 might be
and this satisfies the test 19 -: ". '+/1 9 9[6'.
The objective of the problem is to use the minimum number of tokens in each row, as measured by the J ‘Word Formation’ primitive (;:). The foregoing list for row 19 has 5 tokens, and it is thus superior to:
which uses 7 tokens, but it is inferior to
which uses only 3 tokens.
Entries will be judged in the following way: if L is the list of the number of tokens in each row of a given entry, and M is the list of the minimum number of tokens in all entries submitted, then the entry which minimizes +/L-M is the winning entry.
To ease your minds, I should say that yes, a complete set of solutions is always possible, and this has been demonstrated mathematically by Donald Knuth and Roger Hui, among others. Since *1996 is 1 then ^.*1996 is a solution for 0; and since ^.o.1 is between 1 and 2, then applying floor or ceiling gives solutions for 1 and 2. Using more instances of o. provides solutions for larger numbers, ad infinitum. Clearly, this shows that a solution is always feasible. Most derived using this method are not, however, very short. Coming up with a short solution for each integer is your problem.
To help you get started, let me suggest that you use a strategy like that employed by Roger Hui. He used a J session in the following way to develop his table:
He worked with two windows present on his screen: an executable window, and a script window called "1996.js" which contained one solution per line.
Initially, each row is set with the row number, a comma, some spaces, and a 0. For example, row 25 would look like this:
You can write potential solutions in the script window, and have them executed in the execution window to see if they are correct:
Roger provided himself with a suite of utility functions:
mat=: (5&}.);._2 @(1!:1) @((<'1996.js')"_)
len=: /:~@(({.,#)/.~)@:(#@;:)
check=: *./@(0&= +. (=i.@#))@:".
pfx =: [: ": #@;: ,. i.@#
tab =: [: \:~ pfx ,. ]
"mat" reads the script file and constructs a matrix from it. As it stands, it is suitable for use with IBM-compatible PCs. To change it for use on Unix or Macintosh systems, you should replace the text '(5&}.@}:)' with '5&}.'. "check" checks that each row is either zero (unsolved) or has the correct number. "len" makes a two-column table with the first column giving a length and the second column giving the number of solutions with that length (unsolved numbers have a length of 0). "tab" makes a table of the solutions sorted in decreasing length, and thus is handy for attacking the really bad solutions.
I wrote the following, to check that only the digits ‘1996’ appear, in that order, in the solution:
To see what these utilities can do for you, after you’ve created your 1996.js file and filled in a few entries, experiment with expressions like:
And after you’ve filled in all the entries,
This problem should help familiarize you with some lesser-known parts of J, like b-form constants, the new p: and q: primitives, and the monadic, or base-2 form of the base primitive (#.). For example, the following five-token expression:
creates the number _19b96, which has the decimal value _165 (in base _19 the values 9 and 6 evaluate to _171 and 6, with sum _165); takes the magnitude of this number, yielding 165; finds its prime factorization with q:, yielding 3 5 11; uses p: to find the third, fifth and eleventh primes in the 0-origin series 2 3 5 7 11 13 17 ..., yielding 7 13 37; and applies the primitive #. to evaluate this list in base-2, yielding 91 (+/4 2 1*7 13 37). Another five-token expression for the same value is:
There is a solution to 91 which is shorter than this, by the way.
Send your solutions to me either by electronic mail or by regular mail.
If you think you have a particularly good solution for a given number but don’t want to do the whole problem, send it to me anyway; it may merit a special commendation.