Doc/Articles/Play124
At Play With J ... Table of Contents ... Previous Chapter ... Next Chapter
10. Year’s Digits for 1996
. By Eugene McDonnell. First published in Vector, 12, 4, (April 1996), 123-126.
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 r =. i { T must satisfy the requirement that i -: ". r for i an item of i.101 (and thus an atom), and (b) '1996' -: r -. a. -. '0123456789'
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
+/1 9 9[6
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:
1+9+9[6
which uses 7 tokens, but it is inferior to
19<.96
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 \junk\1996.ijs 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:
25, 0
You can write potential solutions in the script window, and have them executed in the execution window to see if they are correct:
25, 1+9+9+6
Roger provided himself with a suite of utility functions:
mat =: (5&}.@}:);._2 @(1!:1) @((<'\junk\1996.ijs')"_)
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:
d1996=: [: *./ ('1996' -: (a.-.'0123456789') -.~ ])"1
To see what these utilities can do for you, after you’ve created your \junk\1996.ijs file and filled in a few entries, experiment with expressions like:
$mat 0 check mat 0 len mat 0 +/*/"1 len mat 0 NB. total number of tokens tab mat 0
And after you’ve filled in all the entries,
d1996 mat 0
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:
#.p:q:|_19b96 91
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:
>:1#.q:996 91
There is a solution to 91 which is shorter than this, by the way.*
- In his original paper, Eugene invited readers to send solutions to him, but this is no longer appropriate.
A set of sample solutions for 1996 is available. Thanks to Roger Hui for completing the bulk of them. Ian Clark
The tradition begun by Eugene lives on in the J Wiki as "Puzzle of the year xxxx", for xxxx e. 2005 2006 2007 2008 2009