# 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